Coyote: a system for constructing fine-grain configurable communication services

ABSTRACT

Communication-oriented abstractions such as atomic multicast, group RPC, and protocols for location-independent mobile computing can simplify the development of complex applications built on distributed systems. This article describes Coyote, a system that supports the construction of highly modular and configurable versions of such abstractions. Coyote extends the notion of protocol objects and hierarchical composition found in existing systems with support for finer-grain microprotocol objects and a nonhierarchical composition scheme for use within a single layer of a protocol stack. A customized service is constructed by selecting microprotocols based on their semantic guarantees and configuring them together with a standard runtime system to form a composite protocol implementing the service. This composite protocol is then composed hierarchically with other protocols to form a complete network subsystem. The overall approach is described and illustrated with examples of services that have been constructed using Coyote, including atomic multicast, group RPC, membership, and mobile computing protocols. A prototype implementation based on extending x-kernel version 3.2 running on Mach 3.0 with support for microprotocols is also presented, together with performance results from a suite of microprotocols from which over 60 variants of group RPC can be constructed.

REFERENCES

• 1: Mark B. Abbott , Larry L. Peterson, Increasing network throughput by integrating protocol layers, IEEE/ACM Transactions on Networking (TON), v.1 n.5, p.600-610, Oct. 1993 [doi>10.1109/90.251918]
• 2: ABDELZAHER, T., DAWSON, S., FENG, W., GHOSH, S., JAHANIAN, F., JOHNSON, S., MEHRA, A., MITTON, T., NORTON, J., SHAIKH, A., SHIN, K., VAIDYAN, V., WANG, Z., AND ZOU, g. 1997. ARMADA middleware suite. In Proceedings of the IEEE Workshop on Middleware for Distributed Real-time Systems and Services (San Francisco, CA, Dec.). IEEE Computer Society Press, Los Alamitos, CA, 11-18.
• 3: T. Abdelzaher , A. Shaikh , F. Jahanian , K. Shin, RTCAST: lightweight multicast for real-time process groups, Proceedings of the 2nd IEEE Real-Time Technology and Applications Symposium (RTAS '96), p.250, June 10-12, 1996
• 4: ACHARYA, A. AND BADRINATH, B. 1993. Delivering multicast messages in networks with mobile hosts. In Proceedings of 13th IEEE International Conference on Distributed Computing Systems. IEEE Press, Piscataway, NJ, 292-299.
• 5: ADAMS, N., GOLD, R., SCHILIT, B., AND WANT, R. 1993. An infrared network for mobile computers. In Proceedings of the USENIX Mobile and Location-Independent Computing Symposium. USENIX Assoc., Berkeley, CA, 41-51.
• 6: AGHA, G. AND STURMAN, D. 1994. A methodology for adapting to patterns of faults. In Foundations of Dependable Computing: Models and Frameworks for Dependable Systems, Koob, G. and Lau, C., Eds. Kluwer Academic Publishers, Hingham, MA, 23-60.
• 7: Sudhir Ahuja , Nicholas Carriero , David Gelernter, Linda and friends, Computer, v.19 n.8, p.26-34, Aug. 1986 [doi>10.1109/MC.1986.1663305]
• 8: BADRINATH, B., BAKRE, A., IMIELINSKI, T., AND MARANTZ, R. 1993. Handling mobile clients: A case for indirect interaction. In Proceedings of the 4th Workshop on Workstation Operating Systems (Napa, CA, Oct.).
• 9: David Edward Bakken , Richard D. Schlichting, Supporting Fault-Tolerant Parallel Programming in Linda, IEEE Transactions on Parallel and Distributed Systems, v.6 n.3, p.287-302, March 1995 [doi>10.1109/71.372777]
• 10: BARRERA, J. 1991. A fast Mach network IPC implementation. In Proceedings of the USENIX Mach Symposium. USENIX Assoc., Berkeley, CA, 1-12.
• 11: Philip A. Bernstein , Vassco Hadzilacos , Nathan Goodman, Concurrency control and recovery in database systems, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1987
• 12: B. N. Bershad , S. Savage , P. Pardyak , E. G. Sirer , M. E. Fiuczynski , D. Becker , C. Chambers , S. Eggers, Extensibility safety and performance in the SPIN operating system, Proceedings of the fifteenth ACM symposium on Operating systems principles, p.267-283, December 03-06, 1995, Copper Mountain, Colorado, United States
• 13: Nina Trappe Bhatti , Richard D. Schlichting, A system for constructing configurable high-level protocols, 1996
• 14: André Schiper , Kenneth Birman , Pat Stephenson, Lightweight causal and atomic group multicast, ACM Transactions on Computer Systems (TOCS), v.9 n.3, p.272-314, Aug. 1991 [doi>10.1145/128738.128742]
• 15: Andrew P. Black, Understanding transactions in the operating system context, ACM SIGOPS Operating Systems Review, v.25 n.1, p.73-76, Jan. 1991 [doi>10.1145/122140.122149]
• 16: BROWN, N. AND KINDEL, C. 1998. Distributed component object model protocol--DCOM/1.0. Network Working Group Internet Draft. Microsoft Corp., Redmond, WA.
• 17: CAO, P., FELTEN, E., AND LI, K. 1994. Implementation and performance of applicationcontrolled file caching. In Proceedings of the 1st USENIX Symposium on Operating Systems Design and Implementation (OSDI '94, Monterey, CA, Nov.). USENIX Assoc., Berkeley, CA, 165-178.
• 18: Tushar Deepak Chandra , Sam Toueg, Unreliable failure detectors for reliable distributed systems, Journal of the ACM (JACM), v.43 n.2, p.225-267, March 1996 [doi>10.1145/226643.226647]
• 19: 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
• 20: CMELIK, R., GEHANI, N., AND ROOME, W. 1988. Fault tolerant concurrent C: A tool for writing fault tolerant distributed programs. In Proceedings of the 18th IEEE International Symposium on Fault-Tolerant Computing (Tokyo, Japan, June). IEEE Press, Piscataway, NJ, 55-61.
• 21: COMER, D. AND RUSSO, V. 1994. Using ATM for a campus-wide wireless internetwork. In Proceedings of the IEEE Workshop on Mobile Computing Systems and Applications (Santa Cruz, CA). IEEE Press, Piscataway, NJ.
• 22: COMER, D., LIN, J., AND RUSSO, V. 1995. An architecture for a campus-scale wireless mobile internet. Tech. Rep. CSD-TR95-058. Purdue University, West Lafayette, IN.
• 23: CONDICT, M., BOLINGER, D., MCMANUS, E., MITCHELL, D., AND LEWONTIN, S. 1994. Microkernel modularity with integrated kernel performance. Tech. Rep.. OSF Research Institute, Cambridge, MA.
• 24: R. L. Constable , S. F. Allen , H. M. Bromley , W. R. Cleaveland , J. F. Cremer , R. W. Harper , D. J. Howe , T. B. Knoblock , N. P. Mendler , P. Panangaden , J. T. Sasaki , S. F. Smith, Implementing mathematics with the Nuprl proof development system, Prentice-Hall, Inc., Upper Saddle River, NJ, 1986
• 25: COOPER, E. 1990. Programming language support for multicast communication in distributed systems. In Proceedings of the l Oth International Conference on Distributed Computing Systems. 450-457.
• 26: CRISTIAN, F. 1991. Reaching agreement on processor group membership in synchronous distributed systems. Distrib. Comput. 4, 175-187.
• 27: CRISTIAN, F., AGHILI, H., STRONG, R., AND DOLEV, D. 1985. Atomic broadcast: From simple message diffusion to Byzantine agreement. In Proceedings of the 15th IEEE International Symposium on Fault-Tolerant Computing (Ann Arbor, MI, June). IEEE Press, Piscataway, NJ, 200-206.
• 28: D. R. Engler , M. F. Kaashoek , J. O'Toole, Jr., Exokernel: an operating system architecture for application-level resource management, Proceedings of the fifteenth ACM symposium on Operating systems principles, p.251-266, December 03-06, 1995, Copper Mountain, Colorado, United States
• 29: Jean-Charles Fabre , Tanguy Pérennou, A Metaobject Architecture for Fault-Tolerant Distributed Systems: The FRIENDS Approach, IEEE Transactions on Computers, v.47 n.1, p.78-95, January 1998 [doi>10.1109/12.656088]
• 30: Michael J. Fischer , Nancy A. Lynch , Michael S. Paterson, Impossibility of distributed consensus with one faulty process, Journal of the ACM (JACM), v.32 n.2, p.374-382, April 1985 [doi>10.1145/3149.214121]
• 31: FONSECA, H. 1994. Support environments for the modularization, implementation and execution of communication protocols. Master's Thesis. Instituto Superior T~cnico, Lisboa, Portugal.
• 32: Murray W. Goldberg , Gerald W. Neufeld , Mabo R. Ito, The Parallel Protocol Framework, University of British Columbia, Vancouver, BC, Canada, 1992
• 33: Richard Andrew Golding, Weak-consistency group communication and membership, University of California at Santa Cruz, Santa Cruz, CA, 1992
• 34: Douglas P. Ghormley , Steven H. Rodrigues , David Petrou , Thomas E. Anderson, Interposition as an Operating System Extension Mechanism, University of California at Berkeley, Berkeley, CA, 1997
• 35: Graham Hamilton , Michael L. Powell , James G. Mitchell, Subcontract: a flexible base for distributed programming, Proceedings of the fourteenth ACM symposium on Operating systems principles, p.69-79, December 05-08, 1993, Asheville, North Carolina, United States
• 36: Mark Hayden, The Ensemble System, Cornell University, Ithaca, NY, 1998
• 37: Mark Hayden , Robbert Van Renesse, Optimizing Layered Communication Protocols, Proceedings of the 6th International Symposium on High Performance Distributed Computing (HPDC '97), p.169, August 05-08, 1997
• 38: A. J. Herbert, The ANSA project and standards, Distributed systems, ACM Press, New York, NY, 1990 [doi>10.1145/90417.90753]
• 39: HERBERT, A. 1994. An ANSA overview. IEEE Network 8, 1 (Jan.).
• 40: HILTUNEN, M. 1996. Configurable distributed fault-tolerant services. Ph.D. Dissertation. Department of Computer Science, University of Arizona, Tucson, AZ.
• 41: HILTUNEN, M. AND SCHLICHTING, R. 1993. An approach to constructing modular fault-tolerant protocols. In Proceedings of the 12th IEEE Symposium on Reliable Distributed Systems (Princeton, NJ, Oct.). IEEE Press, Piscataway, NJ, 105-114.
• 42: M. A. Hiltunen , R. D. Schlichting, Constructing a configurable group RPC service, Proceedings of the 15th International Conference on Distributed Computing Systems, p.288, May 30-June 02, 1995
• 43: HILTUNEN, M. AND SCHLICHTING, R. 1995b. Properties of membership services. In Proceedings of the 2nd IEEE Symposium on Autonomous Decentralized Systems (Phoenix, AZ, Apr.). IEEE Press, Piscataway, NJ, 200-207.
• 44: HILTUNEN, M. AND SCHLICHTING, R. 1995c. Understanding membership. Tech. Rep. 95-07. Department of Computer Science, University of Arizona, Tucson, AZ.
• 45: HILTUNEN, M. AND SCHLICHTING, R. 1996. Adaptive distributed and fault-tolerant systems. Comput. Syst. Sci. Eng. 11, 5 (Sept), 125-133.
• 46: Matti A. Hiltunen , Richard D. Schlichting, A Configurable Membership Service, IEEE Transactions on Computers, v.47 n.5, p.573-586, May 1998 [doi>10.1109/12.677244]
• 47: Norman C. Hutchinson , Larry L. Peterson, The X-Kernel: An Architecture for Implementing Network Protocols, IEEE Transactions on Software Engineering, v.17 n.1, p.64-76, January 1991 [doi>10.1109/32.67579]
• 48: Ralf Keller , Wolfgang Effelsberg, MCAM: an application layer protocol for movie control, access, and management, Proceedings of the first ACM international conference on Multimedia, p.21-29, August 02-06, 1993, Anaheim, California, United States [doi>10.1145/166266.166268]
• 49: KOPETZ, g., GRUNSTEIDL, G., AND REISINGER, J. 1991. Fault-tolerant membership service in a synchronous distributed real-time system. In Dependable Computing for Critical Applications, Avizienis, A. and Laprie, J. C., Eds. Springer-Verlag, Vienna, Austria, 411-429.
• 50: M. T. Le , F. Burghardt , S. Seshan , J. Rabaey, InfoNet: The networking infrastructure of InfoPad, Proceedings of the 40th IEEE Computer Society International Conference, p.163, March 05-09, 1995
• 51: LE, M., SESHAN, S., BURGHARDT, F., AND RABAEY, J. 1994. Software architecture of the InfoPad system. In Proceedings of the Mobidata Workshop on Mobile and Wireless Information Systems (Rutgers, NJ, Nov.).
• 52: LINDGREN, B., AMMAR, M., KRUPCZAK, B., AND SCHWAN, K. 1993. Parallel and configurable protocols: Experiences with a prototype and an architectural framework. In Proceedings of the International Conference on Network Protocols.
• 53: P. M. Melliar-Smith , L. E. Moser , V. Agrawala, Broadcast Protocols for Distributed Systems, IEEE Transactions on Parallel and Distributed Systems, v.1 n.1, p.17-25, January 1990 [doi>10.1109/71.80121]
• 54: MICROSOFT. 1995. The Component Object Model Specification (version 0.9). Microsoft Corp., Redmond, WA.
• 55: MISHRA, S., PETERSON, L., AND SCHLICHTING, R. 1992. A membership protocol based on partial order. In Dependable Computing for Critical Applications 2, Schlichting, R. and Meyer, J., Eds. Springer-Verlag, Vienna, Austria, 309-331.
• 56: MISHRA, S., PETERSON, L., AND SCHLICHTING, R. 1993a. Consul: A communication substrate for fault-tolerant distributed programs. Distrib. Syst. Eng. 1, 3, 87-103.
• 57: Shivakant Mishra , Larry L. Peterson , Richard D. Schlichting, Experience with modularity in consul, Software—Practice & Experience, v.23 n.10, p.1059-1075, Oct. 1993 [doi>10.1002/spe.4380231002]
• 58: MONTZ, A., MOSBERGER, D., O'MALLEY, S., PETERSON, L., PROEBSTING, T., AND HARTMAN, J. 1994. Scout: A communications-oriented operating system. In Proceedings of the 1st USENIX Symposium on Operating Systems Design and Implementation (OSDI '94, Monterey, CA, Nov.). USENIX Assoc., Berkeley, CA.
• 59: David Mosberger , Larry L. Peterson, Making paths explicit in the Scout operating system, Proceedings of the second USENIX symposium on Operating systems design and implementation, p.153-167, October 29-November 01, 1996, Seattle, Washington, United States
• 60: L. E. Moser , P. M. Melliar-Smith , D. A. Agarwal , R. K. Budhia , C. A. Lingley-Papadopoulos, Totem: a fault-tolerant multicast group communication system, Communications of the ACM, v.39 n.4, p.54-63, April 1996 [doi>10.1145/227210.227226]
• 61: Unification of Active and Passive Objects in an Object-Oriented Operating System, Proceedings of the 4th International Workshop on Object-Orientation in Operating Systems, p.68, August 14-15, 1995
• 62: Hilarie Orman , Sean W. O'Malley , Edwin Menze, III , Larry L. Peterson , Richard Schroeppel, A Fast and General Implementation of Mach IPC in a Network, USENIX MACH III Symposium, p.75-88, April 19-21, 1993
• 63: OBJECT MANAGEMENT GROUP. 1997. CORBAservices: Common Object Services Specification (updated). Object Management Group.
• 64: OBJECT MANAGEMENT GROUP. 1998. The Common Object Request Broker: Architecture and Specification. Object Management Group.
• 65: OLSEN, M., OSKIEWICZ, E., AND WARNE, J. 1991. A model for interface groups. In Proceedings of the lOth IEEE Symposium on Reliable Distributed Systems (Pisa, Italy, Sept.). IEEE Press, Piscataway, NJ, 98-107.
• 66: Sean W. O'Malley , Larry L. Peterson, A dynamic network architecture, ACM Transactions on Computer Systems (TOCS), v.10 n.2, p.110-143, May 1992 [doi>10.1145/128899.128901]
• 67: Larry L. Peterson , Nick C. Buchholz , Richard D. Schlichting, Preserving and using context information in interprocess communication, ACM Transactions on Computer Systems (TOCS), v.7 n.3, p.217-246, Aug. 1989 [doi>10.1145/65000.65001]
• 68: RITCHIE, D.1984. A stream input-output system. AT&T Bell Lab. Tech. J. 63, 8 (Oct.), 311-324.
• 69: Laura Sabel , Keith Marzullo, Simulating fail-stop in asynchronous distributed systems, Proceedings of the thirteenth annual ACM symposium on Principles of distributed computing, p.399, August 14-17, 1994, Los Angeles, California, United States [doi>10.1145/197917.198181]
• 70: SCHILIT, B., THEIMER, M., AND WELCH, B. 1993. Customizing mobile applications. In Proceedings of the USENIX Mobile and Location-Independent Computing Symposium. USENIX Assoc., Berkeley, CA, 129-138.
• 71: SCHIPER, A. AND RICCIARDI, A. 1993. Virtually-synchronous communication based on a weak failure suspector. In Proceedings of the 23rd IEEE International Symposium on Fault- Tolerant Computing (Toulouse, France, June). IEEE Computer Society Press, Los Alamitos, CA, 534-543.
• 72: SCHMIDT, D. AND SUDA, T. 1994. The service configurator framework: An extensible architecture for dynamically configuring concurrent, multi-service network deamons. In Proceedings of the 2nd International Workshop on Configurable Distributed Systems (Pittsburgh, PA, Mar.). 190-201.
• 73: SCHMIDT, D., BOX, D., AND SUDA, T. 1993. ADAPTIVE: A dynamically assembled protocol transformation, integration, and evaluation environment. Concurrency: Pract. Exper. 5, 4 (June), 269-286.
• 74: Fred B. Schneider, Implementing fault-tolerant services using the state machine approach: a tutorial, ACM Computing Surveys (CSUR), v.22 n.4, p.299-319, Dec. 1990 [doi>10.1145/98163.98167]
• 75: Margo I. Seltzer , Yasuhiro Endo , Christopher Small , Keith A. Smith, Dealing with disaster: surviving misbehaved kernel extensions, Proceedings of the second USENIX symposium on Operating systems design and implementation, p.213-227, October 29-November 01, 1996, Seattle, Washington, United States
• 76: SUN MICROSYSTEMS. 1997. JavaBeans API Specification (version 1.01). Sun Microsystems, Inc., Mountain View, CA.
• 77: Franco Travostino , Ed Menze , Franklin Reynolds, Paths: Programming with System Resources in Support of Real-Time Distributed Applications, Proceedings of the 2nd Workshop on Object-Oriented Real-Time Dependable Systems (WORDS '96), p.36, February 01-02, 1996
• 78: Robbert van Renesse, Masking the overhead of protocol layering, Conference proceedings on Applications, technologies, architectures, and protocols for computer communications, p.96-104, August 28-30, 1996, Palo Alto, California, United States
• 79: Robbert van Renesse , Kenneth P. Birman , Roy Friedman , Mark Hayden , David A. Karr, A framework for protocol composition in Horus, Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing, p.80-89, August 20-23, 1995, Ottowa, Ontario, Canada [doi>10.1145/224964.224974]
• 80: Robbert van Renesse , Kenneth P. Birman , Silvano Maffeis, Horus: a flexible group communication system, Communications of the ACM, v.39 n.4, p.76-83, April 1996 [doi>10.1145/227210.227229]
• 81: Robbert Van Renesse , Takako M. Hickey , Kenneth P. Birman, Design and Performance of Horus: A Lightweight Group Communications System, Cornell University, Ithaca, NY, 1994
• 82: P. Veríssimo , L. Rodrigues , M. Baptista, AMp: a highly parallel atomic multicast protocol, Symposium proceedings on Communications architectures & protocols, p.83-93, September 25-27, 1989, Austin, Texas, United States
• 83: U. Wilhelm , A. Schiper, A hierarchy of totally ordered multicasts, Proceedings of the 14TH Symposium on Reliable Distributed Systems, p.106, September 13-15, 1995
• 84: YAVANTKAR, R. 1992. MCP: A protocol for coordination and temporal synchronization in multimedia collaborative applications. In Proceedings of the 12th IEEE Conference on Distributed Computing Systems (Yokohama, Japan, June). IEEE Press, Piscataway, NJ, 606-613.
• 85: Yasuhiko Yokote, The Apertos reflective operating system: the concept and its implementation, conference proceedings on Object-oriented programming systems, languages, and applications, p.414-434, October 18-22, 1992, Vancouver, British Columbia, Canada

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Protocol architecture (OSI model)

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Distributed applications

  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
          Subjects: Distributed programming
  D.2 SOFTWARE ENGINEERING
  D.4 OPERATING SYSTEMS
      D.4.4 Communications Management
          Subjects: Network communication
      D.4.5 Reliability
          Subjects: Fault-tolerance
      D.4.7 Organization and Design
          Subjects: Distributed systems

General Terms:
Design, Experimentation, Performance, Reliability

Keywords:
x-kernal, configurable sevices, customization, event handlers, event-driven execution, membership, microprotocols, mobile computing, modularity, multicast, protocols, remote procedure call