Breaking the O ( n 2 ) bit barrier

DOI10.1145/1989727.1989732zbMath1281.68047OpenAlexW2001271834MaRDI QIDQ5395663

Valerie King, Jared Saia

Publication date: 17 February 2014

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1989727.1989732

zbMATH Keywords

Monte Carlo algorithmsdistributed computingconsensussecret-sharingByzantine agreementpeer-to-peersamplers

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Distributed systems (68M14) Network protocols (68M12) Authentication, digital signatures and secret sharing (94A62)

Related Items (11)

Optimal extension protocols for Byzantine broadcast and agreement ⋮ Breaking the \(O(\sqrt{n})\)-bit barrier: Byzantine agreement with polylog bits per party ⋮ Communication complexity of Byzantine agreement, revisited ⋮ On the Amortized Communication Complexity of Byzantine Broadcast ⋮ Brief Announcement: Improved Consensus in Quantum Networks ⋮ Deterministic Fault-Tolerant Distributed Computing in Linear Time and Communication ⋮ Near-optimal self-stabilising counting and firing squads ⋮ Sublinear-round Byzantine agreement under corrupt majority ⋮ Leader Election in Sparse Dynamic Networks with Churn ⋮ Unnamed Item ⋮ Distributed agreement in dynamic peer-to-peer networks

This page was built for publication: Breaking the O ( n ² ) bit barrier