The BG distributed simulation algorithm

DOI10.1007/PL00008933zbMath1448.68467MaRDI QIDQ5138357

Eli Gafni, Sergio Rajsbaum, Elizabeth Borowsky, Nancy A. Lynch

Publication date: 3 December 2020

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

zbMATH Keywords

simulationfault-tolerancedistributed computingconsensusset-agreement

Mathematics Subject Classification ID

Distributed systems (68M14) Reliability, testing and fault tolerance of networks and computer systems (68M15) Distributed algorithms (68W15)

Related Items (21)

Collapsibility of read/write models using discrete Morse theory ⋮ Unnamed Item ⋮ From wait-free to arbitrary concurrent solo executions in colorless distributed computing ⋮ Distributed computability: relating \(k\)-immediate snapshot and \(x\)-set agreement ⋮ Power and limits of distributed computing shared memory models ⋮ Tasks in modular proofs of concurrent algorithms ⋮ The solvability of consensus in iterated models extended with safe-consensus ⋮ Locality and checkability in wait-free computing ⋮ Tasks in modular proofs of concurrent algorithms ⋮ Hundreds of impossibility results for distributed computing ⋮ Condition-based consensus solvability: a hierarchy of conditions and efficient protocols ⋮ A closer look at fault tolerance ⋮ Anonymous obstruction-free \((n,k)\)-set agreement with \(n-k+1\) atomic read/write registers ⋮ The topology of look-compute-move robot wait-free algorithms with hard termination ⋮ Generalized Symmetry Breaking Tasks and Nondeterminism in Concurrent Objects ⋮ Revisionist simulations: a new approach to proving space lower bounds ⋮ Untangling Partial Agreement: Iterated x-consensus Simulations ⋮ Wait-freedom with advice ⋮ Wait-free approximate agreement on graphs ⋮ The topology of local computing in networks ⋮ Wait-free approximate agreement on graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• More \(choices\) allow more \(faults\): Set consensus problems in totally asynchronous systems
• Computer science today. Recent trends and developments
• Renaming in an asynchronous environment
• A combinatorial characterization of the distributed 1-solvable tasks
• Impossibility of distributed consensus with one faulty process
• Generalized FLP impossibility result for t-resilient asynchronous computations
• Wait-free k-set agreement is impossible
• The asynchronous computability theorem for t-resilient tasks
• Set consensus using arbitrary objects (preliminary version)
• Wait-freedom vs. t-resiliency and the robustness of wait-free hierarchies (extended abstract)

This page was built for publication: The BG distributed simulation algorithm