Algorithm Design for Large Graphs and Communications Networks

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

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. ********