Algorithm Design for Large Graphs and Communications Networks

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

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

图被广泛用于实体之间的连接建模，例如通信网络中的链接、蛋白质相互作用和社会关系。像网络图或人脑模型这样的大规模图形可能包含数十亿个节点，这使得它们难以分析，并且节点代表不同的代理，难以协调。这给网络中的处理时间、内存和带宽等计算资源带来了负担。