Understanding Network Reliability
Project 2023-24
Project Title: Understanding Network Reliability
Lab/Research Group: Theory Group
The theory group consists of eight faculty members (plus four adjuncts) who use mathematical techniques to study problems throughout computer science. We work on network algorithms, coding theory, combinatorial optimization, computational geometry, data streams, dynamic algorithms and complexity, model checking and static analysis, database theory, descriptive complexity, parallel algorithms and architectures, and computational complexity theory. Members of the theory group wear other hats as well and collaborate throughout the department and the world beyond. For more details of the myriad work going on, please visit our web-pages.
You can find more about the group and the weekly seminars at https://groups.cs.umass.edu/theory/
Project Description:
One desirable feature of a network is its ability to withstand failures. There are two types of failures: node and edge. Traffic jam in a road network is an example of an edge failure. A non-functioning server in a network of hundred to thousand servers in a data center is an example of a node failure. A basic task in understanding the reliability of a network is to determine how many edges or nodes must fail before the network becomes disconnected. This task is the goal of this project.
Students in this project will learn basic data structures to represent a network. They also learn how to manipulate the data structures to perform basic computational tasks on the network, such as computing shortest paths or network flow. The students then deep dive into fast algorithms for testing network reliability. The goal is to implement and test these algorithms on real-world networks.
Learning Objectives:
The students should be able to:
(a) use and manipulate data structure for representing graph data,
(b) analyze an algorithmic problem on graphs,
(c) optimize the running time of a computer program, and (d) write and communicate research ideas.
Skills needed:
Knowing how to program is the only prerequisite along with clear communication.