Kirsten Hildrum, Sean Ma and Satish Rao

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-04-1329
June 2004

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2004/CSD-04-1329.pdf

Rumor spreading algorithms are a useful way to disseminate information to a group of players in the presence of faults. Rumors are either spread by pushing, in which the players knowing the rumor call other players at random and spread the rumor, or by pulling, where players who do not know the rumor call other players and ask for any new rumors.

The efficiency of these algorithms is often measured in the number of transmissions (the number of times the rumor is shared), but could also be measured in phone calls (the number of connections that need to be made between players).

In this technical report, we make two observations to reduce the number of phone calls. The first idea spreads the rumor in a randomized way and then uses a fixed-connection network (such as a tree) to finish sharing. This uses many fewer phone calls than pure rumor spreading, though some nodes may not be notified. Second, we observe that using both push and pull but pulling infrequently can reduce the number of phone calls if rumors enter the network at a slow rate.

BibTeX citation:

@techreport{Hildrum:CSD-04-1329,
    Author = {Hildrum, Kirsten and Ma, Sean and Rao, Satish},
    Title = {Randomized Rumor Spreading with Fewer Phone Calls},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {2004},
    Month = {Jun},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2004/5533.html},
    Number = {UCB/CSD-04-1329},
    Abstract = {Rumor spreading algorithms are a useful way to disseminate information to a group of players in the presence of faults. Rumors are either spread by pushing, in which the players knowing the rumor call other players at random and spread the rumor, or by pulling, where players who do not know the rumor call other players and ask for any new rumors. <p> The efficiency of these algorithms is often measured in the number of transmissions (the number of times the rumor is shared), but could also be measured in phone calls (the number of connections that need to be made between players). <p> In this technical report, we make two observations to reduce the number of phone calls. The first idea spreads the rumor in a randomized way and then uses a fixed-connection network (such as a tree) to finish sharing. This uses many fewer phone calls than pure rumor spreading, though some nodes may not be notified. Second, we observe that using both push and pull but pulling infrequently can reduce the number of phone calls if rumors enter the network at a slow rate.}
}

EndNote citation:

%0 Report
%A Hildrum, Kirsten
%A Ma, Sean
%A Rao, Satish
%T Randomized Rumor Spreading with Fewer Phone Calls
%I EECS Department, University of California, Berkeley
%D 2004
%@ UCB/CSD-04-1329
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2004/5533.html
%F Hildrum:CSD-04-1329