当前位置: 首页 > news >正文

ParBFT: Faster Asynchronous BFT Consensus with a Parallel Optimistic Path

目录

  • 笔记
  • 后续的研究方向
  • 摘要
  • 引言

ParBFT: Faster Asynchronous BFT Consensus with a Parallel Optimistic Path
CCS 2023

在这里插入图片描述

笔记

后续的研究方向

摘要

为了减少异步拜占庭容错(BFT)共识的延迟和通信开销,通常会添加一条乐观的路径,Ditto和BDT是最先进的代表。这些协议首先尝试运行乐观路径,该路径通常适用于部分同步的BFT,并在良好的情况下保证良好的性能。如果乐观路径无法取得进展,这些协议会在超时后切换到悲观路径,以确保异步网络中的活跃性。这种设计主要依赖于对网络延迟Δ的准确估计来正确设置超时参数。Δ的错误估计可能导致过早或延迟切换到悲观路径,在这两种情况下都会损害协议的效率。

为了解决上述问题,我们提出了采用并行乐观路径的ParBFT。只要乐观路径的引导者没有故障,ParBFT就可以确保低延迟,而不需要精确估计网络延迟。我们提出了ParBFT的两种变体,即ParBFT1和ParBFT2,在延迟和通信之间进行权衡。ParBFT1同时启动两条路径,在故障引导器下实现了较低的延迟,但即使在良好的情况下也具有二次消息复杂性。ParBFT2在好的情况下通过延迟悲观路径来降低消息的复杂性,代价是在有故障的引导器下有更高的延迟。实验结果表明,ParBFT的性能优于Ditto或BDT。特别是当网络条件恶劣时,ParBFT可以通过乐观路径达成共识,而Ditto和BDT则存在路径切换问题,必须使用悲观路径才能取得进展。

引言

在过去的十年里,区块链[38,55,66]的日益普及使人们重新关注拜占庭容错(BFT)共识协议[34,65,67]。一般来说,BFT共识协议确保多个副本达成一致,即使其中一小部分副本可能表现得任意(称为拜占庭副本)[44]。BFT共识协议根据其时序假设大致可分为三类:同步协议、部分同步协议和异步协议。在这三类中,异步协议对不可预测的网络条件提供了最强的鲁棒性[27,37,50]。然而,由于性能原因,异步BFT协议很少在生产中部署[46]。更具体地说,与同步和部分同步的对等协议相比,异步BFT协议具有更高的延迟(更大的轮数)和更高的通信开销,即使在所有副本都没有故障并且网络状况良好的情况下也是如此。

为了弥补异步BFT的较差性能,许多工作引入了一种乐观路径[43,57],Ditto[33]和BDT[46]是最近的代表。在高层,这些协议通常有两条路径:由领导者驱动的乐观部分同步路径和异步工作的悲观路径。系统首先尝试运行乐观路径,该路径具有低延迟和较小的通信开销。如果乐观路径无法取得进展,则协议会在超时事件后返回到悲观路径。在悲观路径上的一个或多个协议实例之后,协议将切换回乐观路径。由于在任何给定时间只有一条路径被执行,我们将这种设计称为串行路径范式。

串行路径范例有几个缺点。首先,它需要对网络延迟(通常表示为Δ)进行良好的估计,以相应地设置计时器。正确地获得参数Δ是相当具有挑战性的。当领导者是拜占庭人时,乐观的道路无法取得任何进展,理想情况下应该尽快启动向悲观道路的后退。Δ的大值将延迟回退并损害延迟。相反,如果Δ被错误地设置得太小,超时和回退事件将提前触发,可能会干扰乐观道路上即将取得进展的无故障领导者。

此外,何时回到乐观的道路上也是一个艰难的决定。如果由于网络已经恢复,切换执行得太晚,则协议不必要地在悲观路径上停留太长时间。相反,在网络状况仍然不佳的情况下过于匆忙地切换回来是没有意义和浪费的,因为乐观的道路仍然无法取得进展。这甚至可能导致频繁的来回切换,使协议比简单地单独运行悲观路径更慢。在某些情况下,Ditto[33]选择了仓促的方法,并在悲观路径上的单个协议实例完成时执行切换。BDT[46]在其伪代码中同样使用了一个仓促切换。尽管BDT提到可以使用其他启发式方法进行切换,但设计这些启发式方法也是一项棘手的任务。

为了解决路径切换方面的这些挑战,我们提出了一种向异步BFT添加乐观路径的替代范式:并行运行这两条路径。在高级别上,通过并行运行这两条路径,副本可以在两条路径中的一条成功后立即做出决定。这使得协议能够优雅地处理好的和坏的网络条件,并避免串行路径模式的缺点。更具体地说,我们提出了并行运行部分同步乐观路径和异步悲观路径的ParBFT。这两条路径可以各自产生一个输出(称为候选)。然后,ParBFT利用异步二进制协议(ABA)算法在这两个候选者之间达成协议。ParBFT的最后一个关键设计元素是一种快捷机制:如果领导者没有故障,网络良好,所有副本都将在乐观路径的末尾决定,并直接前进到下一个实例,而不需要执行ABA算法,甚至不需要执行悲观路径。这使得ParBFT在良好情况下的性能类似于串行路径范式。

我们提出了ParBFT的两种变体,我们称之为ParBFT1和ParBFT2,它们在延迟和通信之间进行了权衡。ParBFT1同时启动这两条路径;这种变体在拜占庭领导人的领导下提供了更好的延迟,但即使在良好的情况下也会受到二次消息复杂性的影响。相反,ParBFT2延迟了悲观路径的启动,因此,在拜占庭领导人的领导下,以更高的延迟为代价,在良好的情况下将消息复杂性降低为线性。

如表1所示,Ditto[33]和BDT[46]之前的工作实现了5的低延迟𝛿(𝛿表示实际网络延迟),并且参数Δ被正确估计时(即。,𝛿 ≤Δ)。相比之下,ParBFT1和ParBFT2实现了5的良好延迟𝛿只要乐观路径的领导者是非错误的,无论Δ是否被正确估计。如前所述,在良好的情况下,ParBFT1牺牲了消息的复杂性:当领导者没有错误并且Δ的估计是正确的时,ParBFT 1会导致二次通信。ParBFT2通过将悲观路径的启动延迟5Δ时间来避免这个问题:这将在良好情况下的通信复杂性降低到𝑂(𝑡𝑛)1(𝑡和𝑛分别表示实际故障副本和总副本的数量),但在拜占庭领导人的领导下增加了该数量的延迟。

我们还注意到,虽然ParBFT1根本不需要参数Δ,但ParBFT2带回了Δ的参数。但与先前的工作不同,对Δ的错误估计的惩罚要小得多。具体来说,当Δ设置得太小时,即Δ<𝛿,ParBFT2只会增加通信成本,而之前的工作会产生更长的延迟、增加的通信成本以及来回切换的潜在问题。

我们实现了ParBFT的两种变体,并进行了广泛的实验,以评估其与先前工作相比的性能。我们的实现使用基于链的范式,其中不同的协议实例被流水线传输以提高吞吐量。实验分为三个部分,分别对应三种不同的场景。第一部分模拟了一个良好的情况,即领导者没有故障,网络良好。

在第二部分中,我们通过故意延迟消息来模拟慢速网络,同时假设一个没有故障的领导者。最后,在第三部分中,我们通过延迟领导者的建议来引入一个错误的领导者。

实验结果表明,在良好的情况下,ParBFT2的性能与Ditto和BDT相当好,因为所有三个协议都可以通过乐观路径提交。正如预期的那样,随着副本数量的增加,ParBFT1的性能由于其二次消息复杂性而恶化。在慢速网络的情况下,延迟设置为大于Δ,与Ditto和BDT相比,ParBFT1和ParBFT2表现出明显更低的延迟。ParBFT实现了更低的延迟,因为即使网络延迟估计错误,它也可以通过乐观路径提交,而Ditto或BDT必须切换到悲观路径。在一个错误的领导者的情况下,所有协议都将通过悲观路径提交。然而,ParBFT1提供了比Ditto、BDT和ParBFT2更低的延迟,因为它可以立即启动悲观路径,而无需等待超时事件。

