LOGICALLY INSTANTANEOUS MESSAGE-PASSING IN ASYNCHRONOUS DISTRIBUTED SYSTEMS

Asynchrony (due to unknown message transmission delay) complicates the design of protocols for distributed systems. To simplify he protocol design task, therefore this paper proposes an interprocess (point-to-p oint) communication mechanism that has the characteristic of instantan eous message passing. This paper first establishes a hierarchy among s ynchronization properties, which shows that to ensure the logically in stantaneous message passing property it is not always necessary to use a rendezvous mechanism. Next, this paper proposes a solution to the l ogically instantaneous message passing problem that is more efficient -than Bagrodia's rendezvous and Goldman's logically synchronous multic ast in the point-to-point (''single-cast'') setting. This algorithm ha s the following properties. 1) It is applicable without deadlock to th e partner model in which each process acts as both client and server. 2) It requires three control messages to send an application message, which is shown to be quasioptimum message complexity (i.e., at most on e larger than the lower bound). 3) Its worst-case response time from a send request to the occurrence of the corresponding send event is 2kD ELTA (sec.), where k is the maximum number of interfering send request s and DELTA (sec.) is an assumed upper bound on interprocess communica tion delay. Furthermore, two modified algorithms are proposed: one for reducing the number of control messages required for an application m essage, and the other for attaining a shorter average response time by using a randomization technique.