Soma Chaudhuri and Jennifer L. Welch

A fundamental aspect of any concurrent system is how processes communicate with each other. Ultimately, all communication involves concurrent reads and writes of shared memory cells, or registers. The stronger the guarantees provided by a register, the more useful it is to the user, but the harder it may be to implement in practice. We consider the problem of implementing a k-ary regular (resp., safe) register out of binary regular (resp., safe) registers, assuming a single writer. While algorithms have been developed previously for these problems, no non-trivial lower bounds were known. The cost measures we consider are the number of physical registers and the number of reads and writes on the physical registers required 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. Two new algorithms are presented that improve on the costs of previously known algorithms: the hypercube algorithm implements a k-ary safe register out of binary safe registers, requiring only one physical write per logical write; and the tree algorithm implements a k-ary regular register out of binary regular registers, requiring only ceiling(log k) physical operations per logical operation. Both algorithms use novel combinatorial techniques.