Optimal space distributed order-preserving lists

Authors
Saks, M Zaharoglou, F
Citation
M. Saks et F. Zaharoglou, Optimal space distributed order-preserving lists, J ALGORITHM, 31(2), 1999, pp. 320-334
Citations number
7
Categorie Soggetti
Computer Science & Engineering
Journal title
JOURNAL OF ALGORITHMS
ISSN journal
01966774 → ACNP
Volume
31
Issue
2
Year of publication
1999
Pages
320 - 334
Database
ISI
SICI code
0196-6774(199905)31:2<320:OSDOL>2.0.ZU;2-C
Abstract
A move-to-front list is a distributed data object that provides an abstract ion of a temporal ordering on a set of processes in a distributed system. W e present a lower bound and a matching upper bound of Theta(log(2)n) bits o n the space per processor needed to implement such a list using single-writ er multiple-reader registers. A generalization is also discussed. (C) 1999 Academic Press.