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
Qi Xia, Shanghai Jiaotong University, Shanghai, China
Ruijun Yang, Shanghai Jiaotong University, Shanghai, China
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