Bounds on the Costs of Multivalued Register Implementations
- Additional Document Info
- View All
THis paper considers the problem of implementing a k-ary regular (respectively, safe) register out of binary regular (respectively, safe) registers, assuming a single writer. While algorithms have been developed previously for these problems, no nontrivial lower bounds were known. The cost measures considered here are the number of physical registers and the number of reads and writes on the physical registers to implement the logical register. Tight bounds are obtained on the cost measures in many cases, and interesting trade-offs between the cost measures are identified. The lower bounds are shown using information-theoretic techniques.
author list (cited authors)
Chaudhuri, S., & Welch, J. L.