eas@utcsrgv.UUCP (Ann Struthers) (11/19/84)
THEORETICAL ASPECTS SEMINAR
Thursday, November 22, 1984
4:00 PM
Sandford Fleming Building 1101
Professor Baruch Awerbuch
Laboratory for Computer Science
MIT
"An Efficient Network Synchronization Protocol"
We propose a new, simple methodology for designing distributed algorithms
in asynchronous networks. Asynchronous algorithms are in many cases
substantially inferior in terms of their complexity to corresponding
synchronous algorithms, and their design and analysis are much more
complicated. Thus, it makes sense to develop a general technique, referred
to as "synchronizer", which allows the user to write his algorith as if it
is run in a synchronous network.
The main contribution of this paper is a new efficient synchronizer, which
can be used not only to simplify the design of asynchronous algorithms, but
also to reduce complexities of existing algorithms. In particular, we are
able to improve the best known distributed Maximum Flow and Breadth-First
Search algorithms in terms of their communication and time requirements.
In our solution, we synchronize the network through an imbedded spanning
forest, where each tree has logarithmic height and the number of neigh-
bouring trees is at most linear.
We also provide a lower bound, showing that the proposed synchronizer
exhibits an optimal (up to a constant factor) trade-off between its
communication and time requirements.