Database and Data Management - Field Guide to Hadoop - page 33

test the hypothesis that everyone in the industry is connected to Kevin Bacon within six hops
in the graph. Each node is given an initial value to the number of hops; for Kevin Bacon, it is
zero. For everyone else, the initial value is a very large integer. At the first superstep, each
node sends its value to all those nodes connected to it. Then, at each of the other supersteps,
each node first reads all its messages and takes the minimum value. If it is less than its cur-
rent value, the node adds 1 and then sends this to all its connected nodes at the end of the su-
perstep. Why? Because if a connected node is N steps from Kevin, then this node is at mosts
N+1 steps away. Once a node has established a new value, it opts out of sending more mes-
sages.
At the end of six supersteps, you'll have all the persons connected to Kevin Bacon by six or
fewer hops.
Tutorial Links
The official product page has a quick start guide . In addition, there are a handful of video-
taped talks, including one by PayPal and another by Facebook . Finally, there's this particu-
larly informative blog post .