We study the problem of reliable dissemination information in a wide area network. Traditional reliable broadcast protocols provide high reliability but do not scale well. Gossip-based protocols appear to be a viable approach. They have been developed to address scalability while still providing high reliability of message delivery. However, gossip protocols either ignore the topology of the wide-area network and thus incur a large load on some network elements or can suffer from a low reliability because they do not take the connectivity of the wide-area network into account. We present a new gossip protocol, called directional gossip, that uses flooding when necessary to attain good reliability and that uses gossip when flooding (and hence its inherent high overhead) is not needed. The determination of when to use flooding or gossip is done dynamically.

Pre-2018 CSE ID: CS1999-0622

Rumor mongering (also known as gossip) is an epidemiological protocol that implements broadcasting with a reliability that can be very high. Rumor mongering is attractive because it is generic, scalable, adapts well to failures and recoveries, and has a reliability that gracefully degrades with the number of failures in a run. In this paper we present a protocol that superficially resembles rumor mongering but is deterministic. We show that this new protocol has most of the same attractions as rumor mongering. The one attraction that rumor mongering has - namely graceful degradation - comes at a high cost in terms of the number of messages sent. We compare the two approaches both at an abstract level and in terms of how they perform in an Ethernet.

Pre-2018 CSE ID: CS1999-0637

A process that is under the control of an intruder may masquerade as a legitimate process and, like an arbitrarily faulty process, may not follow the specification that other processes expect it to. Given this similarity, it seems plausible to mask the effects of such compromised processes in the same way that one masks arbitrary failures. One must, however, be able to bound the number of such compromised processes. We examine this problem in the context of multicast protocols. We cast the problem into terms of availability, which is the probability that no more than a certain number of processes are infected. We consider the two questions "what is the availability of the system after having run for some period of time?" and "how long can a system run until the availability is unacceptably low?" We examine how the answers to these questions change as the number of processes grows, as the probability of a message being infective changes, and as different multicast strategies are used.

Pre-2018 CSE ID: CS1999-0610