Gossiping in Cayley Graphs by Packets - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 1996

Gossiping in Cayley Graphs by Packets

Résumé

Gossiping (also called total exchange or all-to-all communication) is the process of information di usion in which each node of a network holds a packet that must be communicated to all other nodes in the network. We consider here gossiping in the store-and-forward, fullduplex and-port (or shouting) model. In such a model, the protocol consists of a sequence of rounds and during each round, each node can send (and receive) messages from all its neighbors. The great majority of the previous works on gossiping problems allows the messages to be freely concatenated and so messages of arbitrary length can be transmitted during a round. Here we restrict the problem to the case where at each round communicating nodes can exchange exactly one packet. We give a lower bound of N ?1 , where is the minimum degree, and show that it is attained in Cayley symmetric digraphs with some additional properties. That implies the existence of an optimal gossiping protocol for classical networks like hypercubes, k-dimensional tori, and star-graphs.
Fichier principal
Vignette du fichier
110-BKP96-gossiping Cayley.pdf (230 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-03762695 , version 1 (28-08-2022)

Identifiants

  • HAL Id : hal-03762695 , version 1

Citer

Jean-Claude Bermond, Takako Kodate, Stéphane Pérennes. Gossiping in Cayley Graphs by Packets. Proceedings Conference Franco-Japonaise, Lecture Notes in Computer Science ,1120, Springer Verlag 1996,, Jul 1995, Brest, France. pp.301-315. ⟨hal-03762695⟩
7 Consultations
18 Téléchargements

Partager

Gmail Facebook X LinkedIn More