Optimal Maintenance of Replicated Information
Baruch Awerbuch
Department of Mathematics and
Laboratory for Computer Science
MIT, Cambridge, MA 02139
baruch@theory.lcs.mit.edu
Israel Cidon
IBM T.J. Watson Research Center,
P.O. Box 704 Yorktown Heights, NY 10598
cidon@ibm.com
Shay Kutten
IBM T.J. Watson Research Center,
P.O. Box 704, Yorktown Heights, NY 10598
kutten@ibm.com
May 27, 1993
Abstract
"Those who cannot remember the past, are condemned to repeat it." (Philosopher George Santayana)
In this paper we show that keeping track of history enables significant improvements in the communication
complexity of dynamic networks protocols. We improve the communication complexity for solving any graph
problem from \Theta (E) to \Theta (V ), thus achieving the lower bound. Moreover, O(V ) is also our
amortized complexity of solving any function (not only graph functions) defined on the local inputs of the
nodes. This proves, for the first time, that amortized communication complexity, i.e. incremental cost of
adapting to a single topology change, can be smaller than the communication complexity of solving the
problem from scratch. This also has a practical importance: in real networks the topology and the local
inputs of the nodes change.
The first stage in our solution is a communication optimal maintenance of a spanning tree in a dynamic
network. The second stage is the optimal maintenance of replicas of databases. An important example of this
task is the problem of updating the description of the network's topology at every node (the well-known
Topology Update problem). For this problem we improve the message complexity from O(EV ) to Theta(V). The
improvement for a general database is even larger if the database size is larger than E.
It is interesting to note that we improved also the results of papers that used unbounded message size, from
O(E) to Theta(V). The time complexity of those papers was not bounded by the size of the database at all.
The time complexity of our solution is O(E + V*logV ). (For a general database of size M it is (M +V*logV ).)
This is optimal for the case that V*logV = O(E) (or V*logV = O(M)).
Our results are obtained using a novel technique to save communication. A node uses information received in
the past in order to deduce present information using its copy of the replicated database. This general
technique is one of our main contributions.