### Spatial gossip and resource location protocolsSpatial gossip and resource location protocols

Access Restriction
Subscribed

 Author Kempe, David ♦ Kleinberg, Jon ♦ Demers, Alan Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2004 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Gossip ♦ Decentralized algorithm ♦ Resource location Abstract The dynamic behavior of a network in which information is changing continuously over time requires robust and efficient mechanisms for keeping nodes updated about new information. Gossip protocols are mechanisms for this task in which nodes communicate with one another according to some underlying deterministic or randomized algorithm, exchanging information in each communication step. In a variety of contexts, the use of randomization to propagate information has been found to provide better reliability and scalability than more regimented deterministic approaches.In many settings, such as a cluster of distributed computing hosts, new information is generated at individual nodes, and is most "interesting" to nodes that are nearby. Thus, we propose distance-based propagation bounds as a performance measure for gossip mechanisms: a node at distance $\textit{d}$ from the origin of a new piece of information should be able to learn about this information with a delay that grows slowly with $\textit{d},$ and is $\textit{independent}$ of the size of the network.For nodes arranged with uniform density in Euclidean space, we present natural gossip mechanisms, called spatial gossip, that satisfy such a guarantee: new information is spread to nodes at distance $\textit{d},$ with high probability, in $\textit{O}(log1$ + ϵ $\textit{d})$ time steps. Such a bound combines the desirable qualitative features of uniform gossip, in which information is spread with a delay that is logarithmic in the full network size, and deterministic flooding, in which information is spread with a delay that is linear in the distance and independent of the network size. Our mechanisms and their analysis resolve a conjecture of Demers et al. [1987].We further show an application of our gossip mechanisms to a basic resource location problem, in which nodes seek to rapidly learn the location of the nearest copy of a $\textit{resource}$ in a network. This problem, which is of considerable practical importance, can be solved by a very simple protocol using Spatial Gossip, whereas we can show that no protocol built on top of uniform gossip can inform nodes of their approximately nearest resource within poly-logarithmic time. The analysis relies on an additional useful property of spatial gossip, namely that information travels from its source to sinks along short paths not visiting points of the network far from the two nodes. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2004-11-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 51 Issue Number 6 Page Count 25 Starting Page 943 Ending Page 967

#### Open content in new tab

Source: ACM Digital Library