Easy impossibility proofs for distributed consensus problems

No abstract is available for this paper.

• Publication year

  1985

• Venue

  ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing

• Publication date

  1985-08-01

• Fields of study

  Computer Science

• Identifiers
  DOI 10.1007/BF01843568
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Reaching approximate agreement in the presence of faults

  1986influential reference
• The distributed firing squad problem

  1985cited by this paper
• The Byzantine Firing Squad Problem.

  1985cited by this paper
• On the possibility and impossibility of achieving clock synchronization

  1984influential reference
• The Weak Byzantine Generals Problem

  1983influential reference
• The Byzantine Generals Problem

  1982cited by this paper
• Symmetry breaking in distributive networks

  1981cited by this paper
• The Byzantine Generals Strike Again

  1981cited by this paper
• Local and global properties in networks of processors (Extended Abstract)

  1980cited by this paper
• Reaching Agreement in the Presence of Faults

  1980cited by this paper

• Reaching Univalency with Subquadratic Communication

  2026cites this paper
• Scalable and Highly Fault-Tolerant Circular Quantum Byzantine Agreement

  2026cites this paper
• Byzantine Broadcast with Unknown Participants

  2025cites this paper
• On Time-Optimal, Fault-Tolerant Algorithms for Connected Consensus Beyond Grade Two

  2025cites this paper
• Building a Theory of Distributed Systems: Work by Nancy Lynch and Collaborators

  2025influential citation
• Improved Byzantine Agreement under an Adaptive Adversary

  2025cites this paper
• Message Size Matters: AlterBFT’s Approach to Practical Synchronous BFT in Public Clouds

  2025cites this paper
• Coordinate-Wise Median in Byzantine Federated Learning

  2025cites this paper
• Computing in a Faulty Congested Clique

  2025cites this paper
• Byzantine Agreement with Predictions

  2025cites this paper
• On cofactored verification of EdDSA signatures

  2025cites this paper
• TEE is not a Healer: Rollback-Resistant Reliable Storage

  2025cites this paper
• Optimal Byzantine Agreement in the Presence of Message Drops

  2025cites this paper
• A Graph-Relaxed Method for Byzantine-Resilient Distributed Multidimensional Consensus

  2025cites this paper
• A Tutorial on Distributed Multi-Armed Bandits

  2025cites this paper
• Byzantine Stable Matching

  2025cites this paper
• Repeated Agreement is Cheap! On Weak Accountability and Multishot Byzantine Agreement

  2025cites this paper
• Saturation-tolerant prescribed performance neural formation control for air-floating robots under false data injection attacks

  2025cites this paper
• SoK: Approximate Agreement

  2025cites this paper
• An Analysis of Avalanche Consensus

  2024cites this paper
• Optimal Load-Balanced Scalable Distributed Agreement

  2024cites this paper
• Experimental quantum Byzantine agreement on a three-user quantum network with integrated photonics

  2024cites this paper
• BeRGeR: Byzantine-Robust Geometric Routing

  2024cites this paper
• Consensus Under Adversary Majority Done Right

  2024cites this paper
• MBFT: A Modular Byzantine Fault Tolerance Protocol for high adaptability

  2024cites this paper
• Validity in Network-Agnostic Byzantine Agreement

  2024cites this paper
• Trusted Hardware-Assisted Leaderless Byzantine Fault Tolerance Consensus

  2024cites this paper
• Granular Synchrony

  2024cites this paper
• How Robust Are Synchronous Consensus Protocols?

  2024cites this paper
• DARE to Agree: Byzantine Agreement With Optimal Resilience and Adaptive Communication

  2024cites this paper
• On the Communication Complexity of Secure Multi-Party Computation With Aborts

  2024cites this paper
• Completeness Theorems for Adaptively Secure Broadcast

  2023influential citation
• Memory Checking for Parallel RAMs

  2023cites this paper
• A Quantum Detectable Byzantine Agreement Protocol Using Only EPR Pairs

  2023cites this paper
• Desirable Properties of Heterogeneous Quorum Systems

  2023cites this paper
• Byzantine-Resilient Decentralized Multi-Armed Bandits

  2023cites this paper
• All Byzantine Agreement Problems Are Expensive

  2023cites this paper
• Consensus on Unknown Torus with Dense Byzantine Faults

  2023cites this paper
• Network Abstractions for Characterizing Communication Requirements in Asynchronous Distributed Systems

  2023cites this paper
• Consensus on an Unknown Torus with Dense Byzantine Faults

  2023cites this paper
• Communication lower bounds for cryptographic broadcast protocols

  2023cites this paper
• Concurrent Asynchronous Byzantine Agreement in Expected-Constant Rounds, Revisited

  2023cites this paper
• Scalable Agreement Protocols with Optimal Optimistic Efficiency

  2023cites this paper
• V-Guard: An Efficient Permissioned Blockchain for Achieving Consensus under Dynamic Memberships in V2X Networks

  2023cites this paper
• Complete Characterization of Broadcast and Pseudo-Signatures from Correlations

  2023influential citation
• Quorum Subsumption for Heterogeneous Quorum Systems

  2023cites this paper
• Bounds on Worst-Case Responsiveness for Agreement Algorithms

  2023cites this paper
