Tight Bounds for Distributed MinimumWeight Spanni

Authors: Liah Kor Amos Korman David Peleg

Publish Date: 2013/05/15

Volume: 53, Issue: 2, Pages: 318-340

PDF Link

Abstract

This paper introduces the notion of distributed verification without preprocessing It focuses on the Minimumweight Spanning Tree MST verification problem and establishes tight upper and lower bounds for the time and message complexities of this problem Specifically we provide an MST verification algorithm that achieves simultaneously tildeOm messages and tildeOsqrtn + D time where m is the number of edges in the given graph G n is the number of nodes and D is G’s diameter On the other hand we show that any MST verification algorithm must send tildevarOmegam messages and incur tildevarOmegasqrtn + D time in worst caseOur upper bound result appears to indicate that the verification of an MST may be easier than its construction since for MST construction both lower bounds of tildevarOmegam messages and tildevarOmegasqrtn + D time hold but at the moment there is no known distributed algorithm that constructs an MST and achieves simultaneously tildeOm messages and tildeOsqrtn + D time Specifically the best known timeoptimal algorithm using tildeOsqrt n + D time requires Om+n 3/2 messages and the best known messageoptimal algorithm using tildeOm messages requires On time On the other hand our lower bound results indicate that the verification of an MST is not significantly easier than its construction

Keywords: