Name
Abstract | ||
|---|---|---|
We propose a general self-stabilizing scheme for solving any synchronization problem whose safety specification can be defined using a local property. We demonstrate the versatility of our scheme by showing that very memory-efficient solutions to many well-known problems (e.g., asynchronous phase clock, local mutual exclusion, local reader-writers, and local group mutual exclusion) can be derived using the proposed framework. We show that all these algorithms use a phase clock whose minimum size in terms of number of states per process is equal to CG + TG - 1, where CG is the length of the maximal cycle of the shortest maximum cycle basis if the graph contains cycles and 2 (otherwise) for tree networks, and TG is the length of the longest chordless cycle (i.e., hole) if the graph contains cycles and 2 for tree networks. In particular, for the asynchronous phase clock problem, our solution significantly improves all existing self-stabilizing solutions---all of them require quadratic space in terms of the number of states.As a by-product of our scheme, we present a silent bounded algorithm which can be used to transform any serial system into a distributed one. Thus, it answers an open question in [16], if there exists a bounded system transformation which is silent. |
Year | DOI | Venue |
|---|---|---|
2004 | 10.1145/1011767.1011790 | PODC |
Keywords | Field | DocType |
asynchronous phase clock,tree network,local property,general self-stabilizing scheme,local mutual exclusion,local reader-writers,graph theory,local group,maximal cycle,asynchronous phase clock problem,longest chordless cycle,mutual exclusion,self stabilization,synchronization | Graph theory,Discrete mathematics,Asynchronous communication,Combinatorics,Synchronization,Computer science,Cycle basis,Self-stabilization,Local property,Mutual exclusion,Bounded function,Distributed computing | Conference |
ISBN | Citations | PageRank |
1-58113-802-4 | 30 | 1.15 |
References | Authors | |
14 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Christian Boulinier | 1 | 53 | 3.66 |
| Franck Petit | 2 | 736 | 60.02 |
| Vincent Villain | 3 | 544 | 45.77 |