Name
Abstract | ||
|---|---|---|
We study distributed broadcasting protocols with few transmissions (`shotsu0027) in radio networks where the topology is unknown. In particular, we examine the case in which a bound $k$ is given and a node may transmit at most $k$ times during the broadcasting protocol. Initially, we focus on oblivious algorithms for $k$-shot broadcasting, that is, algorithms where each node decides whether to transmit or not with no consideration of the transmission history. Our main contributions are (a) a lower bound of $Omega(n^2/k)$ on the broadcasting time of any oblivious $k$-shot broadcasting algorithm and (b) an oblivious broadcasting protocol that achieves a matching upper bound, namely $O(n^2/k)$, for every $k le sqrt{n}$ and an upper bound of $O(n^{3/2})$ for every $k u003e sqrt{n}$. We also study the general case of adaptive broadcasting protocols where nodes decide whether to transmit based on all the available information, namely the transmission history known by each. We prove a lower bound of $Omegaleft(n^{frac{1+k}{k}}right)$ on the broadcasting time of any protocol by introducing the emph{transmission tree} construction which generalizes previous approaches. |
Year | Venue | Field |
|---|---|---|
2016 | arXiv: Distributed, Parallel, and Cluster Computing | Broadcasting,Radio networks,Broadcasting algorithms,Upper and lower bounds,Computer science,Omega,Distributed computing |
DocType | Volume | Citations |
Journal | abs/1603.08393 | 0 |
PageRank | References | Authors |
0.34 | 4 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Sushanta Karmakar | 1 | 35 | 13.86 |
| Paraschos Koutris | 2 | 347 | 26.63 |
| Aris Pagourtzis | 3 | 150 | 25.24 |
| Dimitris Sakavalas | 4 | 15 | 5.46 |