Abstract | ||
---|---|---|
A system is self-stabilizing if when started in any configuration it reaches a legal configuration, all subsequent configurations are legal. We present a randomized self-stabilizing mutual exclusion that works on any uniform graphs. It is based on irregularities that have to be present in the graph. Irregularities make random walks and merge on meeting. The number of states is bounded by o(Delta ln n) where Delta is the maximal degree and n is the number of vertices. The protocol is also proof against addition and removal of processors. (C) 2000 Elsevier Science B.V. All rights reserved. |
Year | DOI | Venue |
---|---|---|
2000 | 10.1016/S0020-0190(00)00056-9 | Inf. Process. Lett. |
Keywords | Field | DocType |
randomization,fault tolerance,random walks,algorithm,self stabilization,distributed system,random walk,interconnection,graph theory,mutual exclusion,scheduling,distributed computing | Graph theory,Discrete mathematics,Combinatorics,Vertex (geometry),Random walk,Scheduling (computing),Self-stabilization,Fault tolerance,Mutual exclusion,Mathematics,Bounded function | Journal |
Volume | Issue | ISSN |
74 | 5-6 | 0020-0190 |
Citations | PageRank | References |
7 | 0.52 | 5 |
Authors | ||
1 |
Name | Order | Citations | PageRank |
---|---|---|---|
Jérôme Durand-Lose | 1 | 127 | 14.93 |