AF: Small: Distributed Algorithmic Foundations of Dynamic Networks

AF：小：动态网络的分布式算法基础

• 批准号: 1527867
• 负责人: Gopal Pandurangan
• 金额: $ 40万
• 依托单位: University of Houston
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2015
• 资助国家: 美国
• 起止时间: 2015-09-01 至 2019-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1527867&HistoricalAwards=false
• 关键词: AF; Small; Distributed; Algorithmic; Foundations

The overarching goal of this project is to significantly advance the state of the art in the algorithmic foundations of distributed computing for dynamic networks. In a dynamic network, the topology of the network---both nodes (representing processors/endhosts) and communication links---changes continuously over time. Modern networking technologies such as peer-to-peer networks, overlay networks, and ad hoc wireless and mobile networks, are inherently very dynamic; furthermore, they are resource-constrained, unreliable, and vulnerable to attacks. Distributed/decentralized algorithms are critical to the efficient operation of large-scale communication networks, e.g., distributed shortest paths algorithms are used for routing in the Internet. Till recently, much of the distributed algorithmic theory developed over the last three decades has focused mainly on static networks; as such its results do not apply to dynamic networks. This necessitates the development of a solid theoretical foundation for robust, secure, and scalable distributed computing for dynamic networks. Such a foundation is critical to realize the full potential of these large-scale networks that have a wide variety of applications including communication, data storage and retrieval, environment monitoring, electronic commerce, resource distribution and sharing, and search.The project will develop a rigorous theoretical foundation for distributed computing in highly dynamic networks. In particular, it will develop and analyze distributed algorithms that scale well to very large-sized networks, are highly robust to dynamic changes and large-scale failures, and are secure against malicious participants in the network. The project will result in an algorithmic toolkit which will provide the building blocks for performing distributed computation in dynamic networks, besides providing algorithms with performance guarantees and theoretical benchmarks for practitioners. The project has the potential to impact the design and engineering of topologically-aware and self-regulating networks, i.e., networks that can measure, monitor, and regulate themselves in a decentralized fashion. The PI plans to develop a new course and a textbook on distributed network algorithms that is closely related to the research undertaken. This research will actively involve postdoctoral researchers, graduate students, and undergraduate students.The project has two key research goals. First, it will design and analyze scalable and robust distributed algorithms for fundamental distributed computing problems including agreement, leader election, storage and search, and routing. These problems are basic building blocks in distributed computing and are widely used. Motivated by fault-tolerance and security considerations, the project will study the above problems in an adversarial dynamic setting, that can also include the presence of Byzantine (malicious) nodes which may try to foil the distributed algorithm. The project will also study lower bounds on the performance of distributed algorithms including the amount of dynamism that can be tolerated. Second, it will develop fully-distributed algorithms for computing key global metrics of a network and to maintain dynamic networks with desirable properties. This addresses an important issue that is complementary and also critical to the first goal, i.e., how to measure basic parameters of a dynamic network such as its size, connectivity properties, conductance, average degree and other node-related statistics. A related goal is to construct and maintain dynamic networks with good topological properties such as low diameter, high connectivity, and high conductance. In both the above research goals, the key challenge is to design scalable distributed algorithms that are robust and fault-tolerant even under a high amount of dynamism and the presence of a large amount of Byzantine nodes. The project will build on and significantly extend the distributed algorithmic framework for dynamic networks that was recently developed by the PI and his collaborators.

该项目的总体目标是在动态网络的分布式计算算法基础中显着提高最新技术。 在动态网络中，网络的拓扑结构 - - 节点（代表处理器/Endhosts）和通信链接 - - 随着时间的流逝而不断变化。 现代网络技术，例如点对点网络，覆盖网络以及临时无线和移动网络，本质上是非常动态的。此外，它们是资源受限，不可靠的，并且容易受到攻击。 分布式/分散的算法对于大规模通信网络的有效操作至关重要，例如，分布式最短路径算法用于在Internet中路由。 直到最近，在过去的三十年中，许多分布式算法理论主要集中在静态网络上。因此，其结果不适用于动态网络。 这需要为动态网络的稳健，安全和可扩展的分布计算开发坚实的理论基础。 这样的基础对于实现这些大规模网络的全部潜力至关重要，这些网络具有各种应用程序，包括通信，数据存储和检索，环境监测，电子商务，资源分配和共享以及搜索。 特别是，它将开发和分析分布式算法，以很好地扩展到非常大的网络，对动态变化和大规模失败非常强大，并且可以防止网络中的恶意参与者。 该项目将导致算法工具包，除了为从业者提供具有性能保证和理论基准的算法外，还将为执行动态网络中执行分布式计算的构建块。 该项目有可能影响拓扑感知和自我调节网络的设计和工程，即可以以分散的方式测量，监视和调节自己的网络。 PI计划开发一门新课程和一本有关分布式网络算法的教科书，该课程与所进行的研究密切相关。这项研究将积极涉及博士后研究人员，研究生和本科生。该项目具有两个关键的研究目标。首先，它将设计和分析可扩展和健壮的分布式算法，以用于基本分布式计算问题，包括协议，领导者选举，存储和搜索以及路由。这些问题是分布式计算中的基本构建基础，并且被广泛使用。该项目以耐断层和安全性考虑的因素为动机，将在对抗性动态环境中研究上述问题，其中还可以包括拜占庭（恶意）节点的存在，这些节点可能试图试图挫败分布式算法。该项目还将研究分布式算法的性能，包括可以耐受的动态量。其次，它将开发完全分布的算法，用于计算网络的关键全局指标，并维护具有理想属性的动态网络。这解决了一个重要的问题，该问题是互补的，对于第一个目标，即如何测量动态网络的基本参数，例如其大小，连接性能，电导，平均程度和其他与节点相关的统计信息。 一个相关的目标是构建和维护具有良好拓扑特性的动态网络，例如低直径，高连通性和高电导率。在上述两个研究目标中，关键挑战是设计可扩展的分布式算法，即使在高度的动态和存在大量拜占庭节点的情况下，这些算法即使是稳健且容易耐受的算法。该项目将基于PI及其合作者最近开发的动态网络的分布式算法框架并大大扩展了分布式算法框架。

项目成果

Fast and Efficient Distributed Computation of Hamiltonian Cycles in Random Graphs

随机图中哈密顿环的快速高效分布式计算

• DOI: 10.1109/icdcs.2018.00079
• 发表时间: 2018
• 期刊: 38th IEEE International Conference on Distributed Computing Systems (ICDCS
• 作者: Chatterjee, Soumyottam;Fathi, Reza;Pandurangan, Gopal;Pham, Nguyen Dinh
• 通讯作者: Pham, Nguyen Dinh