College Publications logo   College Publications title  
View Basket
Homepage Contact page
   
 
AiML
Academia Brasileira de Filosofia
Algorithmics
Cadernos de Lógica e Computação
Cadernos de Lógica e Filosofia
Cahiers de Logique et d'Epistemologie
Communication, Mind and Language
Computing
Cuadernos de lógica, Epistemología y Lenguaje
DEON
Dialogues
Economics
Encyclopaedia of Logic
Filosofia
Handbooks
Historia Logicae
IfColog series in Computational Logic
IfColog Lecture series
IfColog Proceedings
Journal of Applied Logics - IfCoLog Journal
About
Editorial Board
Scope of the Journal
Submissions
Forthcoming papers
Journals
Landscapes
Logics for New-Generation AI
Logic and Law
Logic and Semiotics
Logic PhDs
Logic, Methodology and Philosophy of Science
The Logica Yearbook
Neural Computing and Artificial Intelligence
Philosophy
Research
The SILFS series
Studies in Logic
Studies in Talmudic Logic
Systems
Texts in Logic and Reasoning
Texts in Mathematics
Tributes
Other
Digital Downloads
Information for authors
About us
Search for Books
 



Forthcoming papers


Back

Strengthening Gossip Protocols using Protocol-Dependent Knowledge

Hans van Ditmarsch, Malvin Gattinger, Louwe B. Kuijer and Pere Pardo

Distributed dynamic gossip is a generalization of the classic telephone problem in which agents communicate to share secrets, with the additional twist that also telephone numbers are exchanged to determine who can call whom.

Recent work focused on the success conditions of simple protocols such as ``Learn New Secrets'' (LNS) wherein an agent $a$ may only call another agent $b$ if $a$ does not know $b$'s secret.

A protocol execution is successful if all agents get to know all secrets.

On partial networks these protocols sometimes fail because they ignore information available to the agents that would allow for better coordination.

We study how epistemic protocols for dynamic gossip can be strengthened, using epistemic logic as a simple protocol language with a new operator for protocol-dependent knowledge.

We provide definitions of different strengthenings and show that they perform better than LNS, but we also prove that there is no strengthening of $LNS$ that always terminates successfully.

Together, this gives us a better picture of when and how epistemic coordination can help in the dynamic gossip problem in particular and distributed systems in general.


11 October 2018






© 2005–2022 College Publications / VFH webmaster