A push&pull gossiping primitive for replica sub-networks
A broadcast communication primitive that can be used for communicating within a group has various utilities, and is widely studied by distributed computing community. One of the obvious need for such a communication mechanism in P2P systems is to maintain replicas. In a peer-to-peer setting, there are some additional challenges than traditionally encountered to achieve such a communication primitive. These challenges include:
- Lack of global knowledge at individual peers, i.e.; a fully connected graph as assumed in traditional gossip algorithms is not valid.
- Membership dynamics is the norm, i.e.; the limited number of faults or the fail-stop models considered traditionally do not hold.
We propose a hybrid push&pull scheme. The essential idea is to probabilistically spread the gossip/update among all the online peers. The peers offline during the push phase may then pull the gossip from some online replica(s). This procedure ensures that the online peer population is up-to-date.
Challenges for an effective and efficient push scheme
In order to deal with the the unreliability of individual peers (which may go offline even during the push phase), it is essential to have redundancy. On the other hand, to make the communication primitive efficient it is important to reduce communication overhead by reducing the actual duplicate messages received by peers.
Probabilistic solution
We deal with these conflicting design goals be exploiting the fact that the gossip initially spreads fast to unaffected members, while at later stage, most peers have received the gossip, and hence reducing the probability of forwarding (PF) of the gossip with age. Also a randomized partial list of peers to which the gossip had been sent is piggy-backed to reduce duplicates. Such probabilistic techniques can eliminate substantial amount of duplicates without compromising the coverage. The guarantees for such an algorithm are probabilistic in nature, which is good enough given the highly unreliable environment, and potential application scenarios.
