Gossiping in a Multi-channel Radio Network
Lists
Only you see this
Abstract
We study oblivious deterministic gossip algorithms for multi-channel radio networks with a malicious adversary. In a multi-channel network, each of the n processes in the system must choose, in each round, one of the c channels of the system on which to participate. Assuming the adversary can disrupt one channel per round, preventing communication on that channel, we establish a tight bound of $\max\left(\Theta\left(\frac{(1-\epsilon)n}{c-1} + \log_c{n}\right), \Theta\left(\frac{n(1-\epsilon)}{\epsilon c^2}\right)\right)$ on the number of rounds needed to solve the ε-gossip problem, a parameterized generalization of the all-to-all gossip problem that requires (1 − ε)n of the “rumors” to be successfully disseminated. Underlying our lower bound proof lies an interesting connection between ε-gossip and extremal graph theory. Specifically, we make use of Turán’s theorem, a seminal result in extremal combinatorics, to reason about an adversary’s optimal strategy for disrupting an algorithm of a given duration. We then show how to generalize our upper bound to cope with an adversary that can simultaneously disrupt t < c channels. Our generalization makes use of selectors: a combinatorial tool that guarantees that any subset of processes will be “selected” by some set in the selector. We prove this generalized algorithm optimal if a maximum number of values is to be gossiped. We conclude by extending our algorithm to tolerate traditional Byzantine corruption faults.
BibTeX
@inproceedings{dolev2007gossiping,
author = {Shlomi Dolev and Seth Gilbert and Rachid Guerraoui and Calvin C. Newport},
title = {{Gossiping in a Multi-channel Radio Network}},
booktitle = {DISC},
year = {2007},
doi = {10.1007/978-3-540-75142-7\_18},
}Loading related content...