Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Conferences, Workshops, Symposiums, and Seminars
  4. Gossiping in a Multi-Channel Radio Network (An Oblivious Approach to Coping With Malicious Interference)
 
conference paper

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

Dolev, Shlomi
•
Gilbert, Seth  
•
Guerraoui, Rachid  
Show more
2007
Proceedings of the 21st International Symposium on Distributed Computing (DISC'07)
Symposium on Distributed Computing (DISC'07)

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.

  • Files
  • Details
  • Metrics
Loading...
Thumbnail Image
Name

multichannel.pdf

Type

N/a

Access type

openaccess

License Condition

Copyright

Size

228.94 KB

Format

Adobe PDF

Checksum (MD5)

aa35d130eb4adba3781ade477ef4db50

Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés