Optimal space distributed move-to-front lists

Michael Saks; Fotios Zaharoglou

doi:10.1145/112600.112607

Optimal space distributed move-to-front lists

Michael Saks
, Fotios Zaharoglou

Research output: Chapter in Book/Report/Conference proceeding › Conference 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 language	American English
Title of host publication	Proceedings of the Annual ACM Symposium on Principles of Distributed Computing
Publisher	Association for Computing Machinery
Pages	65-73
Number of pages	9
ISBN (Print)	0897914392
DOIs	https://doi.org/10.1145/112600.112607
State	Published - Jul 1 1991
Externally published	Yes
Event	10th Annual ACM Symposium on Principles of Distributed Computing, PODC 1991 - Montreal, Canada Duration: Aug 19 1991 → Aug 21 1991

Publication series

Name	Proceedings of the Annual ACM Symposium on Principles of Distributed Computing

Other

Other	10th Annual ACM Symposium on Principles of Distributed Computing, PODC 1991
Country/Territory	Canada
City	Montreal
Period	8/19/91 → 8/21/91

ASJC Scopus subject areas

Software
Hardware and Architecture
Computer Networks and Communications

Access to Document

10.1145/112600.112607

Cite this

@inproceedings{4bf013cd578044728b73ce97659a5856,

title = "Optimal space distributed move-to-front lists",

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 {\textregistered}(log2n) bits on the space per processor needed to implement a distributed move-to-front list using single writer-multiple reader registers.",

author = "Michael Saks and Fotios Zaharoglou",

note = "Publisher Copyright: {\textcopyright} 1991 ACM; 10th Annual ACM Symposium on Principles of Distributed Computing, PODC 1991 ; Conference date: 19-08-1991 Through 21-08-1991",

year = "1991",

month = jul,

day = "1",

doi = "10.1145/112600.112607",

language = "American English",

isbn = "0897914392",

series = "Proceedings of the Annual ACM Symposium on Principles of Distributed Computing",

publisher = "Association for Computing Machinery",

pages = "65--73",

booktitle = "Proceedings of the Annual ACM Symposium on Principles of Distributed Computing",

}

Saks, M & Zaharoglou, F 1991, Optimal space distributed move-to-front lists. in Proceedings of the Annual ACM Symposium on Principles of Distributed Computing. Proceedings of the Annual ACM Symposium on Principles of Distributed Computing, Association for Computing Machinery, pp. 65-73, 10th Annual ACM Symposium on Principles of Distributed Computing, PODC 1991, Montreal, Canada, 8/19/91. https://doi.org/10.1145/112600.112607

Optimal space distributed move-to-front lists. / Saks, Michael; Zaharoglou, Fotios.
Proceedings of the Annual ACM Symposium on Principles of Distributed Computing. Association for Computing Machinery, 1991. p. 65-73 (Proceedings of the Annual ACM Symposium on Principles of Distributed Computing).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Optimal space distributed move-to-front lists

AU - Saks, Michael

AU - Zaharoglou, Fotios

PY - 1991/7/1

Y1 - 1991/7/1

N2 - 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.

AB - 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.

UR - https://www.scopus.com/pages/publications/0002866802

UR - https://www.scopus.com/pages/publications/0002866802#tab=citedBy

U2 - 10.1145/112600.112607

DO - 10.1145/112600.112607

M3 - Conference contribution

SN - 0897914392

T3 - Proceedings of the Annual ACM Symposium on Principles of Distributed Computing

SP - 65

EP - 73

BT - Proceedings of the Annual ACM Symposium on Principles of Distributed Computing

PB - Association for Computing Machinery

T2 - 10th Annual ACM Symposium on Principles of Distributed Computing, PODC 1991

Y2 - 19 August 1991 through 21 August 1991

ER -

Optimal space distributed move-to-front lists

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this