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.