Mandatory: Distributed Algorithms
Philip Bille Inge Li Gørtz Eva Rotenberg
1 Exercise (5pt) Give a randomised distributed algorithm that finds any
independent set of expected size n/(∆ + 1) for a graph of maximal degree ∆.
2 Exercise (10pt) Model: There is no bandwidth limitation on the com-
munication along an edge.
Graph: the maximal degree of a vertex is ∆.
Task: Colour each edge of the graph such that for each vertex, all its edges
have different colours.
Give an efficient randomised distributed algorithm for 2∆ − 1-colouring all
edges with high probability. For the algorithm to terminate correctly, both
endpoints of each edge need to agree on the colour of that edge.
3 Exercise (10pt) Model: The Congest Model.
Graph: The graph is connected.
Task: Assign an integer value f(v) to each vertex v such that
• f is injective. Different vertices v 6= u have different values f(v) 6= f(u).
•
∑
v f(v) = 0, that is, the sum of f(v) over all vertices in the whole graph
is zero.
• f(v) is always in the range from −nC to nC for some constant C.
Give an efficient deterministic distributed algorithm for assigning f(v) to
each vertex v.
Efficiency: Analyse the performance of the algorithm as a function of n, the
number of vertices, and as a function of diam(G), the diameter of the graph.
1