PÉRENNES , Stéphane

La plupart des problèmes d'optimisation combinatoire sont NP-difficiles, c'est-à-dire qu'ils ne peuvent être résolus en temps polynomial que si les classes P et NP sont identiques. Pour ces problèmes on peut espérer soit trouver des algorithmes d'approximation, soit prouver qu'ils ne peuvent pas être approximés de manière efficace. En 2002 S....

no abstract

In this paper we describe an efficient gossiping algorithm for short messages into the 3-dimensional torus networks (wrap-around or toroidal meshes) that uses synchronous circuit-switched routing. The algorithm is based on a recursive decomposition of a torus. It requires an optimal number of rounds and a quasi-optimal number of intermediate...

In this paper we describe, in the case of short messages, an efficient gossiping algorithm for 3-dimensional torus networks (wrap-around or toroidal meshes) that uses synchronous circuit-switched routing. The algorithm is based on a recursive decomposition of a torus. The algorithm requires an optimal number of rounds and a quasi-optimal number...

Les systèmes pair-à-pair à grande échelle ont été proposé comme un moyen fiable d'assurer un stockage de donnée à faible côut. Pour assurer la pérennité des données, ces systèmes codent les fichiers des utilisateurs en un ensemble de fragments redondants qui sont répartis entre les pairs. Nous étudions dans ce rapport l'impact des différents...

In this paper we extend the technique provided in [6] to allow the determination of lower bounds on the broadcasting and gossiping time required by the so-called «restricted» protocols. Informally, a protocol is (i,o)-restricted at a given processor if every outgoing activation of an arc depends on at most i previous incoming activations and...

RAIRO, afcet (Éditions Hermès), ISSN 0752-4072 - Fraigniaud, Pierre and Roman, Jean (Editors)

Peer-to-peer systems are foreseen as an efficient solution to achieve reliable data storage at low cost. To deal with common P2P problems such as peer failures or churn, such systems encode the user data into redundant fragments and distribute them among peers. The way they distribute it, known as placement policy, has a significant impact on...

Les systèmes pair-à-pair à grande échelle représentent un moyen fiable pour stocker des données à faible coût. Afin d'assurer la pérennité des données des utilisateurs, il est nécessaire d'ajouter de la redondance. Ainsi à partir de s fragments initiaux composant un bloc de données, s+r fragments sont générés et répartis entre les pairs du...

In a P2P storage system using erasure codes, a data block is en- coded in many redundancy fragments. These fragments are then sent to distinct peers of the network. In this work, we study the impact of different placement policies of these fragments on the performance of storage systems. Several practical factors (easier control, software...

Peer-to-peer systems are foreseen as an efficient solution to achieve reliable data storage at low cost. To deal with common P2P problems such as peer failures or churn, such systems encode the user data into redundant fragments and distribute them among peers. The way they distribute it, known as placement policy, has a significant impact on...

In a P2P storage system using erasure codes, a data block is en- coded in many redundancy fragments. These fragments are then sent to distinct peers of the network. In this work, we study the impact of different placement policies of these fragments on the performance of storage systems. Several practical factors (easier control, software...

Broadcasting is an information dissemination process in which a message is to be sent from a single originator to all members of a network by placing calls over the communication lines of the network. This is to be completed as quickly as possible subject to the constraints that each call involves only two vertices, each call requires one unit...

The (edge) forwarding index of a graph is the minimum, over all possible routings of all the demands, of the maximum load of an edge. This metric is of a great interest since it captures the notion of global congestion in a precise way: the lesser the forwarding-index, the lesser the congestion. In this paper, we study the following design...

In this paper we define and study a call scheduling problem that is motivated by radio networks. In such networks the physical space is a common resource that nodes have to share, since concurrent transmissions cannot be interfering. We study how one can satisfy steady bandwidth demands according to this constraint. This leads to the definition...

In Graph Searching, a team of searchers aims at capturing an invisible fugitive moving arbitrarily fast in a graph. Equivalently, the searchers try to clear a contaminated network.The problem is to compute the minimum number of searchers required to accomplish this task. Several variants of Graph Searching have been studied mainly because of...

We study two characteristics of a small-world graph proposed by Zhang et al. to model complex networks. Our study relies on the recursive structure of the graph. Firstly, we use it to design a labelling scheme in order to create an implicit routing (i.e., a routing scheme based on the label of vertices). Secondly, proving the average distance...

Motivated by wavelength division multiplexing in all-optical networks, we consider the problem of finding a set of paths from a fixed source to a multiset of destinations, which can be coloured by the fewest number of colours so that paths of the same colour do not share an arc. We prove that this minimum number of colours is equal to the...

Distributed and peer-to-peer storage systems are foreseen as an alternative to the traditional data centers and in-house backup solutions. In the past few years many peer-to-peer storage systems have been proposed. Most of them rely on the use of erasure codes to introduce redundancy to the data. This kind of system depends on many parameters...

This work considers broadcast protocols made of successive communication rounds in the linear cost model: the time needed to send a message of length L is defined as \alpha +L\tau. In this model, the communication time of any algorithm \mathcal{A} is expressed as the sum R_\mathcalA\cdot\alp- ha +T_\mathcal{A} \cdot\tau, where R_\mathcalA is...

In this paper, we address the routing and call scheduling problem in which one has to find a minimum-length schedule of selected links in a TDMA (Time Division Multiple Access) based wireless network. As we deal with a multi-hop networks, these selected links represent a routing solution (paths) providing enough capacity to achieve the routers...

In telecommunication networks packets are carried from a source s to a destination t on a path that is determined by the underlying routing protocol. Most routing protocols belong to the class of shortest path routing protocols. In such protocols, the network operator assigns a length to each link. A packet going from s to t follows a shortest...

An attractive way of implementing efficient local interconnection networks is to use the Optical Transpose Interconnecting System (OTIS) architecture proposed in [8]. This system allows to optically interconnect some set of processors in a Free Space of Optical Interconnections (FSOI). Briefly, it consists of two lenslet arrays allowing a large...

Large scale peer-to-peer systems are foreseen as a way to provide highly reliable data storage at low cost. To achieve high durability, such P2P systems encode the user data in a set of redundant fragments and distribute them among the peers. We study here the impact of different data placement strategies on the system performance when using...

Ce travail montre que dans un réseau (général) où le protocole de routage est OSPF avec la stratégie d'équilibrage de charge ECMP, le problème qui consiste à maximiser un flot simple d'une source vers un puits ne peut être approché à une constante près.