Distributed Lagrangean Optimization: a case in P2P Overlay Network Design

Marco A. Boschetti
Department of mathematics, University of Bologna, Bologna, Italy, 
boschett@csr.unibo.it

Vittorio Maniezzo, Matteo Roffilli
Department of Computer Science, University of Bologna, Bologna, Italy, 
vittorio.maniezzo@unibo.it, roffilli@csr.unibo.it

Peer-to-peer computing (P2P) is likely to become as ubiquitous as current client / server architectures in next generation information systems. This paper addresses a central problem of P2P system: the design
of an optimal overlay communication network for a set of processes on the Internet (a problem named
Membership Overlay Problem, MOP). Such a network defines membership to the P2P group and allows
for members to disseminate information within the group. The problem 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 on-line in the fully decentralized P2P systems,
and integrate it with a heuristic which can thus achieve sound hot start states for fast response to varying network structures.
Key words : Lagrangean relaxation, distributed optimization, peer-to-peer networks, overlay optimization