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

摘要

We consider linearizable implementations of shared FIFO queues an general deterministic objects on a dis- tributed 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 imple- mented objects. We show the following results under the assump- tion 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_v) = u for any ack-type operation op_a an 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 opera- tion which is not ack-type.