loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
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
Weinong Wang, 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
Usage of this product signifies your acceptance of the Terms of Use.