Wait-free k-set agreement is impossible

DOI10.1145/167088.167122MaRDI QIDQ5248476zbMATH OpenOpenAlexFDO

Authors Fotios Zaharoglou, Michael Saks

Publication date 7 May 2015

Published in Proceedings of the twenty-fifth annual ACM symposium on Theory of computing - STOC '93 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/167088.167122

Mathematics Subject Classification ID

Distributed systems (68M14) Reliability, testing and fault tolerance of networks and computer systems (68M15) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Cited in

(26)

• Classifying rendezvous tasks of arbitrary dimension
• An algorithmic approach to the asynchronous computability theorem
• Geometric and combinatorial views on asynchronous computability
• A classification of wait-free loop agreement tasks
• A computationally intractable problem on simplicial complexes
• Renaming and the weakest family of failure detectors
• The evolution of non-degenerate and degenerate rendezvous tasks
• On the weakest failure detector ever
• Closed schedulers: a novel technique for analyzing asynchronous protocols
• The BG distributed simulation algorithm
• An adaptive collect algorithm with applications
• An Introduction to the Topological Theory of Distributed Computing with Safe-consensus
• A Sound Foundation for the Topological Approach to Task Solvability
• A topological perspective on distributed network algorithms
• Communication pattern logic: epistemic and topological views
• Wait-free computing
• The combinatorial structure of wait-free solvable tasks (extended abstract)
• On set consensus numbers
• Communication pattern models: an extension of action models for dynamic-network distributed systems
• The topology of randomized symmetry-breaking distributed computing
• Optimal resilience in systems that mix shared memory and message passing
• A speedup theorem for asynchronous computation with applications to consensus and approximate agreement
• Semitopology: a topological approach to decentralized collaborative action
• Brief announcement: No broadcast abstraction characterizes k-set-agreement in message-passing systems
• The complexity of full-information iterated protocols
• Iterated chromatic subdivisions are collapsible

This page was built for publication: Wait-free k-set agreement is impossible

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5248476)