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 size is available, we provide finite-state algorithms for computing frequency-based functions which tolerates asynchronous starts and can cope with network topology changes if the dynamic diameter is finite. We also discuss the impact of multiple connectivity assumptions and remaining gaps in the computability landscape in the case of dynamic networks when the number of agents is not bounded.
Joint work with Patrick Lambein-Monette
