Optimal Space Distributed Order-Preserving Lists

Michael Saks, Fotios Zaharoglou

Research output: Contribution to journalArticle

1 Scopus citations

Abstract

A move-to-front list is a distributed data object that provides an abstraction of a temporal ordering on a set of processes in a distributed system. We present a lower bound and a matching upper bound of Θ(log2n) bits on the space per processor needed to implement such a list using single-writer multiple-reader registers. A generalization is also discussed.

Original languageEnglish (US)
Pages (from-to)320-334
Number of pages15
JournalJournal of Algorithms
Volume31
Issue number2
DOIs
StatePublished - May 1999

All Science Journal Classification (ASJC) codes

  • Control and Optimization
  • Computational Mathematics
  • Computational Theory and Mathematics

Keywords

  • Data structures
  • Distributed systems

Fingerprint Dive into the research topics of 'Optimal Space Distributed Order-Preserving Lists'. Together they form a unique fingerprint.

  • Cite this