|
Abstract : |
We present in this paper a general garbage collection scheme that reduces the ?noise ? in gossip-based broadcast algorithms. In short, our garbage collection scheme uses a simple heuristic to trade ?useless ? messages with ?useful? ones. Used with a given gossip-based broadcast algorithm, a given size of buffers, and a given number of disseminated messages (e.g., per gossip round), our garbage collection scheme provides higher overall reliability than more conventional schemes. We illustrate our approach through two algorithms: Bimodal Multicast (pbcast) [1] and Lightweight Probabilistic Broadcast (lpbcast) [5]. Our scheme is based on the intuitive idea of discarding messages according to their ?age?. The ?age ? of a message represents the number of times the message has been retransmitted. Roughly speaking, if you have to choose among a set of jokes to memorize, you might probably not choose the one you have heard the most often: it is very likely that there will be someone in your audience to already know this joke. 1, |
