Wait-freedom and Locality are not Incompatible (with Distributed Ring Coloring as an Example)

Abstract : In the world of message-passing distributed computing, reliable synchronous systems and asyn-chronous failure-prone systems lie at the two 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. This paper is an attempt to reconcile these two extreme worlds, and benefit from both of them. To this end, it first proposes a new distributed computing model, where (differently from the two previous ones) processing and communication are decoupled. The communication component (made up of n nodes) is considered as reliable and synchronous, while the processing component (composed of n processes, each attached to a communication node) is asyn-chronous and any number of its processes may suffer crash failures. To illustrate the benefit of this model, the paper presents an asynchronous algorithm that, assuming a ring communication component , colors the processes with at most three colors. From a process crash failure point of view, this algorithm is wait-free. From a locality point of view, each process needs information only from processes at distance O(log * n) from it. This local wait-free algorithm is made up of a communication phase followed by a purely local simulation (by each process) of an extended version of Cole and Vishkin's vertex coloring algorithm (this extension does not require the processes to start simultaneously). This new communication/processing decoupled model seems to offer a promising approach for distributed computing.
Type de document :
Pré-publication, Document de travail
Liste complète des métadonnées

Littérature citée [26 références]  Voir  Masquer  Télécharger

Contributeur : Michel Raynal <>
Soumis le : lundi 1 février 2016 - 19:00:06
Dernière modification le : jeudi 13 décembre 2018 - 15:26:38
Document(s) archivé(s) le : samedi 12 novembre 2016 - 01:10:10


Fichiers produits par l'(les) auteur(s)


  • HAL Id : hal-01265958, version 1


Armando Castañeda, Carole Delporte, Hugues Fauconnier, Sergio Rajsbaum, Michel Raynal. Wait-freedom and Locality are not Incompatible (with Distributed Ring Coloring as an Example). 2016. 〈hal-01265958〉



Consultations de la notice


Téléchargements de fichiers