CS计算机代考程序代写 distributed system algorithm Distributed Computing, COMP 4001 1

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 su�cient
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)

• •

%
i.try
in square

triangle
tiling –

Distributed Computing, COMP 4001 5

Proof of �(R2) � 3

• Here is the proof.

• Assume on the contrary two colors su�ce.

• 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)

• B

n ^

Boo n • a

hexagonal
tiling

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 di↵erent 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 e�cient?

, , SCS (September 11, 2021)

Distributed Computing, COMP 4001 9

Di↵erent Fields Di↵erent 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)

{
mm

Distributed Computing, COMP 4001 10

Di↵erent Fields Di↵erent 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 di↵erent approaches

, , SCS (September 11, 2021)

Distributed Computing, COMP 4001 11

Similarities and Di↵erent Approaches (Coloring)

• Parallel algorithms have a di↵erent 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)

Yes =Blank

•f§° Mo = Red

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 di↵er?

, , SCS (September 11, 2021)

0 ☐
Drunkard

=

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)

1

206 %oa?

☐ ☐

3

joy
3 1

¥,

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 2 V such that for any edge e = {v, w} 2 E we
have that u, v are assigned di↵erent 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)

✗pupa
chrome

0

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)

I 2 1 2

② a • 21 3 ”

l z
1

2

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)

✗camo aÉ¥¥o÷É

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)

d¥÷÷÷÷””

: i. .

0
I cancolor v with

one ofthe
colors 1,2, ydt

1?

→← E. be

¥÷¥¥÷¥÷÷-*

÷

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)

0 I

Distributed Computing, COMP 4001 24

Example (2/4)

• How many colours do you need with distributed computation?

• A distributed algorithm decides on the colors.
– Di↵erent 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.
– Di↵erent 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)

@
• Vertices
• Ports

11 a • Node Identifiers
2 31

a
5

• Port Identifies
2

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 di↵erent;

– 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 a↵ects 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)

§
put vertices in sequence
a
, big d) e , . . – –

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)

ok In a distributed

.

⑤⑧ setting, a
sequential
algorithm⑧⑧
will not¥0
always work .

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)

asbs . – – 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)