Length and Number of Buses for Gossiping in Networks
Résumé
Gossiping is an information dissemination problem in which each node of a communication network has a unique piece of information that must be transmitted to all the other nodes. A bus network is a network of processing elements that communicate by sending messages along buses in a sequence of calls. We assume that (i) each node can participate to at most one call at a time, (ii) a node can either read or write on a bus, (iii) no more than one node can write on a given bus at a given time, and (iv) communicating a message on a bus takes a unit of time. This model extends the telegraph model in allowing the number of nodes connected to each bus to be as large as needed, instead on being bounded by 2. In this paper, we are interested in minimizing the ``hardware'' of a bus network in keeping optimal the communication performances for solving the gossiping problem. More precisely, we compute the minimum number of buses required for a gossiping to be optimal. Similarly, we give upper bounds on the minimum length of buses required for a gossiping to be optimal. Finally, we combine the two approaches in trying to minimize both parameters: length and number of buses.
L'échange total consiste en des changes de données entre les processeurs d'un réseau d'interconnexion où chaque processeur possède une information qu'il doit diffuser à l'ensemble des autres processeurs. Un réseau par bus est un réseau interconnexion dont les éléments échangent leurs informations au moyen de bus. Dans cet article, nous supposons que (i) chaque processeur ne peut participer qu'à une communication à in instant donnée (ii) chaque processeur peut soit lire ou écrire sur un bus, mais pas les deux à la fois (iii) au plus un processeur sur un bis donnée à un instant donné, et (iv) la communication d'une information sur un bus coûte une unité de temps. Ce modèle peut être vu comme une extension du modèle télégraphe en supposant que le nombre de processeurs connectés à un même bus peut être aussi grand que souhaité au lieu d'être limité à deux
Dans cet article, nous nous sommes intéressé à minimiser le "matériel" d'un réseau par bus tout en permettant de résoudre de façon optimale le problème de l’échange total. plus précisément, nous calculons le même nombre minimum de bus que requiert un réseau par bus afin de réaliser l’échange total de façon optimal. De la m^me manière, nous donnons des bornes supérieures sur la longueur des bus que requiert un réseau par bus afin de réaliser l’échange total de façon optimale. Finalement, nous combinons les deux approches en essayant de minimiser ces deux paramètres : longueur et nombre de bus
Domaines
Informatique [cs]
Origine : Fichiers produits par l'(les) auteur(s)
Loading...