Tolerating Malicious Gossip

Abstract

A new class of gossip protocols is presented to diffuse updates securely. The protocols rely on annotating updates with the path along which they travel. To avoid a combinatorial explosion in the number of such annotated updates, rules are employed to choose which updates to keep. Different sets of rules lead to different protocols. Results of simulated executions of a collection of such protocols are described---the protocols would appear to be practical, even in large networks.