• REACi-llNG APPROXIMATE AGREEMENT IN THE PRESENCE OF FAUL TS

  2023cites this paper
• On the Power of an Honest Majority in Three-Party Computation Without Broadcast

  2023cites this paper
• Efficient Agreement Over Byzantine Gossip

  2023cites this paper
• Byzantine agreement in polynomial time with near-optimal resilience

  2022cites this paper
• Embedding reverse links in a blockchain

  2022cites this paper
• Optimal Clock Synchronization with Signatures

  2022cites this paper
• TSBFT: A scalable and efficient leaderless byzantine consensus for consortium blockchain

  2022cites this paper
• Gradecast in Synchrony and Reliable Broadcast in Asynchrony with Optimal Resilience, Efficiency, and Unconditional Security

  2022cites this paper
• On Secure Computation of Solitary Output Functionalities With and Without Broadcast

  2022cites this paper
• Player-Replaceability and Forensic Support are Two Sides of the Same (Crypto) Coin

  2022cites this paper
• Communication-Efficient BFT Using Small Trusted Hardware to Tolerate Minority Corruption

  2022cites this paper
• Byzantine Agreement with Optimal Resilience via Statistical Fraud Detection

  2022cites this paper
• LWSBFT: Leaderless weakly synchronous BFT protocol

  2022cites this paper
• New Dolev-Reischuk Lower Bounds Meet Blockchain Eclipse Attacks

  2022cites this paper
• Beating the Fault-Tolerance Bound and Security Loopholes for Byzantine Agreement with a Quantum Solution

  2022cites this paper
• Reaching Efficient Byzantine Agreements in Bipartite Networks

  2022cites this paper
• TrustBoost: Boosting Trust among Interoperable Blockchains

  2022cites this paper
• Reaching Agreement Among k out of n Processes

  2022cites this paper
• Byzantine-Robust Decentralized Learning via ClippedGossip

  2022cites this paper
• Consensus Capacity of Noisy Broadcast Channels

  2022cites this paper
• Byzantine-Robust Decentralized Learning via Self-Centered Clipping

  2022cites this paper
• Breaking the O(√ n)-Bit Barrier: Byzantine Agreement with Polylog Bits Per Party

  2021cites this paper
• Distributed Online Optimization with Byzantine Adversarial Agents

  2021cites this paper
• Byzantine-Resilient Multiagent Optimization

  2021cites this paper
• Optimal Communication Complexity of Authenticated Byzantine Agreement

  2021cites this paper
• The Epigenetic Consensus Problem

  2021cites this paper
• Efficient Asynchronous Byzantine Agreement without Private Setups

  2021cites this paper
• Adaptively Secure Broadcast in Resource-Restricted Cryptography

  2021influential citation
• Disconnected Agreement in Networks Prone to Link Failures

  2021cites this paper
• Wait-free approximate agreement on graphs

  2021cites this paper
• Payment Does Not Imply Consensus (For Distributed Payment Systems)

  2021cites this paper
• PISTIS: An Event-Triggered Real-Time Byzantine-Resilient Protocol Suite

  2021cites this paper
• Optimal Good-case Latency for Rotating Leader Synchronous BFT

  2021cites this paper
• Communication-Efficient BFT Protocols Using Small Trusted Hardware to Tolerate Minority Corruption

  2021cites this paper
• Consensus in Networks Prone to Link Failures

  2021cites this paper
• Byzantine Agreement with Unknown Participants and Failures

  2021cites this paper
• Pravuil: Global Consensus for a United World

  2021cites this paper
• Towards a Smart Data Processing and Storage Model

  2021cites this paper
• On Communication Models and Best-Achievable Security in Two-Round MPC

  2021cites this paper
• Byzantine Consensus with Local Multicast Channels

  2021cites this paper
• Secure Consensus with Distributed Detection via Two-hop Communication

  2021cites this paper
• Genome-Wide Epigenetic Modifications as a Shared Memory Consensus Problem

  2020influential citation
• Asynchronous Byzantine Approximate Consensus in Directed Networks

  2020cites this paper
• Threshold ECDSA for Decentralized Asset Custody

  2020cites this paper
• Resource-Restricted Cryptography: Revisiting MPC Bounds in the Proof-of-Work Era

  2020cites this paper
• Breaking the $O(\sqrt n)$-Bits Barrier: Balanced Byzantine Agreement with Polylog Bits Per-Party.

  2020cites this paper
• Revisiting asynchronous fault tolerant computation with optimal resilience

  2020cites this paper
• Leveraging Federated Clouds for Improving Blockchain Performance

  2020cites this paper
• Topics in Cryptology – CT-RSA 2020: The Cryptographers’ Track at the RSA Conference 2020, San Francisco, CA, USA, February 24–28, 2020, Proceedings

  2020cites this paper
• Succinctly Reconstructed Distributed Signatures and Balanced Byzantine Agreement

  2020cites this paper
• Bitcoin Consensus in Distributed Systems

  2020cites this paper
• MPC for MPC: Secure Computation on a Massively Parallel Computing Architecture

  2020cites this paper
• Asynchronous Byzantine Agreement in Incomplete Networks

  2020cites this paper