Publication
Through the decentralization of control and resources, distributed systems combine each participant's individual capabilities to achieve greater flexibility, scalability, and robustness compared to their centralized counterparts. The performance and consistency of a distributed system relies on efficient message spreading. This thesis focuses on one of the most prominent methods for achieving information dissemination, specifically ``gossiping''. Gossip protocols offer rapid, fault-tolerant, and asynchronous communication that can adapt to changes in the network environment. We examine from different angles their robustness, specifically the efficacy in the face of adversarial influence or network disruptions.
First, we investigate the susceptibility of gossip protocols to adversarial attacks. We focus on a large subclass of the so-called all-to-all protocols and analyze their vulnerability to disruptions caused by process crashes and communication delays. For doing so, we propose an adaptive adversary called Universal Gossip Fighter (UGF). We prove that UGF effectively hampers execution time and message complexity of any all-to-all gossip protocol, thereby preventing scalability. We support our theoretical findings with experimental evaluations.
Next, we examine the anonymity of message sources in gossip protocols. We do so by adopting the well-recognized concept of -differential privacy (-DP) that provides anonymity guarantees that hold against any adversarial attack. First, we prove a fundamental limit on -DP for source anonymity for any gossip protocol. Then, we demonstrate that a large family of gossip protocols, namely cobra walks, achieves tight privacy guarantees. We conclude that gossip protocols, which initially spread messages as a random walk, offer the highest level of source anonymity. Additionally, our tight analysis precisely captures the trade-off between dissemination time of a gossip protocol and its source anonymity.
Last, we study gossip-based peer-samplers -- services that provide each system participant with a random sample of other peers to interact with. Many distributed applications rely on peer samplers to ensure robust performance. Despite the practical effectiveness of existing peer samplers, their ability to produce random samples within a reasonable time remains theoretically unproven. We bridge this gap by introducing PeerSwap, a protocol that provides system participants with provably random samples. We establish execution time bounds for PeerSwap both theoretically and experimentally, demonstrating its effectiveness.