A fault-tolerant directory service for mobile agents based on forwarding pointers

ABSTRACT

A reliable communication layer is an essential component of a mobile agent system. We present a new fault-tolerant directory service for mobile agents, which can be used to route messages to them. The directory service, based on a technique of forwarding pointers, introduces some redundancy in order to ensure resilience to stopping failures of nodes containing forwarding pointers; in addition, it avoids cyclic routing of messages, and it supports a technique to collapse chains of pointers that allows direct communications between agents. We have formalised the algorithm and derived a fully mechanical proof of its correctness using the proof assistant Coq; we report on our experience of designing the algorithm and deriving its proof of correctness. The complete source code of the proof is made available from the WWW.

REFERENCES

• 1: B. Barras, S. Boutin, C. Cornes, J. Courant, J. C. Filliatre, E. Giménez, H. Herbelin, G. Huet, C. Mu noz, C. Murthy, C. Parent, C. Paulin, A. Saïbi, and B. Werner. The Coq Proof Assistant Reference Manual --- Version V6.1. Technical Report 0203, INRIA, August 1997.
• 2: Joachim Baumann , Kurt Rothermel, The Shadow Approach: An Orphan Detection Protocol for Mobile Agents, Proceedings of the Second International Workshop on Mobile Agents, p.2-13, September 01, 1998
• 3: Krishna Bharat , Luca Cardelli, Migratory Applications, Selected Presentations and Invited Papers Second International Workshop on Mobile Object Systems - Towards the Programmable Internet, p.131-148, July 08-09, 1996
• 4: Giacomo Cabri , Letizia Leonardi , Franco Zambonelli, Reactive Tuple Spaces for Mobile Agent Coordination, Proceedings of the Second International Workshop on Mobile Agents, p.237-248, September 01, 1998
• 5: Danny B. Lange , Oshima Mitsuru, Programming and Deploying Java Mobile Agents Aglets, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1998
• 6: Sashi Lazar, Ishan Weerakoon, and Deepinder Sidhu. A Scalable Location Tracking and Message Delivery Scheme for Mobile Agents. Technical report, University of Maryland, 1998.
• 7: Nancy Lynch. Distributed Algorithms. Morgan Kaufmann Publishers, December 1995.
• 8: S. Mishra, X. Jiang, and B. Yang. Providing Fault Tolerance to Mobile Intelligent Agents. In Proceedings of the ISCA 8th International Conference on Intelligent Systems, Denver, June 1999.
• 9: Luc Moreau. A Fault-Tolerant Distributed Directory Service for Mobile Agents: the Constructive Proof in Coq. Available from http://www.ecs.soton.ac.uk/~lavm/coq/failure/, September 2000.
• 10: Luc Moreau, Distributed directory service and message routing for mobile agents, Science of Computer Programming, v.39 n.2-3, p.249-272, March 2001 [doi>10.1016/S0167-6423(00)00011-3]
• 11: Luc Moreau, Nick Gibbins, David DeRoure, Samhaa El-Beltagy, Wendy Hall, Gareth Hughes, Dan Joyce, Sanghee Kim, Danius Michaelides, Dave Millard, Sigi Reich, Robert Tansley, and Mark Weal. SoFAR with DIM Agents: An Agent Framework for Distributed Information Management. In The Fifth International Conference and Exhibition on The Practical Application of Intelligent Agents and Multi-Agents, pages 369-388, Manchester, UK, April 2000.
• 12: Luc Moreau and Daniel Ribbens. Mobile Objects in Java. Scientific Programming, 2002. Special issue of the International Workshop on Performance-oriented Application Development for Distributed Architectures (PADDA'2001).
• 13: Luc Moreau, David De Roure, Wendy Hall, and Nick Jennings. MAGNITUDE: Mobile AGents Negotiating for ITinerant Users in the Distributed Enterprise. http://www.ecs.soton.ac.uk/ lavm/magnitude/, 2001.
• 14: Amy L. Murphy , Gian Pietro Picco, Reliable Communication for Highly Mobile Agents, Proceedings of the First International Symposium on Agent Systems and Applications Third International Symposium on Mobile Agents, p.141, October 03-06, 1999
• 15: Saurab Nog , Sumit Chawla , David Kotz, An RPC Mechanism for Transportable Agents, Dartmouth College, Hanover, NH, 1996
• 16: ObjectSpace. Voyager. http://www.objectspace.com/.
• 17: Gian Pietro Picco , Amy L. Murphy , Gruia-Catalin Roman, LIME: Linda meets mobility, Proceedings of the 21st international conference on Software engineering, p.368-377, May 16-22, 1999, Los Angeles, California, United States [doi>10.1145/302405.302659]
• 18: R. Prakash and M. Singhal. A Dynamic Approach to Location Management in Mobile Computing Systems. In The 8th International Conference on Software Engineering and Knowledge Engineering (SEKE'96), pages 488-495, Lake Tahoe, Nevada, June 1996.
• 19: Pawel T. Wojciechowski , Peter Sewell, Nomadic Pict: Language and Infrastructure Design for Mobile Agents, Proceedings of the First International Symposium on Agent Systems and Applications Third International Symposium on Mobile Agents, p.2, October 03-06, 1999

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence
            Subjects: Coherence and coordination

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence
            Subjects: Multiagent systems

General Terms:
Algorithms, Design, Experimentation, Reliability, Theory

Keywords:
distributed directory service, fault tolerance, mobile agents