Constructing Regular Variables in Message-Passing Systems

Writing fault-tolerant programs in distributed systems is a delicate task. It is relatively difficult for message passing systems than for shared memory systems. To ameliorate some difficulties, 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 l-writer n-reader atomic variables is of Attiya. She first constructs l-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 O(n sup 3), constant time. A new construction of l-writer n reader regular variable is proposed. Each operation execution requires exchanging 2n messages of size O(n sup 2 log n) bits, constant time.