Skip to Main content Skip to Navigation
Reports

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

https://hal.inria.fr/inria-00139305
Contributor : Anne Jaigu <>
Submitted on : Friday, March 30, 2007 - 11:17:55 AM
Last modification on : Thursday, January 7, 2021 - 4:17:26 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⟩

Share

Metrics

Record views

551

Files downloads

223