1996 · 57 citations · 20 references
ComputingComputer ScienceDistributed SystemsFault-tolerant SystemsMemoryMemory HierarchyMemory Modeling
A self-stabilizing algorithm is silent if it converges to a glc)bal state after which the values stored in the communication registers are fixed. The silence property of self-stabilizing algorithms is a desirable property in terms of simplicity and communication overhead. In this work we show that no constant memory silent self-stabilizing algorithms exist for identification of the centers of a graph, leader election, and spanning tree construction. Lower bounds of Cl(log n) bits per communication register are obtained for each of the above tasks. The existence of a silent legitimate global state that uses less than log n bits per register is assumed. This legitimate global state is used to construct a silent global state that is illegitimate.
20
Self-stabilizing systems in spite of distributed control
Edsger W. Dijkstra · Communications of the ACM · 1974 · 2.1K citations · Full text
Choice Reviews Online · 2009 · 956 citations
Anish Arora, Mohamed G. Gouda · IEEE Transactions on Computers · 1994 · 274 citations