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