Brief announcement: distributed universality: contention-awareness; wait-freedom; object progress, and other properties

Abstract : A notion of a universal construction suited to distributed computing has been introduced by M. Herlihy in his celebrated paper "Wait-free synchronization" (ACM TOPLAS, 1991). A universal construction is an algorithm that can be used to wait-free implement any object defined by a sequential specification. Herlihy's paper shows that the basic system model, which supports only atomic read/write registers, has to be enriched with consensus objects to allow the design of universal constructions. The generalized notion of a k-universal construction has been recently introduced by Gafni and Guerraoui (CONCUR, 2011). A k-universal construction is an algorithm that can be used to simultaneously implement k objects (instead of just one object), with the guarantee that at least one of the k constructed objects progresses forever. While Herlihy's universal construction relies on atomic registers and consensus objects, a k-universal construction relies on atomic registers and k-simultaneous consensus objects (which have been shown to be computationally equivalent to k-set agreement objects in the read/write system model where any number of processes may crash). This paper significantly extends the universality results introduced by Herlihy and Gafni-Guerraoui. In particular, we present a k-universal construction which satisfies the following five desired properties, which are not satisfied by the previous k-universal construction: (1) among the k objects that are constructed, at least l objects (and not just one) are guaranteed to progress forever; (2) the progress condition for processes is wait-freedom, which means that each correct process executes an infinite number of operations on each object that progresses forever; (3) if one of the k constructed objects stops progressing, it stops in the same state at each process; (4) the proposed construction is contention-aware, which means that it uses only read/write registers in the absence of contention; and (5) it is indulgent with respect to the obstruction-freedom progress condition, which means that each process is able to complete any one of its pending operations on the k objects if all the other process hold still long enough. The proposed construction, which is based on new design principles, is called a (k,l)-universal construction. It uses a natural extension of k-simultaneous consensus objects, called (k,l)-simultaneous consensus objects ((k,l)-SC). Together with atomic registers, (k,l)-SC objects are shown to be necessary and sufficient for building a (k,l)-universal construction, and, in that sense, (k,l)-SC objects are (k,l)-universal.
Type de document :
Communication dans un congrès
Proceedings of the 2014 ACM symposium on Principles of distributed computing, 2014, Paris, France. Proceedings of the 2014 ACM symposium on Principles of distributed computing Pages 206-208, pp.206-208, 〈https://dl.acm.org/citation.cfm?doid=2611462.2611503〉. 〈10.1145/2611462.2611503〉
Liste complète des métadonnées

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

Identifiants

Citation

Michel Raynal, Julien Stainer, Gadi Taubenfeld. Brief announcement: distributed universality: contention-awareness; wait-freedom; object progress, and other properties. Proceedings of the 2014 ACM symposium on Principles of distributed computing, 2014, Paris, France. Proceedings of the 2014 ACM symposium on Principles of distributed computing Pages 206-208, pp.206-208, 〈https://dl.acm.org/citation.cfm?doid=2611462.2611503〉. 〈10.1145/2611462.2611503〉. 〈hal-01097396〉

Partager

Métriques

Consultations de la notice

749