Ben-Ami & Shehory (2005) A Comparative Evaluation of Agent Location Mechanisms in Large Scale MAS

Cited by 3 [ATGSATOP]

So this was one of the papers I printed out last year since it cited Koubarakis (2003), and am reading as part of trying to put together an invited paper for the AP2PC 2007 workshop proceedings. Putting together the proceedings and the invited paper has been a somewhat ill fated process interrupted by the death of my father, the collapse of the industry grant that was funding my position at University of Hawaii, and the birth of my twin sons! I am back on track now, although new crises loom on the horizon I am actually making some progress reading all the papers I printed out last October (Sycara, 1998; Sycara, 1991; Rosenschein, 1993; Koubarakis, 2003). If I can just hang in there I can wrap this thing up by the end of the summer - fingers crossed.

So after reading this paper I think I probably should have been reading Shehory (2000) which describes the distributed agent location mechanism that this paper is evaluating in comparison with centralized location mechanisms. However this is the one I had printed out, so partly not to waste the paper, and also because it is easier to read paper papers when pushing the twin stroller around I am sticking with this. It also reflects my earlier literature searching tendencies to print out things that look interesting without necessarily doing sufficient investigation to find the critical highly-cited papers in a particular domain; but enough of that.

This paper was presented at AAMAS 2005, which I attended. It describes a number of problems associated with centralized location services

the middle agent that supplies the directory services becomes one of the system failure points and/or communication bottlenecks

although no academic or industry systems are cited. I get the feeling that the problems described are based on observations of toy systems and simulations rather than on experience with really large scale systems. I may be wrong, but the paper is not really providing me re-assurance to the contrary. The paper mentions the P2P approach, but only the flooding model is considered rather than anything more sophisticated like a distributed hashtable (DHT) although this is understandable given the year of publication. Compared to simulations of P2P systems, the testing of simply random and grid networks seems a little overly simplistic. Furthermore the efforts at generalizability are restricted to a fixed number of repeat runs rather than an assessment of the number of runs needed to achieve a particular confidence level. Of course the same criticism could be leveled at most P2P simulation studies.

The main conclusions of the paper are as follows:

1. the response time of a distributed location mechanism is significantly better than the response time of a centralized one, in particular for large scale MAS (see fig 1 above). This result does not hold, however, in capability-deprived MAS, where a centralized mechanism will perform better.
2. it is evident that a centralized location mechanism is very sensitive to workloads. At a medium to high load, in particular in large MAS, the centralized mechanism will perform poorly, whereas the distributed one will hardly be affected.
3. the advantages of the distributed solution do come at the cost of a communication overhead
   

Although it feels like these follow logically from the definition of distributed and centralized location systems. It is not clear that we necessarily need simulations to confirm these assertions. So overall I don't come away thinking that P2P researchers would find much of interest in this paper, except in so far as to see the parallel concepts in the two fields, but I have to concede that this may be the right paper for some agents researchers to read in order to see the applicability of the P2P approach. So let us say that I was slightly disappointed by the level of this paper, but it would be unfair to judge the potential contribution of agents to P2P based on this one paper, and I think my overall opinion is turning. It might be helped by reading Shehory (2000), but right now I am going to forge on with the other papers I have printed out.


David Ben-Ami, & Onn Shehory (2005). A comparative evaluation of agent location mechanisms in large scale MAS Proceedings of the fourth international joint conference on Autonomous agents and multiagent systems, 339-346 DOI: 10.1145/1082473.1082525

References

Barabasi, A. L., Albert, R., "Emergence of Scaling in Random Networks" (Cited by 6145). Science, page 286(509), 1999.
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
Clarke I., Sandberg O., Wiley B., Hong T. W., "Freenet: A Distributed Anonymous Information Storage and Retrieval System" (Cited by 1760). Proceedings of the ICSI Workshop on Design Issues in Anonymity and Unobservability. Berkeley, CA, 2000.
Decker K., Sycara K., Williamson M. "Middle-Agents for the Internet" (Cited by 398) .Proceedings of IJCAI-97, pages 578--583, Nagoya Japan 1997.
Dimakopoulos V. V., Pitoura E., "A Peer-to-Peer Approach to Resource Discovery in Multi-agent Systems" (Cited by 13). Proceedings of. CIA 2003: pages 62--77.
Michael R. Genesereth, Steven P. Ketchpel, Software agents, Communications of the ACM, v.37 n.7, p.48-ff., July 1994
Gibbins, N. and Hall, W. "Scalability Issues for Query Routing Service Discovery" (Cited by 19). Proceedings of the Second Workshop on Infrastructure for Agents, MAS and Scalable MAS (2001), pages 209--217.
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
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
Koubarakis M., "Multi-agent Systems and Peer-to-Peer Computing: Methods, Systems, and Challenges" (Cited by 12). Proceedings of. CIA 2003 pages 46--61.
Kuokka D., Harada L., "Matchmaking for information agents" (Cited by 100). Proceedings of IJCAI-95, pages 672--679, 1995.
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
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
Smithson A., Moreau L., "Engineering an Agent-Based Peer-To-Peer Resource Discovery System" (Cited by 3). In Gianluca Moro and Manolis Koubarakis, editors, First International Workshop on Agents and Peer-to-Peer Computing, pages 69--80, Bologna, Italy, July 2002.
Srinivasan N. et al., "Enabling Peer-to-Peer Resource Discovery in Agent Environment" (Cited by 1). Proceedings of Challenges in Open Agent Systems (AAMAS 2002), July 2002.
Stoica I., Morris R., Karger D., Kasshoek M. F., Balakrishnan H., "Chord: A scalable peer-to-peer lookup service for Internet Applications" (Cited by 6651). Technical Report TR-819, MIT, March 2001.
Vitaglione G., Quarta F. and Cortese E., "Scalability and Performance of JADE Message Transport System" (Cited by 38). Proceedings of the AAMAS Workshop on AgentCities, Bologna, 2002.
Watts, D. J., Strogatz, S. H, "Collective Dynamics of 'Small World' Networks" (Cited by 7766). Nature, 393: pages 440--442, 1998.
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
Yolum P., Singh M. P., "An Agent-Based Approach for Trustworthy Service Location" (Cited by 13). Proceedings of the 1st International Workshop on Agents and Peer-to-Peer Computing, Bologna, Italy 2002.
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