Fast Byzantine Agreement

Nicolas Braud-Santoni; Rachid Guerraoui; Florian Huc

doi:10.1145/2484239.2484243

Fast Byzantine Agreement

Nicolas Braud-Santoni, Rachid Guerraoui, Florian Huc

Institute of Applied Information Processing and Communications (7050)

Research output: Chapter in Book/Report/Conference proceeding › Conference paper › peer-review

Abstract

This paper presents the first probabilistic Byzantine Agreement algorithm whose communication and time complexities are poly-logarithmic. So far, the most effective probabilistic Byzantine Agreement algorithm had communication complexity Õ(√n) and time complexity Õ(1).

Our algorithm is based on a novel, unbalanced, almost-everywhere to everywhere Agreement protocol which is interesting in its own right

Original language	English
Title of host publication	PODC '13: Proceedings of the 2013 ACM Symposium on Principles of Distributed Computing
Place of Publication	New York
Publisher	Association of Computing Machinery
Pages	57-64
ISBN (Print)	978-1-4503-2065-8
DOIs	https://doi.org/10.1145/2484239.2484243
Publication status	Published - 2013
Event	ACM Symposium on Principles of Distributed Computing: PODC 2013 - Montreal, Canada Duration: 22 Jul 2013 → 24 Jul 2013

Conference

Conference	ACM Symposium on Principles of Distributed Computing
Country/Territory	Canada
City	Montreal
Period	22/07/13 → 24/07/13

Fields of Expertise

Information, Communication & Computing

Treatment code (Nähere Zuordnung)

Theoretical

Access to Document

10.1145/2484239.2484243

Fast-Byzantine-Agreement.pdfFinal published version, 427 KB

Cite this

@inproceedings{2f5453c63bef4cc68a3c360535cd038d,

title = "Fast Byzantine Agreement",

abstract = "This paper presents the first probabilistic Byzantine Agreement algorithm whose communication and time complexities are poly-logarithmic. So far, the most effective probabilistic Byzantine Agreement algorithm had communication complexity {\~O}(√n) and time complexity {\~O}(1).Our algorithm is based on a novel, unbalanced, almost-everywhere to everywhere Agreement protocol which is interesting in its own right",

author = "Nicolas Braud-Santoni and Rachid Guerraoui and Florian Huc",

year = "2013",

doi = "10.1145/2484239.2484243",

language = "English",

isbn = "978-1-4503-2065-8",

pages = "57--64",

booktitle = "PODC '13: Proceedings of the 2013 ACM Symposium on Principles of Distributed Computing",

publisher = "Association of Computing Machinery",

address = "United States",

note = "ACM Symposium on Principles of Distributed Computing : PODC 2013 ; Conference date: 22-07-2013 Through 24-07-2013",

}

TY - GEN

T1 - Fast Byzantine Agreement

AU - Braud-Santoni, Nicolas

AU - Guerraoui, Rachid

AU - Huc, Florian

PY - 2013

Y1 - 2013

N2 - This paper presents the first probabilistic Byzantine Agreement algorithm whose communication and time complexities are poly-logarithmic. So far, the most effective probabilistic Byzantine Agreement algorithm had communication complexity Õ(√n) and time complexity Õ(1).Our algorithm is based on a novel, unbalanced, almost-everywhere to everywhere Agreement protocol which is interesting in its own right

AB - This paper presents the first probabilistic Byzantine Agreement algorithm whose communication and time complexities are poly-logarithmic. So far, the most effective probabilistic Byzantine Agreement algorithm had communication complexity Õ(√n) and time complexity Õ(1).Our algorithm is based on a novel, unbalanced, almost-everywhere to everywhere Agreement protocol which is interesting in its own right

UR - https://dl.acm.org/citation.cfm?id=2484239

U2 - 10.1145/2484239.2484243

DO - 10.1145/2484239.2484243

M3 - Conference paper

SN - 978-1-4503-2065-8

SP - 57

EP - 64

BT - PODC '13: Proceedings of the 2013 ACM Symposium on Principles of Distributed Computing

PB - Association of Computing Machinery

CY - New York

T2 - ACM Symposium on Principles of Distributed Computing

Y2 - 22 July 2013 through 24 July 2013

ER -

Fast Byzantine Agreement

Abstract

Conference

Fields of Expertise

Treatment code (Nähere Zuordnung)

Access to Document

Other files and links

Fingerprint

Cite this