Paper Info
Title
A New Efficient Tool for the Design of Self-Stabilizing l-Exclusion Algorithms: The Controller
Abstract
In this paper, we present the first self-stabilizing protocols for l-exclusion problem in the message passing model. The l-exclusion problem is a generalization of the mutual exclusion problem--we allow l (l 驴 1) processors, instead of 1, to use a shared resource. We propose a new technique for the design of self-stabilizing l-exclusion: the controller. This tool allows to count tokens of the system without any counter variable for all processors except one called Root. We also introduce a new protocol composition called parametric composition. Then we present protocols on rings and on trees. The space requirement of both algorithms is independent of l for all processors except Root. The stabilization time of the first protocol is 3n time, where n is the ring size and the stabilization time of the second one is 6h + 2 time, where h is the tree height.
Year
DOI
Venue
2001
10.1007/3-540-45438-1_10
WSS
Keywords
Field
DocType
counter variable,new efficient tool,l-exclusion algorithms,present protocol,parametric composition,stabilization time,mutual exclusion problem,l-exclusion problem,self-stabilizing protocol,new protocol composition,self-stabilizing l-exclusion,new technique,mutual exclusion,message passing
Supervisor,Control theory,Computer science,Critical section,Algorithm,Parametric statistics,Fault tolerance,Loop counter,Mutual exclusion,Message passing,Distributed computing
Conference
ISBN
Citations 
PageRank 
3-540-42653-1
9
0.62
References 
Authors
11
2
Name
Order
Citations
PageRank
Rachid Hadid1314.93
Vincent Villain254445.77