The Heard-Of model: computing in distributed systems with benign faults

DOI10.1007/S00446-009-0084-6zbMath1267.68151OpenAlexW2155037890MaRDI QIDQ2377130

André Schiper, Bernadette Charron-Bost

Publication date: 28 June 2013

Published in: Distributed Computing (Search for Journal in Brave)

Full work available at URL: http://infoscience.epfl.ch/record/159550

zbMATH Keywords

computational modelconsensusbenign faultHO (Heard-Of) modeltransmission fault

Mathematics Subject Classification ID

Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85) Reliability, testing and fault tolerance of networks and computer systems (68M15)

Related Items (51)

Survey on Parameterized Verification with Threshold Automata and the Byzantine Model Checker ⋮ Derivation of Heard-of Predicates from Elementary Behavioral Patterns ⋮ Approximate Consensus in Highly Dynamic Networks: The Role of Averaging Algorithms ⋮ Valency-based consensus under message adversaries without limit-closure ⋮ Unnamed Item ⋮ Fault-tolerant multiparty session types ⋮ Synthesis of distributed algorithms with parameterized threshold guards ⋮ In search of lost time ⋮ The Firing Squad Problem Revisited. ⋮ Power and limits of distributed computing shared memory models ⋮ On the performance of a retransmission-based synchronizer ⋮ On the radius of nonsplit graphs and information dissemination in dynamic networks ⋮ Asynchronous Byzantine reliable broadcast with a message adversary ⋮ Communication pattern logic: epistemic and topological views ⋮ Cardinality constraints for arrays (decidability results and applications) ⋮ Blockchain in dynamic networks ⋮ Of choices, failures and asynchrony: the many faces of set agreement ⋮ Booting clock synchronization in partially synchronous systems with hybrid process and link failures ⋮ Unnamed Item ⋮ Continuous Consensus with Failures and Recoveries ⋮ Bosco: One-Step Byzantine Asynchronous Consensus ⋮ Using Bounded Model Checking to Verify Consensus Algorithms ⋮ Verification of consensus algorithms using satisfiability solving ⋮ 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 ⋮ Reachability in Parameterized Systems: All Flavors of Threshold Automata ⋮ MinMax algorithms for stabilizing consensus ⋮ Gracefully degrading consensus and \(k\)-set agreement in directed dynamic networks ⋮ Consensus in rooted dynamic networks with short-lived stability ⋮ A modular framework for verifying versatile distributed systems ⋮ Consensus when all processes may be Byzantine for some time ⋮ Synchronous consensus under hybrid process and link failures ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Higher-order quantifier elimination, counter simulations and fault-tolerant systems ⋮ Untangling Partial Agreement: Iterated x-consensus Simulations ⋮ A topological perspective on distributed network algorithms ⋮ Counting Constraints in Flat Array Fragments ⋮ Consensus vs. Broadcast in Communication Networks with Arbitrary Mobile Omission Faults ⋮ Characterizing Consensus in the Heard-Of Model ⋮ Fast Multidimensional Asymptotic and Approximate Consensus ⋮ A Reduction Theorem for the Verification of Round-Based Distributed Algorithms ⋮ The firing squad problem revisited ⋮ Unnamed Item ⋮ Back to the Coordinated Attack Problem ⋮ A characterization of oblivious message adversaries for which consensus is solvable ⋮ Making Byzantine consensus live ⋮ Synthesis in presence of dynamic links ⋮ A Characterization of Dynamic Networks Where Consensus Is Solvable ⋮ Synchronization modulo \(P\) in dynamic networks

Cites Work

• Unnamed Item
• Unnamed Item
• Computing input multiplicity in anonymous synchronous networks with dynamic faults
• Decomposition of distributed programs into communication-closed layers
• How processes learn
• A lower bound for the time to assure interactive consistency
• Broadcasting in a hypercube when some calls fail
• In search of lost time
• Fast Paxos
• Agreement in synchronous networks with ubiquitous faults
• A Layered Analysis of Consensus
• Unifying synchronous and asynchronous message-passing models
• Round-by-round fault detectors (extended abstract)
• Authenticated Algorithms for Byzantine Agreement
• Automatically increasing the fault-tolerance of distributed algorithms
• Early stopping in Byzantine agreement
• Using Bounded Model Checking to Verify Consensus Algorithms
• A Reduction Theorem for the Verification of Round-Based Distributed Algorithms
• Distributed agreement in the presence of processor and communication faults
• Impossibility of distributed consensus with one faulty process
• On the minimal synchronism needed for distributed consensus
• Reaching Agreement in the Presence of Faults
• The Byzantine generals strike again
• Unreliable failure detectors for reliable distributed systems
• The weakest failure detector for solving consensus
• Timeliness, failure-detectors, and consensus performance
• Distributed Computing
• Tolerating corrupted communication
• Broadcasting in synchronous networks with dynamic faults
• Structural Information and Communication Complexity

This page was built for publication: The Heard-Of model: computing in distributed systems with benign faults