The Universe of Symmetry Breaking Tasks

Abstract : Processes in a concurrent system need to coordinate using a shared memory or a message-passing subsystem in order to solve agreement tasks such as, for example, consensus or set agreement. However, often coordination is needed to “break the symmetry” of processes that are initially in the same state, for example, to get exclusive access to a shared resource, to get distinct names or to elect a leader. This paper introduces and studies the family of generalized symmetry breaking (GSB) tasks, that includes election, renaming and many other symmetry breaking tasks. Differently from agreement tasks, a GSB task is “inputless”, in the sense that processes do not propose values; the task specifies only the symmetry breaking requirement, independently of the system's initial state (where processes differ only on their identifiers). Among many various characterizing the family of GSB tasks, it is shown that (non adaptive) perfect renaming is universal for all GSB tasks.
Type de document :
Rapport
[Research Report] PI-1965, 2011, pp.16
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00560453
Contributeur : Ist Rennes <>
Soumis le : vendredi 28 janvier 2011 - 13:42:44
Dernière modification le : mercredi 16 mai 2018 - 11:23:13
Document(s) archivé(s) le : vendredi 29 avril 2011 - 03:03:45

Fichier

PI-1965.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00560453, version 1

Citation

Damien Imbs, Sergio Rajsbaum, Michel Raynal. The Universe of Symmetry Breaking Tasks. [Research Report] PI-1965, 2011, pp.16. 〈inria-00560453〉

Partager

Métriques

Consultations de la notice

432

Téléchargements de fichiers

220