Lower bound for function computation in distributed networks

Abstract

Distributed computing network systems are modeled as graphs with which vertices represent compute elements and adjacency-edges capture their uni- or bi-directional communication. Distributed computation over a network system proceeds in a sequence of time-steps in which vertices update and/or exchange their values based on the underlying algorithm constrained by the time-(in)variant network topology. For finite convergence of distributed information dissemination and function computation in the model, we present a lower bound on the number of time-steps for vertices to receive (initial) vertex-values of all vertices regardless of underlying protocol or algorithmics in time-invariant networks via the notion of vertex-eccentricity.