LIPIcs.DISC.2019.21.pdf
- Filesize: 0.64 MB
- 16 pages
Document
Wait-Free Solvability of Equality Negation Tasks
Authors
-
Part of:
Volume:
33rd International Symposium on Distributed Computing (DISC 2019)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Symposium on Distributed Computing (DISC) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2019-10-08
Cite AsGet BibTex
Éric Goubault, Marijana Lazić, Jérémy Ledent, and Sergio Rajsbaum. Wait-Free Solvability of Equality Negation Tasks. In 33rd International Symposium on Distributed Computing (DISC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 146, pp. 21:1-21:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.DISC.2019.21
https://doi.org/10.4230/LIPIcs.DISC.2019.21
Abstract
We introduce a family of tasks for n processes, as a generalization of the two process equality negation task of Lo and Hadzilacos (SICOMP 2000). Each process starts the computation with a private input value taken from a finite set of possible inputs. After communicating with the other processes using immediate snapshots, the process must decide on a binary output value, 0 or 1. The specification of the task is the following: in an execution, if the set of input values is large enough, the processes should agree on the same output; if the set of inputs is small enough, the processes should disagree; and in-between these two cases, any output is allowed. Formally, this specification depends on two threshold parameters k and l, with k<l, indicating when the cardinality of the set of inputs becomes "small" or "large", respectively. We study the solvability of this task depending on those two parameters. First, we show that the task is solvable whenever k+2 <= l. For the remaining cases (l = k+1), we use various combinatorial topology techniques to obtain two impossibility results: the task is unsolvable if either k <= n/2 or n-k is odd. The remaining cases are still open.
Subject Classification
ACM Subject Classification
- Theory of computation → Concurrency
Keywords
- Equality negation
- distributed computability
- combinatorial topology
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- H. Attiya and S. Rajsbaum. The Combinatorial Structure of Wait-Free Solvable Tasks. SIAM J. Comput., 31(4):1286-1313, 2002. URL: https://doi.org/10.1137/S0097539797330689.
- E. Borowsky, E. Gafni, N. Lynch, and S. Rajsbaum. The BG Distributed Simulation Algorithm. Distrib. Comput., 14(3):127-146, October 2001. URL: https://doi.org/10.1007/PL00008933.
- Armando Castañeda, Maurice Herlihy, and Sergio Rajsbaum. An Equivariance Theorem with Applications to Renaming. Algorithmica, 70(2):171-194, October 2014. URL: https://doi.org/10.1007/s00453-013-9855-3.
- Armando Castañeda, Damien Imbs, Sergio Rajsbaum, and Michel Raynal. Generalized Symmetry Breaking Tasks and Nondeterminism in Concurrent Objects. SIAM J. Comput., 45(2):379-414, 2016. URL: https://doi.org/10.1137/130936828.
- Armando Castañeda and Sergio Rajsbaum. New combinatorial topology bounds for renaming: the lower bound. Distributed Computing, 22(5):287-301, August 2010. URL: https://doi.org/10.1007/s00446-010-0108-2.
- Benny Chor, Amos Israeli, and Ming Li. On Processor Coordination Using Asynchronous Hardware. In Proceedings of the Sixth Annual ACM Symposium on Principles of Distributed Computing, PODC '87, pages 86-97, New York, NY, USA, 1987. ACM. URL: https://doi.org/10.1145/41840.41848.
- Ky Fan. Simplicial maps from an orientable n-pseudomanifold into S^m with the octahedral triangulation. Journal of Combinatorial Theory, 2(4):588-602, 1967. URL: https://doi.org/10.1016/S0021-9800(67)80063-2.
-
Éric Goubault, Marijana Lazić, Jérémy Ledent, and Sergio Rajsbaum. A Dynamic Epistemic Logic analysis of the Equality Negation task. Dynamic Logic: New Trends and Applications, DaLi 2019, to appear in Springer LNCS.
- Michael Henle. A Combinatorial Introduction to Topology. Dover, 1983. URL: https://doi.org/10.2307/1574757.
- Maurice Herlihy. Wait-free Synchronization. ACM Trans. Program. Lang. Syst., 13(1):124-149, January 1991. URL: https://doi.org/10.1145/114005.102808.
-
Maurice Herlihy, Dmitry Kozlov, and Sergio Rajsbaum. Distributed Computing Through Combinatorial Topology. Morgan Kaufmann, 2013.
- Maurice Herlihy and Nir Shavit. The topological structure of asynchronous computability. J. ACM, 46(6):858-923, 1999. URL: https://doi.org/10.1145/331524.331529.
- Prasad Jayanti. On the Robustness of Herlihy’s Hierarchy. In Proceedings of the Twelfth Annual ACM Symposium on Principles of Distributed Computing, PODC '93, pages 145-157, New York, NY, USA, 1993. ACM. URL: https://doi.org/10.1145/164051.164070.
- Wai-Kau Lo and Vassos Hadzilacos. All of Us Are Smarter than Any of Us: Nondeterministic Wait-Free Hierarchies Are Not Robust. SIAM J. Comput., 30(3):689-728, 2000. URL: https://doi.org/10.1137/S0097539798335766.
-
Hosame H Abu-Amara Michael C Loui. Memory requirements for agreement among unreliable asynchronous processes. In Advances in Computing research, pages 163-183, Greenwich, CT, 1987. JAI Press.
- Sergio Rajsbaum, Michel Raynal, and Panagiota Fatourou. An Introductory Tutorial to Concurrency-Related Distributed Recursion. Bulletin of the EATCS, 111, 2013. URL: http://eatcs.org/beatcs/index.php/beatcs/article/view/223.