what-when-how
In Depth Tutorials and Information
message over longer distances. Kleinberg states that the value of
r
that best balances
this trade-off algorithmically is
r
= 2, which brings us to his
heorem2
.
[5]:
hereisadecentralizedalgorithmAandaconstant
α
2
,independentofn,
sothatwhenr=2andp=q=1,theexpecteddeliverytimeofAisatmost
α
2
(logn)
2
.
he consequence of these two theorems is that, when long-range contacts are
made independently of the grid geometry, short chains will exist, but the nodes will
not be able to find them using only local information. However, when the long-
range contacts are affected in a certain way by the grid geometry, the nodes are able
to find these short chains. Kleinberg notes this as a fundamental consequence of
his model. he representations of inverse
r
-
th power distributions can be seen in
Figures 5.7, 5.8, and 5.9.
In order to achieve the bound of heorem 2, a decentralized algorithm must
follow a simple rule: in each step, the current message holder
u
chooses a contact
that is as close to the target
t
as possible, in the sense of lattice distance. One can see
how this rule benefits from having long-range contacts in relatively close vicinity.
With this rule,
u
does not even need to know anything about the previous message
holders.
A strong characterization theorem can be shown for this family of models:
r
= 2
is the only value for which there is a decentralized algorithm capable of producing
Figure 5.7
The inverse r-th power distribution with r = 1 and n = 9. (From J.
Kleinberg,Thesmall-worldphenomenon:Analgorithmperspective,
Annual ACM
Symposium on Theory of Computing
,2000,pp.163-170.)
