Memory requirements for silent stabilization
Shlomi Dolev, Mohamed G. Gouda, M. Schneider · 1996
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.