BOUNDS ON THE COSTS OF MULTIVALUED REGISTER IMPLEMENTATIONS Academic Article

abstract

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

authors

• Welch, Jennifer

published proceedings

• SIAM JOURNAL ON COMPUTING

author list (cited authors)

• CHAUDHURI, S., & WELCH, J. L.

citation count

• 5

complete list of authors

• CHAUDHURI, S||WELCH, JL

publication date

• April 1994

publisher

• Society for Industrial & Applied Mathematics (SIAM)  Publisher

published in

• SIAM Journal on Computing  Journal

keywords

• Concurrent Computation
• Concurrent Distributed System
• Registers
• Shared Memory Registers
• Time And Space Complexity

Digital Object Identifier (DOI)

• 10.1137/S0097539790190971

start page

• 335

end page

• 354

volume

• 23

issue

• 2

URL

• http%3A%2F%2Fdx.doi.org%2F10.1137%2Fs0097539790190971