Breaking the O ( n 2 ) bit barrier

DOI10.1145/1835698.1835798zbMath1315.68272OpenAlexW1967345158MaRDI QIDQ5176217

Jared Saia, Valerie King

Publication date: 2 March 2015

Published in: Proceedings of the 29th ACM SIGACT-SIGOPS symposium on Principles of distributed computing (Search for Journal in Brave)

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

zbMATH Keywords

Monte Carlo algorithmsdistributed computingconsensussecret-sharingByzantine agreementpeer-to-peersamplers

Mathematics Subject Classification ID

Monte Carlo methods (65C05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Distributed systems (68M14) Authentication, digital signatures and secret sharing (94A62) Distributed algorithms (68W15)

Related Items (10)

Signature-Free Asynchronous Byzantine Systems: From Multivalued to Binary Consensus with t < n/3, O(n 2) Messages, and Constant Time ⋮ Signature-free asynchronous Byzantine systems: from multivalued to binary consensus with \(t<n/3\), \(O(n^2)\) messages, and constant time ⋮ Gossiping for communication-efficient broadcast ⋮ Efficient adaptively-secure Byzantine agreement for long messages ⋮ On the complexity of asynchronous agreement against powerful adversaries ⋮ Must the communication graph of MPC protocols be an expander? ⋮ From fairness to full security in multiparty computation ⋮ The Contest between Simplicity and Efficiency in Asynchronous Byzantine Agreement ⋮ Network-Hiding Communication and Applications to Multi-party Protocols ⋮ Scalable mechanisms for rational secret sharing

Uses Software

• CCSTM

Cites Work

• Elastic Transactions
• Toward a theory of transactional contention managers
• Software transactional memory

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