**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.

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

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 $(\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-\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.

Official source

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

Loading

Related publications

No results

Related concepts (4)

In mathematics and computer science, an algorithm (ˈælɡərɪðəm) is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algo

A number is a mathematical object used to count, measure, and label. The original examples are the natural numbers 1, 2, 3, 4, and so forth. Numbers can be represented in language with number words.

Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many