Empire of colonies: Self-stabilizing and self-organizing distributed algorithm

AbstractSelf-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(logn) 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(logn) 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 snapshots. 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 algorithm is on-demand self-stabilizing when no such distributed spanning tree is defined. Namely, it stabilizes regardless of the number of snapshot invocations.The combination of the self-stabilizing and self-organizing distributed hierarchy construction and the snapshot algorithm forms 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(log2n) rounds