Title : Computable Functions in Anonymous Networks
Date: Tuesday, May 23rd 2023 – 14h00
Place: C103
Abstract: In this talk, we present several computability results in anonymous networks 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 is a distributed algorithm that computes the minimum base of the network.
In the second part of the talk, we tackle the setting of dynamic networks and present a quite different approach based on the popular Push-Sum algorithm: When an upper bound on the network size is available, we provide a more tractable algorithm for computing frequency-based functions, which can cope with dynamic network topology changes.
