Optimal space distributed move-to-front lists

Michael Saks, Fotios Zaharoglou

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations

Abstract

A distributed move-to-front list is a data object that abstracts 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 a distributed move-to-front list using single writer-multiple reader registers.

Original languageEnglish (US)
Title of host publicationProceedings of the Annual ACM Symposium on Principles of Distributed Computing
PublisherAssociation for Computing Machinery
Pages65-73
Number of pages9
ISBN (Print)0897914392
DOIs
StatePublished - Jul 1 1991
Externally publishedYes
Event10th Annual ACM Symposium on Principles of Distributed Computing, PODC 1991 - Montreal, Canada
Duration: Aug 19 1991Aug 21 1991

Publication series

NameProceedings of the Annual ACM Symposium on Principles of Distributed Computing

Other

Other10th Annual ACM Symposium on Principles of Distributed Computing, PODC 1991
Country/TerritoryCanada
CityMontreal
Period8/19/918/21/91

All Science Journal Classification (ASJC) codes

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications

Cite this