Skip to Main content Skip to Navigation

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.
Complete list of metadata

Cited literature [7 references]  Display  Hide  Download
Contributor : Bruno Sericola Connect in order to contact the contributor
Submitted on : Friday, March 4, 2016 - 7:06:50 PM
Last modification on : Wednesday, November 3, 2021 - 4:34:43 AM
Long-term archiving on: : Sunday, November 13, 2016 - 7:38:42 AM


Files produced by the author(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⟩



Record views


Files downloads