Project on Constrained Distributed Symmetry Breaking
Funded by the Icelandic Research Fund.
We are hiring! More details below
Description of the Project
The upsurge of computer networks and big data over the last decade is requiring new tool sets to deal with large graphs, as data is increasingly too large to fit into a single machine’s memory. One direction is in distributed processing, where the nodes collaborate on solving the problem at hand. The bottleneck then becomes the number of communication rounds required to reach a conclusion.
In the classical LOCAL model of distributed computing, introduced by Linial in 1987, the nodes in the networks are computers with only local knowledge, which then communicate in synchronous rounds in order to solve the given problem. At the end of the algorithm, each node should know its part of the output, and the objective is to minimize the number of communication rounds required.
The problem considered by Linial was the (Δ + 1)- graph coloring problem, where the nodes are to assign themselves a value (color) from 1, 2, … , Δ + 1, so that adjacent nodes receive different colors; here Δ is the maximum degree of the graph. Coloring is central in the study of distributed algorithms, as an elegant way to resolve resource contention. In addition to capture a wide range of combinatorial and algorithmic challenges, coloring also has many practical applications of great significance.
We ask the following bold questions:
- When can we color fast?
- What characteristics of the model, communication settings, or coloring assumptions allow us to produce a good coloring quickly?
Project Members at Reykjavik University
- Magnús M. Halldórsson: professor, project leader
- Maxime Flin: Ph.D. student
Collaborators
- Mohsen Ghaffari: MIT
- Fabian Kuhn: Freiburg U.
- Yannic Maus: U. Graz
- Calvin Newport: Georgetown U.
- Alexandre Nolin: CISPA
Selected Publications
-
A Distributed Palette Sparsification Theorem
Maxime Flin, Mohsen Ghaffari, Magnús M. Halldórsson, Fabian Kuhn, Alexandre Nolin
Submitted [arxiv version] -
Fast Distributed Brooks' Theorem
Manuela Fischer, Magnús M. Halldórsson, Yannic Maus
SODA'23 [arxiv version] -
Fast Distributed Vertex Splitting with Applications
Magnús M. Halldórsson, Yannic Maus, Alexandre Nolin
DISC'22 [arxiv version] -
Overcoming Congestion in Distributed Coloring
Magnús M. Halldórsson, Alexandre Nolin, Tigran Tonoyan
PODC'22 [arxiv version] -
Superfast Coloring in CONGEST via Efficient Color Sampling
Magnús M. Halldórsson, Alexandre Nolin
SIROCCO'22, Best paper award [arxiv version], Journal version: TCS '23 -
Efficient Randomized Distributed Coloring in CONGEST
Magnús M. Halldórsson, Fabian Kuhn, Yannic Maus, Tigran Tonoyan
STOC'21 [arxiv version] -
Coloring Fast Without Learning Your Neighbors' Colors
Magnús M. Halldórsson, Fabian Kuhn, Yannic Maus, Alexandre Nolin
DISC'20 [arxiv version] -
Distance-2 Coloring in the CONGEST Model
Magnús M. Halldórsson, Fabian Kuhn, Yannic Maus
PODC'20 [arxiv version]
Join the Team
We invite applications for two positions, that can be either at the Ph.D. or post-doctoral levels.
Reykjavik is a vibrant city with easy outdoors access. With lunar-like landscapes, Iceland offers unsurpassed opportunities to see nature at work. It also ranks high on lists for safety, equality, and happiness.
The PhD position provides a stipend of 425,000 ISK per month before taxes. It is for three years, to start as soon as possible.
The postdoc position is for one year (the start date is negotiable), and can be renewed for one more year, based on mutual agreement, with a salary of 625,000 ISK per month before taxes.
Interested applicants should send their CV, including a list of publications, in PDF to mmh@ru.is
Informal inquiries about the project and the conditions of work are very welcome. For first priority, submit by 28 February 2023.