Tuesday, January 11, 2011
New algorithm enables much faster dissemination of information through self-organizing networks: Censor-Hillel and Shachnai’s algorithm works by alternating communication strategies from round to round. In the first round, you select a neighboring device at random and send it all the information you have — which, since it’s the first round, is limited to the measurement that you yourself have performed. That same round, however, other devices may contact you and send you their information. In the second round, you don’t just select a neighbor at random; you select a neighbor whose information you have not yet received. In the third round, you again select a neighbor at random. By the end of that round, since every device on the network forwards all the information it has, you’ve received not only the measurements performed by the devices you contacted, nor just the measurements performed by the devices that contacted you, but measurements performed by neighbors of your neighbors, and even neighbors of neighbors of neighbors. In the fourth round, you again select a device whose information you haven’t received; in the fifth, you select a device at random; and so on.