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.
All Science Journal Classification (ASJC) codes
- Control and Optimization
- Computational Mathematics
- Computational Theory and Mathematics
- Data structures
- Distributed systems