94-33 Optimal Space Distributed Order-Preserving Lists

DIMACS TR: 94-33

Optimal Space Distributed Order-Preserving Lists

Authors: Michael Saks and Fotis Zaharoglou

ABSTRACT
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: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1994/94-33.ps

DIMACS Home Page