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.

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(opa)=u for any ack-type operation opa and res_time(opv)=2d for any val-type operation opv, 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.