Preserving and using context information in interprocess communication

ABSTRACT

When processes in a network communicate, the messages they exchange define a partial ordering of externally visible events. While the significance of this partial order in distributed computing is well understood, it has not been made an explicit part of the communication substrate upon which distributed programs are implemented. This paper describes a new interprocess communication mechanism, called Psync, that explicitly encodes this partial ordering with each message. The paper shows how Psync can be efficiently implemented on an unreliable communications network, and it demonstrates how conversations serve as an elegant foundation for ordering messages exchanged in a distributed computation and for recovering from processor failures.

REFERENCES

• 1: L. Peterson , N. Hutchinson , S. O'Malley , M. Abbott, RPC in the x-Kernel: evaluating new design techniques, Proceedings of the twelfth ACM symposium on Operating systems principles, p.91-101, November 1989
• 2: AHO, A., GARE~, M., AND ULLMAN, J. The transitive reduction of a directed graph. SIAM J. Comput. (1972), 131-137.
• 3: Kenneth P. Birman , Thomas A. Joseph, Reliable communication in the presence of failures, ACM Transactions on Computer Systems (TOCS), v.5 n.1, p.47-76, Feb. 1987 [doi>10.1145/7351.7478]
• 4: K. Birman , T. Joseph, Exploiting virtual synchrony in distributed systems, Proceedings of the eleventh ACM Symposium on Operating systems principles, p.123-138, November 08-11, 1987, Austin, Texas, United States
• 5: Andrew D. Birrell , Bruce Jay Nelson, Implementing remote procedure calls, ACM Transactions on Computer Systems (TOCS), v.2 n.1, p.39-59, February 1984 [doi>10.1145/2080.357392]
• 6: Nicholas Carriero , David Gelernter, The S/Net's Linda kernel, ACM Transactions on Computer Systems (TOCS), v.4 n.2, p.110-129, May 1986 [doi>10.1145/214419.214420]
• 7: Jo-Mei Chang , N. F. Maxemchuk, Reliable broadcast protocols, ACM Transactions on Computer Systems (TOCS), v.2 n.3, p.251-273, Aug. 1984 [doi>10.1145/989.357400]
• 8: David R. Cheriton , Willy Zwaenepoel, Distributed process groups in the V Kernel, ACM Transactions on Computer Systems (TOCS), v.3 n.2, p.77-107, May 1985 [doi>10.1145/214438.214439]
• 9: D Cheriton, VMTP: a transport protocol for the next generation of communication systems, Proceedings of the ACM SIGCOMM conference on Communications architectures & protocols, p.406-415, August 05-07, 1986, Stowe, Vermont, United States
• 10: CRISTIAN, F. Agreeing on who is present and who is absent in synchronous distributed systems. In Digest of Papers, Fault Tolerant Computing Systems 18. IEEE Computer Society Press, New York, June 1988, 206-211.
• 11: David K. Gifford , Nathan Glasser, Remote pipes and procedures for efficient distributed communication, ACM Transactions on Computer Systems (TOCS), v.6 n.3, p.258-283, Aug. 1988 [doi>10.1145/45059.45061]
• 12: Jim Gray, Notes on Data Base Operating Systems, Operating Systems, An Advanced Course, p.393-481, January 1978
• 13: M. Herlihy, Extending multiversion time-spaning protocols to exploit type information, IEEE Transactions on Computers, v.36 n.4, p.443-448, April 1987 [doi>10.1109/TC.1987.1676926]
• 14: N. Hutchinson , L. Peterson, Design of the x-kernel, Symposium proceedings on Communications architectures and protocols, p.65-75, August 16-18, 1988, Stanford, California, United States
• 15: JOHNSON, D., AND ZWAENEPOEL. Sender-based message logging. In Proceedings of the Seventeenth International Symposium on Fault-Tolerant Computing (June 1987), pp. 14-19.
• 16: David B. Johnson , Willy Zwaenepoel, Recovery in distributed systems using asynchronous message logging and checkpointing, Proceedings of the seventh annual ACM Symposium on Principles of distributed computing, p.171-181, August 15-17, 1988, Toronto, Ontario, Canada [doi>10.1145/62546.62575]
• 17: Leslie Lamport, Time, clocks, and the ordering of events in a distributed system, Communications of the ACM, v.21 n.7, p.558-565, July 1978 [doi>10.1145/359545.359563]
• 18: MISHRA, S., PETERSON, L., AND SCHLICHTING, R. implementing fault-tolerant replicated objects using Psync. To appear in the 8th Symposium on Reliable Distributed Systems, Oct. 1989.
• 19: POSTEL, J. User datagram protocol. In Request For Comments 768, USC Information Sciences Institute, Marina del Rey, Calif., Aug. 1980.
• 20: POSTEL, J. Internet protocol. In Request For Comments 791, USC Information Sciences Institute, Marina del Rey, Calif., Sept. 1981.
• 21: POSTEL, J. Simple mail transfer protocol. In Request/or Comments 821, USC Information Sciences Institute, Marina del Rey, Calif., Aug. 1982.
• 22: Michael L. Powell , David L. Presotto, Publishing: a reliable broadcast communication mechanism, Proceedings of the ninth ACM symposium on Operating systems principles, p.100-109, October 10-13, 1983, Bretton Woods, New Hampshire, United States
• 23: J. H. Saltzer , D. P. Reed , D. D. Clark, End-to-end arguments in system design, ACM Transactions on Computer Systems (TOCS), v.2 n.4, p.277-288, Nov. 1984 [doi>10.1145/357401.357402]
• 24: Rob Strom , Shaula Yemini, Optimistic recovery in distributed systems, ACM Transactions on Computer Systems (TOCS), v.3 n.3, p.204-226, Aug. 1985 [doi>10.1145/3959.3962]
• 25: STROM, R., BACON, D., AND YEMINI, S. Volatile logging in n-fault-tolerant distributed systems. In Proceedings of the Eighteenth International Symposium on Fault-Tolerant Computing (June 1988), to appear.
• 26: Fred B. Schneider, Synchronization in Distributed Programs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.4 n.2, p.125-148, April 1982 [doi>10.1145/357162.357163]
• 27: A. S. Tanenbaum, Computer networks, Prentice-Hall, Inc., Upper Saddle River, NJ, 1988
• 28: USC INFORMATION SCIENCES INSTITUTE. Transmission control protocol. In Request For Comments 793, Marina del Rey, Calif., Sept. 1981.
• 29: Willy Zwaenepoel, Protocols for large data transfers over local networks, Proceedings of the ninth symposium on Data communications, p.22-32, September 1985, Whistler Moutain, British Columbia, Canada

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols

          Nouns: Psync

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Design studies

  D. Software
  D.4 OPERATING SYSTEMS
      D.4.4 Communications Management
          Subjects: Network communication

General Terms:
Design, Performance, Reliability