Stable Service Placement on Dynamic Peer-to-Peer Networks: A Heuristic for the Distributed k-Center Problem

Evan A. Sultanik, William C. Regli

The proliferation of wireless networks has underscored the need for systems capable of coping with sporadic network connectivity. The restriction of communication to neighboring hosts makes determining the global state especially difficult, if not impractical. This paper addresses the problem of coordinating the positions of an arbitrary number of services, encapsulated by mobile agents, in a dynamic peer-to-peer network. The agents’ collective goal is to minimize the distance between hosts and services, even if the topology is changing constantly. We propose a distributed algorithm to efficiently calculate the stationary distribution of the network. This can be used as a hill climbing heuristic for agents to find near-optimal locations at which to provide services. Finally, we show that the agent-based hill climbing approach is temporally-stable relative to the instantaneous optimum.

Content Area: 1. Agents/Multiagent Systems

Subjects: 7. Distributed AI; 7.1 Multi-Agent Systems

Submitted: May 10, 2005

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.