Wait-free k-set agreement is impossible

DOI10.1145/167088.167122zbMath1310.68041MaRDI QIDQ5248476

Fotios Zaharoglou, Michael E. 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

68M20: Performance evaluation, queueing, and scheduling in the context of computer systems

68M14: Distributed systems

68M15: Reliability, testing and fault tolerance of networks and computer systems

Related Items

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 topological perspective on distributed network algorithms, A Sound Foundation for the Topological Approach to Task Solvability, Communication pattern logic: epistemic and topological views, Wait-free computing, On set consensus numbers, Iterated chromatic subdivisions are collapsible, 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