 |
|
|
|
|
|
|
|
|
|
|
| q |
Control of message overhead for flooding is difficult:
|
|
|
Unknown network coverage as a function of the distance d
|
|
Coverage may rise e.g. from 3% to 30%
in one step d d + 1
|
|
|
| q |
A random walk of predefined length L
has fixed expense
|
|
|
Randoms walks can proceed in parallel, with forking or
|
|
|
can be enhanced by flooding
with small d from some points
|
|
|
Many ways to combine random walks &
flooding schemes
|
|
(see Gkantsidis et al., IEEE
Infocom 2004 & ’05)
|
|
|
Network coverage is partial, but
random walk searches are
|
|
|
efficient e.g. for replicated data in
P2P networks
|
|
|
Random network growth is also
efficiently supported by r. walks
|