A comparative evaluation of agent location mechanisms in large scale MAS

ABSTRACT

Agents in open multi-agent systems (MAS) need means for locating other agents with which they may collaborate. To address this need, several agent location mechanisms were suggested. Two major approaches dominate agent location mechanisms: a centralized approach using middle agents, and a distributed, peer-to-peer approach. Agent designers, when designing agents to be part of open MAS, should consider these approaches, to provide the agents with appropriate agent location capabilities. However, selecting an agent location approach, let alone a specific solution, is a nontrivial task. In this study we address this difficulty. We perform a systematic comparative evaluation of agent location approaches. We measure the performance of these approaches subject to various MAS configurations. We draw conclusions regarding the conditions in which each approach is preferable. Prior evaluations fall short in addressing realistic MAS settings. In particular, our evaluation is the first to examine scalability of agent location mechanisms in terms of both system size (thousands of agents) and network distribution (over multiple hosts). We present advantages and shortcomings of the examined approaches.

REFERENCES

• 1: Barabasi, A. L., Albert, R., "Emergence of Scaling in Random Networks". Science, page 286(509), 1999.
• 2: David Ben-Ami , Onn Shehory, Evaluation of Distributed and Centralized Agent Location Mechanisms, Proceedings of the 6th International Workshop on Cooperative Information Agents VI, p.264-278, September 18-20, 2002
• 3: Clarke I., Sandberg O., Wiley B., Hong T. W., "Freenet: A Distributed Anonymous Information Storage and Retrieval System". Proceedings of the ICSI Workshop on Design Issues in Anonymity and Unobservability. Berkeley, CA, 2000.
• 4: Decker K., Sycara K., Williamson M. "Middle-Agents for the Internet" .Proceedings of IJCAI-97, pages 578--583, Nagoya Japan 1997.
• 5: Dimakopoulos V. V., Pitoura E., "A Peer-to-Peer Approach to Resource Discovery in Multi-agent Systems". Proceedings of. CIA 2003: pages 62--77.
• 6: Michael R. Genesereth , Steven P. Ketchpel, Software agents, Communications of the ACM, v.37 n.7, p.48-ff., July 1994 [doi>10.1145/176789.176794]
• 7: Gibbins, N. and Hall, W. "Scalability Issues for Query Routing Service Discovery". Proceedings of the Second Workshop on Infrastructure for Agents, MAS and Scalable MAS (2001), pages 209--217.
• 8: Adriana Iamnitchi , Ian Foster , Daniel C. Nurmi, A Peer-to-Peer Approach to Resource Location in Grid Environments, Proceedings of the 11 th IEEE International Symposium on High Performance Distributed Computing HPDC-11 20002 (HPDC'02), p.419, July 24-26, 2002
• 9: Somesh Jha , Prasad Chalasani , Onn Shehory , Katia Sycara, A formal treatment of distributed matchmaking (poster), Proceedings of the second international conference on Autonomous agents, p.457-458, May 10-13, 1998, Minneapolis, Minnesota, United States [doi>10.1145/280765.280897]
• 10: Koubarakis M., "Multi-agent Systems and Peer-to-Peer Computing: Methods, Systems, and Challenges". Proceedings of. CIA 2003 pages 46--61.
• 11: Kuokka D., Harada L., "Matchmaking for information agents". Proceedings of IJCAI-95, pages 672--679, 1995.
• 12: Elth Ogston , Stamatis Vassiliadis, Matchmaking among minimal agents without a facilitator, Proceedings of the fifth international conference on Autonomous agents, p.608-615, May 2001, Montreal, Quebec, Canada [doi>10.1145/375735.376467]
• 13: Onn Shehory, A Scalable Agent Location Mechanism, 6th International Workshop on Intelligent Agents VI, Agent Theories, Architectures, and Languages (ATAL),, p.162-172, July 15-17, 1999
• 14: Smithson A., Moreau L., "Engineering an Agent-Based Peer-To-Peer Resource Discovery System". In Gianluca Moro and Manolis Koubarakis, editors, First International Workshop on Agents and Peer-to-Peer Computing, pages 69--80, Bologna, Italy, July 2002.
• 15: Srinivasan N. et al., "Enabling Peer-to-Peer Resource Discovery in Agent Environment". Proceedings of Challenges in Open Agent Systems (AAMAS 2002), July 2002.
• 16: Stoica I., Morris R., Karger D., Kasshoek M. F., Balakrishnan H., "Chord: A scalable peer-to-peer lookup service for Internet Applications". Technical Report TR-819, MIT, March 2001.
• 17: Vitaglione G., Quarta F. and Cortese E., "Scalability and Performance of JADE Message Transport System". Proceedings of the AAMAS Workshop on AgentCities, Bologna, 2002.
• 18: Watts, D. J., Strogatz, S. H, "Collective Dynamics of 'Small World' Networks". Nature, 393: pages 440--442, 1998.
• 19: A Taxonomy of Middle-Agents for the Internet, Proceedings of the Fourth International Conference on MultiAgent Systems (ICMAS-2000), p.465, July 10-12, 2000
• 20: Yolum P., Singh M. P., "An Agent-Based Approach for Trustworthy Service Location". Proceedings of the 1st International Workshop on Agents and Peer-to-Peer Computing, Bologna, Italy 2002.
• 21: Bin Yu , Munindar P. Singh, A Social Mechanism of Reputation Management in Electronic Communities, Proceedings of the 4th International Workshop on Cooperative Information Agents IV, The Future of Information Agents in Cyberspace, p.154-165, July 07-09, 2000

INDEX TERMS

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

General Terms:
Algorithms, Design, Management, Measurement, Performance

Keywords:
distributed, evaluation, location mechanisms, multi agent systems, peer to peer, simulation