Distributed Computing, COMP 4001 1
Locality
Evangelos Kranakis, Carleton University, SCS (October 31, 2020)
Distributed Computing, COMP 4001 2
Locality Everywhere
Evangelos Kranakis, Carleton University, SCS (October 31, 2020)
Distributed Computing, COMP 4001 3
• Locality everywhere.
• Locality in Computing • Local Coloring
• Coloring Trees
• Lower Bounds
Outline
Distributed
Comp .
Evangelos Kranakis, Carleton University, SCS (October 31, 2020)
Distributed Computing, COMP 4001 4
Locality Everywhere
Evangelos Kranakis, Carleton University, SCS (October 31, 2020)
Distributed Computing, COMP 4001 5
Locality Everywhere!
• Locality is everywhere: – Physics
– Biology
– Social Sciences – Mathematics
• They have di↵erences and similarities.
Evangelos Kranakis, Carleton University, SCS (October 31, 2020)
Distributed Computing, COMP 4001 6
Locality in Physics
• An object is only directly influenced by its immediate surroundings.
• A theory using the principle of locality is said to be a “local theory”. Theory
• Relativity is a local theory
– It limits the speed at which such influences can travel to the
speed of light c.
• Quantum mechanics is not a local theory.
•
HT
very far
HT – A measurement made on one of a pair of separated but
entangled particles causes a simultaneous e↵ect, the collapse of the wave function, in the remote particle (i.e. an e↵ect exceeding the speed of light).
Evangelos Kranakis, Carleton University, SCS (October 31, 2020)
Distributed Computing, COMP 4001 7
Locality in Biology
• Phenotypes might be influenced by local variations and e↵ects. – Shape
– Size
– Color
– Nature
– Other environmental factors
• In turn, this a↵ects the genotype.
• Quantum Biology is a newly developing field for the study of
non-local biological phenomena. – Bird navigation ‘Turtle
Evangelos Kranakis, Carleton University, SCS (October 31, 2020)
Distributed Computing, COMP 4001 8
• Local Characteristics – Language
– Behaviour – Culture
– Food
• Global Phenomena – Cascades
– Rumors
• How do certain events cascade?
Social
O
Locality in Social Sciences
O
Evangelos Kranakis, Carleton University, SCS (October 31, 2020)
Distributed Computing, COMP 4001 9
Locality in Mathematics
• It has a proximity interpretation.
• Related somehow to distance.
( geometric distance )
• Concerns phenomena that are geometrically close to each other.
• Locality is influenced by distance but is not the same thing as
location!
oaf
paths of a certain
sends messages to all nodes three
G
paths between nodes
,
length
:
u
hops
w
away
Evangelos Kranakis, Carleton University, SCS (October 31, 2020)
Distributed Computing, COMP 4001 10
Locality in Computing
Evangelos Kranakis, Carleton University, SCS (October 31, 2020)
Distributed Computing, COMP 4001 11
Locality
– the execution of a process depends on nearby processes.
• Usually it means:
– there is no dependency between events that occur far away.
• It has a special role in computing and communication.
– What can be computed globally if there is a restriction on
how far information can propagate? • Can you elect a leader
– making use only of local information?
a
no
n
:
Evangelos Kranakis, Carleton University, SCS (October 31, 2020)
Distributed Computing, COMP 4001 12 Locality
• Decision made at node u not a↵ected by nodes far away from u. locality
is somehow
hop –
distance
u
• How do we quantify “far away” from u?
Evangelos Kranakis, Carleton University, SCS (October 31, 2020)
Distributed Computing, COMP 4001 13
How far is local?
• Given that locality is influenced by distance “how far is far away”?
• May depend on the topology rt
too
I
O
•
✓
anodes
•
nk
• How do you parametrize locality?
• Best to study specific problems!
Evangelos Kranakis, Carleton University, SCS (October 31, 2020)
Distributed Computing, COMP 4001 14
Coloring
• Global vs Local Algorithms • On a Line
• On a Tree
Evangelos Kranakis, Carleton University, SCS (October 31, 2020)
Distributed Computing, COMP 4001 15
O
Local Algorithms in DC
• An algorithm is local if messages initiated by the nodes do not propagate too far from their originator.
– How can you ensure correctness of the algorithm? – Which problems can you solve this way?
– How far is too far?
• Local approach is important for wireless communication! rum
• Lets go back to coloring. –
1 rift ”
ti
Mg ,
Example:
Afg
ooh
Evangelos Kranakis, Carleton University, SCS (October 31, 2020)
Distributed Computing, COMP 4001 16
Coloring
• A vertex coloring is an assignment of colors to vertices of a graph so that any two adjacent vertices are assigned di↵erent colors.
• How do you color a set of points on a line?
• If nodes have identities 1, 2, . . . , n then color nodes with even
identities blue, and with odd identities red. l
l
i324 51
dO Oromo
– Is the algorithm correct?
– Is this a local algorithm?
d
– Is there a local colouring algorithm?
l
O
I2345
lU 0-0–0-0
Evangelos Kranakis, Carleton University, SCS (October 31, 2020)
Distributed Computing, COMP 4001 17
Global vs Local Coloring
• Before a node decides on its colour it must collect information about its neighboring nodes.
• There are two ways to do this depending on how far this information collection can spread
1. Globally 2. Locally
Evangelos Kranakis, Carleton University, SCS (October 31, 2020)
Distributed Computing, COMP 4001 18
Globally/Locally
• Globally? 1212121212121
– You are not constrained by # of hops. o • Locally? fault
x
– Constrained by # of hops.
safe
– In a distributed setting, the di culty lies in keeping the assignment of colors consistent throughout the graph despite the fact that propagation is limited!
Evangelos Kranakis, Carleton University, SCS (October 31, 2020)
Why do you want a local coloring algorithm
If not
l o c a l to
global ,
IX.
then it is fault tolerant
are more robust or link)
algorithm is
algorithms failures ( node
Distributed Computing, COMP 4001 19
Coloring with Restricted Number of Hops
• Consider nodes “independently” initiating coloring. →
• If the number of hops a message can propagate is restricted you may not be able to complete the coloring!
• If a given set of nodes start colorinag at the same time how do you ensure consistent coloring?
←
– Nodes will start with their own identifiers.
• More than that, you may have to use more than the minimum
required number of colors so as to achieve a correct coloring!
• Regardless of the number of colors you use
– can you achieve a proper coloring, and
– at the same time restrict the number of hops?
Evangelos Kranakis, Carleton University, SCS (October 31, 2020)
8 To 0
OlOl—-
the # of hops, will the # of colors – used!
Ol
limit on affect
Distributed Computing, COMP 4001 20
Quantifying Locality: Network
• Consider a class N of networks.
• A typical network G = (V, E) in N is a graph with n vertices. – Line,
– Ring, – Tree, – etc.
• The concept should be applicable to all classes of graphs (networks).
Evangelos Kranakis, Carleton University, SCS (October 31, 2020)
Distributed Computing, COMP 4001 21
Quantifying Locality: Distance
• Locality should depend on distance.
• Let n ! h(n) be an integer valued function:
– h(n) is the number of hops allowed in a network of size n.
• Examples:
– n!h(n)=1,
h – local
an
is algorithm
– n!h(n)=c,cissomeconstant,
– n!h(n)=logn,
– n!h(n)=log⇤n,etc a-
– n!h(n)=pn,
i÷:÷:÷
– n!h(n)=n,
Evangelos Kranakis, Carleton University, SCS (October 31, 2020)
Distributed Computing, COMP 4001 22
Quantifying Locality: Problems
• Consider a problem P (e.g., colouring), and a class A of synchronous, distributed algorithms solving P for N .
– The class A of distributed algorithms is h-local if during the executionofanalgorithmA2AonanetworkG2N (onn vertices) a message emanating from a node will never propagate more than h(n) hops from its originator.
Propagation
distance)
(hop-
i s determined
distance
by h.
the function
Evangelos Kranakis, Carleton University, SCS (October 31, 2020)
Distributed Computing, COMP 4001 23
Which Problems in DC are Local?
• Not all problems are going to be h-local, for a given function h. • Which ones are h-local, for a function n ! h(n) = c, where c a
constant?
– Leader Election ←
– Spanning Tree
– Maximum Independent Set – Coloring
– Minimum Dominating Set
• For which topologies?
“%I : mango
←
maybe I log*io”°°
Evangelos Kranakis, Carleton University, SCS (October 31, 2020)
Distributed Computing, COMP 4001 24
Local Coloring
Evangelos Kranakis, Carleton University, SCS (October 31, 2020)
Distributed Computing, COMP 4001 25 Coloring a Line Graph: Assumptions
• Assume you are on a line of n nodes.
I 3 2 15 25 6 7 8 23 21 5 6 34
• To start, assume that each node v has a distinct identity idv (for example, either their location or the network interface card would do).
– Identity selection is much easier than the coloring problem…besides we also know several ways to solve this problem!
191 ¥→ ¥
All
student
.
Evangelos Kranakis, Carleton University, SCS (October 31, 2020)
Distributed Computing, COMP 4001 26
Local Coloring Algorithm
• Our main goal is to show –
• Theorem 1 There is a coloring algorithm which can 3-color
any line in O(log⇤ n) time, where
– log⇤ n is the iterated lograithm of n dogflogf. fog n ) )) – in the algorithm all nodes start with their identifiers.
• This result is important in certain types of networks (like wireless) where messages should not propagate too far!
• NB: Note the important parameters taken into account: – Final number of colors in the graph.
– Termination time of the coloring algorithm.
Ez
Evangelos Kranakis, Carleton University, SCS (October 31, 2020)
Distributed Computing, COMP 4001 27
Assumptions for Coloring
• Let v ! cv be an arbitrary coloring of the vertices. – Observe that cv := idv is a legal coloring!
• For example,
– the identity assignment below is a colouring using n colors,
1 2 3 4 5 6 7 8 9 10 11 12 13
– and so is any permutation of the identities.
line of neverfrees
with n colors :
=
Ln
I
can be colored
:
-1,2″
22,
”
,
….
,
2
Evangelos Kranakis, Carleton University, SCS (October 31, 2020)
iii.
n’ 37 ,,
5
,
–
52,
.. .
.
son
,
7′
.–
–
,
Distributed Computing, COMP 4001 28 v
Assumptions for Coloring
• Represent each c
– Let |cv| be the number of bits in cv, and – cv(i) the i-th bit of cv.
• Example:
Every vertex is initially
as a sequence of bits.
colored
v
576
cu
592594
– cu =594=512+64+16+2=29 +26 +24 +21.
– In binary cu = 1001010010
– cu(i) is the ith bit where counting-starts from i = 0 from
left to right: cu(0) = 1, cu(2) = 0. n
• The concatenation 10110
– of two sequences s,s0 of bits is the sequence ss0.
– Example: if s = 1010 and s0 = 110 then ss0 = 1010110
1011011
Evangelos Kranakis, Carleton University, SCS (October 31, 2020)
Distributed Computing, COMP 4001 29
Idea for an Algorithm on a Line
• Assume an ordering of the vertices (left to right would do).
pre(v) v suc(v)
• Starting Rule:
– Start with any legal coloring,
⇤ for example cv := idv, for all v.
– Color “leftmost vertex” with the bit 0.a
• Any other starting coloring would do.
aThis is a starting condition and we will need to justify it: will do this later!
Evangelos Kranakis, Carleton University, SCS (October 31, 2020)
Distributed Computing, COMP 4001 30
Recoloring Rule
• Since nodes u ! v are neighbors (with u preceding v), their current colors must be di↵erent: cu 6= cv.
• Produce a new “legal” coloring for a vertex v from the current one, say cv, as follows:
– Find the first index 1 i |cv| such that v’@s color di↵ers from the colour of its predecessor.
– Set new color to “i concatenated with cv(i)”: cv ! icv(i);
• Recoloring rule guarantees that neighbors will get new
di↵erent colors.
• NB: Bit representation o*f each new color is of length
logarithmic of the length of the previous color!
→9→q
Evangelos Kranakis, Carleton University, SCS (October 31, 2020)
~
color :c , a start ionic) ( log cu )
-11
Distributed Computing, COMP 4001 31
Coloring Algorithm for Vertex v
• Assume an ordering of the vertices (left to right would do).
prev(v)
• Coloring Algorithm:
1. cv idv;
2. Repeat:
v
suc(v)
Iqftks
(a) ` |cv|;
(b) if v is “leftmost vertex” then set I 0
else set I min{i : cv(i) 6= cpre(v)(i)}; (c) Set cv Icv(I); /* concatenation */
(d) Inform the successor suc(v) of v of this choice; 3. Until |cv| = `; /*Until length does not change */
Evangelos Kranakis, Carleton University, SCS (October 31, 2020)
Distributed Computing, COMP 4001 32
Example (1/2)
• Given two nodes u ! v.
• Lets show how the color of node v changes from the old color
cv to a new color cv.
– A similar change occurs to the color of u, but this is
influenced from the predecessor of u. U-v
• Let their current colors be cu = 594 and cv = 631.
• Convert to binary:
cu =512+64+16+2=29 +26 +24 +21
cv = 512+64+32+16+4+2+1 = 29 +26 +25 +24 +22 +21 +20
• cu = 1001010010 and cv = 1001110111
Evangelos Kranakis, Carleton University, SCS (October 31, 2020)
Distributed Computing, COMP 4001 33
Example (2/2)
• Consider the two nodes with colors
cu = 1001010010 and cv = 1001110111
• What is the smallest i such that cu(i) 6= cv(i)?
• Line up the bits
1001010010
”
1001110111
• So i = 4 (counting starts from 0); in binary 4 is 100 and the
new colour of v in binary representation is icv(i) = 1001 = 9
Evangelos Kranakis, Carleton University, SCS (October 31, 2020)
Distributed Computing, COMP 4001 34
Execution of Coloring Algorithm
• A node receives input from its predecessor. . .
Hw
• . . .and provides input to its successor. tofu
Evangelos Kranakis, Carleton University, SCS (October 31, 2020)
Distributed Computing, COMP 4001 35
Correctness: Legal Coloring (1/2)
• Consider three consecutive neighboring nodes u, v, w at some iteration of the algorithm with u = prev(v), v = pre(w).
m
–
KImJ
= pre(v) v w=succ(v)
• Let I, J be the indices picked by v, w in Step 2(b), respectively. – I := min{i : cu(i) 6= cv(i)} and J := min{j : cv(j) 6= cw(j)} – v, w receive the new colours:
u
and
cv Icv(I) cw Jcw(J)
Evangelos Kranakis, Carleton University, SCS (October 31, 2020)
Distributed Computing, COMP 4001 36
Correctness: Legal Coloring (2/2)
• We need to show that Icv(I) 6= Jcw(J). • There are two cases to consider:
1. If I 6= J then rule 2(b) ensures that the new labels Icv(I),Jcw(J) as defined in 2(c) di↵er in a bit
– because I,J do
2. If I = J then rule 2(b) ensures that the new labels as
defined in 2(c) di↵er in the last bit
– Recall that cu(I) 6= cv(I) and cv(J) 6= cw(J)
– Since I = J we have that cu(I) 6= cv(I) and cv(I) 6= cw(I)
– The new labels for v,w will be Icv(I) and Icw(I) and by
choice of I we have that cv(I) 6= cw(I).
Evangelos Kranakis, Carleton University, SCS (October 31, 2020)
Distributed Computing, COMP 4001 37
Number of Rounds
• At the start, K0 = K = O(logn) is the max number of5bits of a
:
iteration
il
node in the original ID coloring.
• Let K
after the rth iteration.
bits, the third of roughly log log log n bits, etc.
• As a matter of fact the “sizes of the colours” shrink very
rapidly!
– The size of the colour (measured in bits) in the new step is the logarithm of the size of the colour in the previous step!
Slogan
r
r.- Curti
denote the number of bits in the color representation
t h
est
flogKitt
• ObservethatK
– Therefore the second coloring will be of roughly log log n
=dlogK e+1. r
–
r+1
L
Evangelos Kranakis, Carleton University, SCS (October 31, 2020)
r
Distributed Computing, COMP 4001 38 Iterated Logarithm: log⇤
• log⇤ n is not really a logarithm:
– it is rather the number of iterations of the log function on a
number n until it stops having an e↵ect! • Log-Star (in base 2) of n:
– Is the number of logarithms in base 2 needed so that starting from n you get down to 2.
• Can be defined in any base! Here we look only on base 2.
37-11=3 =2↳
flog -51+1=4 flog 41+1
4 logy
Fogt -51+1=5
flog
is
=3
Evangelos Kranakis, Carleton University, SCS (October 31, 2020)
Distributed Computing, COMP 4001 39
Definition of log⇤ • Iterated Definition of log⇤ n: Let
– log(1) n = log n, and (I
– log(x+1) n = log(logx n), for x 1.
Then log⇤ n = first integer x such that log(x) n 2. a
• Recursive definition8of log⇤ n:
log⇤ x = <: 1 if x 2
1+log⇤(logx) ifx>2
alog(x) n should not be confused with logx n: the logarithm to the power x.
Evangelos Kranakis, Carleton University, SCS (October 31, 2020)
Distributed Computing, COMP 4001 40
Example
• Log-star is a very slowly growing function.
• Consider the number n = 225 .
log(225 ) = 25
log(225 ) = 5
log(5) ⇡ 2.32192809489
log(2.32) < 2. Hence, log⇤(225 ) = 4.
• Log-star of all the atoms in the observable universe (estimated to be 1080) is 5.
Evangelos Kranakis, Carleton University, SCS (October 31, 2020)
Distributed Computing, COMP 4001 41
The Starting Nodes: Something Wrong?
• Recall the leftmost node was given the color 0.
are reduced to constant size. ← Ate
• It is not clear from the description of the algorithm why the identities of the nodes “located” at the beginning of the line
– By beginning we mean the first O(log⇤ n) nodes.
• Observe that the identities of the nodes after location O(log⇤ n) )
og*n
are indeed reduced to constant size. log* Gogh • Can remedy this by adding an additional step at the end of the
algorithm:
– The first O(log⇤ n) nodes run a recoloring algorithm to
OAg*n)t log* n
reduce their colors to constant size.
• Note that this step takes additional time O(log⇤ n).
Evangelos Kranakis, Carleton University, SCS (October 31, 2020)
Distributed Computing, COMP 4001 42 Six Coloring in log⇤ n Iterations
• If K = number of bits in the coloring after i iterations then i
• In the final iteration r we have that Kr = Kr 1 3. 't¥1
– Kr+1 =dlogKre+1.
– Kr+1 < Kr as long as Kr 4. A
• Therefore in the final coloring you have
– at most three choices for an index to a bit in the (r 1)-st
coloring, and
– two choices for the value of the bit,
which gives a total of six colors. • It turns out,
Can color the line in 6
colors . But
– we can improve on # of colors from six to three, but w e promised
can do itin3! Evangelos Kranakis, Carleton University, SCS (October 31, 2020)
– cannot improve on the log⇤ n.
Distributed Computing, COMP 4001 43
Three Colors Su ce
• How do we reduce the number of colors from six to three?
• Suppose that the algorithm we discussed before has colored a
line with the six colors 0, 1, 2, 3, 4, 5 as follows 0542530315423014324010245
• How do you color it using only the colors 0, 1, 2?
, 314,5
Odin
Evangelos Kranakis, Carleton University, SCS (October 31, 2020)
Distributed Computing, COMP 4001 44
Three Colors Su ce
I• Start with the sequence 0542530315423014324010245
2 2
• Eliminate 5: by choosing a color from 0, 1, 2
fI t
0142030310423014324010240 • Eliminate 4: by choosing a color from 0, 1, 2
f
f
990
0102030310123010321010210 • Eliminate 3: by choosing a color from 0, 1, 2
a
0102010010121010121010210
£
Evangelos Kranakis, Carleton University, SCS (October 31, 2020)
Distributed Computing, COMP 4001 45
Coloring Rings
• Theorem 2 There is an algorithm which can 3-color any ring
O
of size n in log⇤ n time. • Same algorithm.
↳
reduce u.in#aYitwmerrlbs*nl
Can
you
Evangelos Kranakis, Carleton University, SCS (October 31, 2020)
Distributed Computing, COMP 4001 46
Coloring Trees
Evangelos Kranakis, Carleton University, SCS (October 31, 2020)
Distributed Computing, COMP 4001 47
From Lines to Trees
• The line colouring algorithm also works on trees!
• The basic assumption is that you must have a node of the tree
designated as the root!
• Further, other nodes mu*st have a parent (i.e., a predecessor)!
• The main theorem is the following.'
" :
¥**. Evangelos Kranakis, Carleton University, SCS (October 31, 2020)
Distributed Computing, COMP 4001 48
6-Coloring Theorem
• Theorem 3 There is an algorithm which can I6-color any tree in log⇤ n time.
color
-
Evangelos Kranakis, Carleton University, SCS (October 31, 2020)
Distributed Computing, COMP 4001
49
6-Coloring Algorithm for Trees: Vertex v
•
Algorithm: 6-Color
1. cv idv; 2. Repeat:
pred(u ) v
(a) ` |cv|;
(b) ifvis“theroot”thensetI
o
0
else set I min{i : cv(i) 6= cparent(v)(i)};
I HRH
(c) Set cv Icv(I); /* concatenation */ (d) Inform all children of v of this choice;
ai ai ie; -
ay
3. Until |cv| = `;
• Why is the algorithm correct?
Evangelos Kranakis, Carleton University, SCS (October 31, 2020)
Distributed Computing, COMP 4001 50
3-Coloring Theorem for Trees
• Theorem 4 There is an algorithm which can 3-color any tree
in O(log⇤ n) time.
• The reason is that the coloring on the descendants of a given node is independent when done on disjoint paths.
Evangelos Kranakis, Carleton University, SCS (October 31, 2020)
Distributed Computing, COMP 4001 51
Shift-Down Algorithm
• The color reduction method is called “shift-down”.
•
Algorithm Shift-Down
1. Concurrently at all vertices:
2. Recolor each non-root vertex by the color of its parent.
3. Recolor root by a new color, di↵erent from its current one.
• Why is “shift-down” correct?
• Colors (of the original coloring) are shifted down.
Evangelos Kranakis, Carleton University, SCS (October 31, 2020)
Distributed Computing, COMP 4001 52
Analysis of Shift-Down Algorithm
• Lemma 1 (Analysis of Algorithm Shift Down) Algorithm Shift Down preserves coloring legality; also siblings are monochromatic.
• Two vertices v = parent(w), w are recolored by cparent(v) and cv, which are di↵erent since c was a legal colouring.
• Ifv=root,thenthenewcolorsarexandcv,wherexissome color di↵erent from cv.
• Also, all children of some vertex v get the same new color cv.
Evangelos Kranakis, Carleton University, SCS (October 31, 2020)
Distributed Computing, COMP 4001 53
Final Color Reduction
• Now assume the six colors employed in the tree are 0,1,2,3,4,5
• The final three reduction steps involve cancelling colors 3,4,5
one at a time.
• In the end, there will be three colors left 0, 1, 2. – This is done by Algorithm Six2Three
Evangelos Kranakis, Carleton University, SCS (October 31, 2020)
Distributed Computing, COMP 4001 54
•
Algorithm Six2Three
Six2Three Algorithm
1. for x = 5, 4, 3 do /* Cancel color x */
2. Perform subroutine Shift-Down on the current colouring;
3. ifcv =xthen
4. v chooses new color cv 2 {0,1,2} not used by any of the
neighbors.
5. endif
6. endfor
Evangelos Kranakis, Carleton University, SCS (October 31, 2020)
Distributed Computing, COMP 4001 55
Example of Six2Three
• Recolouring method
• Example discarding color 4.
Evangelos Kranakis, Carleton University, SCS (October 31, 2020)
Distributed Computing, COMP 4001 56
Analysis of Six2Three
• Theorem 5 (Analysis of Algorithm Six to Three) Algorithm Six2Three colors a tree with three colors in time O(log⇤ n).
• Each vertex colored x will find an available color from the set {1, 2, 3},
– since by the Shift-Down Lemma at most two of these colors are occupied, one by its parent and one by its children.
• Now note that recoloring the x colored vertices simultaneously creates no problem since they are all mutually nonadjacent.
Evangelos Kranakis, Carleton University, SCS (October 31, 2020)
Distributed Computing, COMP 4001 57
Optimality
• Fast tree-coloring with only 2 colors is more than exponentially more expensive than coloring with 3 colors.
– In a tree degenerated to a line, nodes far away need to figure out whether they are an even or odd number of hops away from each other in order to get a 2-coloring.
– To do that one has to send a message to these nodes. This costs time linear in the number of nodes.
Evangelos Kranakis, Carleton University, SCS (October 31, 2020)
Distributed Computing, COMP 4001 58
Lower Bounds
Evangelos Kranakis, Carleton University, SCS (October 31, 2020)
Distributed Computing, COMP 4001 59
Can anything be better than log⇤ n?
• The only thing better than O(log⇤ n) running time is O(1)
running time!
– A 2-coloring is possible with O(1) running time in a distributed system with GPS!
• It turns out that we can prove a lower bound of ⌦(log⇤ n) on the time required to color the n-vertex line (ring) by three colors.
– This implies a tight bound of ⇥(log⇤ n) on the time required for 3-coloring the line (ring).
Evangelos Kranakis, Carleton University, SCS (October 31, 2020)
Distributed Computing, COMP 4001 60
⌦(log⇤ n) Lower Bound
• Theorem 6 Every deterministic, distributed algorithm to color a directed ring with 3 or less colors needs at least (log⇤ n)/2 1 rounds.
• The proof uses a theorem of Frank P. Ramsey.
(22 February 1903 19 January 1930).
• We will not prove Theorem 6 here.
Evangelos Kranakis, Carleton University, SCS (October 31, 2020)
Distributed Computing, COMP 4001 61
Generalizations and Additional Results
• Linial (1992) proves that
– in rooted d-regular tree Td,r of radius r, any synchronous
distributed algorithm running in time 2 r cannot color
colored with 5 2 log n colors in one time unit distributively.
– for G labeled, in time O(log ⇤n) it is possible to color G
with O( 2) colors in a distributive synchronous algorithm. • There exists a deterministic distributed algorithm for coloring
arbitrary graphs with max degree ;
– can be colored with + 1 colors in O( log⇤ n) time.
Td,r by fewer than 1 2
p
3
d colors.
– an arbitrary graph G of order n and max degree , can be
Evangelos Kranakis, Carleton University, SCS (October 31, 2020)
Distributed Computing, COMP 4001 62
Exercisesa
1. For any graph G = (V, E) define the chromatic numbers
centralized(G), distributed(G), local(G)
for centralized, distributed, and local computation. (a) How do they di↵er?
(b) Is there a natural order of these three quantities?
2. Define the concepts of centralized, distributed and local for any algorithmic computation and make a comparison.
3. Let n ! h(n) be an integer valued function, where h(n) is the number of hops allowed in a network of size n to complete the computation. Formulate the various types of computation discussed above in terms of the function h(n).
4. (??) Consider Exercise 3. If h(n) = n then the number of aDo not submit!
Evangelos Kranakis, Carleton University, SCS (October 31, 2020)
Distributed Computing, COMP 4001 63
colors is 2. If h(n) = 1 then the number of colors is 3. For which threshold value of h(n) does the number of colors jumps from 2 to 3?
5. Compute log⇤(101000).
6. Compute log⇤(22216 ).
7. Explain in more detail (than the slide presented in class) that the local coloring algorithm (before the six ! three reductions) reduces to a six coloring.
8. Show in detail that on the line graph three colors su ce.
9. Prove that a log⇤ coloring algorithm is possible on a ring. How many colors does it require?
10. Prove in detail the correctness of the log⇤ tree coloring algorithm.
Evangelos Kranakis, Carleton University, SCS (October 31, 2020)
Distributed Computing, COMP 4001 64
Sources
• L. Barenboim, and M. Elkin. Distributed graph coloring: Fundamentals and recent developments. Synthesis Lectures on Distributed Computing Theory 4.1 (2013): 1-171.
• N. Linial. Locality in distributed graph algorithms. SIAM Journal on Computing 21.1 (1992): 193-201.
• D. Peleg, Distributed Computing: a Locality Sensitive Approach, SIAM, 2000.
Evangelos Kranakis, Carleton University, SCS (October 31, 2020)