Astrolabe: A robust and scalable technology for distributed system monitoring, management, and data mining

ABSTRACT

Scalable management and self-organizational capabilities are emerging as central requirements for a generation of large-scale, highly dynamic, distributed applications. We have developed an entirely new distributed information management system called Astrolabe. Astrolabe collects large-scale system state, permitting rapid updates and providing on-the-fly attribute aggregation. This latter capability permits an application to locate a resource, and also offers a scalable way to track system state as it evolves over time. The combination of features makes it possible to solve a wide variety of management and self-configuration problems. This paper describes the design of the system with a focus upon its scalability. After describing the Astrolabe service, we present examples of the use of Astrolabe for locating resources, publish-subscribe, and distributed synchronization in large systems. Astrolabe is implemented using a peer-to-peer protocol, and uses a restricted form of mobile code based on the SQL query language for aggregation. This protocol gives rise to a novel consistency model. Astrolabe addresses several security considerations using a built-in PKI. The scalability of the system is evaluated using both simulation and experiments; these confirm that Astrolabe could scale to thousands and perhaps millions of nodes, with information propagation delays in the tens of seconds.

REFERENCES

• 1: William Adjie-Winoto , Elliot Schwartz , Hari Balakrishnan , Jeremy Lilley, The design and implementation of an intentional naming system, Proceedings of the seventeenth ACM symposium on Operating systems principles, p.186-201, December 12-15, 1999, Charleston, South Carolina, United States
• 2: Marcos K. Aguilera , Robert E. Strom , Daniel C. Sturman , Mark Astley , Tushar D. Chandra, Matching events in a content-based subscription system, Proceedings of the eighteenth annual ACM symposium on Principles of distributed computing, p.53-61, May 04-06, 1999, Atlanta, Georgia, United States [doi>10.1145/301308.301326]
• 3: David Andersen , Hari Balakrishnan , Frans Kaashoek , Robert Morris, Resilient overlay networks, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 4: Magdalena Balazinska , Hari Balakrishnan , David Karger, INS/Twine: A Scalable Peer-to-Peer Architecture for Intentional Resource Discovery, Proceedings of the First International Conference on Pervasive Computing, p.195-210, August 26-28, 2002
• 5: Kenneth P. Birman , Mark Hayden , Oznur Ozkasap , Zhen Xiao , Mihai Budiu , Yaron Minsky, Bimodal multicast, ACM Transactions on Computer Systems (TOCS), v.17 n.2, p.41-88, May 1999 [doi>10.1145/312203.312207]
• 6: 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
• 7: Andrew D. Birrell , Roy Levin , Michael D. Schroeder , Roger M. Needham, Grapevine: an exercise in distributed computing, Communications of the ACM, v.25 n.4, p.260-274, April 1982 [doi>10.1145/358468.358487]
• 8: Burton H. Bloom, Space/time trade-offs in hash coding with allowable errors, Communications of the ACM, v.13 n.7, p.422-426, July 1970 [doi>10.1145/362686.362692]
• 9: Philippe Bonnet , Johannes Gehrke , Praveen Seshadri, Towards Sensor Database Systems, Proceedings of the Second International Conference on Mobile Data Management, p.3-14, January 08-10, 2001
• 10: Design and evaluation of a wide-area event notification service, ACM Transactions on Computer Systems (TOCS), v.19 n.3, p.332-383, Aug. 2001 [doi>10.1145/380749.380767]
• 11: Alan Demers , Dan Greene , Carl Hauser , Wes Irish , John Larson , Scott Shenker , Howard Sturgis , Dan Swinehart , Doug Terry, Epidemic algorithms for replicated database maintenance, Proceedings of the sixth annual ACM Symposium on Principles of distributed computing, p.1-12, August 10-12, 1987, Vancouver, British Columbia, Canada [doi>10.1145/41840.41841]
• 12: Golding, R. 1992. A weak-consistency architecture for distributed information services. Comput. Syst. 5, 4 (Fall), 379--405.
• 13: Golding, R., Long, D., and Wilkes, J. 1994. The REFDBMS distributed bibliographic database system. In Proceedings of Usenix'94. Santa Fe, NM, 47--62.
• 14: Steven D. Gribble , Matt Welsh , Rob von Behren , Eric A. Brewer , David Culler , N. Borisov , S. Czerwinski , R. Gummadi , J. Hill , A. Joseph , R. H. Katz , Z. M. Mao , S. Ross , B. Zhao , Robert C. Holte, The Ninja architecture for robust Internet-scale systems and services373423, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.35 n.4, p.473-497, March 2001 [doi>10.1016/S1389-1286(00)00179-1]
• 15: John Heidemann , Fabio Silva , Chalermek Intanagonwiwat , Ramesh Govindan , Deborah Estrin , Deepak Ganesan, Building efficient wireless sensor networks with low-level naming, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 16: Butler W Lampson, Designing a global name service, Proceedings of the fifth annual ACM symposium on Principles of distributed computing, p.1-10, August 11-13, 1986, Calgary, Alberta, Canada [doi>10.1145/10590.10591]
• 17: Yaron Moshe Minsky , Fred B. Schneider, Spreading rumors cheaply, quickly, and reliably, 2002
• 18: Paul V. Mockapetris, The domain name system, Proc. of the IFIP WG 6.5 working conference on Computer-based message services, p.61-72, November 1984, Nottingham, United Kingdom
• 19: Brian Oki , Manfred Pfluegl , Alex Siegel , Dale Skeen, The Information Bus: an architecture for extensible distributed systems, Proceedings of the fourteenth ACM symposium on Operating systems principles, p.58-68, December 05-08, 1993, Asheville, North Carolina, United States
• 20: Karin Petersen , Mike J. Spreitzer , Douglas B. Terry , Marvin M. Theimer , Alan J. Demers, Flexible update propagation for weakly consistent replication, Proceedings of the sixteenth ACM symposium on Operating systems principles, p.288-301, October 05-08, 1997, Saint Malo, France
• 21: Sara Radicati, X-500 Directory Services: Technology and Deployment, John Wiley & Sons, Inc., New York, NY, 1994
• 22: George Reese , Andy Oram, Database Programming with JDBC and Java, Second Edition, O'Reilly & Associates, Inc., Sebastopol, CA, 2000
• 23: 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
• 24: Roger E. Sanders, ODBC 3.5 Developer's Guide, McGraw-Hill Professional, 1998
• 25: Alex C. Snoeren , Kenneth Conley , David K. Gifford, Mesh-based content routing using XML, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 26: Stallings, W. 1993. SNMP, SNMPv2, and CMIP. Addison-Wesley.
• 27: Ion Stoica , Robert Morris , David Karger , M. Frans Kaashoek , Hari Balakrishnan, Chord: A scalable peer-to-peer lookup service for internet applications, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.149-160, August 2001, San Diego, California, United States
• 28: Tennenhouse, D., Smith, J., Sincoskie, W., Wetherall, D., and Minden, G. 1997. A survey of active network research. IEEE Communications Magazine 35, 1 (Jan.), 80--86.
• 29: Robbert van Renesse, Power-Aware Epidemics, Proceedings of the 21st IEEE Symposium on Reliable Distributed Systems (SRDS'02), p.358, October 13-16, 2002
• 30: Robbert van Renesse , Dan Dumitriu, Collaborative Networking in an Uncooperative Internet, Proceedings of the 21st IEEE Symposium on Reliable Distributed Systems (SRDS'02), p.51, October 13-16, 2002
• 31: Van Renesse, R., Minsky, Y., and Hayden, M. 1998. A gossip-style failure detection service. In Proceedings of Middleware'98. IFIP, The Lake District, UK, 55--70.
• 32: Van Steen, M., Hauck, F., Homburg, P., and Tanenbaum, A. 1998. Locating objects in wide-area systems. IEEE Communications Magazine 36, 1 (Jan.), 104--109.
• 33: Brian White , Jay Lepreau , Leigh Stoller , Robert Ricci , Shashi Guruprasad , Mac Newbold , Mike Hibler , Chad Barb , Abhijeet Joglekar, An integrated experimental environment for distributed systems and networks, Proceedings of the 5th symposium on Operating systems design and implementation

  Due to copyright restrictions we are not able to make the PDFs for this conference available for downloading

  , December 09-11, 2002, Boston, Massachusetts [doi>10.1145/1060289.1060313]
• 34: 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:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network communications

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.4 OPERATING SYSTEMS
      D.4.4 Communications Management
          Subjects: Network communication
      D.4.5 Reliability
          Subjects: Fault-tolerance
      D.4.6 Security and Protection
          Subjects: Authentication
      D.4.7 Organization and Design
          Subjects: Distributed systems

  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Information filtering
      H.3.4 Systems and Software
          Subjects: Distributed systems
      H.3.5 On-line Information Services
          Subjects: Data sharing

General Terms:
Algorithms, Design, Management, Performance, Reliability, Security

Keywords:
Aggregation, epidemic protocols, failure detection, gossip, membership, publish-subscribe, scalability