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
Type de document :
Communication dans un congrès
SSS, Nov 2016, Lyon, France. LNCS, 10083, pp.16, 2016, Stabilization, Safety, and Security of Distributed Systems
Liste complète des métadonnées

https://hal.inria.fr/hal-01416522
Contributeur : Carole Delporte-Gallet <>
Soumis le : mercredi 14 décembre 2016 - 15:42:00
Dernière modification le : mercredi 16 mai 2018 - 11:23:14

Identifiants

  • 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. LNCS, 10083, pp.16, 2016, Stabilization, Safety, and Security of Distributed Systems. 〈hal-01416522〉

Partager

Métriques

Consultations de la notice

859