Dealing with Unreliable Agents in Dynamic Gossip

Line van den Berg*, Malvin Gattinger

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingChapterAcademicpeer-review

Abstract

Gossip describes the spread of information throughout a network of agents. It investigates how agents, each starting with a unique secret, can efficiently make peer-to-peer calls so that ultimately everyone knows all secrets. In Dynamic Gossip, agents share phone numbers in addition to secrets, which allows the network to grow at run-time.

Most gossip protocols assume that all agents are reliable, but this is not given for many practical applications. We drop this assumption and study Dynamic Gossip with unreliable agents. The aim is then for agents to learn all secrets of the reliable agents and to identify the unreliable agents.

We show that with unreliable agents classic results on Dynamic Gossip no longer hold. Specifically, the Learn New Secrets protocol is no longer characterised by the same class of graphs, so-called sun graphs. In addition, we show that unreliable agents that do not initiate communication are harder to identify than agents that do. This has paradoxical consequences for measures against unreliability, for example to combat the spread of fake news in social networks.
Original languageEnglish
Title of host publicationDynamic Logic. New Trends and Applications
Subtitle of host publicationThird International Workshop, DaLí 2020, Prague, Czech Republic, October 9–10, 2020, Revised Selected Papers
EditorsManuel A. Martins, Igor Sedlár
PublisherSpringer
Chapter4
Pages51-67
Number of pages17
ISBN (Electronic)978-3-030-65840-3
ISBN (Print)978-3-030-65839-7
DOIs
Publication statusPublished - 22-Dec-2020

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume12569
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Cite this