After a long-drawn war, two nations, Oceania and Eurasia, are now at peace but in not much of talking terms. However, they will have to figure out how much shipment their combined rail network can carry from the capital city of Oceania to that of Eurasia. Both Oceania and Eurasia know about their own rail networks in detail, but none of them knows anything about other nation's network plans. Because of the political situation, they want to keep communication between them to a minimum. You are the chief researcher of Eurasia, in contact with Winston Smith, the chief researcher of Oceania. How much communication do you need to do to figure it out?
The aim of this project is to investigate such fundamental network problems where the network data is distributed between multiple processors. Such problems appear in countless guises in modern life: The transportation problem mentioned before is inspired by actual logistic difficulties that kept the US and Russia busy during the first half of the 20th century (see https://tinyurl.com/2p844c2y for a fun read). In the modern realm of data explosion, these network questions are more topical than ever: The network data (think of the friendship network of Facebook or the follower network of Twitter or the hyperlink network of Google) is usually too large to be stored in a single computational processor and hence is generally distributed among a large number of processors/servers who need to communicate with each other via a network in order to perform various computational tasks. This problem is generally addressed via different storage architectures for fast access and efficient software paradigms such as MapReduce, Hadoop, and Spark.
Many traditional algorithms that were widely used in the past have become greatly inefficient in practice for such distributed systems. The main goal of the proposed research is to design (or prove the hardness of) fundamental network algorithms and their generalisations in such distributed models of computation. To be concrete, we will mainly be interested in the following two models in this project.
- Two-party communication protocols: The graph data is distributed to two machines, namely Alice and Bob. Machines can access their local data for free, but it costs for them to communicate.
- Query protocols: The graph data is stored in external memory (e.g., among many external servers or cloud) and the local machine is allowed to access the data only by query accesses which can be answered quickly. "
The project will lead to major advances in our understanding of "distributed network algorithms", which is an important research area within theoretical computer science that is concerned with addressing precisely the question described above. The student will have the possibility to collaborate with prominent international experts from Max-Planck-Institut für Informatik (Germany), University of Illinois Urbana-Champaign (US), University of Warwick (UK) and Tata Institute of Fundamental Research (India).
About the Department
99 percent of our research is rated in the highest two categories in the REF 2021, meaning it is classed as world-leading or internationally excellent. We are rated as 8th nationally for the quality of our research environment, showing that the Department of Computer Science is a vibrant and progressive place to undertake research.
The algorithm research group is a rapidly expanding group with a clear focus on engaging in topical research and cutting-edge solutions. We aim to develop a fun and collaborative environment in the group while maintaining our research excellence. We also plan to host several visitors from around the world who are prominent experts in their field.
Known as the UK's greenest city, Sheffield is a beautiful and welcoming city where nature and culture intertwine. The historic Peak District National Park is only 20 mins away and there are enough activities in the city throughout the year to keep you entertained and help you maintain a proper work-life balance. Being centrally located in the country, it is well connected to the other research hubs in the country, which can be useful in collaborative research.
The student will be working in the research group of Dr. Sagnik Mukhopadhyay (https://sagnikm.github.io/). The research will mainly focus on theoretical aspects of graph algorithm design, i.e., we will use mathematical tools to make breakthroughs in distributed graph algorithm research.
We are looking for motivated and driven students with a keen interest in theoretical research in computer science. Applicants should hold a Master's degree in a related area (computer science or mathematics) even though exceptional candidates holding a bachelor's degree will be considered for the position. The project requires mathematical maturity and previous background in algorithm design and/or complexity theory. The applicant should also be willing to learn the necessary tools and techniques in order to execute the project successfully during the course of the Ph.D. journey. Previous experience in publishing in reputed conferences/journals is beneficial but not necessary.
If English is not your first language, you must have an IELTS score of 6.5 overall, with no less than 6.0 in each component.
How to Apply
To apply for a PhD studentship, applications must be made directly to the University of Sheffield using the Postgraduate Online Application Form. Make sure you name Dr Sagnik Mukhopadhyay as your proposed supervisor.
Information on what documents are required and a link to the application form can be found here - https://www.sheffield.ac.uk/postgraduate/phd/apply/applying
The form has comprehensive instructions for you to follow, and pop-up help is available.
You should include a research proposal, CV, transcripts, and at least two references. Your research proposal should:
- be no longer than 4 A4 pages, include references
- outline your reasons for applying for this studentship
- explain how you would approach the research, including details of your skills and experience in the topic area