The Cost of Fault Tolerance in Multi-Party Communication Complexity
From MaRDI portal
Publication:3189654
DOI10.1145/2597633zbMath1295.68115OpenAlexW2121041710MaRDI QIDQ3189654
Phillip B. Gibbons, Haifeng Yu, Yuda Zhao, Binbin Chen
Publication date: 12 September 2014
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/2597633
Nonnumerical algorithms (68W05) Reliability, testing and fault tolerance of networks and computer systems (68M15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (2)
Some lower bounds in dynamic networks with oblivious adversaries ⋮ Near-optimal communication-time tradeoff in fault-tolerant computation of aggregate functions
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- An information statistics approach to data stream and communication complexity
- Secure and highly-available aggregation queries in large-scale sensor networks via set sampling
- On the Sperner capacity of the cyclic triangle
- Secure multiparty protocols and zero-knowledge proof systems tolerating a faulty minority
- The price of validity in dynamic networks
- Probabilistic counting algorithms for data base applications
- Private vs. common random bits in communication complexity
- Communication complexity of fault-tolerant information diffusion
- Fast consensus in networks of bounded degree.
- LiMoSense: live monitoring in dynamic sensor networks
- A coding theorem for distributed computation
- Almost-Optimal Gossip-Based Aggregate Computation
- The cost of fault tolerance in multi-party communication complexity
- Coding for interactive communication
- Scalable leader election
- From Almost Everywhere to Everywhere: Byzantine Agreement with $\tilde{O}(n^{3/2})$ Bits
- The capacity of wireless networks
- Broadcast Gossip Algorithms for Consensus
- Communication Complexity
- An Optimal Lower Bound on the Communication Complexity of Gap-Hamming-Distance
- Silence-Based Communication
- Fast scalable deterministic consensus for crash failures
- Computing separable functions via gossip
- Asynchronous secure computation
- Information Theoretic Bounds for Distributed Computation Over Networks of Point-to-Point Channels
- Towards coding for maximum errors in interactive communication
- Distributed verification and hardness of distributed approximation
- Robust Multiparty Computation with Linear Communication Complexity
This page was built for publication: The Cost of Fault Tolerance in Multi-Party Communication Complexity
