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.
Origine : Fichiers produits par l'(les) auteur(s)