Transcript Fast, Faster, and Correct

Fast, Faster, and Correct
Roy Friedman
Technion
Haifa
Israel
Based on work and discussions with Vadim Drabkin and Gabi Kliot
Talk Overview

Some recent experience with probabilistic
flooding/gossip in ad-hoc networks



Theoretical analysis, resulting in some design
guidelines
A protocol that follows those guidelines and its
performance analysis
Implications to P2P

Some rules of thumbs for developing efficient
gossip protocols
Ad-Hoc Networks

Devices equipped with omni-directional
wireless antennas

Can transmit messages to all other nodes within a
given transmission range R


Transmission disk model
By forwarding messages, a multiple-hop
network is formed
p
q
Transmission Overlap

On average, the transmission range of two
neighboring nodes is 39% [Tseng et al. 2002]

So, how many nodes should rebroadcast a message
to ensure broadcast delivery with high probability?
Reliability vs. # Transmissions
Probability that an arbitrary node does not receive a message
0.6
Non receive probability
0.55
Successfull transmission probability 1
0.5
Successfull transmission probability 0.8
0.45
Successfull transmission probability 0.6
0.4
0.35
0.3
0.25
0.2
0.15
0.1
0.05
0
1
2
3
4
5
6
Beta
7
8
9
10
Our Conclusions for MANETs

The number of senders in each one-hop
neighborhood should be a small constant
(w.r.t. the network density)
 Given the concaved shape of the graph


It is best to use probabilistic forwarding up to some
point
Then boost the reliability using deterministic
corrective measures
RAPID

A protocol that follows these design rules
Random/
Purely
Deterministic
random deterministic





The probability of forwarding a message is min(1,β/Nr), where
Nr is the number of locally observed neighbors, and β the
number from the optimal graph (2.5)
We use staggering to reduce collisions
If during the staggering one of the neighbors of p retransmits
the message, then the retransmission of p is aborted
If no neighbor retransmits the message after a longer timeout,
then p retransmit it
We use periodic deterministic gossiping of message headers


A node that discovers that it is missing a message m, asks for m
from the gossiper
There is also a version that tolerates selfish and malicious
behavior
Rapid Performance: Reliability
Rapid Performance: Overhead
Rapid Performance
Rapid Performance
What About P2P?

Analyzing random gossip using bins and balls
(Boris Koldehofe 2002)



n nodes/bins
m random forwarding of a message/balls
m / n
The reliability is then ne
# of non-receivers
The Reliability of Gossip
# retransmissions
High Availability 101

Suppose the probability of a simple PC is 0.99
 The probability that two PCs will be down at
the same time is 1-[(1-0.99)^2]=0.9999
 Since a PC is much cheaper than an FT
computer, one should use clusters for HA
Can we Apply the HA Principles for Gossip?

That is, can we use two concurrent cheap/fast
probabilistic gossip processes instead of a
single heavyweight one?
 Answer:

It depends on our cost model and how truly random
the probabilistic process is


For example, if the probabilistic process is perfect, and the
cost is the number of messages, then the only way to
boost the performance is using determinism
If the cost vs. reliability function is heavy tailed, then
we can also gain from multiple random processes
Possible Good Cases

Fast probabilistic dissemination, combined
with periodic gossip of headers (push+pull)


Since headers are shorter than messages, we can
win here probabilistically
Whenever the probabilistic process is not
purely random

E.g., suppose the dissemination is made to partial
views obtained with an lpbcast like membership
mechanism

Here two independent processes have a chance to correct
the imperfectness of each other
Conclusions

Probabilistic gossip/flooding is a simple, robust, and
effective mechanism to disseminate a message to a
large percentage of the nodes

Beyond that, in some cases we can boost the
reliability by having two concurrent probabilistic
processes, but in many cases it does not make sense

To obtain very high reliability, it is best to complement
the probabilistic process with a deterministic recovery
one
Open Issues

Identifying when it is possible to boost the
performance with two independent processes

Incorporating biased gossip

What kind of deterministic corrective measures
can be applied in P2P environments?