SPARSER - A PARADIGM FOR RUNNING DISTRIBUTED ALGORITHMS

This paper introduces a transformer for improving the communication complexity of several classes of distributed algorithms. The transformer takes a distributed algorithm whose message complexity is O(f· m) and produces a new distributed algorithm to solve the same problem with O(f· n log n + m log n) message complexity, where n and m are the total number of nodes and links in the network, and f· is an arbitrary function of n and m. Applying our paradigm to the standard all shortest paths algorithm yields a new algorithm which solves the problem in O(n2 log n) messages (The previous best that we know of is O(m · n) messages). When applied to the O(m + log3n) breadth-first search algorithm of Awerbuch and Peleg (Technical Report CS90-17, Weizman Institute of Science, Department of Comput. Science, July 1990) our paradigm yields an O(m + n · log4n) messages algorithm. © 1993 Academic Press, Inc.