综上所述,我们在本文中做出了以下贡献。我们首先确定了当前串行路径异步协议的主要局限性:它们依赖于对网络延迟的准确估计来在两条路径之间进行适当的切换。然后,我们提出了一种称为ParBFT的新范式,该范式并行运行两条路径以解决这些限制。提出了ParBFT的两种变体,在延迟和通信开销之间进行了权衡。最后,我们实现了我们的协议,并进行了全面的实验来展示它们的优势。
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

相关文章:

ParBFT: Faster Asynchronous BFT Consensus with a Parallel Optimistic Path

目录 笔记后续的研究方向摘要引言 ParBFT: Faster Asynchronous BFT Consensus with a Parallel Optimistic Path CCS 2023 笔记 后续的研究方向 摘要 为了减少异步拜占庭容错&#xff08;BFT&#xff09;共识的延迟和通信开销&#xff0c;通常会添加一条乐观的路径&#xf…...

java小工具util系列3:JSON转实体类对象工具

文章目录 准备工作1.JSONObject获取所有的key2.集合中实体对象转换 list中Enrey转Dto3.字符串转List<BusyTimeIndicatorAlarmThreshold>4.json字符串转JSONObject5.list根据ids数组过滤list6.json字符串转JavaBean对象7.json对象转javabean8.jsonObject转map9.List\<U…...

MySQL:找回root密码

一、情景描述 我们在日常学习中&#xff0c;经常会忘记自己的虚拟机中MySQL的root密码。 这个时候&#xff0c;我们要想办法重置root密码&#xff0c;从而&#xff0c;解决root登陆问题。 二、解决办法 1、修改my.cnf配置文件并重启MySQL 通过修改配置文件&#xff0c;来跳…...

计算机网络扫盲(1)——因特网

一、概述 因特网是一个世界范围的计算机网络&#xff0c;即它是一个互联了遍及全世界数十亿计算设备的网络。大家对此应该并不陌生&#xff0c;我们身边有着不计其数的计算机设备被接入了因特网&#xff0c;如今计算机网络这个术语似乎已经有点过时了&#xff0c;用因特网的术语…...

C语言 if语句有无(;)分号问题

在C语言中&#xff0c;if语句后面不带分号&#xff08;;&#xff09;的情况有两种主要形式&#xff1a; 1. 带有大括号的代码块&#xff1a;如果if语句后面跟随一个由大括号&#xff08;{}&#xff09;包围的代码块&#xff0c;那么这个代码块中的语句只有在if条件为真时才会执…...

Python-列表详解(列表的创建、用法、遍历、注意事项、特点等)

本文有以下内容&#xff1a; 列表的创建 列表的下标索引注意事项 列表的访问 列表的增加元素 列表的删除元素 列表的任意删除元素 列表的查找元素 列表的查找元素位置 列表的插入任意位置 列表的遍历 列表的拼接方式 列表的切片操作以及注意事项 列表类似于其他语言的数组 列…...

【langchain实战】开源项目-RasaGPT

1、概述 RasaGpt是一个建立在 Rasa 和 Langchain 之上的没有显示界面的LMM聊天机器人平台。它是一个Rasa和Telegram这种利用像Langchain这样的LMM库进行索引、检索和上下文注入的样板及参考实现。 开源地址&#xff1a; GitHub - paulpierre/RasaGPT: &#x1f4ac; RasaGPT is…...

在线yml和properties相互转换

目前搜索到的大部分代码都存在以下问题&#xff1a; 复杂结构解析丢失解析后顺序错乱 所以自己写了一个&#xff0c;经过不充分测试&#xff0c;基本满足使用。可以直接在线使用 在线地址 除了yml和properties互转之外&#xff0c;还可以生成代码、sql转json等&#xff0c;可…...

数据收集与处理(爬虫技术)

文章目录 1 前言2 网络爬虫2.1 构造自己的Scrapy爬虫2.1.1 items.py2.1.2 spiders子目录2.1.3 pipelines.py 2.2 构造可接受参数的Scrapy爬虫2.3 运行Scrapy爬虫2.3.1 在命令行运行2.3.2 在程序中调用 2.4 运行Scrapy的一些要点 3 大规模非结构化数据的存储与分析4 全部代码 1 …...

C# 雪花算法生成Id工具类

