Empire of Colonies Self-stabilizing and Self-organizing Distributed Algorithms

摘要

Self-stabilization ensures automatic recovery from an arbitrary state; we define self-organization as a property of algorithms which display local attributes. More precisely, we say that an algorithm is self-organizing if (1) it converges in sublinear time and (2) reacts "fast" to topology changes. If s(n) is an upper bound on the convergence time and d(n) is an upper bound on the convergence time following a topology change, then s(n) ∈ o(n) and d(n) ∈ o(s(n)). The self-organization property can then be used for gaining, in sub-linear time, global properties and reaction to changes. We present self-stabilizing and self-organizing algorithms for many distributed algorithms, including distributed snapshot and leader election.We present a new randomized self-stabilizing distributed algorithm for cluster definition in communication graphs of bounded degree processors. These graphs reflect sensor networks deployment. The algorithm converges in O(log n) expected number of rounds, handles dynamic changes locally and is, therefore, self-organizing. Applying the clustering algorithm to specific classes of communication graphs, in O(log n) levels, using an overlay network abstraction, results in a self-stabilizing and self-organizing distributed algorithm for hierarchy definition.Given the obtained hierarchy definition, we present an algorithm for hierarchical distributed snapshot. The algorithms are based on a new basic snap-stabilizing snapshot algorithm, designed for message passing systems in which a distributed spanning tree is defined and in which processors communicate using bounded links capacity. The combination of the self-stabilizing and self-organizing distributed hierarchy construction and the snapshot algorithm form an efficient self-stabilizer transformer. Given a distributed algorithm for a specific task, we are able to convert the algorithm into a self-stabilizing algorithm for the same task with an expected convergence time of O(log~2 n) rounds.