当前位置：文档之家 › From consensus to atomic broadcast Time-free byzantine-resistant protocols without signatur

From consensus to atomic broadcast Time-free byzantine-resistant protocols without signatur

  • 格式：pdf
  • 大小：220.75 KB
  • 文档页数：32

下载文档原格式

  / 32

合集下载

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

From Consensus to Atomic

Broadcast:Time-Free

Byzantine-Resistant Protocols

without Signatures

Miguel Correia,Nuno Ferreira Neves,

Paulo Ver´ıssimo

DI–FCUL TR–05–14

October2005

Departamento de Inform´a tica

Faculdade de Ciˆe ncias da Universidade de Lisboa

Campo Grande,1749–016Lisboa

Portugal

Technical reports are available at http://www.di.fc.ul.pt/tech-reports.Thefiles are stored in PDF,with the report number asfilename.Alternatively,reports are available by post from the above address.

From Consensus to Atomic Broadcast:Time-Free

Byzantine-Resistant Protocols without Signatures∗

M IGUEL C ORREIA N UNO F ERREIRA N EVES P AULO V ER´I SSIMO

Faculdade de Ciˆe ncias da Universidade de Lisboa,Campo Grande,1749-016Lisboa-Portugal

{mpc,nuno,pjv}@di.fc.ul.pt

Keywords:consensus,atomic broadcast,asynchronous systems,Byzantine faults,intrusion tolerance,randomization

First published:June2004

Revised:October2005

Abstract

This paper proposes a stack of three Byzantine-resistant protocols aimed to be used in practical dis-tributed systems:multi-valued consensus,vector consensus and atomic broadcast.These protocols are

designed as successive transformations from one to another.Thefirst protocol,multi-valued consensus,is

implemented on top of a randomized binary consensus and a reliable broadcast protocol.

The protocols share a set of important structural properties.Firstly,they do not use digital signatures constructed with public-key cryptography,a well-known performance bottleneck in this kind of protocols.

Secondly,they are time-free,i.e.,they make no synchrony assumptions,since these assumptions are often

vulnerable to subtle but effective attacks.Thirdly,they are completely decentralized,thus avoiding the cost

of detecting corrupt leaders.Fourthly,they have optimal resilience,i.e.,they tolerate f= n−1

out of

3

a total of n processes.In terms of time complexity,the multi-valued consensus protocol terminates in a

constant expected number of rounds,while the vector consensus and atomic broadcast protocols have O(f)

complexity.

The paper also proves the equivalence between multi-valued consensus and atomic broadcast in the Byzantine failure model without signatures.A similar proof is given for the equivalence between multi-

valued consensus and vector consensus.These two results have theoretical relevance since they show once

more that consensus is a fundamental problem in distributed systems.

∗This work was partially supported by the EU through project CRitical UTility InfrastructurAL Resilience(CRUTIAL),and the FCT through project POSI/EIA/60334/2004(RITAS)and the Large-Scale Informatic Systems Laboratory(LASIGE).A version of this paper was accepted for publication by Oxford University Press in the Computer Journal.