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:

Project Members at Reykjavik University


Selected Publications

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, together with a statement outlining their suitability for the project and the names of at least two referees.

Informal inquiries about the project and the conditions of work are very welcome. For first priority, submit by 28 February 2023.