写在前面 传说自然界中并不存在两片完全一样的雪花的&#xff0c;每一片雪花都拥有自己漂亮独特的形状、独一无二&#xff1b;雪花算法也表示生成的ID如雪花般独一无二&#xff0c;该算法源自Twitter。 雪花算法主要用于解决分布式系统的唯一Id生成问题&#xff0c;在生产环境…...

什么是通配符证书?

通配符证书是一种特殊的数字证书&#xff0c;主要用于加密网站与用户之间的通信&#xff0c;以保证数据的私密性和完整性。它的独特之处在于可以使用一个单一的证书来保护无限数量的相关子域名。它使用通配符字符&#xff08;*&#xff09;作为占位符&#xff0c;代表任意子域名…...

西南科技大学模拟电子技术实验五(集成运算放大器的应用设计)预习报告

一、计算/设计过程 设计一:用集成运放设计一个输入为0.05v,放大为-100的反相比例运算电路。 对于理想电路,反相比例运算电路的输出电压与输入电压之间的关系如下: =-100,所以 =100 若是假定R1为100k,则R2= =1k 为了减小输入级偏置电流引起的运算误差,在同相输入端…...

LeetCode 每日一题 Day 4

2477. 到达首都的最少油耗 给你一棵 n 个节点的树&#xff08;一个无向、连通、无环图&#xff09;&#xff0c;每个节点表示一个城市&#xff0c;编号从 0 到 n - 1 &#xff0c;且恰好有 n - 1 条路。0 是首都。给你一个二维整数数组 roads &#xff0c;其中 roads[i] [ai,…...

服务器数据恢复—重装系统导致XFS文件系统分区丢失的数据恢复案例

服务器数据恢复环境&#xff1a; 服务器使用磁盘柜RAID卡搭建了一组riad5磁盘阵列。服务器上层分配了一个LUN&#xff0c;划分了两个分区&#xff1a;sdc1分区和sdc2分区。通过LVM扩容的方式&#xff0c;将sdc1分区加入到了root_lv中&#xff1b;sdc2分区格式化为XFS文件系统。…...

Scala 从入门到精通

Scala 从入门到精通 数据类型 pom.xml <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.org/POM/4.0.0"xmlns:xsi"http://www.w3.org/2001/XMLSchema-instance"xsi:schemaLocation"http:…...

华为OD机试 - 九宫格按键输入 - 逻辑分析(Java 2023 B卷 200分)

目录 专栏导读一、题目描述二、输入描述三、输出描述四、解题思路五、Java算法源码六、效果展示1、输入2、输出3、说明 华为OD机试 2023B卷题库疯狂收录中&#xff0c;刷题点这里 专栏导读 本专栏收录于《华为OD机试&#xff08;JAVA&#xff09;真题&#xff08;A卷B卷&#…...

leetcode:225. 用队列实现栈

一、题目 链接&#xff1a;225. 用队列实现栈 - 力扣&#xff08;LeetCode&#xff09; 函数原型&#xff1a; typedef struct { } MyStack; MyStack* myStackCreate() void myStackPush(MyStack* obj, int x) int myStackPop(MyStack* obj) int myStackTop(MyStack* obj) …...

Centos7安装GItLab(在线版)

基础环境准备 1.配置清华大学镜像仓库 新建仓库配置文件使用 vim /etc/yum.repos.d/gitlab-ce.repo 命令&#xff0c;输入以下内容,保存 [gitlab-ce] nameGitlab CE Repository baseurlhttps://mirrors.tuna.tsinghua.edu.cn/gitlab-ce/yum/el$releasever/ gpgcheck0 enabl…...

Linux入门笔记

1 Linux概述 Linux 是一套免费使用和自由传播的类 Unix 操作系统&#xff0c;是一个基于 POSIX 和 UNIX 的多用户、多任务、支持多线程和多 CPU 的操作系统。Linux 能运行主要的 UNIX 工具软件、应用程序和网络协议。它支持 32 位和 64 位硬件。Linux 继承了 Unix 以网络为核心…...

nvm for windows使用与node/npm/yarn的配置

1 下载 nvm for windows download – github 下拉到Assets, 下载.exe文件 2 安装 安装到如下文件夹中 目录可以自己选, 可以换别的名字, 自己记住即可 新手建议全部看完再进行个人配置, 或者使用与博主一致的路径 D:\DevelopEnvironment\nvm3 配置nvm使用的镜像 node_mir…...

