Skip to Main content Skip to Navigation
Conference papers

Making Local Algorithms Wait-Free: The Case of Ring Coloring

Abstract : When considering distributed computing, reliable message-passing synchronous systems on the one side, and asynchronous failure-prone shared-memory systems on tyhe other side, remain two quite independently studied ends of the reliability/asynchrony spectrum. The concept of locality of a computation is central to the first one, while the concept of wait-freedom is central to the second one. The paper proposes a new DECOUPLED model in an attempt to reconcile these two worlds. It consists of a synchronous and reliable communication graph of n nodes, and on top a set of asynchronous crash-prone processes, each attached to a communication node. To illustrate the DECOUPLED model, the paper presents an asynchronous 3-coloring algorithm for the processes of a ring. From the processes point of view, the algorithm is wait-free. From a locality point of view, each process uses information only from processes at distance O(log∗n)O(log∗⁡n) from it. This local wait-free algorithm is based on an extension of the classical Cole and Vishkin vertex coloring algorithm in which the processes are not required to start simultaneously.
Keywords : wait free local
Document type :
Conference papers
Complete list of metadata
Contributor : Carole Delporte-Gallet Connect in order to contact the contributor
Submitted on : Wednesday, December 14, 2016 - 3:42:00 PM
Last modification on : Friday, January 21, 2022 - 3:18:36 AM



Armando Castañeda, Carole Delporte-Gallet, Hugues Fauconnier, Sergio Rajsbaum, Michel Raynal. Making Local Algorithms Wait-Free: The Case of Ring Coloring. SSS, Nov 2016, Lyon, France. pp.16, ⟨10.1007/978-3-319-49259-9_9⟩. ⟨hal-01416522⟩



Les métriques sont temporairement indisponibles