A Fully Distributed Lagrangean Solution for a Peer‐to‐Peer Overlay Network Design Problem

A Fully Distributed Lagrangean Solution for a Peer‐to‐Peer Overlay Network Design Problem

0.00 Avg rating0 Votes
Article ID: iaor20112499
Volume: 23
Issue: 1
Start Page Number: 90
End Page Number: 104
Publication Date: Dec 2011
Journal: INFORMS Journal on Computing
Authors: , ,
Keywords: combinatorial optimization, heuristics, networks
Abstract:

Peer‐to‐peer (P2P) computing already accounts for a large part of the traffic on the Internet, and it is likely to become as ubiquitous as current client/server architectures in next generation information systems. This paper addresses a central problem of P2P systems: the design of an optimal overlay communication network for a set of processes on the Internet. Such a network defines membership to the P2P group and allows for members to disseminate information within the group. The problem, named the membership overlay problem (MOP), can be formulated as a dynamic optimization problem where classical combinatorial optimization techniques must face the further challenge of time‐varying input data. This paper proposes an innovative, fully distributed, and asynchronous subgradient optimization algorithm for the Lagrangean relaxation of the MOP, which can run online in fully decentralized P2P systems, and integrates it with a distributed heuristic that can achieve sound hot‐start states for fast response to varying network structures.

Reviews

Required fields are marked *. Your email address will not be published.