2011 · 35 citations · 24 references
ComputingComputer EngineeringComputer ScienceAlgorithmsDistributed SystemsFault-tolerant ComputingDistributed AlgorithmsDistributed ComputingFault Tolerance In CommunicationReliable Distributed SystemsSelf-stabilizing SystemsAsynchronous Distributed AlgorithmsDominating SetsFault-tolerant Distributed AlgorithmsSelf-stabilizationSelf-stabilizing AlgorithmsSelf-stabilizing Distributed AlgorithmsSilent Self-stabilizationTransient Faults
A self-stabilizing algorithm, after transient faults hit the system and place it in some arbitrary global state, recovers in finite time without external (e.g., human) intervention. In this paper, we propose a distributed asynchronous silent self-stabilizing algorithm for finding a minimal k-dominating set of at most [n/(k+1)] processes in an arbitrary identified network of size n. We propose a transformer that allows our algorithm work under an unfair daemon (the weakest scheduling assumption). The complexity of our solution is in O(n) rounds and O(Dn <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> ) steps using O(log n + k log n/k) bits per process where D is the diameter of the network.
24
Self-stabilizing systems in spite of distributed control
Edsger W. Dijkstra · Communications of the ACM · 1974 · 2.1K citations · Full text
Max-min d-cluster formation in wireless ad hoc networks
A.D. Amis, Ravi Prakash, T.H.P. Vuong et al. · 2002 · 985 citations
A trade-off between space and efficiency for routing tables
David Peleg, Eli Upfal · Journal of the ACM · 1989 · 350 citations · Full text
Anish Arora, Mohamed G. Gouda · IEEE Transactions on Computers · 1994 · 274 citations