Gossiping in a Multi-Channel Radio Network (An Oblivious Approach to Coping With Malicious Interference)

Seth Gilbert, Rachid Guerraoui
Springer, 2007
Conference paper

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 (Θ((1ϵ)nc1+logcn),Θ(n(1ϵ)ϵc2))(\Theta(\frac{(1-\epsilon)n}{c-1}+log_cn), \Theta(\frac{n(1-\epsilon)}{\epsilon c^2})) on the number of rounds needed to solve the ϵ\epsilon-gossip problem, a parameterized generalization of the all-to-all gossip problem that requires (1ϵ)n(1-\epsilon)n of the "rumors" to be successfully disseminated. Underlying our lower bound proof lies an interesting connection between ϵ\epsilon-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.

About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.
Related concepts


Related publications

No results