Gal A. Kaminka: Publications

Sorted by DateClassified by Publication TypeClassified by TopicGrouped by Student (current)Grouped by Former Students

Reducing Communication Cost via Overhearing

Adrian Perreau de Pinninck, Gery Gutnik, and Gal A. Kaminka. Reducing Communication Cost via Overhearing. In Proceedings of the European Workshop on Multi-Agent Systems (EUMAS-2008), 2008.

Download

[PDF]180.7kB  

Abstract

Coordination of task execution, in open distributed multi-agent systems, is often accomplished through communications between agents. Thus, most tasks carry some cost associated with those communications. The work in this article proposes to use overhearing for reducing some of this cost, and therefore reducing the overall cost of task execution. Since in open distributed systems, and in particular in large-scale settings, it is rare for two agents to communicate directly, their communications (as in real-world networks) are routed to their destination through other agents. We allow those intermediate agents to overhear and monitor passing through communications. In doing so, the intermediate agents detect some of the errors generated by communicating agents before they reach their final destination. Filtering those erroneous messages in advance reduces the cost associated with routing them through the system. This work first formalizes this problem, and then proposes algorithms for finding an effective set of filtering agents. Unfortunately, finding an optimal solution for this problem turned out to be intractable. Thus, an efficient heuristic solution is proposed. An empirical simulation of these algorithms shows that the heuristic algorithm achieves similar performance to that of the optimal algorithm, while maintaining efficient run-time complexity.

Additional Information

BibTeX

@InProceedings{eumas08, 
  author = 	 {Adrian Perreau de Pinninck and Gery Gutnik and Gal A. Kaminka}, 
  title = 	 {Reducing Communication Cost via Overhearing},
  OPTcrossref =  {}, 
  OPTkey = 	 {}, 
  booktitle = {Proceedings of the European Workshop on Multi-Agent Systems ({EUMAS}-2008)}, 
  OPTpages = 	 {}, 
  year = 	 {2008}, 
  abstract = { Coordination of task execution, in open distributed multi-agent systems, is often  accomplished through communications between agents. Thus, most tasks carry some cost associated with  those communications. The work in this article proposes to use overhearing for reducing some of this  cost, and therefore reducing the overall cost of task execution. Since in open distributed systems,  and in particular in large-scale settings, it is rare for two agents to communicate directly, their  communications (as in real-world networks) are routed to their destination through other agents. We  allow those intermediate agents to overhear and monitor passing through communications. In doing so,  the intermediate agents detect some of the errors generated by communicating agents before they reach  their final destination. Filtering those erroneous messages in advance reduces the cost associated with routing them through the system. This work first formalizes this problem, and then proposes  algorithms for finding an effective set of filtering agents. Unfortunately, finding an optimal  solution for this problem turned out to be intractable. Thus, an efficient heuristic solution is  proposed. An empirical simulation of these algorithms shows that the heuristic algorithm achieves  similar performance to that of the optimal algorithm, while maintaining efficient run-time  complexity. },  
  wwwnote = {}, 
  OPTeditor = 	 {}, 
  OPTvolume = 	 {}, 
  OPTnumber = 	 {}, 
  OPTseries = 	 {}, 
  OPTaddress = 	 {}, 
  OPTmonth = 	 {}, 
  OPTorganization = {}, 
  OPTpublisher = {}, 
  OPTnote = 	 {}, 
  OPTnote = 	 {}, 
  OPTannote = 	 {} 
} 

Generated by bib2html.pl (written by Patrick Riley ) on Fri Aug 30, 2024 17:29:52