How to pass from local to global scales in anonymous networks? How to organize a selfstabilizing propagation of information with feedback. From the Angluin impossibility results, we cannot elect a leader in a general anonymous network. Thus, it is impossible to build a rooted spanning tree. Many problems can only be solved by probabilistic methods. In this paper we show how to use Unison to design a self-stabilizing barrier synchronization in an anonymous network. We show that the commuication structure of this barrier synchronization designs a self-stabilizing wave-stream, or pipelining wave, in anonymous networks. We introduce two variants of Wave: the strong waves and the wavelets. A strong wave can be used to solve the idempotent r-operator parametrized computation problem. A wavelet deals with k-distance computation. We show how to use Unison to design a self-stabilizing wave stream, a self-stabilizing strong wave stream and a self-stabilizing wavelet stream.
@cite_3 designs a self-stabilizing Barrier Synchonization algorithm in asynchronous anonymous complet networks. For the other topologies the authors use the network with a root, the program is not uniform, but only semi-uniform. An interesting question is to give a solution to this problem in a general connected asynchronous anonymous network. As far as we know, the algorithm @cite_2 is the only decentralised uniform wave algorithm for a general anonymous network. This algorithm requires that the processors know the diameter, or most simply a common upper bound @math of the diameter. This algorithm is not self-stabilizing.
@cite_3 @cite_2
1520594164 2623176784 2591036807 2952504335
Consider a distributed network of n nodes that is connected to a global source of "beats". All nodes receive the "beats" simultaneously, and operate in lock-step. A scheme that produces a "pulse" every Cycle beats is shown. That is, the nodes agree on "special beats", which are spaced Cycle beats apart. Given such a scheme, a clock synchronization algorithm is built. The "pulsing" scheme is self-stabilized despite any transient faults and the continuous presence of up to f < n 3 Byzantine nodes. Therefore, the clock synchronization built on top of the "pulse" is highly fault tolerant. In addition, a highly fault tolerant general stabilizer algorithm is constructed on top of the "pulse" mechanism. Previous clock synchronization solutions, operating in the exact same model as this one, either support f < n 4 and converge in linear time, or support f < n 3 and have exponential convergence time that also depends on the value of max-clock (the clock wrap around value). The proposed scheme combines the best of both worlds: it converges in linear time that is independent of max-clock and is tolerant to up to f < n 3 Byzantine nodes. Moreover, considering problems in a self-stabilizing, Byzantine tolerant environment that require nodes to know the global state (clock synchronization, token circulation, agreement, etc.), the work presented here is the first protocol to operate in a network that is not fully connected. Consider a complete communication network of @math nodes, where the nodes receive a common clock pulse. We study the synchronous @math -counting problem: given any starting state and up to @math faulty nodes with arbitrary behavior, the task is to eventually have all correct nodes labeling the pulses with increasing values modulo @math in agreement. Thus, we are considering algorithms that are self-stabilizing despite Byzantine failures. In this work, we give new algorithms for the synchronous counting problem that (1) are deterministic, (2) have optimal resilience, (3) have a linear stabilization time in @math (asymptotically optimal), (4) use a small number of states, and, consequently, (5) communicate a small number of bits per round. Prior algorithms either resort to randomization, use a large number of states and need high communication bandwidth, or have suboptimal resilience. In particular, we achieve an exponential improvement in both state complexity and message size for deterministic algorithms. Moreover, ... We consider distributed plurality consensus in a complete graph of size @math with @math initial opinions. We design an efficient and simple protocol in the asynchronous communication model that ensures that all nodes eventually agree on the initially most frequent opinion. In this model, each node is equipped with a random Poisson clock with parameter @math . Whenever a node's clock ticks, it samples some neighbors, uniformly at random and with replacement, and adjusts its opinion according to the sample. A prominent example is the so-called two-choices algorithm in the synchronous model, where in each round, every node chooses two neighbors uniformly at random, and if the two sampled opinions coincide, then that opinion is adopted. This protocol is very efficient and well-studied when @math . If @math for some small @math , we show that it converges to the initial plurality opinion within @math rounds, w.h.p., as long as the initial difference between the largest and second largest opinion is @math . On the other side, we show that there are cases in which @math rounds are needed, w.h.p. One can beat this lower bound in the synchronous model by combining the two-choices protocol with randomized broadcasting. Our main contribution is a non-trivial adaptation of this approach to the asynchronous model. If the support of the most frequent opinion is at least @math times that of the second-most frequent one and @math , then our protocol achieves the best possible run time of @math , w.h.p. We relax full synchronicity by allowing @math nodes to be poorly synchronized, and the well synchronized nodes are only required to be within a certain time difference from one another. We enforce this synchronicity by introducing a novel gadget into the protocol. Consider a complete communication network of @math nodes, where the nodes receive a common clock pulse. We study the synchronous @math -counting problem: given any starting state and up to @math faulty nodes with arbitrary behaviour, the task is to eventually have all correct nodes labeling the pulses with increasing values modulo @math in agreement. Thus, we are considering algorithms that are self-stabilising despite Byzantine failures. In this work, we give new algorithms for the synchronous counting problem that (1) are deterministic, (2) have optimal resilience, (3) have a linear stabilisation time in @math (asymptotically optimal), (4) use a small number of states, and consequently, (5) communicate a small number of bits per round. Prior algorithms either resort to randomisation, use a large number of states and need high communication bandwidth, or have suboptimal resilience. In particular, we achieve an exponential improvement in both state complexity and message size for deterministic algorithms. Moreover, we present two complementary approaches for reducing the number of bits communicated during and after stabilisation.