Strengthening Gossip Protocols using ProtocolDependent Knowledge 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 xe2x80x9cLearn New Secretsxe2x80x9d (LNS) wherein an agent a may only call another agent b if a does not know bxe2x80x99s 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 protocoldependent 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.

Revisiting Asynchronous Rumor Spreading in the Blockchain Era Asynchronous rumor spreading, or epidemic algorithms, are a class of data dissemination protocols that have been used throughout the years for a large variety of distributed applications. The emergence of largescale, public blockchains, such as Bitcoin and Ethereum, has reinvigorated research interest in these protocols as they are employed to disseminate pending transactions and confirmed blocks in their peertopeer (P2P) networks. Efficient, timely and faulttolerant information dissemination is vital for blockchain networks as it affects issues ranging from security to block finality. Recent works have analyzed the structural properties of blockchain network overlay graphs. Their findings show that they have inherent similarities to those of social networks, such as powerlaw degree distributions, small diameters and starlike communities. In this work, we present an experimental analysis of the vanilla asynchronous push u0026 pull rumor spreading protocol that is employed by public blockchains. This protocol, although robust and scalable, can be substantially improved. We demonstrate this by analyzing the effect that multiple parameters have on the protocolu0027s performance, such as using memory to avoid contacting the same neighbor twice in a row, varying the stopping criteria of nodes to decide when to stop spreading the rumor, employing more sophisticated neighbor selection policies instead of the standard uniform random choice and others. Prior works have focused on either providing theoretical upper bounds on the number of rounds needed to spread the rumor to all nodes, or, propose improvements by adjusting isolated parameters. To our knowledge, our work is the first to study how multiple parameters affect the protocolu0027s behavior both in isolation and combination and under a wide range of values. Moreover, prior theoretical works have studied rumor spreading only on bidirectional social topologies. Our study examines the behavior of the protocol in multiple topology classes. These include bidirectional, directed, and also a special type of social topologies, called signed topologies, which resemble more closely the topologies of blockchain P2P networks. Our work is the first to indicate and deal with how chains of communities that are sparsely connected to the core of the network can hamper the rumoru0027s spreading. Thus, we complement prior theoretical work to shed light on how the protocol behaves in practical, realworld, large scale distributed systems. Finally, through our detailed analysis, we demonstrate how a few simple additions to the protocol deliver a percentage decrease of the time required to inform all nodes by a maximum of 99.69% and an average of 86.04%.