For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Wait-Free Linearizable Distributed Shared Memory
Sen MORIYA Katsuro SUDA Michiko INOUE Toshimitsu MASUZAWA Hideo FUJIWARA
IEICE TRANSACTIONS on Information and Systems
Publication Date: 2000/08/25
Print ISSN: 0916-8532
Type of Manuscript: PAPER
synchronous message-passing system, distributed shared memory, linearizability, wait-freedom,
Full Text: PDF>>
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.