Efficient Linearizable Implementation of Shared FIFO Queues and General Objects on a Distributed System

Michiko INOUE; Toshimitsu MASUZAWA; Nobuki TOKURA

Efficient Linearizable Implementation of Shared FIFO Queues and General Objects on a Distributed System

Michiko INOUE, Toshimitsu MASUZAWA, Nobuki TOKURA

Full Text Views

0

Cite this

Summary :

We consider linearizable implementations of shared FIFO queues and general deterministic objects on a distributed message-passing system which provides a real-time timer. The efficiency of an implementation is measured by the worst-case 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 [d-u,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 ack-type operation op_a and res_time(op_v)=2d for any val-type operation op_v, where an ack-type operation is an operation which always returns a unique response and a val-type operation is an operation which is not ack-type. 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(n-1)/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.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E81-A No.5 pp.768-775

Publication Date: 1998/05/25

Publicized

Online ISSN

DOI

Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)

Category

Cite this

Copy

Michiko INOUE, Toshimitsu MASUZAWA, Nobuki TOKURA, "Efficient Linearizable Implementation of Shared FIFO Queues and General Objects on a Distributed System" in IEICE TRANSACTIONS on Fundamentals, vol. E81-A, no. 5, pp. 768-775, May 1998, doi: .
Abstract: We consider linearizable implementations of shared FIFO queues and general deterministic objects on a distributed message-passing system which provides a real-time timer. The efficiency of an implementation is measured by the worst-case 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 [d-u,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 ack-type operation op_a and res_time(op_v)=2d for any val-type operation op_v, where an ack-type operation is an operation which always returns a unique response and a val-type operation is an operation which is not ack-type. 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(n-1)/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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e81-a_5_768/_p

Copy

@ARTICLE{e81-a_5_768,
author={Michiko INOUE, Toshimitsu MASUZAWA, Nobuki TOKURA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Efficient Linearizable Implementation of Shared FIFO Queues and General Objects on a Distributed System},
year={1998},
volume={E81-A},
number={5},
pages={768-775},
abstract={We consider linearizable implementations of shared FIFO queues and general deterministic objects on a distributed message-passing system which provides a real-time timer. The efficiency of an implementation is measured by the worst-case 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 [d-u,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 ack-type operation op_a and res_time(op_v)=2d for any val-type operation op_v, where an ack-type operation is an operation which always returns a unique response and a val-type operation is an operation which is not ack-type. 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(n-1)/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.},
keywords={},
doi={},
ISSN={},
month={May},}

Copy

TY - JOUR
TI - Efficient Linearizable Implementation of Shared FIFO Queues and General Objects on a Distributed System
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 768
EP - 775
AU - Michiko INOUE
AU - Toshimitsu MASUZAWA
AU - Nobuki TOKURA
PY - 1998
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E81-A
IS - 5
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - May 1998
AB - We consider linearizable implementations of shared FIFO queues and general deterministic objects on a distributed message-passing system which provides a real-time timer. The efficiency of an implementation is measured by the worst-case 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 [d-u,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 ack-type operation op_a and res_time(op_v)=2d for any val-type operation op_v, where an ack-type operation is an operation which always returns a unique response and a val-type operation is an operation which is not ack-type. 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(n-1)/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.
ER -