Discrete Location Theory and Its Application to Peer-to-Peer Computing

离散定位理论关注的是组合优化问题，其中空间因素起着突出的作用。例如，一个基本的离散定位问题要求在给定度量空间中标记指定数量的点，以便所有点到最近标记点的距离之和最小。点对点计算是一门新兴的学科，它关注的是动态节点集合的无缝互连，目的是共享计算资源，如带宽、存储和CPU。一个良好的一阶点对点网络模型假设节点位于度量空间中，并且一对节点之间的通信成本由底层度量空间中的相应距离给出。由于点对点网络中的节点间距离往往变化很大，空间考虑在点对点计算中起着突出的作用。该项目解决了离散定位理论中的一些基本问题，强调了在点对点计算应用中出现的问题。离散定位理论并不是一门新学科，在运筹学领域已经研究了几十年。这一领域的许多基本问题都是np困难的，因此从业者通常采用启发式方法来寻找最优或接近最优的解决方案。不幸的是，除了少数例外，这些启发式方法返回的解决方案可能与最佳解决方案相差甚远。近年来，人们对设计和分析可证明的np -hard优化问题的良好近似算法产生了浓厚的兴趣。这项研究揭示了许多基本离散定位问题的近似性，例如，确定了设施定位问题的最佳解决方案可以在多项式时间内近似于1.52因子，但达到1.463因子将违反标准硬度假设。考虑到这些理论的进步，人们很自然地会问，这些可证明的良好近似算法在实践中是否优于现有的启发式算法。在大多数情况下，情况并非如此，因为这些近似算法的运行时间虽然是多项式，但往往比现有的启发式算法要高得多。对于本项目中解决的离散位置问题，本项目的主要目标是开发在运行时间和易于实现方面与现有启发式相当（或改进）的常因子近似算法。点对点计算是一个具有明显潜力的年轻领域，但在实现这一潜力之前，仍有重大的技术挑战有待解决。点对点比客户机-服务器更具可伸缩性，它支持现有服务器群无法支持的大范围大规模应用程序。此外，点对点计算有望为普通用户提供类似超级计算机的性能。但在实现这些崇高的目标之前，现有的点对点系统需要大量的改进和扩展，以全面解决与局域性、并发性、容错性、自稳定性、异构性、成本分担和安全性相关的问题。该项目研究了设计实用且可证明高效的点对点基础设施的新方法，强调了与位置相关的问题。

Discrete location theory is concerned with combinatorial optimizationproblems in which spatial considerations play a prominent role. Forexample, one basic discrete location problem asks for a specifiednumber of points in a given metric space to be marked so that the sum,over all points, of the distance to the nearest marked point isminimized. Peer-to-peer computing is an emerging discipline concernedwith the seamless interconnection of dynamic collections of nodes forthe purpose of sharing computational resources such as bandwidth,storage, and CPU. A good first-order model of peer-to-peer networksassumes that the nodes reside in a metric space, and that the cost ofcommunication between a pair of nodes is given by the correspondingdistance in the underlying metric space. Because the internodedistances in peer-to-peer networks tend to vary significantly, spatialconsiderations play a prominent role in peer-to-peer computing. Thisproject addresses a number of basic questions in discrete locationtheory, emphasizing questions that arise in applications topeer-to-peer computing.Discrete location theory is not a new subject, having been studiedwithin the operations research community for decades. Many of thebasic problems in this area are NP-hard, so practitioners havegenerally resorted to heuristics in order to search for optimal ornear-optimal solutions. Unfortunately, with few exceptions, thesolutions returned by these heuristics can be arbitrarily far fromoptimal. In recent years, there has been an explosion of interest inthe design and analysis of provably good approximation algorithms forNP-hard optimization problems. This research has shed considerablelight on the approximability of a number of basic discrete locationproblems, for example, establishing that the optimal solution to thefacility location problem can be approximated to within a factor of1.52 in polynomial time, but that achieving a factor of 1.463 wouldviolate a standard hardness assumption. Given such theoreticaladvances, it is natural to ask whether these provably goodapproximation algorithms are preferable to existing heuristics inpractice. For the most part this is not the case, since the runningtimes of these approximation algorithms, while polynomial, tend to beconsiderably higher than those of existing heuristics. For thediscrete location problems addressed in this project, the primaryobjective of this project is to develop constant-factor approximationalgorithms that are comparable to (or improve upon) existingheuristics in terms of running time and ease of implementation.Peer-to-peer computing is a young field with obvious potential, butsignificant technical challenges remain to be addressed before thispotential can be realized. More scalable than client-server,peer-to-peer enables a wide-range of large-scale applications thatcannot be supported by existing server farms. Furthermore,peer-to-peer computing holds the promise of deliveringsupercomputer-like performance to the average user. But before suchlofty goals can be achieved, existing peer-to-peer systems need to besignificantly refined and extended in order to comprehensively addressissues related to locality, concurrency, fault tolerance,self-stabilization, heterogeneity, cost sharing, and security. Thisproject investigates novel approaches to the design of practical andprovably efficient peer-to-peer infrastructure, emphasizinglocality-related concerns.