Armando Castañeda
Sergio Rajsbaum
Abstract
In the renaming task, n+1 processes start with unique input names from a large space and must choose unique output names taken from a smaller name space, 0,1,…, K. To rule out trivial solutions, a protocol must be anonymous: the value chosen by a process can depend on its input name and on the execution, but not on the specific process ID.
Attiya et al. [1990] showed that renaming has a wait-free solution when K≥ 2n. Several algebraic topology proofs of a lower bound stating that no such protocol exists when K < 2n have been published. In a companion article, we present the first completely combinatorial renaming lower bound proof stating if n + 1 is a primer power, then renaming is not wait-free solvable when K < 2n. In this article, we show that if n + 1 is not a primer power, then there exists a wait-free renaming protocol for K = 2n−1. Therefore the renaming lower bound for K < 2n is incorrect. More precisely, our main theorem states that there exists a wait-free renaming protocol for K < 2n if and only if n + 1 is not a prime power. We prove this result using the known equivalence of K-renaming for K = 2n − 1 and the weak symmetry breaking task: processes have no input values and the output values are 0 or 1, and it is required that in every execution in which all processes participate, at least one process decides 1 and at least one process decides 0.
- Attiya, H., Bar-Noy, A., and Dolev, D. 1995. Sharing memory robustly in message-passage systems. J. ACM 42, 1, 124--142. Google Scholar
Digital Library
- Attiya, H., Bar-Noy, A., Dolev, D., Peleg, D., and Reischuck, R. 1990. Renaming in an asynchronous environment. J. ACM 37, 3, 524--548. Google ScholarDigital Library
- Attiya, H. and Rajsbaum, S. 2002. The combinatorial structure of wait-free solvable tasks. SIAM J. Comput. 31, 4, 1286--1313. Google ScholarDigital Library
- Attiya, H. and Welch, J. 1998. Distributed Computing: Fundamentals, Simulations and Advanced Topics. McGraw-Hill, New York. Google ScholarDigital Library
- Borowsky, E. and Gafni, E. 1993a. Generalized FLP impossibility result for t-resilient asynchronous computations. In Proceedings of the 25th Annual ACM Symposium on Theory of Computing. ACM, New York, 91--100. Google ScholarDigital Library
- Borowsky, E. and Gafni, E. 1993b. Immediate atomic snapshots and fast renaming. In Proceedings of the 12th Annual ACM Symposium on Principles on Distributed Computing. ACM, New York, 41--51. Google ScholarDigital Library
- Borowsky, E. and Gafni, E. 1997. A simple algorithmically reasoned characterization of wait-free computations. In Proceedings of the 16th Annual ACM Symposium on Principles on Distributed Computing. ACM, New York, 189--198. Google ScholarDigital Library
- Castañeda, A., Herlihy, M., and Rajsbaum, S. 2011. An equivariance theorem with applications to renaming. Tech rep. #1975, IRISA, Université de Rennes 1 (France), http://hal.inria.fr/docs/00/58/61/90/PDF/PI-1975.pdf.Google Scholar
- Castaneda, A. and Rajsbaum, S. 2008. New combinatorial topology upper and lower bounds for renaming. In Proceedings of the 27th Annual ACM Symposium on Principles on Distrib. Comput. ACM, New York, 295--304. Google ScholarDigital Library
- Casta&tildn;eda, A. and Rajsbaum, S. 2010. New combinatorial topology upper and lower bounds for renaming: The lower bound. Distrib. Comput. 25, 5, 287--301.Google ScholarDigital Library
- Chaudhuri, S. 1990. Agreement is harder than consensus: Set consensus problems in totally asynchronous systems. In Proceedings of the 9th Annual ACM Symposium on Principles of Distrib. Comput. ACM, New York, 311--234. Google ScholarDigital Library
- Dence, J. B. and Dence, T. 1999. Elements of the Theory of Numbers. Academic Press.Google Scholar
- Dickson, L. E. 2005. History of the Theory of Numbers---I. Dover Books on Mathematics.Google Scholar
- Dieck, T. 1987. Transformation Groups. Gruiter Studies in Mathematics.Google Scholar
- Gafni, E. 2008. The 0-1 exclusion families of tasks. In Proceedings of the 12th International Conference on Principles of Distributed Systems. Springer, New York, 246--258. Google ScholarDigital Library
- Gafni, E., Mostéfaoui, A., Raynal, M., and Travers, C. 2009. From adaptive renaming to set agreement. Theoret. Comput. Sci. 410, 14, 1328--1335. Google ScholarDigital Library
- Gafni, E., Rajsbaum, S., and Herlihy, M. 2006. Subconsensus tasks: Renaming is weaker than set agreement. In Proceedings of the 20th International Symposium on Distributed Computing. Springer, New York, 329--338. Google ScholarDigital Library
- Hardy, G. H. 1999. Ramanujan: Twelve Lectures on Subjects Suggested by His Life and Work. AMS Chelsea Publishing.Google Scholar
- Havlicek, J. 2004. A note on the homotopy type of wait-free atomic snapshot protocol complexes. SIAM J. Comput. 33, 5, 1215--1222. Google ScholarDigital Library
- Herlihy, M. and Rajsbaum, S. 2000. Algebraic spans. Math. Struct. Comput. Sci. 10, 4, 549--573. Google ScholarDigital Library
- Herlihy, M. and Shavit, N. 1993. The asynchronous computability theorem for t-resilient tasks. In Proceedings of the 25th ACM Symposium on the Theory of Computing. ACM, New York, 111--120. Google ScholarDigital Library
- Herlihy, M. and Shavit, N. 1999. The topological structure of asynchronous computability. J. ACM 46, 6, 858--923. Google ScholarDigital Library
- Hopf, H. 1927. Abbildungklassen n-dimensionaler mannigfaltigkeiten. Math. Ann. 96, 209--224.Google ScholarCross Ref
- Munkres, J. R. 1993. Elements of Algebraic Topology. Addison-Wesley, Reading.Google Scholar
- Saks, M. and Zaharoglou, F. 2000. Wait-free k-set agreement is impossible: The topology of public knowledge. SIAM J. Comput. 29, 5, 1449--1483. Google ScholarDigital Library
Index Terms
- New combinatorial topology bounds for renaming: The upper bound
Recommendations
New combinatorial topology bounds for renaming: the lower bound
In the renaming task n + 1 processes start with unique input names taken from a large space and must choose unique output names taken from a smaller name space, 0, 1, . . . , K. To rule out trivial solutions, a protocol must be anonymous: the value ...
New combinatorial topology upper and lower bounds for renaming
PODC '08: Proceedings of the twenty-seventh ACM symposium on Principles of distributed computingIn the renaming task n+1 processes start with unique input names from a large space and must choose unique output names taken from a smaller name space, namely 0,1,...,K. To rule out trivial solutions, a protocol must be anonymous: the value chosen by a ...
Bounds on the Step and Namespace Complexity of Renaming
The $M(n)$-renaming task requires $n+1$ processes, each starting with a unique input name (from an arbitrary large range), to coordinate the choice of new output names from a range of size $M(n)$. It is known that $2n$-renaming can be solved if and only if $n+...
Comments