LEBLET Jimmy1, PIANESE Fabio1, SIMON Gwendal1
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(TB) - Dépt. Informatique (Institut Mines-Télécom-Télécom Bretagne-UEB)
Overlay network, Distributed algorithm