Computing in the Presence of Concurrent Solo Executions - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2013

Computing in the Presence of Concurrent Solo Executions

Résumé

In a wait-free model any number of processes may crash. A process runs solo when it computes its local output without receiving any communication 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. The paper introduces the (d, epsilon)-solo approximate agreement problem, which generalizes epsilon-approximate agreement. It proves that (d, epsilon)-solo approximate agreement can be solved in the d-solo model, but it cannot be solved in the (d + 1)-solo model. The paper also studies the relation linking d-set agreement and (d, epsilon)-solo approximate agreement in asynchronous wait-free message-passing systems. These results establish for the first time a hierarchy of wait-free models weaker than the basic read/write model, that are nevertheless still strong enough to solve many tasks. The new failure model, based on taking into account solo executions, has message passing as well as shared-memory instantiations.
Dans un modèle wait-free, un nombre quelconque de processus peut arrêter de fonctionner. Un processus s'exécute en solo lorsqu'il calcule sa sortie sans communiquer avec les autres processus. Dans les modèles wait-free avec des processus communicant par mémoire partagée, au plus un processus peut s'exécuter en solo, alors que, dans les modèles wait-free ou ils échangent des messages, un nombre quelconque d'entre eux peut avoir à s'exécuter en solo. Cet article étudie la calculabilité dans des modèles intermédiaires, appelés d-solo modèles, dans lesquels au plus d processus s'exécutent en solo.
Fichier principal
Vignette du fichier
Hierarchy-Comm-Sub-Consensus-V27prime.pdf (556.7 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-00825619 , version 1 (24-05-2013)
hal-00825619 , version 2 (04-06-2013)
hal-00825619 , version 3 (05-12-2013)

Identifiants

  • HAL Id : hal-00825619 , version 1

Citer

Sergio Rajsbaum, Michel Raynal, Julien Stainer. Computing in the Presence of Concurrent Solo Executions. [Research Report] PI-2004, 2013. ⟨hal-00825619v1⟩
465 Consultations
345 Téléchargements

Partager

Gmail Facebook X LinkedIn More