Sixth International Conference on Parallel and Distributed Computing Applications and Technologies (PDCAT'05) Spatial Gossip on the Percolation Model Dalian, China December 05-December 08 ISBN: 0-7695-2405-2
For scalability and reliability, gossip protocol is widely used in distributed database updates, information dissemination, membership maintenance et al. Spatial gossip [9], which means gossiping within a finite distance independent of the network size, was also proposed to rapidly locate resource in some networks, such as wireless sensor networks. The previous study on spatial gossip used a percolation model, where in each step, a node x chooses a random node y to forward message with probability \beta /(d_{xy} +1)^8 . The study showed a fine result that if D \le s \le 2D, where D is the dimension of the network, the propagation time steps for a message propagated to a node within distance d is O(\log ^{2+\varepsilon}d), with probability 1 -o(\log ^{-k}d). Our work uses a similar model, but let s = D, we show through explicit computation that the propagation time is better, i.e, O(log d) with probability 1 - O(d^k ). We further discuss other cases where s is chosen different values, and point out the limitation of the percolation model.
Citation:
Qi Xia, Ruijun Yang, Weinong Wang, "Spatial Gossip on the Percolation Model," pdcat, pp.755-758, Sixth International Conference on Parallel and Distributed Computing Applications and Technologies (PDCAT'05), 2005 Usage of this product signifies your acceptance of the Terms of Use. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||