Performance Evaluation of a Distributed Synchronization Protocol

Abstract : This paper presents a solution to the well-known problem of synchronization in a distributed asynchronous system prone to process crashes. This problem is also known as the Test&Set problem. The Test&Set is a distributed synchronization protocol that, when invoked by a set of processes, returns a unique winning process. This unique process is then allowed to use, for instance, a shared resource. Recently many advances in implementing Test&Set objects have been achieved, however all of them uniquely target the shared memory model. In this paper we propose an implementation of a Test&Set object for a message passing distributed system. This implementation can be invoked by any number n ≤ N of processes where N is the total number of processes in the system. We show in this paper, using a Markov model, that our implementation has an expected step complexity in O(log n) and we give an explicit formula for the distribution of the number of steps needed to solve the problem. We also analyze the expected value and the distribution of the number of operations invoked by the n processes to determine the winning process.
Liste complète des métadonnées

Littérature citée [7 références]  Voir  Masquer  Télécharger
Contributeur : Bruno Sericola <>
Soumis le : vendredi 4 mars 2016 - 19:06:50
Dernière modification le : samedi 12 janvier 2019 - 01:06:56
Document(s) archivé(s) le : dimanche 13 novembre 2016 - 07:38:42


Fichiers produits par l'(les) auteur(s)


  • HAL Id : hal-01283064, version 1


Emmanuelle Anceaume, François Castella, Achour Mostefaoui, Bruno Sericola. Performance Evaluation of a Distributed Synchronization Protocol. [Research Report] Inria; Irisa; Lina; Irmar. 2016. 〈hal-01283064〉



Consultations de la notice


Téléchargements de fichiers