This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
27th International Conference on Distributed Computing Systems (ICDCS '07)
Protocol Design for Dynamic Delaunay Triangulation
Toronto, Canada
June 25-June 27
ISBN: 0-7695-2837-3
Dong-Young Lee, University of Texas at Austin
Simon S. Lam, University of Texas at Austin
Delaunay triangulation (DT) is a useful geometric structure for networking applications. In this paper we investigate the design of join, leave, and maintenance protocols to construct and maintain a distributed DT dynamically. We define a distributed DT and present a necessary and sufficient condition for a distributed DT to be correct. This condition is used as a guide for protocol design. We present join and leave protocols as well as correctness proofs for serial joins and leaves. In addition, to handle concurrent joins and leaves as well as node failures, we present a maintenance protocol. An accuracy metric is defined for a distributed DT. Experimental results show that our join, leave and maintenance protocols are scalable, and they achieve high accuracy for systems under churn and with node failures. We also present application protocols for greedy routing, clustering, broadcast, and multicast within a radius, and discuss and prove their correctness.
Citation:
Dong-Young Lee, Simon S. Lam, "Protocol Design for Dynamic Delaunay Triangulation," icdcs, pp.26, 27th International Conference on Distributed Computing Systems (ICDCS '07), 2007
Usage of this product signifies your acceptance of the Terms of Use.