The complexity of early deciding set agreement: how can topology help? (English) Zbl 1339.68306
Goubault, Eric (ed.), Proceedings of the workshops on geometric and topological methods in concurrency theory (GETCO 2004, 2005, 2006), Amsterdam, The Netherlands 2004, San Francisco, CA, USA 2005, Bonn, Germany 2006. Amsterdam: Elsevier. Electronic Notes in Theoretical Computer Science 230, 71-78 (2009).
Summary: The aim of this paper is to pose a challenge to the experts of (algebraic) topology techniques. We present an early deciding algorithm that solves the set agreement problem, i.e., the problem which triggered research on applying topology techniques to distributed computing. We conjecture the algorithm to be optimal, and we discuss the need and challenges of applying topology techniques to prove the lower bound.
For the entire collection see [Zbl 1280.68025].
For the entire collection see [Zbl 1280.68025].
MSC:
| 68W15 | Distributed algorithms |
| 55P99 | Homotopy theory |
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
| 68Q25 | Analysis of algorithms and problem complexity |
References:
| [1] | B. Charron-Bost and A. Schiper. Uniform consensus harder than consensus. Technical Report DSC/2000/028, École Polytechnique Fédérale de Lausanne, Switzerland, May 2000; B. Charron-Bost and A. Schiper. Uniform consensus harder than consensus. Technical Report DSC/2000/028, École Polytechnique Fédérale de Lausanne, Switzerland, May 2000 · Zbl 1078.68157 |
| [2] | Chaudhuri, S., More choices allow more faults: set consensus problems in totally asynchronous systems, Information and Computation, 105, 1, 132-158 (July 1993) · Zbl 0776.68016 |
| [3] | Chaudhuri, S.; Herlihy, M.; Lynch, N. A.; Tuttle, M. R., Tight bounds for \(k\)-set agreement, Journal of the ACM, 47, 5, 912-943 (2000) · Zbl 1320.68034 |
| [4] | Fischer, M. J.; Lynch, N. A.; Paterson, M. S., Impossibility of distributed consensus with one faulty process, Journal of the ACM, 32, 2, 374-382 (1985) · Zbl 0629.68027 |
| [5] | E. Gafni, R. Guerraoui, and B. Pochon. From a static impossibility to an adaptive lower bound: the complexity of early deciding set agreement. In Proceedings of the \(37^{th} \); E. Gafni, R. Guerraoui, and B. Pochon. From a static impossibility to an adaptive lower bound: the complexity of early deciding set agreement. In Proceedings of the \(37^{th} \) · Zbl 1192.68846 |
| [6] | M. Herlihy, S. Rajsbaum, and M. Tuttle. Unifying synchronous and asynchronous message-passing models. In Proceedings of the \(17^{th} \); M. Herlihy, S. Rajsbaum, and M. Tuttle. Unifying synchronous and asynchronous message-passing models. In Proceedings of the \(17^{th} \) · Zbl 1333.68061 |
| [7] | Herlihy, M.; Shavit, N., The topological structure of asynchronous computability, Journal of the ACM, 46, 6, 858-923 (1999) · Zbl 1161.68469 |
| [8] | I. Keidar and S. Rajsbaum. On the cost of fault-tolerant consensus when there are no faults – a tutorial. Technical report, MIT Technical Report MIT-LCS-TR-821, 2001. (Preliminary version in SIGACT News, Distributed Computing Column, 32(2):45-63, 2001); I. Keidar and S. Rajsbaum. On the cost of fault-tolerant consensus when there are no faults – a tutorial. Technical report, MIT Technical Report MIT-LCS-TR-821, 2001. (Preliminary version in SIGACT News, Distributed Computing Column, 32(2):45-63, 2001) |
| [9] | Lynch, N. A., Distributed Algorithms (1996), Morgan-Kaufmann · Zbl 0877.68061 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
