Wait-Free Linearizable Distributed Shared Memory

Sen MORIYA  Katsuro SUDA  Michiko INOUE  Toshimitsu MASUZAWA  Hideo FUJIWARA  

IEICE TRANSACTIONS on Information and Systems   Vol.E83-D   No.8   pp.1611-1621
Publication Date: 2000/08/25
Online ISSN: 
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Algorithms
synchronous message-passing system,  distributed shared memory,  linearizability,  wait-freedom,  

Full Text: PDF>>
Buy this Article

We consider a wait-free linearizable implementation of shared objects on a distributed message-passing system. We assume that the system provides each process with a local clock that runs at the same speed as global time and that all message delays are in the range [d-u,d] where d and u (0< u d) are constants known to every process. We present four wait-free linearizable implementations of read/write registers on reliable and unreliable broadcast models. We also present two wait-free linearizable implementations of general objects on a reliable broadcast model. The efficiency of an implementation is measured by the worst-case response time for each operation of the implemented object. Response times of our wait-free implementations of read/write registers on a reliable broadcast model is better than a previously known implementation in which wait-freedom is not taken into account.