Gwendal SIMON

Gwendal SIMON

Maître de Conférences, HDR
Département Systèmes Réseaux, Cybersécurité et Droit du numérique

Téléphone : (+33) 2 99 12 70 48
Télécopie : 02 99 12 70 30
Courriel :
ENST Bretagne

Optimizing resource sharing in node-capacitated overlay networks


LEBLET Jimmy1, PIANESE Fabio1, SIMON Gwendal1

Type de document

Communication dans une conférence sans acte


Autonomous and Spontaneous Networks Symposium, November 20-21, Paris, Institut TELECOM, 2008




A frequently occurring problem in the field of distributed systems is to determine an allocation of a generic resource so that the demand of every node in the system is fulfilled. Node-capacitated graphs, i.e. graphs where the weight of a node corresponds to the amount of resources it can give to the system, provide an appealing model that can be readily applied to real-world applications, such as peer-to-peer and grid-based systems. In this paper, we propose a model for this problem and show that it can be reduced to a problem of maximizing a flow in a bipartite network. We then describe a distributed fault-tolerant algorithm which allows each peer to compute the allocation of its resources using only local knowledge. Finally, we show that computing the maximal flow in a bounded-degree graph is NP-complete, which means that optimizing resource sharing in bounded-degree overlays is still an open problem.


1 : INFO - Dépt. Informatique (Institut Mines-Télécom-Télécom Bretagne-UEB)

Mots clés

Overlay network, Distributed algorithm



retour à la liste des publications
Technopôle Brest-Iroise - CS 83818 - 29238 Brest Cedex 3 - France
Tél : 33 (0)2 29 00 11 11 - Fax : 33 (0)2 29 00 10 00