Unreliable Gossip
Line van den Berg

Abstract:
Dynamic communication is the field that describes the spread of information throughout a network of agents. More specifically, it assumes that every agent has a secret and investigates how agents should decide, based on their own knowledge about the network, what calls to make so that ultimately everyone knows all the secrets. In the dynamic setting, next to sharing secrets, agents additionally share phone numbers. This means that while the context spreads, the network grows. In this thesis, we adapt the framework of dynamic communication to account for unreliable agents. The motivation behind this is the question whether the assumption that everybody is reliable is realistic for any kind of practical application. This adaptation for unreliable agents puts an additional requirement on the executed communication protocols: to not only result in everyone knowing all the secrets (of the reliable agents), but also in everyone successfully identifying the unreliable agents. With this we provide an exploration in the field of dynamic communication with a possibility of error. We show that already by introducing a small amount of unreliability the known results dynamic communication cannot be extended. In particular, we prove that the Learn New Secrets protocol may not be sufficient on networks with only terminal alternating bluffers, agents that bluff about their own secret in every second call they are involved in—whereas this was true in the reliable case. Additionally, we show that unreliable agents that do not initiate communication are harder to identify than those that do. This has some seemingly paradoxical consequences for the kind of security measures taken against fake news. Namely, as we will prove, that individual actions as deleting or blocking the agents that are considered unreliable might actually have the opposite effect on the network: the unreliable agents may remain unidentified by the entire network. This exemplifies that security measures against the spreading of false information might come at the cost of the identification of the unreliable source. In conclusion, by putting unreliability in the spotlight, this thesis takes the research of dynamic communication in the direction of practical application and opens the doors for future research.