Skip to Main content Skip to Navigation
Reports

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 metadatas

Cited literature [7 references]  Display  Hide  Download

https://hal.inria.fr/hal-01283064
Contributor : Bruno Sericola <>
Submitted on : Friday, March 4, 2016 - 7:06:50 PM
Last modification on : Friday, July 10, 2020 - 4:03:43 PM
Long-term archiving on: : Sunday, November 13, 2016 - 7:38:42 AM

File

tasRI.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01283064, version 1

Citation

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⟩

Share

Metrics

Record views

898

Files downloads

745