Service interruption on Monday 11 July from 12:30 to 13:00: all the sites of the CCSD (HAL, EpiSciences, SciencesConf, AureHAL) will be inaccessible (network hardware connection).
Skip to Main content Skip to Navigation

Length and Number of Buses for Gossiping in Networks

Abstract : 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.
Document type :
Complete list of metadata

Cited literature [18 references]  Display  Hide  Download
Contributor : Colette ORANGE Connect in order to contact the contributor
Submitted on : Wednesday, April 17, 2019 - 9:13:51 AM
Last modification on : Saturday, September 11, 2021 - 3:19:16 AM


Files produced by the author(s)


  • HAL Id : hal-02102083, version 1



Pierre Fraigniaud, Christian Laforest. Length and Number of Buses for Gossiping in Networks. [Research Report] LIP RR-1994-23, Laboratoire de l'informatique du parallélisme. 1994, 2+16p. ⟨hal-02102083⟩



Record views


Files downloads