Distributed Computing, COMP 4001 1
Distributed
Graph Coloring
, , SCS (September 11, 2021)
Distributed Computing, COMP 4001 2
Outline
• Coloring the Plane
• Introduction
• Distributed Computation
– Input (Garbage) Collection
– Coloring
• Non-Distributed Algorithms
• Distributed Algorithms
• Algorithms on Trees
, , SCS (September 11, 2021)
Distributed Computing, COMP 4001 3
Coloring the Plane
, , SCS (September 11, 2021)
Distributed Computing, COMP 4001 4
An Open Problem
• Color the plane R2 without any restrictions and by assigning a
single color to every point of the plane.
– Given a positive integer n, we say that the plane is
n-colored, if every point of the plane is assigned one of the
given n colors.
• Problem 1 What is the smallest number of colors sufficient
for coloring the Euclidean plane in such a way that no two
points of the same color are unit distance apart?
– This number is called the chromatic number of the plane
and is denoted by χ(R2).a
aSoifer, Alexander. The mathematical coloring book: Mathematics of color-
ing and the colorful life of its creators. Springer Science, 2008.
, , SCS (September 11, 2021)
Distributed Computing, COMP 4001 5
Proof of χ(R2) ≥ 3
• Here is the proof.
• Assume on the contrary two colors suffice.
• Draw an equilateral “unit” triangle anywhere on the plane.
• Since the triangle has three vertices, two vertices must have the
same color, which is a contradiction.
• Surprisingly all we know is that
4 ≤ χ(R2) ≤ 7
• See Exercises 2 and 3 for a proof of 4 ≤ χ(R2) and χ(R2) ≤ 9.
, , SCS (September 11, 2021)
Distributed Computing, COMP 4001 6
Introduction
, , SCS (September 11, 2021)
Distributed Computing, COMP 4001 7
Vertex Coloring
• What is the min number of “vertex colors” needed in a graph
so that any two neighoring nodes have different colors?
• An important problem in graph theory…and
– even more so in Distributed Computing.
• It is also a useful way to introduce basic concepts in distributed
computing.
• Has quite a few practical applications,
– In wireless networks where it is the basis of so-called TDMA
MAC protocols.
– In distributed computing, vertex coloring is also used to
break symmetries.
• We investigate the problem in an abstract setting.
, , SCS (September 11, 2021)
Distributed Computing, COMP 4001 8
But . . . Where is the Novelty?
• We compare three approaches:
1. Centralized
2. Parallel
3. Distributed
• Which approach is the most efficient?
, , SCS (September 11, 2021)
Distributed Computing, COMP 4001 9
Different Fields Different Approaches (Coloring)
• Centralized algorithms
– Graph G is encoded as a string, and the string is given as
input to a computer.
– The computer program finds a coloring of the graph,
encodes the coloring as a string, and outputs the result.
• Parallel algorithms
– Graph G is encoded as a string. However, multiple
computers can access the same string in parallel.
– Each computer might focus on one part of the graph and
produce a coloring for that part.
– Main focus is on high-performance computation exploiting
the processing power of multiple computers in parallel.
, , SCS (September 11, 2021)
Distributed Computing, COMP 4001 10
Different Fields Different Approaches (Coloring)
• Distributed algorithms
– Graph G is the structure of the computer network.
– There is one computer for each node of G and one
communication link for each edge of G.
– Initially, each computer only knows about its immediate
neighbors in the graph G; the computers must exchange
messages with each other to discover more about the
structure of G.
– Each computer must produce its own color as output.
– The main focus is on coordinating the operation of an
arbitrary distributed system.
• So there are different approaches
, , SCS (September 11, 2021)
Distributed Computing, COMP 4001 11
Similarities and Different Approaches (Coloring)
• Parallel algorithms have a different focus than distributed
algorithms,
– there is a lot of interaction between the two fields.
– sometimes same technique can also be used directly as a
distributed algorithm.
• A parallel algorithm can be implemented either in a parallel
system (using shared memory) or in a distributed system
(using message passing).
• The traditional boundary between parallel and distributed
algorithms (choose a suitable network vs. run in any given
network) does not lie in the same place as the boundary
between parallel and distributed systems (shared memory vs.
message passing).
, , SCS (September 11, 2021)
Distributed Computing, COMP 4001 12
Holding an Election: Input Collection
• You are given as input graph.
• Each node in the graph voted YES or NO after holding an
election and recorded its vote at the node.
• If I am a(ny) node in the graph can I decide whether or not
there is a YES somewhere in a node (possibly another one) of
the graph?
, , SCS (September 11, 2021)
Distributed Computing, COMP 4001 13
What is a Distributed Computation?
• Can I solve the problem with a
– centralized computation?
– distributed computation?
– mobile agent?
– random walk?
• How do I ensure that every node gets the correct outcome?
• How do these computations differ?
, , SCS (September 11, 2021)
Distributed Computing, COMP 4001 14
Example coloring:
• How many colours do you need?
• Can be a challenge even in a centralized setting!
, , SCS (September 11, 2021)
Distributed Computing, COMP 4001 15
Vertex Coloring Problem
• Vertex Coloring.
Given an undirected graph G = (V,E), assign a color χ(u) to
each vertex u ∈ V such that for any edge e = {v, w} ∈ E we
have that u, v are assigned different colors, i.e., χ(v) 6= χ(w).
• Example.
• Usually, we denote the colors with positive integers.
• The chromatic number of G, denoted by χ(G), is the smallest
number k for which G is k-colourable.
, , SCS (September 11, 2021)
Distributed Computing, COMP 4001 16
Example:
• How many colours do you need?
• χ(G) for the Petersen graph is 3.
, , SCS (September 11, 2021)
Distributed Computing, COMP 4001 17
Examples
• Determine χ(G) for the graphs below:
• K7
, , SCS (September 11, 2021)
Distributed Computing, COMP 4001 18
How Many Colors Do You Need?
• If a graph G has n vertices, then χ(G) ≤ n.
– However, this upper bound is usually poor, except when G
has many edges.
– This inequality becomes an equality χ(G) = n only when G
is the complete graph Kn.
• We can improve on this upper bound considerably if we know
the largest vertex degree in G.
, , SCS (September 11, 2021)
Distributed Computing, COMP 4001 19
How Many Colors Do You Need?
• Theorem 1 Let G be a simple graph whose maximum vertex
degree is d. Then χ(G) ≤ d+ 1.
• Proof: By induction on n.
• Step 1: True for n = 1 (graph has one node and d = 0).
• Step 2: Assume χ(H) ≤ d+ 1 for all simple graphs H with
fewer than n vertices.
– We wish to show that χ(G) ≤ d+ 1 for all simple graphs G
with exactly n vertices.
, , SCS (September 11, 2021)
Distributed Computing, COMP 4001 20
How Many Colors Do You Need?
• Let G be a simple graph with n vertices and maximum vertex
degree d.
• Let H be any graph obtained from G by removing a vertex v
and all the edges incident with it.
• The graph H has fewer than n vertices and maximum vertex
degree d (or less) so, by our assumption, χ(H) ≤ d+ 1, that is,
the graph H is (d+ 1)-colourable.
, , SCS (September 11, 2021)
Distributed Computing, COMP 4001 21
How Many Colors Do You Need?
• We can now obtain a (d+ 1)-colouring of G by colouring v with
any colour not assigned to the (at most d) vertices adjacent to
v, since these vertices can be coloured with at most d colours.
– Here we used the fact that the max degree is d.
• It follows that χ(G) ≤ d+ 1.
• Thus if the statement is true for all simple graphs with fewer
than n vertices, then it is true for all simple graphs with n
vertices. This completes Step 2.
• Therefore, by the principle of mathematical induction, the
statement is true for all simple graphs with n vertices, for each
positive integer n.
, , SCS (September 11, 2021)
Distributed Computing, COMP 4001 22
As an Algorithm
• Can you present the previous method as an algorithm?
– It has to be based on selecting a vertex and removing it.
– Which vertex will be removed?
• Is the decision of “removing” centralized or distributed?
– If centralized, it is clear who will make the decision!
– Not so clear if distributed since more than one node may
decide to be removed!
• Example. What happens if both nodes 1 and 2 decide to be
removed?
, , SCS (September 11, 2021)
Distributed Computing, COMP 4001 23
Example (1/4)
• How many colours do you need with centralized computation?
• A central algorithm decides on the colors.
, , SCS (September 11, 2021)
Distributed Computing, COMP 4001 24
Example (2/4)
• How many colours do you need with distributed computation?
• A distributed algorithm decides on the colors.
– Different nodes may start at the same time!
– How are messages exchanged?
, , SCS (September 11, 2021)
Distributed Computing, COMP 4001 25
Example (3/4)
• How many colours do you need with distributed computation?
• A distributed algorithm decides on the colors.
– Different nodes may start at the same time!
– What happens when a vertex receives “conflicting signals”.
– What color should it use?
, , SCS (September 11, 2021)
Distributed Computing, COMP 4001 26
Example (4/4)
• Imagine a mobile agent doing a random walk (jumping from
vertex to vertex) colouring vertices?
– Can it decide colorability?
• How can a mobile agent do it?
, , SCS (September 11, 2021)
Distributed Computing, COMP 4001 27
Node Identifiers
• We assume that we have node identifiers.
• Each node has a unique identifier, e.g., its IP address.
• We usually assume that each identifier consists of only O(log n)
bits if the network has n nodes.
• Sometimes we might even assume that the nodes have exactly
the identifiers 1, . . . , n.
, , SCS (September 11, 2021)
Distributed Computing, COMP 4001 28
Node Identifiers
• The size of the identifiers (in bits) may impact the complexity
of an algorithm.
– Identifiers are (may be) exchanged during the distributed
computation.
• How do you assign unique identifiers to the nodes with
distributed computation?
• Previously we discussed a randomized algorithm for assigning
identifiers.
• NB: Identifiers should not be confused with port numbers!
, , SCS (September 11, 2021)
Distributed Computing, COMP 4001 29
Chromatic Number
• Node identifiers provide a solution to the coloring problem
– they are pairwise different;
– essentially requiring n colors.
• Chromatic Number.
Given an undirected Graph G = (V,E), the chromatic number
χ(G) is the minimum number of colors to solve the graph
colouring problem for G.
• Basic Questions.
– How many colors are needed is a well-studied problem, but
in the centralized model!
– How many colors are needed in distributed computation
model?
• The type of computation affects the chromatic number!
, , SCS (September 11, 2021)
Distributed Computing, COMP 4001 30
Non-Distributed
Algorithms
, , SCS (September 11, 2021)
Distributed Computing, COMP 4001 31
Non-distributed Vertex Coloring Algorithm
• Without loss of generality we may assume colors are numbers.
• Algorithm: Greedy Sequential
• Input Graph G
1. while there exists an uncolored vertex v do
2. color v with the minimal color (number) that does not
conflict with the already colored neighbors
3. end while
, , SCS (September 11, 2021)
Distributed Computing, COMP 4001 32
Example:
• How do we color this graph?
• Use colors 1, 2, 3, 4, . . .
• Start at a node and use the algorithm.
, , SCS (September 11, 2021)
Distributed Computing, COMP 4001 33
Example: Other Graphs
• How do we color these graphs?
, , SCS (September 11, 2021)
Distributed Computing, COMP 4001 34
Issues
• Who starts the coloring?
– The vertex with smallest identifier!
– The algorithm then proceeds in order of identifiers!
• This is a sequential algorithm:
– Only one processor is active at a time!
– This is kind of cheating!
, , SCS (September 11, 2021)
Distributed Computing, COMP 4001 35
Issues
• Nodes are assumed to have distinct identifiers.
• At least, can we show the algorithm is good?
• But according to what benchmark?
– By that we usually mean, how does it perform with respect
to the global (centralized) algorithm?
• E.g., Is the number of colors of Centralized and Distributed
algorithms the same?
, , SCS (September 11, 2021)
Distributed Computing, COMP 4001 36
Degree of a Graph
• (Degree). The number of neighbors of a vertex v, denoted by
δ(v), is called the degree of v.
• ( ). The maximum degree vertex in a graph G
defines the graph degree ∆(G) = ∆ (also denoted d := d(G)).
, , SCS (September 11, 2021)
Distributed Computing, COMP 4001 37
Better Way to State the Algorithm
• Start with a graph G and a list of available colours, say
1, 2, 3, . . .
• Label the vertices a, b, c, . . . in any manner.
– Identify the uncoloured vertex labelled with the earliest
letter in the alphabet;
– colour it with the first colour in the list not used for any
adjacent coloured vertex.
• Repeat Step 2 of the algorithm until all the vertices are
coloured, then Stop.
, , SCS (September 11, 2021)
Distributed Computing, COMP 4001 38
Example (1/2)
• Find a vertex colouring of the following graph G
• Label the vertices a, . . . , f as follows.
, , SCS (September 11, 2021)
Distributed Computing, COMP 4001 39
Example (2/2)
• We successively color
vertex a with colour l,
vertex b with colour 2,
vertex c with colour 1,
vertex d with colour 2,
vertex e with colour 3,
vertex f with colour 4.
, , SCS (September 11, 2021)
Distributed Computing, COMP 4001 40
Degree Coloring Bound
• Theorem 2 (Analysis of Greedy Sequential Algorithm)
The algorithm is correct and terminates in n steps. The
algorithm uses at most ∆ + 1 colors.
• Since each node has at most ∆ neighbors, there is always at
least one color free in the range {1, . . . ,∆ + 1}.
• Correctness and termination are straightforward, because the
algorithm is sequential.
, , SCS (September 11, 2021)
Distributed Computing, COMP 4001 41
Issues
• What do we mean by step?
• For many graphs coloring can be done with much less than
∆ + 1 colors
– E.g.,Trees.
• Algorithm is not distributed at all;
– only one processor is active at a time.
• Question:
– Can we drop the sequential assumption?
– We can transform the simple idea of this algorithm to
provide a distributed coloring subroutine.
, , SCS (September 11, 2021)
Distributed Computing, COMP 4001 42
Coloring with Distributed Assumption
• How do we color these graphs if more than one node is
operating at a time in the coloring algorithm?
, , SCS (September 11, 2021)
Distributed Computing, COMP 4001 43
Distributed
Algorithms
, , SCS (September 11, 2021)
Distributed Computing, COMP 4001 44
First Free
• Requirement: Each node has a unique identifier.
• Procedure: First Free
1. Give v the smallest admissible color
– this is the smallest node color not used by any of its
neighbors
• With this subroutine we have to make sure that two adjacent
vertices are not colored at the same time.
• Otherwise, the neighbors may conclude (at the same time!)
that some small color c is still available in their neighborhood,
and then at the same time decide to choose this color c.
– We overcome this difficulty with some kind of “distributed
scheduling”: the idea of the round.
, , SCS (September 11, 2021)
Distributed Computing, COMP 4001 45
Synchronous Distributed Algorithm
• Synchronous Distributed Algorithm
• Nodes operate in synchronous rounds.
• In each round, each processor executes the following steps:
1. Do some local computation
– of reasonable complexity.
2. Send messages to neighbors in graph
– of reasonable size.
3. Receive messages
– that were sent by neighbors in step 2 of the same round.
, , SCS (September 11, 2021)
Distributed Computing, COMP 4001 46
Issues
• What is reasonable complexity?
– Somehow the number of rounds will be important!
• What is reasonable size of a message?
– Anything, as long as you account for it!
• Can you attach the ID to a message?
– Yes! Why not!
, , SCS (September 11, 2021)
Distributed Computing, COMP 4001 47
A Subroutine
• Procedure First Free(v)
– Require: Distinct Node Identifiers.
– Give v the smallest admissible color /* i.e., the smallest
node color not used by any neighbor */
, , SCS (September 11, 2021)
Distributed Computing, COMP 4001 48
Algorithm Reduce
• Assume that initially all nodes have (distinct) IDs
• Algorithm Reduce
1. Each node v executes the following
2. node v sends its ID to all neighbors
3. node v receives IDs of neighbors
4. while node v has an uncolored neighbor with higher ID do
5. node v sends “undecided” to all neighbors
6. node v receives new decisions from neighbors
7. end while
8. node v chooses a free color using subroutine First Free
9. node v informs all its neighbors about its choice
, , SCS (September 11, 2021)
Distributed Computing, COMP 4001 49
Example
• Vertex 100 receives the lowest possible (“consistent”) color.
, , SCS (September 11, 2021)
Distributed Computing, COMP 4001 50
Time Complexity
• For synchronous algorithms the time complexity is the number
of rounds until the algorithm terminates.
– Sometimes we may be interested in the number of steps in
each round!
• The algorithm terminates when the last processor has decided
to terminate.
• In addition to input graph G, to guarantee correctness the
procedure requires a legal input (i.e., pairwise different node
IDs).
, , SCS (September 11, 2021)
Distributed Computing, COMP 4001 51
Time Complexity
• Theorem 3 (Analysis of Algorithm Reduce) Algorithm
Reduce is correct and has time complexity n.
– The algorithm uses at most ∆ + 1 colors.
• How does the algorithm perform on a tree?
• Can we improve this algorithm?
, , SCS (September 11, 2021)
Distributed Computing, COMP 4001 52
Trees
, , SCS (September 11, 2021)
Distributed Computing, COMP 4001 53
Trees
• Trees are acyclic graphs.
, , SCS (September 11, 2021)
Distributed Computing, COMP 4001 54
Rooted Trees
• Trees may have a root (a designated vertex).
• In binary trees all vertices have degree ≤ 3.
, , SCS (September 11, 2021)
Distributed Computing, COMP 4001 55
Trees in Computer Science
• Used to model and describe branching procedures in
programming languages.
• Used to store data in a computer’s memory in many different
ways.
• In distributed computing it may represent the spread of
information.
• For example, consider the list of seven numbers 7, 5, 4, 2, 1, 6, 8.
, , SCS (September 11, 2021)
Distributed Computing, COMP 4001 56
Trees in Computer Science
• The following trees represent ways of storing the list
7, 5, 4, 2, 1, 6, 8 in memory – as a stack and as a binary tree.
• Each representation has its advantages, depending on how the
data is to be manipulated.
• In both representations it is important to distinguish where the
data starts, so the trees are rooted.
, , SCS (September 11, 2021)
Distributed Computing, COMP 4001 57
Coloring Trees
• How many colors do you need in a tree?
Lemma 1 χ(T ) ≤ 2, for T a tree.
, , SCS (September 11, 2021)
Distributed Computing, COMP 4001 58
Observations
• Trees are bipartite graphs.
• If the distance of a node to the root is odd (respectively, even),
color it 1 (respectively, 0).
• An “odd node” has only “even neighbors” and vice versa.
• If we assume that
– each node knows its parent (root has no parent) and
children in a tree
this constructive proof gives a very simple algorithm.
• How do you determine a root?
, , SCS (September 11, 2021)
Distributed Computing, COMP 4001 59
Slow Tree Coloring
• Algorithm: Slow Tree Coloring
1. Color the root 0, root sends 0 to its children
2. Each node v concurrently executes the following code:
3. if node v receives a message x (from parent) then
4. node v chooses the color χ(v) = (1− x) mod 2 /* x is a
boolean variable */
5. node v sends χ(v) to its children (all neighbors except
parent)
6. end if
• Is the starting root important for the correctness of the
algorithm?
, , SCS (September 11, 2021)
Distributed Computing, COMP 4001 60
Trees: Observations
• Algorithm “Slow Tree Coloring” can be shown to be correct.
• The time complexity of the algorithm is the height of the tree.
• This algorithm does not need to be synchronous!
, , SCS (September 11, 2021)
Distributed Computing, COMP 4001 61
Trees: Observations
• If the root was chosen unfortunately, and the tree has a
degenerated topology, the time complexity may be up to n, the
number of nodes.
• Main Question: How can we determine a root in a tree if it is
not already given?
, , SCS (September 11, 2021)
Distributed Computing, COMP 4001 62
Asynchronous Distributed Algorithms
• In the asynchronous model, algorithms are event driven
– upon receiving message…do…
• Processors cannot access a global clock.
• A message sent from one processor to another will arrive in
finite but unbounded time.
, , SCS (September 11, 2021)
Distributed Computing, COMP 4001 63
Issues
• The asynchronous model and the synchronous models are
“vital” to distributed computing.
• They do not necessarily reflect reality:
– there are several models in between synchronous and
asynchronous.
• From a theoretical point of view the synchronous and the
asynchronous model are the most interesting ones (because
every other model is in between these extremes).
• In the asynchronous model, messages that take a longer path
may arrive earlier.
, , SCS (September 11, 2021)
Distributed Computing, COMP 4001 64
Time/Message Complexity
• (Time Complexity). For synchronous algorithms, the time
complexity is
– the number of time units from the start of the execution to
its completion in the worst case,
for every legal input, every execution scenario, assuming that
each message has a delay of at most one time unit.
• (Message Complexity). For synchronous or asynchronous
algorithm, the message complexity is determined by
– the number of messages exchanged, or
– the sum of the number of bits of messages exchanged,
for every legal input, every execution scenario.
, , SCS (September 11, 2021)
Distributed Computing, COMP 4001 65
Issues
• You cannot use the maximum delay in the algorithm design
– because you don’t know it in advance!
– In wireless, ethernet networks, etc, you may have to use
delay just to break symmetry!
• In our “distributed setting” the algorithm has to be correct
even if there is no such delay upper bound.
, , SCS (September 11, 2021)
Distributed Computing, COMP 4001 66
Algorithm Correctness
• Theorem 4 Algorithm Slow Tree Coloring is correct. If each
node knows its parent and its children,
– the (asynchronous) time complexity is the tree height which
is bounded by the diameter of the tree;
– the message complexity is n− 1 in a tree with n nodes.
, , SCS (September 11, 2021)
Distributed Computing, COMP 4001 67
Issues
• In this case the asynchronous time complexity is the same as
the synchronous time complexity.
• For nice trees, e.g. balanced binary trees, we have logarithmic
height, and hence also logarithmic time complexity.
• Can we do better than logarithmic?
– Local algorithms do just that!
, , SCS (September 11, 2021)
Distributed Computing, COMP 4001 68
Exercisesa
1. The chromatic number χ(R2) was defined so that no two points
in the plane are distance 1 apart. Would anything change if the
distance was some given real number r > 0?
2. (?) Use “Moser’s Spindle”
to show that χ(R2) ≥ 4.b
aNot to hand in!
bFor additional research see: Soifer, Alexander. The mathematical coloring
book: Mathematics of coloring and the colorful life of its creators. Springer
Science, 2008.
, , SCS (September 11, 2021)
Distributed Computing, COMP 4001 69
3. (?) Use the following tiling of the plane
to show that χ(R2) ≤ 9.
4. Show that in any graph the sum of the degrees of all the
vertices is equal to twice the number of edges.
5. Determine the chromatic number χ(G) of the graphs below:
For each graph, devise a suitable colouring and explain why
there is no colouring with fewer colours.
, , SCS (September 11, 2021)
Distributed Computing, COMP 4001 70
6. What can you say about the graphs G for which (a) χ(G) = 1?
(b) χ(G) = 2?
7. In a connected graph, what is the smallest number of edges
that must be removed in order that no cycles remain?
8. What is chromatic number of the graph below
9. A forest with k (connected) components and n vertices has
n− k edges.
10. How many edges does a cycle graph (denoted by Cn) with n
vertices have? What is the diameter of Cn? What is the degree
, , SCS (September 11, 2021)
Distributed Computing, COMP 4001 71
sequence of Cn?
11. A wheel graph with n vertices, denoted by Wn, is obtained
from a cycle graph Cn with n vertices by adding a new vertex
w and joining an edge from w to each vertex of Cn. How many
vertices does Wn have? How many edges does Wn have? What
is the diameter of Wn? What is the degree sequence of Wn?
12. Are any of the following two pairs of graphs isomorphic? If so,
find a suitable one-one correspondence between the vertices of
the first and those of the second; if not, explain why no such
one-one correspondence exists.
If necessary, you can show this by drawing the correspondence.
, , SCS (September 11, 2021)
Distributed Computing, COMP 4001 72
13. The degree sequence of a graph is the sequence of vertex
degrees in non-decreasing order (with repetitions). Prove or
disprove the statements below.
(a) If two graphs are isomorphic, must they have the same
degree sequence?
(b) If two graphs have the same degree sequence, must they be
isomorphic?
14. Assume that 25 chicks sit on vertices of a square 5× 5 grid
(one chick per vertex). Suddenly, each chick randomly pecks a
neighboring chick selected randomly and independently with
equal probability. What is the expected number of unpecked
chicks?
15. Prove that adding an edge to a graph increases its chromatic
number by at most one.
16. Prove that deleting a vertex from a graph decreases the
, , SCS (September 11, 2021)
Distributed Computing, COMP 4001 73
chromatic number by at most one.
, , SCS (September 11, 2021)