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 metadatas

https://hal.inria.fr/hal-01416522
Contributor : Carole Delporte-Gallet <>
Submitted on : Wednesday, December 14, 2016 - 3:42:00 PM
Last modification on : Friday, January 11, 2019 - 3:13:38 PM

Identifiers

  • HAL Id : hal-01416522, version 1

Citation

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. ⟨hal-01416522⟩

Share

Metrics

Record views

1222