web vue 项目 Docker化部署

Web 项目 Docker 化部署详细教程 目录 Web 项目 Docker 化部署概述Dockerfile 详解 构建阶段生产阶段 构建和运行 Docker 镜像 1. Web 项目 Docker 化部署概述 Docker 化部署的主要步骤分为以下几个阶段&#xff1a; 构建阶段&#xff08;Build Stage&#xff09;&#xff1a…...

Golang 面试经典题:map 的 key 可以是什么类型?哪些不可以?

Golang 面试经典题&#xff1a;map 的 key 可以是什么类型&#xff1f;哪些不可以&#xff1f; 在 Golang 的面试中&#xff0c;map 类型的使用是一个常见的考点&#xff0c;其中对 key 类型的合法性 是一道常被提及的基础却很容易被忽视的问题。本文将带你深入理解 Golang 中…...

安宝特方案丨XRSOP人员作业标准化管理平台:AR智慧点检验收套件

在选煤厂、化工厂、钢铁厂等过程生产型企业&#xff0c;其生产设备的运行效率和非计划停机对工业制造效益有较大影响。 随着企业自动化和智能化建设的推进&#xff0c;需提前预防假检、错检、漏检&#xff0c;推动智慧生产运维系统数据的流动和现场赋能应用。同时&#xff0c;…...

跨链模式:多链互操作架构与性能扩展方案

跨链模式&#xff1a;多链互操作架构与性能扩展方案 ——构建下一代区块链互联网的技术基石 一、跨链架构的核心范式演进 1. 分层协议栈&#xff1a;模块化解耦设计 现代跨链系统采用分层协议栈实现灵活扩展&#xff08;H2Cross架构&#xff09;&#xff1a; 适配层&#xf…...

python如何将word的doc另存为docx

将 DOCX 文件另存为 DOCX 格式&#xff08;Python 实现&#xff09; 在 Python 中&#xff0c;你可以使用 python-docx 库来操作 Word 文档。不过需要注意的是&#xff0c;.doc 是旧的 Word 格式&#xff0c;而 .docx 是新的基于 XML 的格式。python-docx 只能处理 .docx 格式…...

智能分布式爬虫的数据处理流水线优化:基于深度强化学习的数据质量控制

在数字化浪潮席卷全球的今天&#xff0c;数据已成为企业和研究机构的核心资产。智能分布式爬虫作为高效的数据采集工具&#xff0c;在大规模数据获取中发挥着关键作用。然而&#xff0c;传统的数据处理流水线在面对复杂多变的网络环境和海量异构数据时&#xff0c;常出现数据质…...

HDFS分布式存储 zookeeper

hadoop介绍 狭义上hadoop是指apache的一款开源软件 用java语言实现开源框架&#xff0c;允许使用简单的变成模型跨计算机对大型集群进行分布式处理&#xff08;1.海量的数据存储 2.海量数据的计算&#xff09;Hadoop核心组件 hdfs&#xff08;分布式文件存储系统&#xff09;&a…...

群晖NAS如何在虚拟机创建飞牛NAS

套件中心下载安装Virtual Machine Manager 创建虚拟机 配置虚拟机 飞牛官网下载 https://iso.liveupdate.fnnas.com/x86_64/trim/fnos-0.9.2-863.iso 群晖NAS如何在虚拟机创建飞牛NAS - 个人信息分享...

Python 实现 Web 静态服务器(HTTP 协议)

目录 一、在本地启动 HTTP 服务器1. Windows 下安装 node.js1&#xff09;下载安装包2&#xff09;配置环境变量3&#xff09;安装镜像4&#xff09;node.js 的常用命令 2. 安装 http-server 服务3. 使用 http-server 开启服务1&#xff09;使用 http-server2&#xff09;详解 …...

Android写一个捕获全局异常的工具类

项目开发和实际运行过程中难免会遇到异常发生&#xff0c;系统提供了一个可以捕获全局异常的工具Uncaughtexceptionhandler&#xff0c;它是Thread的子类&#xff08;就是package java.lang;里线程的Thread&#xff09;。本文将利用它将设备信息、报错信息以及错误的发生时间都…...