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) output port awareness, (b) bidirectional links, or (c) outdegree awareness: In each case, I 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 this positive result is the Boldi and Vigna’s algorithm that distributively computes the minimum base of the network.
In the second part of the talk, I 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, this provides a more tractable algorithm for computing frequency-based functions, which can cope with dynamic network topology changes.
