Algorithm Design for Large Graphs and Communications Networks

大图和通信网络的算法设计

• 批准号: RGPIN-2016-04234
• 负责人: King, Valerie
• 金额: $ 3.93万
• 依托单位: University of Victoria
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2019
• 资助国家: 加拿大
• 起止时间: 2019-01-01 至 2020-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=690431
• 关键词: Algorithm; Design; Large; Graphs; Communications

Graphs are widely used to model connections between entities, such as links in communications networks, protein interactions, and social relationships. Massive graphs like the web graph or a model of the human brain may contain billions of nodes, making them hard to analyze, and where the nodes represent different agents, hard to coordinate. This puts a burden on computing resources like processing time, memory, and bandwidth in networks.******One approach to reduce time has been to recognize that such graph problems are typically ongoing, with incremental changes over time. Dynamic graph algorithms store information from prior computations so that solutions can be updated quickly as the graph changes. Another approach, when the graph is too large to fit into memory, is to create a compact representation or "sketch" of the graph as its edges stream into the computer and to then solve the problem on that sketch. A third approach is parallel or distributed computation, where the information about the graph is spread out over many processing nodes or the distributed network is itself a changing graph with problems to be solved.******Part I of this research is concerned with developing provably correct and efficient algorithms for large, changing graphs, by using ideas from dynamic graph algorithms and streaming. I am developing a type of "hybrid" algorithm which can maintain a solution to a graph problem quickly (and correctly with high probability) as edges are inserted and deleted, yet keeps only a sketch of the graph in memory while doing so. Representing graph information compactly is important for saving communication costs in distributed and parallel systems as well. Ideas from streaming and dynamic graphs can be used to find algorithms for distributed and parallel systems which are communication and time efficient. As both processing time and communication consume energy, understanding the possible trade-offs between these resources may enable more energy-efficient algorithms. Algorithms and lower bounds will be investigated. ******Part II explores fault tolerance in distributed networks. The creation of large decentralized networks of diverse agents, such as peer-to-peer networks, has created a need for protocols which are robust to the malicious behavior of some agents and can run in an asynchronous environment. We have recently made a theoretical breakthrough in a basic problem for that scenario, Byzantine agreement. It enables nodes to come to agreement without the use of secrecy or cryptography with qualitatively stronger provably correct guarantees than currently known schemes. This research will take the next steps to make this proof of concept a practical scheme. I will also explore other applications of our techniques, which include simplifying the design of randomized Byzantine fault tolerant protocols and reducing the effects of adversarial manipulation of data in a machine learning setting. ********

图广泛用于建模实体之间的连接，例如通信网络中的链接、蛋白质相互作用和社会关系。 像网络图或人脑模型这样的海量图可能包含数十亿个节点，这使得它们难以分析，并且节点代表不同的代理，难以协调。 这给计算资源（例如网络中的处理时间、内存和带宽）带来了负担。******减少时间的一种方法是认识到此类图问题通常是持续存在的，并且随着时间的推移而发生增量变化。动态图算法存储先前计算的信息，以便解决方案可以随着图的变化而快速更新。当图形太大而无法放入内存时，另一种方法是在图形的边缘流入计算机时创建图形的紧凑表示或“草图”，然后解决该草图上的问题。第三种方法是并行或分布式计算，其中有关图的信息分布在许多处理节点上，或者分布式网络本身就是一个需要解决的变化图。******本研究的第一部分涉及通过使用动态图算法和流的思想，为大型变化图开发可证明正确且高效的算法。我正在开发一种“混合”算法，它可以在插入和删除边时快速（并且以高概率正确地）维护图形问题的解决方案，但同时只在内存中保留图形的草图。 紧凑地表示图形信息对于节省分布式和并行系统中的通信成本也很重要。来自流和动态图的想法可用于寻找通信和时间高效的分布式并行系统的算法。由于处理时间和通信都会消耗能量，了解这些资源之间可能的权衡可能会启用更节能的算法。 将研究算法和下限。 ******第二部分探讨分布式网络中的容错能力。不同代理的大型去中心化网络（例如对等网络）的创建需要对某些代理的恶意行为具有鲁棒性并且可以在异步环境中运行的协议。我们最近在该场景的一个基本问题——拜占庭协议上取得了理论上的突破。它使节点能够在不使用保密或加密技术的情况下达成协议，并具有比当前已知方案更强大的可证明正确的保证。这项研究将采取下一步措施，使这一概念验证成为一个实用的方案。我还将探索我们技术的其他应用，其中包括简化随机拜占庭容错协议的设计以及减少机器学习环境中数据的对抗性操纵的影响。 ******