Computing in the Presence of Concurrent Solo Executions

Abstract : In a wait-free model any number of processes may crash. A process runs solo when it computes its local output without receiving any information from other processes, either because they crashed or they are too slow. While in wait-free shared-memory models at most one process may run solo in an execution, any number of processes may have to run solo in an asynchronous wait-free message-passing model. This paper is on the computability power of models in which several processes may concurrently run solo. It first introduces a family of round-based wait-free models, called the d-solo models, 1 ≤ d ≤ n, where up to d processes may run solo. The paper gives then a characterization of the colorless tasks that can be solved in each d-solo model. It also introduces the (d,ε)-solo approximate agreement task, which generalizes ε-approximate agreement, and proves that (d,ε)-solo approximate agreement can be solved in the d-solo model, but cannot be solved in the (d + 1)-solo model. The paper studies also the relation linking d-set agreement and (d,ε)-solo approximate agreement in asynchronous wait-free message-passing systems. These results establish for the first time a hierarchy of wait-free models that, while weaker than the basic read/write model, are nevertheless strong enough to solve non-trivial tasks.
Type de document :
Communication dans un congrès
LATIN 2014: Theoretical Informatics, 2014, Montevideo, Uruguay. LATIN 2014: Theoretical Informatics Lecture Notes in Computer Science Volume 8392, 2014, pp 214-225, 8392, pp.214-225, 〈http://link.springer.com/chapter/10.1007%2F978-3-642-54423-1_19〉. 〈10.1007/978-3-642-54423-1_19〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01097416
Contributeur : Julien Stainer <>
Soumis le : vendredi 19 décembre 2014 - 15:51:49
Dernière modification le : mercredi 16 mai 2018 - 11:23:13

Lien texte intégral

Identifiants

Citation

Maurice Herlihy, Sergio Rajsbaum, Michel Raynal, Julien Stainer. Computing in the Presence of Concurrent Solo Executions. LATIN 2014: Theoretical Informatics, 2014, Montevideo, Uruguay. LATIN 2014: Theoretical Informatics Lecture Notes in Computer Science Volume 8392, 2014, pp 214-225, 8392, pp.214-225, 〈http://link.springer.com/chapter/10.1007%2F978-3-642-54423-1_19〉. 〈10.1007/978-3-642-54423-1_19〉. 〈hal-01097416〉

Partager

Métriques

Consultations de la notice

774