Modularity: a first class concept to address distributed systems

ABSTRACT

Decomposing distributed systems into modules, each with a precise interface and a functional implementation independent specification, is highly effective both from a software engineering point of view and for theoretical purposes. The usefulness of this approach has been demonstrated in the past in several areas of distributed computing. Yet, despite its attractiveness, so far work on peer to peer systems failed to do so. This paper argues in favor of this approach and advocates such a decomposition for peer to peer systems. This allows designers to understand and explain both what a system does and how it does it.

REFERENCES

• 1: http://www.gnutella.com/
• 2: Hagit Attiya , Amotz Bar-Noy , Danny Dolev, Sharing memory robustly in message-passing systems, Journal of the ACM (JACM), v.42 n.1, p.124-142, Jan. 1995 [doi>10.1145/200836.200869]
• 3: Hagit Attiya , Jennifer L. Welch, Sequential consistency versus linearizability, ACM Transactions on Computer Systems (TOCS), v.12 n.2, p.91-122, May 1994 [doi>10.1145/176575.176576]
• 4: Bonnet F., Kermarrec A.-M. and Raynal M., Small-world networks: from theoretical bounds to practical systems. Proc. 11th Int'l Conference On Principles Of Distributed Systems (OPODIS'07), Springer-Verlag LNCS 4878, pp. 372--385, 2007.
• 5: 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]
• 6: Flaviu Cristian , Christof Fetzer, The Timed Asynchronous Distributed System Model, IEEE Transactions on Parallel and Distributed Systems, v.10 n.6, p.642-657, June 1999 [doi>10.1109/71.774912]
• 7: Dabek F., Zhao B., Druschel P., Kubiatowicz J., and Stoica I., Towards a common API for structured peer to peer overlays. Proc. 2nd Int'l Workshop on peer to peer Systems (IPTPS '03), Berkeley, CA, 2003.
• 8: Cynthia Dwork , Nancy Lynch , Larry Stockmeyer, Consensus in the presence of partial synchrony, Journal of the ACM (JACM), v.35 n.2, p.288-323, April 1988 [doi>10.1145/42282.42283]
• 9: P. Th. Eugster , R. Guerraoui , S. B. Handurukande , P. Kouznetsov , A.-M. Kermarrec, Lightweight probabilistic broadcast, ACM Transactions on Computer Systems (TOCS), v.21 n.4, p.341-374, November 2003 [doi>10.1145/945506.945507]
• 10: 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]
• 11: Ayalvadi J. Ganesh , Anne-Marie Kermarrec , Laurent Massoulié, Peer-to-Peer Membership Management for Gossip-Based Protocols, IEEE Transactions on Computers, v.52 n.2, p.139-149, February 2003 [doi>10.1109/TC.2003.1176982]
• 12: Kourosh Gharachorloo , Daniel Lenoski , James Laudon , Phillip Gibbons , Anoop Gupta , John Hennessy, Memory consistency and event ordering in scalable shared-memory multiprocessors, Proceedings of the 17th annual international symposium on Computer Architecture, p.15-26, May 28-31, 1990, Seattle, Washington, United States
• 13: Alex Gontmakher , Assaf Schuster, Java consistency: nonoperational characterizations for Java memory behavior, ACM Transactions on Computer Systems (TOCS), v.18 n.4, p.333-386, Nov. 2000 [doi>10.1145/362670.362673]
• 14: James Gosling , Bill Joy , Guy L. Steele, The Java Language Specification, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1996
• 15: Jelasity M. and Babaoglu O., T-Man: Gossip-Based Overlay Topology Management Engineering Self-Organising Systems, 1(15), 2005.
• 16: Márk Jelasity , Spyros Voulgaris , Rachid Guerraoui , Anne-Marie Kermarrec , Maarten van Steen, Gossip-based peer sampling, ACM Transactions on Computer Systems (TOCS), v.25 n.3, p.8-es, August 2007 [doi>10.1145/1275517.1275520]
• 17: Jon Kleinberg, The small-world phenomenon: an algorithm perspective, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.163-170, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335325]
• 18: Leslie Lamport, Composition: A Way to Make Proofs Harder, Revised Lectures from the International Symposium on Compositionality: The Significant Difference, p.402-423, September 08-12, 1997
• 19: Mostefaoui A., Mourgaya E., and Raynal M., Asynchronous implementation of failure detectors. Proc. Int'l IEEE Conference on Dependable Systems and Networks (DSN'03), IEEE Computer Press, pp. 351--360, 2003.
• 20: William Pugh, Fixing the Java memory model, Proceedings of the ACM 1999 conference on Java Grande, p.89-98, June 12-14, 1999, San Francisco, California, United States [doi>10.1145/304065.304106]
• 21: Antony I. T. Rowstron , Peter Druschel, Pastry: Scalable, Decentralized Object Location, and Routing for Large-Scale Peer-to-Peer Systems, Proceedings of the IFIP/ACM International Conference on Distributed Systems Platforms Heidelberg, p.329-350, November 12-16, 2001
• 22: Sylvia Ratnasamy , Paul Francis , Mark Handley , Richard Karp , Scott Schenker, A scalable content-addressable network, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.161-172, August 2001, San Diego, California, United States
• 23: Ion Stoica , Robert Morris , David Liben-Nowell , David R. Karger , M. Frans Kaashoek , Frank Dabek , Hari Balakrishnan, Chord: a scalable peer-to-peer lookup protocol for internet applications, IEEE/ACM Transactions on Networking (TON), v.11 n.1, p.17-32, February 2003 [doi>10.1109/TNET.2002.808407]
• 24: Voulgaris S., Gavidia D. and van Steen M., CYCLON: inexpensive membership management for unstructured P2P overlays. Journal of Network and Systems Management, 13(2):197--217, 2005.
• 25: Watts D. J. and Stogatz S. H. Collective dynamics of small-world networks. Nature, 393, 1998.
• 26: Ben Y. Zhao , John D. Kubiatowicz , Anthony D. Joseph, Tapestry: An Infrastructure for Fault-tolerant Wide-area Location and, University of California at Berkeley, Berkeley, CA, 2001

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.2 Design Tools and Techniques
          Subjects: Modules and interfaces

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

  D. Software
  D.2 SOFTWARE ENGINEERING
        D.2.11 Software Architectures

General Terms:
Design