|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
 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, namely 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. showed in 1990 that renaming has a wait-free solution when K<=2n. Several proofs of a lower bound stating that no such protocol exists when K<2n have been published. In this paper we prove that, for certain values of n, this lower bound is incorrect, exhibiting a wait-free renaming protocol for K=2n-1. For the other values of n, we present the first completely combinatorial lower bound proof stating that no such protocol exists when K<2n. More precisely, our main theorem states that there exists a wait-free renaming protocol for K<2n if and only if the set of integers (n+1 choose i+1) | 0 <= i <= floor((n-1)/2)} are relatively prime. Thus, such protocol exists for six processes, and not for less. The proof of the theorem uses combinatorial topology techniques, both for the lower bound and to derive the renaming protocol. REFERENCES
Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.
INDEX TERMS
Primary Classification:
General Terms:
Keywords:
The ACM Portal is published by the Association for Computing Machinery. Copyright © 2009 ACM, Inc.
Terms of Usage Privacy Policy Code of Ethics Contact Us Useful downloads:  Adobe Acrobat
 QuickTime
 Windows Media Player
 Real Player
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Pdf
F.0