On the communication complexity of strong time-optimal distributed algorithms
Stefan Dobrev, Peter Růžička · Nordic journal of computing · 1998
In this paper we introduce the notion of time optimality in the strong sense and we investigate the communication complexity of strong time-optimal distributed algorithms. We show that a strong time-optimal algorithm solving the MST problem on networks with n nodes and m links interchanges at least (m-n)2 messages. We also present an Θ(m2) bound on communication complexity for strong time-optimal algorithms solving the gossip problem. As a consequence, similar results can be shown for other interesting problems on arbitrary networks, such as electing a leader, determining the median and the center, computing the diameter and others.