DIMACS TR: 94-33
Optimal Space Distributed Order-Preserving Lists
Authors: Michael Saks and Fotis Zaharoglou
We investigate the problem of implementing a order-preserving lists in a
multiprocessor system. The main example is a move-to-front list, which main-
tains an ordering on the set of n processors and supports two operations:
REPORT which returns the permutation and MOVE-TO-FRONT(i) which changes the
permutation by moving processor i to the beginning of the permutation.
This latter operation can only be performed by processor i. The move-to-front
list is of interest in distributed computation because it can maintain a
precedence order of the active jobs in the distributed system. It is
closely related to time stamp systems, which were proposed by Israeli and Li.
We investigate the space efficiency of implementations of move-to-front lists
and provide matching upper and lower bounds of (log n)^2 on the space per
processor needed to implement move-to-front lists.
Paper available at:
DIMACS Home Page