Skip to Main content Skip to Navigation
New interface
Reports (Research report)

Hierarchical token based mutual exclusion algorithms

Marin Bertier 1 Luciana Arantes 1 Pierre Sens 1 
1 Regal - Large-Scale Distributed Systems and Applications
LIP6 - Laboratoire d'Informatique de Paris 6, Inria Paris-Rocquencourt
Abstract : Mutual exclusion is a basic block of distributed synchronization algorithms. One of the challenge in highly distributed environments (like peer-to-peer or Grid configurations) is to provide scalable synchronizations taking into account the hierarchical network topology. This paper proposes hierarchical mutual exclusion algorithms. These algorithms are extensions of the Naimi-Trehel's token algorithm, reducing the cost of latency and the number of messages exchanges between far hosts. We propose three main extensions : (1) hierarchical proxy-based approach, (2) aggregation of requests, and (3) token preemption by closer hosts. We compared the performance of these algorithms on an emulated Grid testbed. We study the impact of each of the extensions, showing that the combination of them can greatly improve performances of the original algorithm.
Document type :
Reports (Research report)
Complete list of metadata

Cited literature [1 references]  Display  Hide  Download
Contributor : Rapport De Recherche Inria Connect in order to contact the contributor
Submitted on : Tuesday, May 23, 2006 - 5:21:50 PM
Last modification on : Wednesday, October 26, 2022 - 8:16:14 AM
Long-term archiving on: : Sunday, April 4, 2010 - 10:11:41 PM


  • HAL Id : inria-00071411, version 1


Marin Bertier, Luciana Arantes, Pierre Sens. Hierarchical token based mutual exclusion algorithms. [Research Report] RR-5177, INRIA. 2004. ⟨inria-00071411⟩



Record views


Files downloads