2004 · 77 citations · 15 references
ComputingComputer EngineeringComputer ScienceAlgorithmsDistributed SystemsTheory Of ComputationClock SynchronizationData SynchronizationDistributed ComputingDistributed SynchronizationGraph AlgorithmsSelf-stabilizing SystemsAsynchronous Mutual ExclusionMutual ExclusionSafety Requirement SpecificationSelf-stabilizationSelf-stabilizing AlgorithmsSilent Self-stabilizationSynchronizationTree Networks
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.
15
Self-stabilizing systems in spite of distributed control
Edsger W. Dijkstra · Communications of the ACM · 1974 · 2.1K citations · Full text
Dominic Welsh · Bulletin of the London Mathematical Society · 1974 · 1.1K citations
Complexity of network synchronization
Baruch Awerbuch · Journal of the ACM · 1985 · 691 citations · Full text
Anish Arora, Mohamed G. Gouda · IEEE Transactions on Computers · 1994 · 274 citations