We consider linearizable implementations of shared FIFO queues angeneral deterministic objects on a dis- tributed message-passingsystem which provides a real-time timer. The efficiency of animplementation is measured by the worst-case response timeres-time(op) for each operation op of the imple- mented objects. Weshow the following results under the assump- tion that all messagedelays are in the range d － u, d for some constants d and u (0 ≤u ≤d). We first present an implementation of deterministic objectswith res_time(op_v) = u for any ack-type operation op_a anres_time(op_v) = 2d for any val-type operation op_v, where anack-type operation is an operation which always returns a uniqueresponse and a val-type operation is an opera- tion which is notack-type.
展开▼
机译：我们考虑共享FIFO队列的线性化实现，即分布式消息传递系统上的一般确定性对象，该系统提供实时计时器。实现的效率是通过实现对象的每个操作操作的最坏情况响应时间（op）来衡量的。假设所有消息延迟都在某些常量 d 和 u （0 ≤u ≤d） 范围内，我们显示了以下结果。我们首先提出了一个确定性对象的实现，对于任何 ack 类型的操作，res_time（op_v） = u op_a anres_time（op_v） = 2d 对于任何 val 类型的操作op_v，其中 anack 类型的操作是始终返回唯一响应的操作，而 val 类型的操作是 notack 类型的操作。
展开▼
