@COMMENT This file was generated by bib2html.pl <https://sourceforge.net/projects/bib2html/> version 0.94
@COMMENT written by Patrick Riley <http://sourceforge.net/users/patstg/>
@COMMENT This file came from Gal A. Kaminka's publication pages at
@COMMENT http://www.cs.biu.ac.il/~galk/publications/
@PhdThesis{gutnik-phd, 
  author = 	 {Gery Gutnik}, 
  title = 	 {Monitoring large-scale multi-agent systems using overhearing}, 
  school = 	 {{B}ar {I}lan {U}niversity}, 
  year = 	 {2006}, 
  OPTkey = 	 {}, 
  OPTtype = 	 {}, 
  OPTaddress = 	 {}, 
  OPTmonth = 	 {}, 
  OPTnote = 	 {}, 
  abstract = { 
Overhearing is fast gaining attention as a generic method for monitoring open, distributed multi-agent systems. 
In such settings, agents' internal structure is not generally known to a monitoring agent, but overhearing does 
not require such knowledge. Instead, the monitoring agent uses the overheard routine communications as a basis 
for inference about the other agents. Our work focuses on cooperative overhearing, in which the overheard agents 
usually know they are being overheard, and do not in any way intend to disrupt the monitor. 
Previous work on overhearing investigated an extensive set of techniques and implementations of overhearing. 
However, focusing mainly on its potential applications, those investigations often rely on assumptions related 
to the fundamentals of overhearing. In contrast, we dedicate our research to a comprehensive study of the 
fundamental building blocks that allow overhearing in the first place. In doing so, we systematically tackle 
various assumptions made by previous investigations. In particular, our study focuses on overhearing in 
large-scale multi-agent systems and addresses the specific challenges and limitations that characterize such 
settings. 
The first overhearing building block, addressed by our research, is the representation of multi-agent 
conversations. Various formalism have been proposed for that purpose. In particular, recent investigations 
showed Petri nets to provide a viable representation approach for modelling multi-agent interactions. By 
analyzing the strengths and weaknesses of the rather radical Petri net approaches introduced by previous work, 
we propose a novel representation technique especially suitable for overhearing. Furthermore, we show this 
representation to be more scalable than previous representations, and thus more appropriate for monitoring 
conversations in large-scale settings. We show that this new representation offers a comprehensive coverage of 
essentially all conversation features needed to represent complex multi-agent conversations. We also present a 
procedure for transforming human-readable AUML conversation protocol diagrams to our machine-readable Petri net 
representation. 
Next, we addressed the building block of conversation recognition. Conversation recognition is the process of 
identifying the actual conversation based on a sequence of overheard messages. In the process, the overhearing 
agent extracts various parameters of the overheard conversation such as the set of conversing agents, the 
corresponding conversation protocol, etc. In addition, it also handles possible errors caused by differences 
between the conversation as it was overheard and as it was actually carried out by the agents (e.g., in cases 
where the overhearer was not able to overhear some of the exchanged messages). 
Although conversation recognition is a key step in overhearing prior to any possible inference based on 
overheard communications, it is often discarded by previous investigations. Our work addresses the challenges 
related to conversation recognition by first introducing a formal model of overhearing. Most previous works 
focus on potential applications of overhearing. Therefore, the proposed model was the first to formalize the 
general problem of overhearing unrelated to any specific task. 
Then, based on this model, we provide a skeleton algorithm for conversation recognition, and provide 
instantiations of it for lossless and lossy settings. Since in large-scale multi-agent systems overhearing agent 
has to process large quantities of intercepted messages, conversation recognition algorithms must be efficient. 
Accordingly, the time-complexity of these algorithms was analyzed. We show that handling conversation 
recognition of systematic message loss, which is unique to overhearing, is significantly more efficient than 
handling the general case of randomly lost messages (which is intractable). 
The final building block addressed in this work is selective overhearing, i.e. overhearing under the restriction 
of selectivity. The restriction of selectivity is mainly compelled by the specific characteristics of 
large-scale multi-agent systems. In such settings, it is reasonable to assume that the overhearing resources 
will be essentially limited, thus allowing the overhearing agent to overhear only a subset of inter-agent 
communications carried out in the monitored settings. Accordingly, the overhearer must be careful in choosing 
which targets to overhear on account of other potential targets. 
Most previous investigations on overhearing ignore the limitation of selectivity, assuming that all relevant 
inter-agent communications can be overheard. Tackling this problematic assumption, our work provides an 
empirical study of selective overhearing focusing on widely common hierarchical organizations. Here, we first 
propose a model for selective overhearing of such organizations. Then, using a simulation of this model, we 
perform an extensive set of experiments in which we empirically evaluate and compare performance of various 
overhearing policies taking into consideration both the limitations of selectivity and the specific 
characteristics of hierarchical organizations. 
We empirically study both centralized and distributed selective overhearing policies. In doing so, we tackle 
another problematic assumption by previous investigations. Those investigations either assume a single 
overhearer or a group of non-cooperative overhearing agents that perform overhearing out of their own interest. 
In contrast, our work considers overhearing committed by a group of collaborative overhearers. First, we 
consider centrally-coordinated overhearing groups which are equivalent to a single centrally-located overhearer. 
But, then, we empirically study the transition to a group of overhearing agents acting collaboratively in a 
distributed manner. 
Based on the performed experiments, we were able to isolate the factors influencing the behavior of those 
policies and reach several qualitative conclusions. With respect to centralized overhearing policies, we have 
found a classical value-volume tradeoff. This tradeoff was found to be surprisingly robust to many 
characteristics of hierarchical organizations. However, what was more surprising is that the combination of two 
types of policies (value and volume) in addition to being fully robust, outperformed each of the policies 
separately. 
Addressing distributed policies, we considered the transition from effective centralized policies to distributed 
ones by gradually decreasing the level of collaboration between the overhearing agents. Here, we found some 
factors to significantly influence the performance of the examined policies, while finding that others can 
simply be neglected or only partially solved. 
}, 
  wwwnote = {}, 
  OPTannote = 	 {} 
}