Performance Evaluation of a Distributed Synchronization Protocol - Archive ouverte HAL Access content directly
Reports (Research Report) Year : 2016

Performance Evaluation of a Distributed Synchronization Protocol

(1) , (2) , (3) , (4)
1
2
3
4

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.
Fichier principal
Vignette du fichier
tasRI.pdf (281.83 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-01283064 , version 1 (04-03-2016)

Identifiers

  • HAL Id : hal-01283064 , version 1

Cite

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⟩
503 View
495 Download

Share

Gmail Facebook Twitter LinkedIn More