Constructing regular variables in message passing systems

Developing fault-tolerant programs for distributed systems is a difficult task. It seems that it is more difficult to develop fault-tolerant programs for message passing systems than for shared memory systems. Consequently, there has been a lot of interest in simulating atomic shared memory by constructing atomic shared variables in message passing systems. The best known construction of 1-writer n-reader atomic variables is of Attiya (J. Algorithms 34 (2000) 109). She first constructs 1-writer n-reader regular variables, and then uses them to construct atomic variables. Her regular variable construction requires, for each operation execution, exchanging 2n messages of size ◯(n3) bits. A new construction of 1-writer n-reader regular variables is proposed. Each operation execution requires exchanging 2n messages of size ◯(n2logn) bits.