The weakest failure detector for solving consensus
From MaRDI portal
Publication:4371681
DOI10.1145/234533.234549zbMath0885.68022OpenAlexW2077240273WikidataQ56571313 ScholiaQ56571313MaRDI QIDQ4371681
Sam Toueg, Vassos Hadzilacos, Tushar Deepak Chandra
Publication date: 22 January 1998
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://hdl.handle.net/1813/6208
Computer system organization (68M99) Reliability, testing and fault tolerance of networks and computer systems (68M15)
Related Items
Consensus in Data Management: From Distributed Commit to Blockchain ⋮ Abstractions for fault-tolerant global computing ⋮ Open consensus ⋮ From binary consensus to multivalued consensus in asynchronous message-passing systems ⋮ Byzantine disk paxos: optimal resilience with Byzantine shared memory ⋮ Practically-self-stabilizing virtual synchrony ⋮ The Heard-Of model: computing in distributed systems with benign faults ⋮ On the computability power and the robustness of set agreement-oriented failure detector classes ⋮ On implementing omega in systems with weak reliability and synchrony assumptions ⋮ On the weakest failure detector ever ⋮ Implementing unreliable failure detectors with unknown membership ⋮ Managed agreement: generalizing two fundamental distributed agreement problems ⋮ A timing assumption and two \(t\)-resilient protocols for Implementing an eventual leader service in asynchronous shared memory systems ⋮ Communication Patterns and Input Patterns in Distributed Computing ⋮ A weakest failure detector-based asynchronous consensus protocol for \(f<n\) ⋮ A distributed leader election algorithm in crash-recovery and omissive systems ⋮ Anonymous asynchronous systems: the case of failure detectors ⋮ In search of lost time ⋮ The weakest failure detector to implement a register in asynchronous systems with hybrid communication ⋮ Power and limits of distributed computing shared memory models ⋮ Agreeing within a few writes ⋮ Fault tolerant network constructors ⋮ A Paxos based algorithm to minimize the overhead of process recovery in consensus ⋮ Partial synchrony based on set timeliness ⋮ Failure detectors encapsulate fairness ⋮ Renaming and the weakest family of failure detectors ⋮ Automated test case generation for the paxos single-decree protocol using a coloured Petri net model ⋮ Efficient fault-tolerant collision-free data aggregation scheduling for wireless sensor networks ⋮ The Iterated Restricted Immediate Snapshot Model ⋮ Communication-efficient and crash-quiescent omega with unknown membership ⋮ Consensus in the presence of mortal Byzantine faulty processes ⋮ About informatics, distributed computing, and our job: a personal view ⋮ Self-stabilizing indulgent zero-degrading binary consensus ⋮ Using asynchrony and zero degradation to speed up indulgent consensus protocols ⋮ A knowledge-theoretic analysis of uniform distributed coordination and failure detectors ⋮ Active disk Paxos with infinitely many processes ⋮ Tight bounds for \(k\)-set agreement with limited-scope failure detectors ⋮ On the importance of having an identity or, is consensus really universal? ⋮ The weakest failure detector to solve nonuniform consensus ⋮ Booting clock synchronization in partially synchronous systems with hybrid process and link failures ⋮ Failure detectors as type boosters ⋮ The weakest failure detectors to boost obstruction-freedom ⋮ Low-latency atomic broadcast in the presence of contention ⋮ How to Solve Consensus in the Smallest Window of Synchrony ⋮ The Weakest Failure Detector for Message Passing Set-Agreement ⋮ Non-blocking atomic commit in asynchronous distributed systems with failure detectors ⋮ Communication-optimal eventually perfect failure detection in partially synchronous systems ⋮ Hundreds of impossibility results for distributed computing ⋮ Randomized protocols for asynchronous consensus ⋮ The disagreement power of an adversary ⋮ On set consensus numbers ⋮ The minimum information about failures for solving non-local tasks in message-passing systems ⋮ Distributed consensus, revisited ⋮ Multi-shot distributed transaction commit ⋮ Anonymous obstruction-free \((n,k)\)-set agreement with \(n-k+1\) atomic read/write registers ⋮ Gracefully degrading consensus and \(k\)-set agreement in directed dynamic networks ⋮ Consensus in anonymous asynchronous systems with crash-recovery and omission failures ⋮ What Can be Computed in a Distributed System? ⋮ Consensus using omega in asynchronous systems with unknown membership and degenerative Byzantine failures ⋮ The weakest failure detector for eventual consistency ⋮ The impossibility of boosting distributed service resilience ⋮ An impossibility about failure detectors in the iterated immediate snapshot model ⋮ Genuine atomic multicast in asynchronous distributed systems ⋮ On the road to the weakest failure detector for \(k\)-set agreement in message-passing systems ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Implementing uniform reliable broadcast with binary consensus in systems with fair-lossy links ⋮ A simple and communication-efficient omega algorithm in the crash-recovery model ⋮ A simple proof of the necessity of the failure detector \(\Sigma \) to implement an atomic register in asynchronous message-passing systems ⋮ Adaptive progress: a gracefully-degrading liveness property ⋮ Anti-\(\Omega \): the weakest failure detector for set agreement ⋮ The DHCP Failover Protocol: A Formal Perspective ⋮ Packet efficient implementation of the Omega failure detector ⋮ Wait-freedom with advice ⋮ Implementing the Omega failure detector in the crash-recovery failure model ⋮ Perfect failure detection with very few bits ⋮ From adaptive renaming to set agreement ⋮ Characterizing Consensus in the Heard-Of Model ⋮ Reducing \(\Omega\) to \(\lozenge\mathcal W\) ⋮ t-Resilient Immediate Snapshot Is Impossible ⋮ A flexible formal framework for masking/demasking faults ⋮ Consensus in Byzantine asynchronous systems ⋮ On modelling mobility ⋮ Revisiting the PAXOS algorithm ⋮ Contention-related crash failures: definitions, agreement algorithms, and impossibility results ⋮ Asynchronous bounded lifetime failure detectors ⋮ Using the heartbeat failure detector for quiescent reliable communication and consensus in partitionable networks ⋮ Fair Exchange Is Incomparable to Consensus ⋮ Unnamed Item ⋮ Byzantine-resistant total ordering algorithms. ⋮ Making Byzantine consensus live ⋮ Simultaneous Consensus vs Set Agreement: A Message-Passing-Sensitive Hierarchy of Agreement Problems ⋮ On the hardness of failure-sensitive agreement problems.
