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