Mace: language support for building distributed systems

ABSTRACT

Building distributed systems is particularly difficult because of the asynchronous, heterogeneous, and failure-prone environment where these systemsmust run. Tools for building distributed systems must strike a compromise between reducing programmer effort and increasing system efficiency. We present Mace, a C++ language extension and source-to-source compiler that translates a concise but expressive distributed system specification into a C++ implementation. Mace overcomes the limitations of low-level languages by providing a unified framework for networking and event handling, and the limitations of high-level languages by allowing programmers to write program components in a controlled and structured manner in C++. By imposing structure and restrictions on how applications can be written, Mace supports debugging at a higher level, including support for efficient model checking and causal-path debugging. Because Mace programs compile to C++, programmers can use existing C++ tools, including optimizers, profilers, and debuggers to analyze their systems.

References

1. Freepastry: an open-source implementation of pastry intended for deployment in the internet. http://freepastry.rice.edu, 2006.
2. AGUILERA, M. K., MOGUL, J. C., WIENER, J. L., REYNOLDS, P., AND MUTHITACHAROEN, A. Performance debugging for distributed systems of black boxes. In Proc. SOSP (2003).
3. ANDERSON, D. P. Automated protocol implementation with RTAG. IEEE Trans. Software Eng. 14, 3 (1988), 291--300.
4. BARHAM, P. T., ISAACS, R., MORTIER, R., AND NARAYANAN, D. Magpie: Online modelling and performance-aware systems. In Proc. HotOS (2003).
5. BOLOGNESI, T., AND BRINKSMA, E. Introduction to the ISO specification language LOTOS. Computer Networks 14 (1987).
6. BUDKOWSKI, S., AND DEMBINSKI, P. An introduction to Estelle: A specification language for distributed systems. Computer Networks 14 (1987), 3--23.
7. CASTRO, M., DRUSCHEL, P., KERMARREC, A.-M., NANDI, A., ROWSTRON, A., AND SINGH, A. SplitStream: High-bandwidth content distribution in cooperative environments. In Proc. SOSP (2003).
8. CHEN, M. Y., KICIMAN, E., FRATKIN, E., FOX, A., AND BREWER, E. Pinpoint: Problem determination in large, dynamic internet services. In Proc. DSN (2002).
9. DABEK, F., COX, R., KAASHOEK, F., AND MORRIS, R. Vivaldi: A decentralized network coordinate system. In Proceedings of the ACM SIGCOMM '04 Conference (Portland, Oregon, 2004).
10. DABEK, F., KAASHOEK, M. F., KARGER, D., MORRIS, R., AND STOICA, I. Wide-area cooperative storage with cfs. In SOSP '01: Proceedings of the eighteenth ACM symposium on Operating systems principles (New York, NY, USA, 2001), ACM Press, pp. 202--215.
11. FORD, B., BACK, G., BENSON, G., LEPREAU, J., LIN, A., AND SHIVERS, O. The Flux OSKit: A substrate for kernel and language research. In Proc. SOSP (1997).
12. GAY, D., LEVIS, P., VON BEHREN, R., WELSH, M., BREWER, E., AND CULLER, D. The nesC language: A holistic approach to networked embedded systems. In Proc. PLDI (2003).
13. GODEFROID, P. Model checking for programming languages using VeriSoft. In Proc. POPL (1997).
14. HOLZMANN, G. The Spin Model Checker: Primer and Reference Manual. Addison-Wesley, 2003.
15. JANNOTTI, J., GIFFORD, D. K., JOHNSON, K. L., KAASHOEK, M. F., AND JAMES W. O'TOOLE, J. Overcast: Reliable multicasting with an overlay network. In Proc. OSDI (2000).
16. KICZALES, G. Aspect-oriented programming. ACM Computing Surveys 28, 4es (1996).
17. KILLIAN, C., ANDERSON, J. W., JHALA, R., AND VAHDAT, A. Life, death, and the critical transition: Detecting liveness bugs in systems code. In NSDI (2007).
18. KOHLER, E., KAASHOEK, M. F., AND MONTGOMERY, D. R. A readable TCP in the Prolac protocol language. In Proc. SIGCOMM (1999).
19. KOHLER, E., MORRIS, R., CHEN, B., JANNOTTI, J., AND KAASHOEK, M. F. The Click modular router. ACM TOCS 18, 3 ý(2000), 263--297.
20. KOSTIÝC, D., BRAUD, R., KILLIAN, C., VANDEKIEFT, E., ANDERSON, J. W., SNOEREN, A. C., AND VAHDAT, A. Maintaining high bandwidth under dynamic network conditions. In Proc. USENIX Tech (Anaheim, CA, Apr. 2005).
21. LAMPORT, L. Specifying Systems: the Tla+ Language and Tools for Hardware and Software Engineers. Addison-Wesley, 2002.
22. LOO, B. T., CONDIE, T., HELLERSTEIN, J. M., MANIATIS, P., ROSCOE, T., AND STOICA, I. Implementing declarative overlays. In Proc. SOSP (2005).
23. LOPES, C. D: A Language Framework for Distributed Programming. PhD thesis, Northeastern University, 1996.
24. LYNCH, N. Distributed Algorithms. Morgan Kaufmann, 1996.
25. MAZIERES, D. A toolkit for user-level file systems. In Proc. USENIX Tech (2001).
26. MILNER, R. Communication and Concurrency. Prentice-Hall, 1989.
27. MUTHITACHAROEN, A., MORRIS, R., GIL, T. M., AND CHEN, B. Ivy: a read/write peer-to-peer file system. In OSDI '02: Proceedings of the 5th symposium on Operating systems design and implementation (New York, NY, USA, 2002), ACM Press, pp. 31--44.
28. PETERSON, L., ANDERSON, T., CULLER, D., AND ROSCOE, T. A Blueprint for Introducing Disruptive Technology into the Internet. In Proceedings of the 1st Workshop on Hot Topics in Networks (HotNets-I) (Princeton, New Jersey, 2002).
29. REYNOLDS, P., KILLIAN, C., WIENER, J. L., MOGUL, J. C., SHAH, M. A., AND VAHDAT, A. Pip: Detecting the unexpected in distributed systems. In NSDI (2006).
30. RHEA, S., GEELS, D., ROSCOE, T., AND KUBIATOWICZ, J. Handling churn in a dht. In USENIX Tech (2004).
31. RODRIGUEZ, A., KILLIAN, C., BHAT, S., KOSTIÝC, D., AND VAHDAT, A. MACEDON: Methodology for automatically creating, evaluating, and designing overlay networks. In Proc. NSDI (2004).
32. ROWSTRON, A., AND DRUSCHEL, P. Pastry: Scalable, distributed object location and routing for large-scale peer-to-peer systems. In Proc. Middleware 2001 (2001).
33. ROWSTRON, A., KERMARREC, A.-M., CASTRO, M., AND DRUSCHEL, P. SCRIBE: The design of a large-scale event notification infrastructure. In Proc. Third InternationalWorkshop on NGC (2001).
34. SEWELL, P., LEIFER, J. J., WANSBROUGH, K., NARDELLI, F. Z., ALLEN-WILLIAMS, M., HABOUZIT, P., AND VAFEIADIS, V. Acute: high-level programming language design for distributed computation. In Proc. ICFP (2005).
35. STOICA, I., MORRIS, R., KARGER, D., KAASHOEK, F., AND BALAKRISHNAN, H. Chord: A scalable peer to peer lookup service for internet applications. In Proc. SIGCOMM (2001).
36. VAHDAT, A., YOCUM, K., WALSH, K., MAHADEVAN, P., KOSTIÝC, D., CHASE, J., AND BECKER, D. Scalability and Accuracy in a Large-Scale Network Emulator. In Proc. OSDI (2002).
37. WELSH, M., CULLER, D., AND BREWER, E. SEDA: an architecture for well-conditioned, scalable internet services. In Proc. SOSP (2001).

Index Terms

• Software and its engineering

  • Software notations and tools

    • Context specific languages

      • Specialized application languages