Department of Computer Sciences

The University of Texas at Austin

Director:
**Simon S. Lam**
(more publications)

**Protocol design for
distributed Delaunay triangulation**

Delaunay triangulation (DT) is a useful geometric
structure that has a long history and many applications in different fields of
science and engineering. Consider a set of nodes (points) that form a DT.
Each node is identified by its location specified by coordinates. For
nodes in a 2D space, Bose and Morin (2004) proved that greedy routing on a DT
always succeeds to find a given destination node. We extended their result
and proved that given a destination location *p* in a *d*-dimensional
Euclidean space (*d *> 1), greedy routing on a DT always finds a DT node that is closest to *p*.
More specifically, if a node exists at location *p*, it is found; else, a
node closest to *p* is found. Note that greedy routing on a DT does
not always find the shortest route, but the quality of the greedy route is very
good, i.e., within a constant of the direct distance.

It is also interesting to note that greedy routing on a
DT always succeeds even if node locations are specified by inaccurate or even
arbitrary coordinates. Our goal is to exploit this
and other properties of DT for its use in wireless mesh networks, p2p networks,
and distributed virtual environments. Towards this goal, we first define a
distributed DT and present a necessary and sufficient condition for a
distributed DT to be correct.

Using the necessary and sufficient condition for correctness as a guide, we
design a protocol suite for a set of nodes in *d*-dimension (*d* > 1)
to construct and maintain a distributed DT in a dynamic environment. The join,
leave, and failure protocols in the suite are proved to be correct for a single
join, leave, and failure, respectively. For a system under churn, it is
impossible to maintain a correct distributed DT continually. We define an
accuracy metric such that accuracy is 100% if and only if the distributed DT is
correct. The suite also includes a maintenance protocol designed to recover from
incorrect system states and to improve accuracy. Experimental results show
that our new suite of protocols maintains high accuracy for systems under churn
and each system converges to 100% accuracy after churning stopped.

We design several application protocols, in addition to greedy routing, which run on top of a correct distributed DT to support networking and simulation-type applications. They include protocols for finding a closest existing node, broadcast, and geocast. We prove that our broadcast and geocast protocols always deliver a message to every target node. Our broadcast and geocast protocols are also efficient in the sense that very few target nodes receive duplicate messages, and non-target nodes receive no message. We evaluate their performance characteristics using simulation experiments, and investigate the impact of inaccurate coordinates, as well as "virtual coordinates," on the performance of greedy routing, broadcast, and geocast.

- Efficient
and Accurate Protocols for Distributed Delaunay Triangulation under Churn

Dong-Young Lee and Simon S. Lam*Proceedings IEEE ICNP 2008*, Orlando, Florida, October 2008 (technical report with corrigenda). - A
Radius Geocast Routing Protocol

Dong-Young Lee, Eui Kyung Chung, and Simon S. Lam

*Proceedings IEEE International Conference on High Performance Computing and Communications*, Dalian, China, September 2008. - Protocol
Design for Dynamic Delaunay Triangulation

Dong-Young Lee and Simon S. Lam*Proceedings of 27th IEEE ICDCS*, Toronto, June 2007 (please read the more complete technical report version)