Asynchrony (due to unknown message transmission delay) complicates the design of protocols for distributed systems. To simplify the protocol design task therefore, the authors propose an interprocess (point-to-point) communication mechanism that has the characteristic of instantaneous message passing. They first establish a hierarchy among synchronization properties, which shows that to ensure the logically instantaneous message passing property it is not always necessary to use a rendezvous mechanism. Next, they propose a solution to the logically instantaneous message passing problem that is more efficient than R. Bagrodia's (1989) rendezvous and K.J. Goldman's (1991) logically synchronous multicast in the point-to-point (single-cast) setting. This algorithm has the following properties: it is applicable without deadlock to the partner model in which each process acts as both client and server; it requires three control messages to send an application message, which is shown to be quasioptimum message complexity; and its worst-case response time from a send request to the occurrence of the corresponding send event is 2k/spl Delta/ (sec.), where k is the maximum number of interfering send requests and /spl Delta/ (sec.) is an assumed upper bound on interprocess communication delay. Furthermore, two modified algorithms are proposed: one for reducing the number of control messages required for an application message, and the other for attaining a shorter average response time by using a randomization technique.
展开▼
