Gossiping with interference in radio ring networks
In this paper, we study the problem of gossiping with interference constraint in radio ring 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 message to every other node in the network. The gossiping p...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2023-10-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | http://dmtcs.episciences.org/9399/pdf |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849344632588075008 |
|---|---|
| author | Jean-Claude Bermond Takako Kodate Joseph Yu |
| author_facet | Jean-Claude Bermond Takako Kodate Joseph Yu |
| author_sort | Jean-Claude Bermond |
| collection | DOAJ |
| description | In this paper, we study the problem of gossiping with interference constraint in radio ring 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 message to every other node in the network. The gossiping problem consists in finding the minimum running time (makespan) of a gossiping protocol and algorithms that attain this makespan. We focus on the case where the transmission network is a ring 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 also suppose that, during one step, a node cannot be both a sender and a receiver (half duplex model). Moreover communication is subject to interference constraints. We use a primary node interference model where, if a node receives a message from one of its neighbors, its other neighbor cannot send at the same time. With these assumptions we completely solve the problem for ring networks. We first show lower bounds and then give gossiping algorithms which meet these lower bounds and so are optimal. The number of rounds depends on the congruences of n modulo 12. |
| format | Article |
| id | doaj-art-557d2d74475b4cf781434c44259b38bc |
| institution | Kabale University |
| issn | 1365-8050 |
| language | English |
| publishDate | 2023-10-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj-art-557d2d74475b4cf781434c44259b38bc2025-08-20T03:42:37ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502023-10-01vol. 25:2Discrete Algorithms10.46298/dmtcs.93999399Gossiping with interference in radio ring networksJean-Claude Bermond0Takako Kodate1Joseph Yu2Combinatorics, Optimization and Algorithms for TelecommunicationsTokyo Woman's Christian UniversityUniversity College of the Fraser ValleyIn this paper, we study the problem of gossiping with interference constraint in radio ring 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 message to every other node in the network. The gossiping problem consists in finding the minimum running time (makespan) of a gossiping protocol and algorithms that attain this makespan. We focus on the case where the transmission network is a ring 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 also suppose that, during one step, a node cannot be both a sender and a receiver (half duplex model). Moreover communication is subject to interference constraints. We use a primary node interference model where, if a node receives a message from one of its neighbors, its other neighbor cannot send at the same time. With these assumptions we completely solve the problem for ring networks. We first show lower bounds and then give gossiping algorithms which meet these lower bounds and so are optimal. The number of rounds depends on the congruences of n modulo 12.http://dmtcs.episciences.org/9399/pdfgossipingradio networksinterferencerings[info]computer science [cs][math]mathematics [math] |
| spellingShingle | Jean-Claude Bermond Takako Kodate Joseph Yu Gossiping with interference in radio ring networks Discrete Mathematics & Theoretical Computer Science gossiping radio networks interference rings [info]computer science [cs] [math]mathematics [math] |
| title | Gossiping with interference in radio ring networks |
| title_full | Gossiping with interference in radio ring networks |
| title_fullStr | Gossiping with interference in radio ring networks |
| title_full_unstemmed | Gossiping with interference in radio ring networks |
| title_short | Gossiping with interference in radio ring networks |
| title_sort | gossiping with interference in radio ring networks |
| topic | gossiping radio networks interference rings [info]computer science [cs] [math]mathematics [math] |
| url | http://dmtcs.episciences.org/9399/pdf |
| work_keys_str_mv | AT jeanclaudebermond gossipingwithinterferenceinradioringnetworks AT takakokodate gossipingwithinterferenceinradioringnetworks AT josephyu gossipingwithinterferenceinradioringnetworks |