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. The Universal Gossip Fighter
 
conference paper

The Universal Gossip Fighter

Gorbunova, Anastasiia
•
Guerraoui, Rachid  
•
Kermarrec, Anne-Marie  
Show more
May 30, 2022
2022 Ieee 36Th International Parallel And Distributed Processing Symposium (Ipdps 2022)
36th IEEE International Parallel & Distributed Processing Symposium (IPDPS 2022)

The notion of adversary is a staple of distributed computing. An adversary typically models “hostile” assumptions about the underlying distributed environment, e.g., a network that can drop messages, an operating system that can delay processes or an attacker that can hack machines. So far, the goal of distributed computing researchers has mainly been to develop a distributed algorithm that can face a given adversary, the abstraction characterizing worst-case scenarios. This paper initiates the study of the somehow opposite approach. Given a distributed algorithm, the adversary is the abstraction we seek to implement. More specifically, we consider the problem of controlling the spread of messages in a large- scale system, conveying the practical motivation of limiting the dissemination of fake news or viruses. Essentially, we assume a general class of gossip protocols, called all-to-all gossip protocols, and devise a practical method to hinder the dissemination. We present the Universal Gossip Fighter (UGF). Just like classical adversaries in distributed computing, UGF can observe the status of a dissemination and decide to stop some processes or delay some messages. The originality of UGF lies in the fact that it is universal, i.e., it applies to any all-to-all gossip protocol. We show that any gossip protocol attacked by UGF ends up exhibiting a quadratic message complexity (in the total number of processes) if it achieves sublinear time of dissemination. We also show that if a gossip protocol aims to achieve a message complexity α times smaller than quadratic, then the time complexity rises exponentially in relation to α. We convey the practical relevance of our theoretical findings by implementing UGF and conducting a set of empirical experiments that confirm some of our results.

  • Files
  • Details
  • Metrics
Type
conference paper
DOI
10.1109/IPDPS53621.2022.00116
Web of Science ID

WOS:000854096200108

Author(s)
Gorbunova, Anastasiia
Guerraoui, Rachid  
Kermarrec, Anne-Marie  
Kucherenko, Anastasiia  
Pinot, Rafaël  
Date Issued

2022-05-30

Publisher

IEEE

Published in
2022 Ieee 36Th International Parallel And Distributed Processing Symposium (Ipdps 2022)
ISBN of the book

978-1-6654-8106-9

Start page

1162

End page

1172

Subjects

Distributed Computing

•

Gossip Protocols

•

Adaptive Adversaries

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
DCL  
SACS  
Event nameEvent placeEvent date
36th IEEE International Parallel & Distributed Processing Symposium (IPDPS 2022)

Online

May 30 – June 3, 2022

Available on Infoscience
March 7, 2022
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/186057
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