HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation

Test&Set, Adaptive Renaming and Set Agreement: a Guided Visit to Asynchronous Computability

Abstract : An important issue in fault-tolerant asynchronous computing is the respective power of an object type with respect to another object type. This question has received a lot of attention, mainly in the context of the consensus problem where a major advance has been the introduction of the consensus number notion that allows ranking the synchronization power of base object types (atomic registers, queues, test\&set objects, compare\&swap objects, etc.) with respect to the consensus problem. This has given rise to the well-known Herlihy's hierarchy. Due to its very definition, the consensus number notion is irrelevant for studying the respective power of object types that are too weak to solve consensus for an arbitrary number of processes (these objects are usually called subconsensus objects). Considering an asynchonous system made up of $n$ processes prone to crash, this paper addresses the power of such object types, namely, the $k$-test\&set object type, the $k$-set agreement object type, and the adaptive $M$-renaming object type for $M=2p-\lceil\frac{p}{k}\rceil$ and $M= \min(2p-1,p+k-1)$, where $p\leq n$ is the number of processes hat want to acquire a new name. It investigates their respective power stating the necessary and sufficient conditions to build objects of any of these types from objects of any of the other types. More precisely, the paper shows that (1) these object types define a strict hierarchy when $k\neq 1, n-1$, (2) they all are equivalent when $k=n-1$, and (3) they all are equivalent except $k$-set agreement that is stronger when $k=1\neq n-1$ (a side effect of these results is that that the consensus number of the renaming problem is 2.)
Complete list of metadata

Cited literature [20 references]  Display  Hide  Download

Contributor : Anne Jaigu Connect in order to contact the contributor
Submitted on : Friday, March 30, 2007 - 11:17:55 AM
Last modification on : Thursday, January 20, 2022 - 4:19:57 PM
Long-term archiving on: : Tuesday, April 6, 2010 - 10:30:52 PM


Files produced by the author(s)


  • HAL Id : inria-00139305, version 1


Eli Gafni, Michel Raynal, Corentin Travers. Test&Set, Adaptive Renaming and Set Agreement: a Guided Visit to Asynchronous Computability. [Research Report] PI 1837, 2007, pp.19. ⟨inria-00139305⟩



Record views


Files downloads