On the road to the weakest failure detector for \(k\)-set agreement in message-passing systems

DOI10.1016/j.tcs.2010.11.007zbMath1222.68117OpenAlexW1593125439MaRDI QIDQ555307

François Bonnet, Michel Raynal

Publication date: 22 July 2011

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2010.11.007

zbMATH Keywords

reductionasynchronous systemswait-freedom\(k\)-set agreementmessage-passing systemsfailure detectorseventual leadersquorums

Mathematics Subject Classification ID

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

Related Items

Gracefully degrading consensus and \(k\)-set agreement in directed dynamic networks ⋮ Simultaneous Consensus vs Set Agreement: A Message-Passing-Sensitive Hierarchy of Agreement Problems

Cites Work

• \(k\)-Arbiter: A safe and general scheme for \(h\)-out of-\(k\) mutual exclusion
• More \(choices\) allow more \(faults\): Set consensus problems in totally asynchronous systems
• Tight bounds for \(k\)-set agreement with limited-scope failure detectors
• Failure detectors as type boosters
• On the computability power and the robustness of set agreement-oriented failure detector classes
• Anti-Ω
• Sharing is harder than agreeing
• Tight bounds for k -set agreement
• The topological structure of asynchronous computability
• Weakening Failure Detectors for k-Set Agreement Via the Partition Approach
• The Weakest Failure Detector for Message Passing Set-Agreement
• Tight failure detection bounds on atomic object implementations
• The Disagreement Power of an Adversary
• Unreliable failure detectors for reliable distributed systems
• The weakest failure detector for solving consensus
• Wait-Free k-Set Agreement is Impossible: The Topology of Public Knowledge
• The weakest failure detector for solving k-set agreement
• k-set agreement with limited accuracy failure detectors
• Generalized FLP impossibility result for t-resilient asynchronous computations
• Failure detectors and the wait-free hierarchy (extended abstract)
• The weakest failure detectors to solve certain fundamental problems in distributed computing

This page was built for publication: On the road to the weakest failure detector for \(k\)-set agreement in message-passing systems