A Provably Starvation-Free Distributed Directory Protocol

Abstract : This paper presents Combine, a distributed directory protocol for shared objects, designed for large-scale distributed systems. Directory protocols support move requests, allowing to write the object locally, as well as lookup requests, providing a read-only copy of the object. They have been used in distributed shared memory implementations and in data-flow implementations of distributed software transactional memory in large-scale systems. The protocol runs on an overlay tree, whose leaves are the nodes of the system; it ensures that the cost of serving a request is proportional to the cost of the shortest path between the requesting node and the serving node, in the overlay tree. The correctness of the protocol, including starvation freedom, is proved, despite asynchrony and concurrent requests. The protocol avoids race conditions by combining requests that overtake each other as they pass through the same node. Using an overlay tree with a good stretch factor yields an efficient protocol, even when requests are concurrent.
Type de document :
Communication dans un congrès
Shlomi Dolev and Jorge Arturo Cobb and Michael J. Fischer and Moti Yung. SSS, 2010, Unknown, Springer, 6366, pp.405-419, 2010, Lecture Notes in Computer Science. 〈10.1007/978-3-642-16023-3_33〉
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00992698
Contributeur : Corentin Travers <>
Soumis le : lundi 19 mai 2014 - 10:55:20
Dernière modification le : dimanche 22 avril 2018 - 01:12:00
Document(s) archivé(s) le : lundi 10 avril 2017 - 23:33:52

Fichier

10.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Hagit Attiya, Vincent Gramoli, Alessia Milani. A Provably Starvation-Free Distributed Directory Protocol. Shlomi Dolev and Jorge Arturo Cobb and Michael J. Fischer and Moti Yung. SSS, 2010, Unknown, Springer, 6366, pp.405-419, 2010, Lecture Notes in Computer Science. 〈10.1007/978-3-642-16023-3_33〉. 〈hal-00992698〉

Partager

Métriques

Consultations de la notice

207

Téléchargements de fichiers

91