General information
- The internship will take place at University Lyon 1, in the
LIRIS lab.
(La Doua campus).
- The advisors will be Théo Pierron
and Laurent Feuilloley
who are part of the GOAL
team, that specializes in all aspects of graph algorithms.
Nicolas Bousquet
may join the advising team.
- The internship will be on the same models as the one discussed
in Course C14
(starting in November).
Topic: Beyond worst-case for distributed graph algorithms
The internship is in the area of distributed graph algorithms.
There are various models for those, but basically, the goal is to
solve classic graph problems (e.g. coloring, matching, minimum spanning
tree) from the perspective where the graph represents a network of
machines, that exchange messages along the edges in order to
solve the problem. The focus is then on the number or the size of the
messages, or the number of communcation rounds (instead of the
number of arithmetic operations).
A beautiful theory has been built in this area, which is still very
active. It uses tools from combinatorics, graph theory, communication
complexity, automata theory, etc.
The classic way to evaluate the quality of algorithms in this area
is, as often in algorithm theory, a worst-case measure. In this
internship we will relax this measure (going "beyond worst-case"), trying
to refine and answer one or several of the following questions.
- In distributed graph algorithms, the graph is both the
input of the problem and the computing infrastructure. One usually
evaluates the performace of an algorithm by considering the worst
possible graph. These "worst graphs" can have very specific strutures,
and it is not clear whether these are a few particular cases,
or if they are common.
Questions: How do state-of-the-art algorithms behave if the
graph is random (e.g. an Erdos-Renyi graph)? For these graphs,
should we use other algorithms? What about different graph models?
- Another aspect of the model is the identifier assignment:
distributed
graph algorithms usually need that every node has a distinct name,
e.g. an integer in [1,n] (to avoid symmetry issues, basically).
Again this is almost always considered to be chosen by an adversary,
that is, worst case. By taking this identifier assignment to
be fully random, one basically gets a model equivalent to randomized
algorithms. But what is in between? How brittle are the identifier
distributions of the lower bounds? A concrete question: Can we
get a large class of identifier distributions such that 3-coloring
a path can be done in constant time (which is impossible in the
worst case)?
- Finally, a model called the sleeping
model was introduced recently. In this model, the nodes can
either be awake (and work normally) or asleep, and then they cannot receive or send messages.
The main question is: Can we design algorithm that minimize
the number of awake round per node? Since this is a new model,
there is a lot to be done in the area, and the specific topic
would have to be discussed. Our group recentely got ANR funding
to study this model, and there is possibility of collaboration
with people in Paris and Bordeaux.