Exploring The Borderlands Of The Gathering Problem

Problems of pattern formation have been extensively studied in distributed computing. One of this problems is the gathering problem: agents must gather at a same position in a distributed manner. When gathering is not possible, a close problem is the convergence problem. In this article, we investigate the two following questions: (1) Can processes gather when each process cannot see more that one other process at the same time? (2) Can a gathering behavior be learned by processes? Regarding the first point, we introduce a new model with an extremely restricted visibility: each process can only see one other process (its closest neighbor). Our goal is to see if (and to what extent) the gathering and convergence problems can be solved in this setting. We first show that, surprisingly, the problem can be solved for a small number of processes (at most 5), but not beyond. This is due to indeterminacy in the case where there are several "closest neighbors" for a same process. By removing this indeterminacy with an additional hypothesis (choosing the closest neighbor according to an order on the positions of processes), we then show that the problem can be solved for any number of processes. We also show that up to one crash failure can be tolerated for the convergence problem. Regarding the second point, we present the first experimental evidence that a gathering behavior can be learned without explicit communication in a partially observable environment. The learned behavior has the same properties as a self-stabilizing distributed algorithm, as processes can gather from any initial state (and thus tolerate any transient failure). Besides, we show that it is possible to scale and then tolerate the brutal loss of up to 90% of agents without significant impact on the behavior.

Distributed average consensus for wireless sensor networks

Florence Bénézit

Wireless sensor networks have emerged a few years ago, enabling large scale sensing at low cost. There are many interesting problems related to this new sensing tool: designing robust and small hardware, defining adapted routing protocols, minimizing the energy consumption of each component, synchronizing the sensors, etc. In this thesis, we focus on the processing of the sensed data within the network itself. We study a specific network signal processing problem, called distributed average consensus. In this problem, the sensors, which are connected in a wireless network, need to know the average of all the measurements in the network. Instead of gathering the data at a central node, which would compute the average and broadcast it to the network, average consensus algorithms offer a distributed solution to the averaging problem. By local message passing and iterative local computations only, nodes can learn the average of the measurements. More precisely, in average consensus algorithms, nodes iteratively compute local weighted averages that conserve the global average of the estimates in the network. The estimates at each node contract until they all converge to the average. Many distributed average consensus algorithms were designed and the literature is vast. This thesis starts by classifying the existing algorithms. Then it describes a small number of useful techniques, which can handle the analysis of all the algorithms. Preexisting algorithms as well as algorithms that we designed are revisited with these unifying and simple techniques. In addition, the performance of the algorithms depends on the topology of the network, and a variety of networks are explored: simple graphs as circles or trees, lattices, random geometric graphs, complete graphs etc. Finally, an extension of average consensus to voting consensus is derived. In particular, we show that with two bits of memory at each node, a network can reach consensus in finite time on majority, when the initial measurements are binary. Distributed algorithms to compute majority with finite memory for ternary and quaternary signals are also given.

EPFL2009

Computing in Social Networks

Andrei Giurgiu, Rachid Guerraoui, Kévin Clément Huguenin, Anne-Marie Kermarrec

This paper defines the problem of Scalable Secure Computing in a Social network: we call it the S-3 problem. In short, nodes, directly reflecting on associated users, need to compute a function f : V -> U of their inputs in a set of constant size, in a scalable and secure way. Scalability means that the message and computational complexity of the distributed computation is at most O(root n . polylog n). Security encompasses (1) accuracy and (2) privacy: accuracy holds when the distance from the output to the ideal result is negligible with respect to the maximum distance between any two possible results; privacy is characterized by how the information disclosed by the computation helps faulty nodes infer inputs of non-faulty nodes.

Springer-Verlag New York, Ms Ingrid Cunningham, 175 Fifth Ave, New York, Ny 10010 Usa2010

Computing in social networks

Andrei Giurgiu, Rachid Guerraoui, Kévin Clément Huguenin, Anne-Marie Kermarrec

This paper defines the problem of Scalable Secure computing in a Social network: we call it the S-3 problem. In short, nodes, directly reflecting on associated users, need to compute a symmetric function f : V-n -> U of their inputs in a set of constant size, in a scalable and secure way. Scalability means that the spatial, computational and message complexity of the distributed computation does not grow too fast with the number of nodes n. Security encompasses (1) accuracy and (2) privacy: accuracy holds when the distance from the output to the ideal result is negligible with respect to the maximum distance between any two possible results; privacy is characterized by how the information disclosed by the computation helps faulty nodes infer inputs of non-faulty nodes, which we capture in our context by the very notion of probabilistic anonymity. We first prove that under mild regularity conditions the problem of computing an arbitrary function can be reduced to that of component-wise addition of vectors of integers. More specifically, if the function f is Lipschitz-continuous and the maximum distance between two possible results is Omega(n), any protocol that S-3-computes component-wise addition of vectors of integers S-3-computes f. We then present AG-S3, a protocol that S-3-computes a class of aggregation functions, that is that can be expressed as a commutative monoid operation on U: f (x(1),...,x(n)) = x(1) circle plus ... circle plus x(n), assuming the number of faulty participants is at most root n/log(2)n. We further prove that AG-S3 S-3-computes component-wise addition of vectors of integers thus extending its application spectrum to regular functions. Key to our protocol is a dedicated overlay structure that enables secret sharing and distributed verifications which leverage the social aspect of the network: nodes care about their reputation and do not want to be tagged as misbehaving. (C) 2013 Elsevier Inc. All rights reserved.

Elsevier2014

Distributed average consensus for wireless sensor networks

Florence Bénézit

EPFL2009

Computing in social networks

Andrei Giurgiu, Rachid Guerraoui, Kévin Clément Huguenin, Anne-Marie Kermarrec

Elsevier2014