The Contest between Simplicity and Efficiency in Asynchronous Byzantine Agreement

DOI10.1007/978-3-642-24100-0_35zbMATH Open1350.68036arXiv1106.5170OpenAlexW1564067556MaRDI QIDQ3095337FDOQ3095337

Author name not available (Why is that?)

Publication date: 28 October 2011

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Abstract: In the wake of the decisive impossibility result of Fischer, Lynch, and Paterson for deterministic consensus protocols in the aynchronous model with just one failure, Ben-Or and Bracha demonstrated that the problem could be solved with randomness, even for Byzantine failures. Both protocols are natural and intuitive to verify, and Bracha's achieves optimal resilience. However, the expected running time of these protocols is exponential in general. Recently, Kapron, Kempe, King, Saia, and Sanwalani presented the first efficient Byzantine agreement algorithm in the asynchronous, full information model, running in polylogarithmic time. Their algorithm is Monte Carlo and drastically departs from the simple structure of Ben-Or and Bracha's Las Vegas algorithms. In this paper, we begin an investigation of the question: to what extent is this departure necessary? Might there be a much simpler and intuitive Las Vegas protocol that runs in expected polynomial time? We will show that the exponential running time of Ben-Or and Bracha's algorithms is no mere accident of their specific details, but rather an unavoidable consequence of their general symmetry and round structure. We define a natural class of "fully symmetric round protocols" for solving Byzantine agreement in an asynchronous setting and show that any such protocol can be forced to run in expected exponential time by an adversary in the full information model. We assume the adversary controls $t$ Byzantine processors for $t=cn$, where $c$ is an arbitrary positive constant $<1/3$. We view our result as a step toward identifying the level of complexity required for a polynomial-time algorithm in this setting, and also as a guide in the search for new efficient algorithms.

Full work available at URL: https://arxiv.org/abs/1106.5170

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Distributed algorithms (68W15) Distributed systems (68M14) Network protocols (68M12)

Cites Work

• Title not available (Why is that?)
• Impossibility of distributed consensus with one faulty process
• Reaching Agreement in the Presence of Faults
• A tight lower bound for randomized synchronous consensus
• Byzantine agreement in the full-information model in O(log n) rounds
• Scalable leader election
• From Almost Everywhere to Everywhere: Byzantine Agreement with $\tilde{O}(n^{3/2})$ Bits
• Breaking the O ( n ² ) bit barrier
• Lower bounds for randomized consensus under a weak adversary
• Fast asynchronous Byzantine agreement and leader election with full information

Cited In (2)

• On the round complexity of randomized Byzantine agreement
• On the complexity of asynchronous agreement against powerful adversaries

This page was built for publication: The Contest between Simplicity and Efficiency in Asynchronous Byzantine Agreement

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3095337)