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

离散选址理论关注的是组合优化问题，其中空间因素起着突出的作用。 例如，一个基本的离散定位问题要求在一个给定的度量空间中指定数量的点被标记，以便在所有点上，到最近的标记点的距离之和最小化。 Peer-to-Peer计算是一门新兴的学科，它关注于节点的动态集合之间的无缝互连，以共享带宽、存储和CPU等计算资源。 一个好的对等网络一阶模型假设节点位于一个度量空间中，一对节点之间的通信成本由底层度量空间中相应的距离给出。 由于对等网络中的节点间距离往往变化很大，因此空间考虑在对等计算中起着突出的作用。 这个项目解决了离散位置理论中的一些基本问题，强调了在点对点计算应用中出现的问题。离散位置理论并不是一个新的学科，在运筹学界已经研究了几十年。 这一领域的许多基本问题都是NP难的，因此，实践者通常采用数学方法来寻找最优或近似最优的解。 不幸的是，除了少数例外，这些算法返回的解可以任意远离最优解。 近年来，对于NP-难优化问题，设计和分析可证明是好的近似算法引起了人们极大的兴趣。 这项研究揭示了一些基本离散选址问题的可近似性，例如，建立了设施选址问题的最优解可以在多项式时间内近似到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.