NECO: Protocol Design for Distributed Delaunay Triangulation and Its Applications

NSF NeTS-NECO提案0830939：分布式Delaunay三角剖分协议设计及其应用[摘要]欧几里得空间中一组点的Delaunay三角剖分（DT）在不同的科学和工程领域有许多应用。分布式DT可用于改善各种网络（例如，P2P、覆盖、传感器和无线网络）以及模拟类型应用（包括分布式虚拟现实系统和多人在线游戏）的性能。发现正确的分布式DT的充分必要条件是本项目协议设计的基础，用于动态变化的节点系统（在d维空间中，d1）来构建和维护分布式DT。除了正确性和效率之外，准确性还被用作性能指标，因为不可能持续维护正确的分布式DT（一旦发生join、leave或故障，分布式DT的正确性就会被破坏）。设计了一套协议，可以从错误的系统状态中快速恢复，从而使系统处于“混乱”状态。在搅拌停止后迅速收敛到100%的精度。预期的结果包括(i)设计一个改进的协议套件，它比现有协议效率高一个数量级，并且仍然满足正确性和准确性的要求，以及（ii）为混乱系统构建分布式欧几里得最小生成树的协议。网络应用协议还设计用于贪婪路由、查找最近的节点、广播、组播、地理广播和集群。这些协议对于具有不准确（或虚拟）坐标的网络节点的性能正在研究中。研究者：Simon S. lamactive Grant awards名单NSF NeTS-NECO提案0830939：分布式Delaunay三角剖分协议设计及其应用，2008年9月1日至2011年8月31日NSF CNS-0434515: net - nr：一种检测共享拥塞和应用的新技术，2004年10月1日至2008年9月30日。林兆文获此资助：无（资助将于2008年9月30日届满）NSF CNS-0627020：合作研究项目：NeTS-NBD：不确定世界中的交通工程，2006年9月1日至2009年8月31日。本基金资助林世文：1个夏季月（2009年）

NSF NeTS-NECO Proposal 0830939: Protocol Design for Distributed Delaunay Triangulation and Its ApplicationsAward AbstractDelaunay triangulation (DT) of a set of points in Euclidean space has many applications in different fields of science and engineering. A distributed DT can be used to improve performance for a variety of networks (e.g., P2P, overlay, sensor, and wireless networks) as well as simulation-type applications, including distributed virtual reality systems and multiplayer online games. The discovery of a necessary and sufficient condition for a correct distributed DT is the basis of protocol design in this project for a dynamically changing system of nodes (in d-dimensional space, d 1) to construct and maintain a distributed DT. In addition to correctness and efficiency, accuracy is used as a performance metric because it is impossible to maintain a correct distributed DT continually (correctness of a distributed DT is broken as soon as a join, leave or failure occurs). A suite of protocols is designed that recovers quickly from incorrect system states such that a system that has been under ?churn? converges to 100% accuracy quickly after churning stops. Expected results include (i) the design of an improved protocol suite that is an order of magnitude more efficient than existing protocols and still satisfies requirements of correctness and accuracy, and (ii) protocols to construct a distributed Euclidean minimum spanning tree for systems under churn. Network application protocols are also designed for greedy routing, finding the closest node, broadcast, multicast, geocast, and clustering. The performance of these protocols for network nodes with inaccurate (or virtual) coordinates is being investigated.Investigator: Simon S. LamList of Active Grant Awards1. NSF NeTS-NECO Proposal 0830939: Protocol Design for Distributed Delaunay Triangulation and Its Applications, 9/1/08 to 8/31/11 Support for Simon Lam from this grant: 1 summer month (2009, 2010, 2011)2. NSF CNS-0434515: NeTS-NR: A Novel Technique to Detect Shared Congestion and Applications, 10/01/04 to 9/30/08. Support for Simon Lam from this grant: none (grant expires on 9/30/08)3. NSF CNS-0627020: Collaborative Research: NeTS-NBD: Traffic Engineering in an Uncertain World, 9/1/06 to 8/31/09. Support for Simon Lam from this grant: 1 summer month (2009)