Performance analysis of distributed search in open agent systems
Performance analysis of distributed search in open agent systems
复制标题
开放代理系统中分布式搜索的性能分析
DOI：
10.1109/ipdps.2003.1213097
复制
发表时间：
2003
期刊：
影响因子：
--
通讯作者：
E. Pitoura
中科院分区：
文献类型：
--
作者：
V. Dimakopoulos;E. Pitoura
在开放的多智能体系统中，智能体需要其他智能体提供的资源，但它们不知道哪个智能体提供了特定的资源。此问题的大多数解决方案都基于维护代理和资源之间映射的中心目录。但是，这种解决方案不能很好地扩展，因为中央目录在性能和可靠性方面都成为瓶颈。在本文中，我们引入了一种不同的方法：每个代理维护一个有限大小的本地缓存，其中保存有关k个不同资源的信息，即对于k个资源中的每一个，它存储提供该资源的一个代理的联系信息。这创建了一个定向的缓存网络。我们解决以下基本问题：需要特定资源的代理如何通过在缓存网络中导航来找到提供该资源的代理？我们提出并分析比较了这个问题的三种不同算法的性能，洪水，拥挤和随机路径，根据三个性能度量：定位资源的概率，步骤的数量和这样做的消息的数量。我们的分析同样适用于非结构化点对点网络中的分布式搜索。
In open multi-agent systems agents need resources provided by other agents but they are not aware of which agents provide the particular resources. Most solutions to this problem are based on a central directory that maintains a mapping between agents and resources. However, such solutions do not scale well since the central directory becomes a bottleneck in terms of both performance and reliability. In this paper, we introduce a different approach: each agent maintains a limited size local cache in which it keeps information about k different resources, that is, for each of k resources, it stores the contact information of one agent that provides it. This creates a directed network of caches. We address the following fundamental problem: how can an agent that needs a particular resource find an agent that provides it by navigating through this network of caches? We propose and analytically compare the performance of three different algorithms for this problem, flooding, teeming and random paths, in terms of three performance measures: the probability to locate the resource, the number of steps and the number of messages to do so. Our analysis is also applicable to distributed search in unstructured peer-to-peer networks.