Reaching Agreement in the Presence of Faults
From MaRDI portal
Publication:3873545
DOI10.1145/322186.322188zbMath0434.68031OpenAlexW2126924915WikidataQ55966961 ScholiaQ55966961MaRDI QIDQ3873545
Robert E. Shostak, M. C. III Pease, Leslie Lamport
Publication date: 1980
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/322186.322188
synchronizationfault tolerancevotingauthenticationfaulty processorsagreementcommunicating processorsdistributed executivefault avoidance
Communication, information (94A99) Theory of operating systems (68N25) Discrete mathematics in relation to computer science (68R99) Theory of software (68N99) Theory of computing (68Q99)
Related Items
Survey on Parameterized Verification with Threshold Automata and the Byzantine Model Checker, Consensus in Data Management: From Distributed Commit to Blockchain, Signature-Free Asynchronous Byzantine Systems: From Multivalued to Binary Consensus with t < n/3, O(n 2) Messages, and Constant Time, On the Versatility of Bracha’s Byzantine Reliable Broadcast Algorithm, Time is not a healer, Unconditional Byzantine agreement for any number of faulty processors, Secure Protocols with Asymmetric Trust, Permissionless consensus in the resource model, Self-stabilizing Byzantine fault-tolerant repeated reliable broadcast, Asynchronous Byzantine reliable broadcast with a message adversary, Correction to: ``Topology-hiding communication from minimal assumptions, Improved deterministic leader election in diameter-two networks, Cloture Votes:n/4-resilient Distributed Consensus int + 1 rounds, A partial equivalence between shared-memory and message-passing in an asynchronous fail-stop distributed environment, Message-optimal protocols for Byzantine Agreement, The Failure Discovery problem, Modular construction of an efficient 1-bit Byzantine agreement protocol, Breaking the \(O(\sqrt{n})\)-bit barrier: Byzantine agreement with polylog bits per party, Graph-theoretic approaches for analyzing the resilience of distributed control systems: a tutorial and survey, A resilient distributed optimization strategy against false data injection attacks, Total ordering algorithms for asynchronous Byzantine systems, Optimal algorithms for synchronous Byzantine \(k\)-set agreement, Reaching agreement in the presence of contention-related crash failures, Gossiping for communication-efficient broadcast, Revisiting the efficiency of asynchronous MPC with optimal resilience against general adversaries, On specifications and proofs of timed circuits, Asymptotically free broadcast in constant expected time via packed VSS, Self-stabilizing Byzantine fault-tolerant repeated reliable broadcast, An algorithm for identification of maliciously faulty units, \textsc{Tardigrade}: an atomic broadcast protocol for arbitrary network conditions, Efficient Counting with Optimal Resilience, Decentralizing information technology: the advent of resource based systems, Unnamed Item, Reaching a consensus with limited information, Distributed computing in asynchronous networks with byzantine edges, Completeness theorems for adaptively secure broadcast, \textsc{FnF-BFT}: a BFT protocol with provable performance under attack, Unnamed Item, On tolerance of discrete systems with respect to transition perturbations, Universally Composable Simultaneous Broadcast against a Dishonest Majority and Applications, Distributed CONGEST Algorithms against Mobile Adversaries, Brief Announcement: Improved Consensus in Quantum Networks, On the Validity of Consensus, Deterministic Fault-Tolerant Distributed Computing in Linear Time and Communication, Almost-surely terminating asynchronous Byzantine agreement against general adversaries with optimal resilience, Order optimal information spreading using algebraic gossip, How to Solve Consensus in the Smallest Window of Synchrony, Continuous Consensus with Failures and Recoveries, No Double Discount: Condition-Based Simultaneity Yields Limited Gain, Optimal time byzantine agreement for t <n/8 with linear-messages, Optimal asynchronous agreement and leader election algorithm for complete networks with Byzantine faulty links, Fast timing-based algorithms, Hundreds of impossibility results for distributed computing, Randomized protocols for asynchronous consensus, Appraising two decades of distributed computing theory research, Resilient-optimal interactive consistency in constant time, Spatial reference frame agreement in quantum networks, Must the communication graph of MPC protocols be an expander?, A closer look at fault tolerance, What Can be Computed in a Distributed System?, Tutorial on Parameterized Model Checking of Fault-Tolerant Distributed Algorithms, On the power of an honest majority in three-party computation without broadcast, Structuring unreliable radio networks, Unnamed Item, Unnamed Item, Byzantine agreement with homonyms, Distributed deterministic edge coloring using bounded neighborhood independence, Compact policy routing, Continuous Consensus with Ambiguous Failures, On Optimal Probabilistic Asynchronous Byzantine Agreement, Reaching Approximate Byzantine Consensus with Multi-hop Communication, Near-optimal self-stabilising counting and firing squads, Wait-free approximate agreement on graphs, Wait-free approximate agreement on graphs, A distributed computing perspective of unconditionally secure information transmission in Russian cards problems, Byzantine agreement with homonyms, Correctness of Tendermint-Core Blockchains, Fault-tolerant algorithms for tick-generation in asynchronous logic, Back to the Coordinated Attack Problem, Asynchronous reference frame agreement in a quantum network, Leader Election in Sparse Dynamic Networks with Churn, Unnamed Item, Analysis of the Blockchain Protocol in Asynchronous Networks, Unbeatable consensus, On the round complexity of randomized Byzantine agreement, Reliable synchronization in distributed systems, Byzantine gathering in networks, Common knowledge and consistent simultaneous coordination, Broadcast from Minicast Secure Against General Adversaries, Valency-based consensus under message adversaries without limit-closure, The Heard-Of model: computing in distributed systems with benign faults, What You Always Wanted to Know About Model Checking of Fault-Tolerant Distributed Algorithms, Byzantine gathering in polynomial time, Instant block confirmation in the sleepy model, Efficient state management in distributed ledgers, High-threshold AVSS with optimal communication complexity, Authenticated broadcast with a partially compromised public-key infrastructure, Rigorously modeling self-stabilizing fault-tolerant circuits: an ultra-robust clocking scheme for systems-on-chip, Agreement in synchronous networks with ubiquitous faults, Communication Patterns and Input Patterns in Distributed Computing, Performance study of Byzantine agreement protocol with artificial neural network, Decentralized asset custody scheme with security against rational adversary, Tight Bounds for Asynchronous Renaming, Atomic read/write memory in signature-free Byzantine asynchronous message-passing systems, Optimal extension protocols for Byzantine broadcast and agreement, Signature-free asynchronous Byzantine systems: from multivalued to binary consensus with \(t<n/3\), \(O(n^2)\) messages, and constant time, piChain: When a Blockchain meets Paxos, Synchronous consensus with optimal asynchronous fallback guarantees, The Firing Squad Problem Revisited., Coordinated consensus in dynamic networks, Error-free multi-valued consensus with byzantine failures, Distributed graph coloring in a few rounds, MIS on trees, Toward more localized local algorithms, The complexity of robust atomic storage, Resilience of mutual exclusion algorithms to transient memory faults, The impact of memory models on software reliability in multiprocessors, A complexity separation between the cache-coherent and distributed shared memory models, From bounded to unbounded concurrency objects and back, The space complexity of long-lived and one-shot timestamp implementations, Locally checkable proofs, Fault-tolerant spanners, Adaptively secure broadcast, revisited, Scalable rational secret sharing, Analyzing consistency properties for fun and profit, Transforming worst-case optimal solutions for simultaneous tasks into all-case optimal solutions, Optimal-time adaptive strong renaming, with applications to counting, The round complexity of distributed sorting, A tight unconditional lower bound on distributed randomwalk computation, Minimum congestion mapping in a cloud, Conflict on a communication channel, Stability of a peer-to-peer communication system, Tight bounds on information dissemination in sparse mobile networks, Time-efficient randomized multiple-message broadcast in radio networks, Faster information dissemination in dynamic networks via network coding, Towards self-stabilizing blockchain, reconstructing totally erased blockchain, Byzantine preferential voting, Algorand: a secure and efficient distributed ledger, A Paxos based algorithm to minimize the overhead of process recovery in consensus, Accuracy of Message Counting Abstraction in Fault-Tolerant Distributed Algorithms, Efficient fully secure computation via distributed zero-knowledge proofs, Round-efficient Byzantine agreement and multi-party computation with asynchronous fallback, On the communication efficiency of statistically secure asynchronous MPC with optimal resilience, Revising the Membrane Computing Model for Byzantine Agreement, Computational aspects of uncertainty profiles and angel-daemon games, Functional diagnosis of information transmission in computer systems with unknown initial information, Self-stabilizing defeat status computation: dealing with conflict management in multi-agent systems, Secure Message Transmission by Public Discussion: A Brief Survey, Optimistically tuning synchronous Byzantine consensus: another win for null messages, Player-Centric Byzantine Agreement, Asynchronous Byzantine agreement with optimal resilience, Efficient algorithms for anonymous Byzantine agreement, Distributed system diagnosis of Byzantine failures in partially connected multicomputer systems, Computer science and decision theory, Lower bounds for weak Byzantine agreement, Quantum multi-valued Byzantine agreement based on d-dimensional entangled states, Characterization of Secure Multiparty Computation Without Broadcast, Global synchronization and consensus using beeps in a fault-prone multiple access channel, An Axiomatic Approach to Computing the Connectivity of Synchronous and Asynchronous Systems, Consensus vs. Broadcast in Communication Networks with Arbitrary Mobile Omission Faults, The Contest between Simplicity and Efficiency in Asynchronous Byzantine Agreement, Byzantine Agreement Using Partial Authentication, Beyond Nash Equilibrium: Solution Concepts for the 21st Century, Probabilistic Termination and Composability of Cryptographic Protocols, Probabilistic termination and composability of cryptographic protocols, Efficient constant-round multi-party computation combining BMR and SPDZ, Defending non-Bayesian learning against adversarial attacks, Recent Results on Fault-Tolerant Consensus in Message-Passing Networks, Authenticated Byzantine Generals in Dual Failure Model, Quantum Byzantine agreement with tripartite entangled states, Contention-related crash failures: definitions, agreement algorithms, and impossibility results, The firing squad problem revisited, Computing (and Life) Is All about Tradeoffs, Xheal, A deterministic worst-case message complexity optimal solution for resource discovery, A characterization of oblivious message adversaries for which consensus is solvable, Practical quantum Byzantine protocol via nearly optimal entanglement resources, A Characterization of Dynamic Networks Where Consensus Is Solvable, A Deterministic Worst-Case Message Complexity Optimal Solution for Resource Discovery, Quantum Byzantine agreement for any number of dishonest parties, Synchronization modulo \(P\) in dynamic networks, The epigenetic consensus problem, Efficient constructions for almost-everywhere secure computation, On the possibility and impossibility of achieving clock synchronization, Easy impossibility proofs for distributed consensus problems, Serializability theory for replicated databases, Invited talk: Resilient distributed algorithms, Agreement under faulty interfaces, Information-theoretic broadcast with dishonest majority for long messages, Stopping times of distributed consensus protocols: a probabilistic analysis, Asynchronous byzantine agreement protocols, Managed agreement: generalizing two fundamental distributed agreement problems, Combination of clock-state and clock-rate correction in fault-tolerant distributed systems, Programming simultaneous actions using common knowledge, Robust gossiping with an application to consensus, A distributed leader election algorithm in crash-recovery and omissive systems, The complexity of reasoning about knowledge and time. I: Lower bounds, The perfectly synchronized round-based model of distributed computing, Optimal resilient threshold GQ signatures, Clone wars: distributed detection of clone attacks in mobile WSNs, Mutual information reconciliation in non-fully connected heterogeneous multicomputer computational systems, Byzantine agreement with homonyms in synchronous systems, Randomized \(k\)-set agreement in crash-prone and Byzantine asynchronous systems, Extracting complexes that ensure sufficient structural conditions for system mutual informational agreement in multicomplex systems, Synchronous counting and computational algorithm design, A modular approach to shared-memory consensus, with applications to the probabilistic-write model, Tight bound on mobile Byzantine agreement, Stability of long-lived consensus., No double discount: condition-based simultaneity yields limited gain, Almost-everywhere secure computation with edge corruptions, On the complexity of asynchronous agreement against powerful adversaries, Communication-efficient and crash-quiescent omega with unknown membership, Communication-efficient failure detection and consensus in omission environments, Fairness versus guaranteed output delivery in secure multiparty computation, Consensus in the presence of mortal Byzantine faulty processes, Secure message transmission in asynchronous networks, A computer scientist looks at game theory., Renaming in synchronous message passing systems with Byzantine failures, The best of both worlds: Guaranteeing termination in fast randomized Byzantine agreement protocols, A new solution for the Byzantine agreement problem, Knowledge and common knowledge in a Byzantine environment: Crash failures, Verifiable secret sharing in a total of three rounds, The robustness of stability under link and node failures, A lower bound for the time to assure interactive consistency, On the impact of link faults on Byzantine agreement, A simple characterization of asynchronous computations, Randomization can be a healer: consensus with dynamic omission failures, Two distributed problems involving Byzantine processes, Modular construction of a Byzantine agreement protocol with optimal message bit complexity, Shifting gears: Changing algorithms on the fly to expedite Byzantine agreement, Fast and compact self-stabilizing verification, computation, and fault detection of an MST, A simple voting protocol on quantum blockchain, The complexity of almost-optimal simultaneous coordination, On the message complexity of binary Byzantine agreement under crash failures, Efficient parallel algorithms can be made robust, A self-adjusting algorithm for Byzantine agreement, Distributed sampled-data control of nonholonomic multi-robot systems with proximity networks, The computational structure of progress conditions and shared objects, A full proof of the BGW protocol for perfectly secure multiparty computation, The computability of relaxed data structures: queues and stacks as examples, Characterization of secure multiparty computation without broadcast, Machine checked proofs of the design of a fault-tolerant circuit, Consensus using omega in asynchronous systems with unknown membership and degenerative Byzantine failures, Reaching approximate Byzantine consensus with multi-hop communication, Consensus when all processes may be Byzantine for some time, Fork sequential consistency is blocking, On the logical unsolvability of the Gettier problem, A simple Byzantine generals protocol, Fault tolerance in large games, Continuous consensus with ambiguous failures, Strongly terminating early-stopping \(k\)-set agreement in synchronous systems with general omission failures, P systems and the Byzantine agreement, A simple and communication-efficient omega algorithm in the crash-recovery model, Yet another compiler for active security or: efficient MPC over arbitrary rings, Refined quorum systems, Toward an algebraic theory of systems, Higher-order quantifier elimination, counter simulations and fault-tolerant systems, On the completeness of bounded model checking for threshold-based distributed algorithms: reachability, Round-preserving parallel composition of probabilistic-termination cryptographic protocols, Implementing the Omega failure detector in the crash-recovery failure model, On expected constant-round protocols for Byzantine agreement, Rapid almost-complete broadcasting in faulty networks, Low-cost clock synchronization, Consensus algorithms with one-bit messages, Models of closed multimachine computer systems with transient-fault-tolerance and fault-tolerance on the basis of replication under byzantine faults, A simple proof of a simple consensus algorithm, A flexible formal framework for masking/demasking faults, Consensus in Byzantine asynchronous systems, Consensus under unreliable transmission, Communication-efficient randomized consensus, Revisiting the PAXOS algorithm, Using knowledge to optimally achieve coordination in distributed systems, Reliable communication over partially authenticated networks, Wait-free implementations in message-passing systems, On the round complexity of Byzantine agreement without initial set-up, The customizable fault/error model for dependable distributed systems., Byzantine-resistant total ordering algorithms., Computing in totally anonymous asynchronous shared memory systems, How to cope with faulty processors in a completely connected network of communicating processors, Efficient agreement using fault diagnosis., Necessary and sufficient conditions for broadcast consensus protocols., Fast consensus in networks of bounded degree., A formal model of asynchronous communication and its use in mechanically verifying a biphase mark protocol
