Byzantine Agreement with Optimal Early Stopping, Optimal Resilience and Polynomial Complexity

DOI10.1145/2746539.2746581zbMath1321.68096arXiv1504.02547OpenAlexW2009547311MaRDI QIDQ2941556

Ittai Abraham, Danny Dolev

Publication date: 21 August 2015

Published in: Proceedings of the forty-seventh annual ACM symposium on Theory of Computing (Search for Journal in Brave)

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

zbMATH Keywords

Byzantine agreementearly stopping

Mathematics Subject Classification ID

Distributed systems (68M14) Reliability, testing and fault tolerance of networks and computer systems (68M15) Network protocols (68M12)

Related Items

Invited talk: Resilient distributed algorithms ⋮ Optimistically tuning synchronous Byzantine consensus: another win for null messages

Uses Software

• Graphs

Cites Work

• Ramsey partitions and proximity data structures
• On sparse spanners of weighted graphs
• Scale-oblivious metric fragmentation and the nonlinear Dvoretzky theorem
• On Approximate Distance Labels and Routing Schemes with Affine Stretch
• Distance Oracles for Unweighted Graphs: Breaking the Quadratic Barrier with Constant Additive Error
• Approximate distance oracles
• Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
• Near-Linear Time Construction of Sparse Neighborhood Covers
• Shortest-path queries in static networks
• Approximate distance oracles with constant query time
• Automata, Languages and Programming
• Unnamed Item