Know your audience: function computability in anonymous networks
Jeudi 6 juin 2024Intervenant(s) : Bernadette Charron-Bost (CNRS senior researcher, LIX)
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 with either (a) output port awareness, (b) bidirectional links, or (c) outdegree awareness: In each case, we prove that a function can be computed if and only it is frequency-based, namely, its value only depends on the frequencies of the different input values. This characterization holds for both exact and approximate computability. Our approach relies on the notion of graph fibration, and the key to our positive result in static networks is a novel linear algebraic result "à la Perron-Frobenius" which shows that, the space of fiber cardinals is of dimension one under any of the assumptions (a), (b), or (c).
In the second part of the talk, we tackle the setting of dynamic networks and present a different approach based on algorithms from statistical physics, namely the popular Metropolis and Push-Sum algorithms: When an upper bound on the network size is available, we provide more tractable algorithms for computing frequency-based functions, which can cope with network topology changes.