Algorithm Design for Large Graphs and Communications Networks

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

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

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