当前位置: 首页 > 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…...

IDEA运行Tomcat出现乱码问题解决汇总

最近正值期末周&#xff0c;有很多同学在写期末Java web作业时&#xff0c;运行tomcat出现乱码问题&#xff0c;经过多次解决与研究&#xff0c;我做了如下整理&#xff1a; 原因&#xff1a; IDEA本身编码与tomcat的编码与Windows编码不同导致&#xff0c;Windows 系统控制台…...

多云管理“拦路虎”:深入解析网络互联、身份同步与成本可视化的技术复杂度​

一、引言&#xff1a;多云环境的技术复杂性本质​​ 企业采用多云策略已从技术选型升维至生存刚需。当业务系统分散部署在多个云平台时&#xff0c;​​基础设施的技术债呈现指数级积累​​。网络连接、身份认证、成本管理这三大核心挑战相互嵌套&#xff1a;跨云网络构建数据…...

OpenLayers 可视化之热力图

注&#xff1a;当前使用的是 ol 5.3.0 版本&#xff0c;天地图使用的key请到天地图官网申请&#xff0c;并替换为自己的key 热力图&#xff08;Heatmap&#xff09;又叫热点图&#xff0c;是一种通过特殊高亮显示事物密度分布、变化趋势的数据可视化技术。采用颜色的深浅来显示…...

Zustand 状态管理库:极简而强大的解决方案

Zustand 是一个轻量级、快速和可扩展的状态管理库&#xff0c;特别适合 React 应用。它以简洁的 API 和高效的性能解决了 Redux 等状态管理方案中的繁琐问题。 核心优势对比 基本使用指南 1. 创建 Store // store.js import create from zustandconst useStore create((set)…...

Swift 协议扩展精进之路:解决 CoreData 托管实体子类的类型不匹配问题(下)

概述 在 Swift 开发语言中&#xff0c;各位秃头小码农们可以充分利用语法本身所带来的便利去劈荆斩棘。我们还可以恣意利用泛型、协议关联类型和协议扩展来进一步简化和优化我们复杂的代码需求。 不过&#xff0c;在涉及到多个子类派生于基类进行多态模拟的场景下&#xff0c;…...

leetcodeSQL解题:3564. 季节性销售分析

leetcodeSQL解题&#xff1a;3564. 季节性销售分析 题目&#xff1a; 表&#xff1a;sales ---------------------- | Column Name | Type | ---------------------- | sale_id | int | | product_id | int | | sale_date | date | | quantity | int | | price | decimal | -…...

[Java恶补day16] 238.除自身以外数组的乘积

给你一个整数数组 nums&#xff0c;返回 数组 answer &#xff0c;其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法&#xff0c;且在 O(n) 时间复杂度…...

初探Service服务发现机制

1.Service简介 Service是将运行在一组Pod上的应用程序发布为网络服务的抽象方法。 主要功能&#xff1a;服务发现和负载均衡。 Service类型的包括ClusterIP类型、NodePort类型、LoadBalancer类型、ExternalName类型 2.Endpoints简介 Endpoints是一种Kubernetes资源&#xf…...

面向无人机海岸带生态系统监测的语义分割基准数据集

描述&#xff1a;海岸带生态系统的监测是维护生态平衡和可持续发展的重要任务。语义分割技术在遥感影像中的应用为海岸带生态系统的精准监测提供了有效手段。然而&#xff0c;目前该领域仍面临一个挑战&#xff0c;即缺乏公开的专门面向海岸带生态系统的语义分割基准数据集。受…...

基于Java+VUE+MariaDB实现(Web)仿小米商城

仿小米商城 环境安装 nodejs maven JDK11 运行 mvn clean install -DskipTestscd adminmvn spring-boot:runcd ../webmvn spring-boot:runcd ../xiaomi-store-admin-vuenpm installnpm run servecd ../xiaomi-store-vuenpm installnpm run serve 注意&#xff1a;运行前…...