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
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 differences 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”.
• 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.
– A measurement made on one of a pair of separated but entangled particles causes a simultaneous effect, the collapse of the wave function, in the remote particle (i.e. an effect 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 effects. – Shape
– Size
– Color
– Nature
– Other environmental factors
• In turn, this affects the genotype.
• Quantum Biology is a newly developing field for the study of
non-local biological phenomena. – Bird navigation
Evangelos Kranakis, Carleton University, SCS (October 31, 2020)
Distributed Computing, COMP 4001 8
Locality in Social Sciences
• Local Characteristics – Language
– Behaviour – Culture
– Food
• Global Phenomena – Cascades
– Rumors
• How do certain events cascade?
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.
• Concerns phenomena that are geometrically close to each other.
• Locality is influenced by distance but is not the same thing as location!
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
• Usually it means:
– the execution of a process depends on nearby processes.
– 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?
Evangelos Kranakis, Carleton University, SCS (October 31, 2020)
Distributed Computing, COMP 4001 12
Locality
• Decision made at node u not affected by nodes far away from u.
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
• 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
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! • Lets go back to coloring.
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 different 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.
– Is the algorithm correct?
– Is this a local algorithm?
– Is there a local colouring algorithm?
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?
Globally/Locally
1212121212121
– You are not constrained by # of hops. • Locally?
– Constrained by # of hops.
– In a distributed setting, the difficulty 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)
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 coloring 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)
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,
– n→h(n)=c,cissomeconstant, – n→h(n)=logn,
– n→h(n)=√n,
– n→h(n)=n,
– n→h(n)=log∗n,etc
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 executionofanalgorithmA∈AonanetworkG∈N (onn vertices) a message emanating from a node will never propagate more than h(n) hops from its originator.
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?
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.
• 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!
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
– 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.
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.
Evangelos Kranakis, Carleton University, SCS (October 31, 2020)
Distributed Computing, COMP 4001 28
Assumptions for Coloring
• Represent each cv as a sequence of bits.
– Let |cv| be the number of bits in cv, and – cv(i) the i-th bit of cv.
• Example:
– 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.
• The concatenation
– of two sequences s,s′ of bits is the sequence ss′.
– Example: if s = 1010 and s′ = 110 then ss′ = 1010110
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 different: cu ̸= 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 differs 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
different colors.
• NB: Bit representation of each new color is of length logarithmic of the length of the previous color!
Evangelos Kranakis, Carleton University, SCS (October 31, 2020)
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)
(a) l ← |cv|;
(b) if v is “leftmost vertex” then set I ← 0
else set I ← min{i : cv(i) ̸= cpre(v)(i)}; (c) Set cv ← Icv(I); /* concatenation */
(d) Inform the successor suc(v) of v of this choice; 3. Until |cv| = l; /*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.
• 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) ̸= 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. . .
• . . .and provides input to its successor.
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).
KIJ
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) ̸= cv(i)} and J := min{j : cv(j) ̸= cw(j)} – v, w receive the new colours:
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) ̸= Jcw(J). • There are two cases to consider:
1. If I ̸= J then rule 2(b) ensures that the new labels Icv(I),Jcw(J) as defined in 2(c) differ 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) differ in the last bit
– Recall that cu(I) ̸= cv(I) and cv(J) ̸= cw(J)
– Since I = J we have that cu(I) ̸= cv(I) and cv(I) ̸= 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) ̸= cw(I).
Evangelos Kranakis, Carleton University, SCS (October 31, 2020)
Distributed Computing, COMP 4001 37
Number of Rounds
• Atthestart,K0 =K=O(logn)isthemaxnumberofbitsofa node in the original ID coloring.
• Let Kr denote the number of bits in the color representation after the rth iteration.
• ObservethatKr+1 =⌈logKr⌉+1.
– Therefore the second coloring will be of roughly log log n
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!
Evangelos Kranakis, Carleton University, SCS (October 31, 2020)
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 effect!
• 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.
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=logn,and
– log(x+1) n = log(logx n), for x ≥ 1.
Then log∗ n = first integer x such that log(x) n ≤ 2. a • Recursive definition of 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.
• It is not clear from the description of the algorithm why the identities of the nodes “located” at the beginning of the line are reduced to constant size.
– By beginning we mean the first O(log∗ n) nodes.
• Observe that the identities of the nodes after location O(log∗ n)
are indeed reduced to constant size.
• 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 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 Ki = number of bits in the coloring after i iterations then – Kr+1 =⌈logKr⌉+1.
– Kr+1