
For FullText 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.

Efficient Linearizable Implementation of Shared FIFO Queues and General Objects on a Distributed System
Michiko INOUE Toshimitsu MASUZAWA Nobuki TOKURA
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E81A
No.5
pp.768775 Publication Date: 1998/05/25
Online ISSN:
DOI:
Print ISSN: 09168508 Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications) Category: Keyword: distributed system, shared object, FIFO queue, linearizability,
Full Text: PDF(756.9KB)>>
Summary:
We consider linearizable implementations of shared FIFO queues and general deterministic objects on a distributed messagepassing system which provides a realtime timer. The efficiency of an implementation is measured by the worstcase response time res_time(op) for each operation op of the implemented objects. We show the following results under the assumption that all message delays are in the range [du,d] for some constants d and u (0 u d). We first present an implementation of deterministic objects with res_time(op_{a})=u for any acktype operation op_{a} and res_time(op_{v})=2d for any valtype operation op_{v}, where an acktype operation is an operation which always returns a unique response and a valtype operation is an operation which is not acktype. We also consider an implementation of FIFO queues, which have two kinds of operations, enq(v) and deq. We show that, for any implementation of FIFO queues, (1) res_time(enq(v)) u(n1)/n holds for some v where n is the number of processes, and (2) res_time(deq) d+u/2 holds in the case of u (2/3)d.

