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

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

2 ASAP - As Scalable As Possible: foundations of large scale dynamic distributed systems
IRISA-D1 - SYSTÈMES LARGE ÉCHELLE, Inria Rennes – Bretagne Atlantique
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.)
Keywords :
Document type :
Reports
Domain :

Cited literature [20 references]

https://hal.inria.fr/inria-00139305
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

PI-1837.pdf
Files produced by the author(s)

### Identifiers

• HAL Id : inria-00139305, version 1

### Citation

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