In the second part of the talk, we tackle the setting of dynamic networks and present a quite different approach for the distributed computation of functions, which is based on popular algorithms in statistical physics, namely the Metropolis algorithm and the Push-Sum algorithm. When an upper bound on the network…
In this talk, we present several results on distributed function computation in anonymous network with broadcast communications. First, we recall the characterization, given by Boldi and Vigna, of the computable functions when agents have no information on their outgoing neighborhoods. Then we characterize the class of computable functions in networks…
One of the most important results in distributed computing was published in April 1985 by Fischer, Lynch and Paterson. Their short paper “Impossibility of Distributed Consensus with One Faulty Process” definitively placed an upper bound on what it is possible to achieve with distributed processes in an asynchronous environment. The problem of…
I present two impossibility proofs for consensus in the presence of byzantine failures based on graph coverings.
In this talk, I present several computability results in anonymous networks with broadcast communications. First, I recall the characterization, given by Hendrickx and Tsitsiklis, of the computable functions when agents have no information on their outgoing neighborhoods. Then I give the characterization of computable functions in networks with either (a)…
