Gossiping with interference in radio chain networks - Archive ouverte HAL Access content directly
Preprints, Working Papers, ... Year :

Gossiping with interference in radio chain networks

(1) , (2) , (3)


IIn this paper, we study the problem of gossiping with neighboring interference con- straint in radio chain networks. Gossiping (or total exchange information) is a protocol where each node in the network has a message and is expected to distribute its own mes- sage to every other node in the network. The gossiping problem consists in finding the minimum running time (makespan) of a gossiping protocol and efficient algorithms that attain this makespan. We focus on the case where the transmission network is a chain (directed path or line) network. We consider synchronous protocols where it takes one unit of time (step) to transmit a unit-length message. During one step, a node receives at most one message only through one of its two neighbors. We suppose that during one step, a node cannot be both a sender and a receiver (half duplex model). Moreover we have neighboring interference constraints with which a node cannot receive a message if one of its neighbors is sending. A round consists of a set of non-interfering (or compatible) calls and uses one step. We solve completely the gossiping problem for Pn, the chain network on n nodes, and give an algorithm that completes the gossiping in 3n − 5 rounds (for n > 3), which is exactly the makespan.
Fichier principal
Vignette du fichier
BKY19-hal.pdf (271.07 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

hal-02424017 , version 1 (26-12-2019)


  • HAL Id : hal-02424017 , version 1


Jean-Claude Bermond, Takako Kodate, Joseph Yu. Gossiping with interference in radio chain networks. 2019. ⟨hal-02424017⟩
74 View
63 Download


Gmail Facebook Twitter LinkedIn More