Dynamic Data Structures on Multiple Storage Media
Michiel Smid

Abstract:
We have studied the problem of maintaining a number of copies of a dynamic data structure in a network of processors. In order to avoid that each processor spends a lot of time in updating its copy, we first “preprocess” the update in a central structure. Then we broadcast information about the update to the processors, and, using this information, each of these processors updates its structure.
The most interesting results are as follows.
For each order decomposable set problem PR, there exists a client structure of size O(PR(n)), that can be maintained at the cost of O(PR(n)) transport and computing time. Here, PR(n) is the size of the answer for a set of n objects. The maintenance of the answer is completely arranged by the central structure. See Section 14.1.
In Section 14.2 we have given techniques for decomposable searching problems. The most general result is Theorem 14.2.3: Suppose we are given a data structure for a decomposable searching problem PR of size S(n) and query time Q(n). Then for each positive integer k there is a client structure solving PR, of size O(S(n)) having a query time of O(k x Q(n)). Insertions into this client structure can be performed at the cost of O(k x (S(n)/n) x (n/Q(n))^(1/k)) transport and computing time.
So this technique gives a client structure of the same size as the structure we started with, having asymptotically the same query time (if k is a constant). This new client structure, however, has a fast insert algorithm.

In Section 14.3 we have given a technique that applies to any data structure: Suppose we have a client structure DS of size S(n), having a query time Q(n). Let C(n) be the amount of data that an update changes in DS. Then we can transform this structure into another client structure of size O(S(n)), having a query time O(Q(n)), that can be updated in O(C(n)) transport and computing time. See Theorem 14.3.3. An interesting application of this result is given in Subsection 14.4.2. Here, we show that we can maintain a class of d-dimensional range trees, such that the central structure needs O((logn)*) time for an update, whereas the client structure can be updated in O((logn)4~') transport and computing time.

Note that most of the techniques of this part share ideas with those given for the reconstruction problem. Especially the general techniques of Sections 9.3 and 14.3 are strongly related to each other.