Distributed Computing, COMP 4001 1
Distributed IS (Part 1)
Evangelos Kranakis, Carleton University, SCS (October 7, 2020)
Distributed Computing, COMP 4001 2
• Independent Set (IS)
• Distributed IS
1. Distributed Slow MIS 2. Distributed Fast MIS
⇐
Outline
Evangelos Kranakis, Carleton University, SCS (October 7, 2020)
Distributed Computing, COMP 4001 3
Independent Sets
Evangelos Kranakis, Carleton University, SCS (October 7, 2020)
Distributed Computing, COMP 4001 4
Inependent Sets
• IS: Given an undirected Graph G = (V, E) an independent set is a subset of nodes U ✓ V , such that no two nodes in U are adjacent.
• MIS: An independent set is maximal if no node can be added without violating independence.
• MaxIS: An independent set of maximum cardinality is called maximum.
007000
Evangelos Kranakis, Carleton University, SCS (October 7, 2020)
-o m e goin
Tao
of
II maxim
a
it ¥h¥¥¥
have Does
maximal
sites
Distributed Computing, COMP 4001 5
Independent Set (IS)
• AnISisasetofnodesofthegraphsuchthatanytwoofthem are not adjacent.
• We also have maximal and maximum independent sets.
al 82
al-um -al
• Every MIS (Maximal Independent Set) is a dominating set.
• In general, the size of every MIS can be larger than the size of an optimal minimum dominating set by a factor of ⌦(n).a
aWe won’t prove this here.
maximal m axim um -↳
–
–
Evangelos Kranakis, Carleton University, SCS (October 7, 2020)
A set D is a dominating set, if every of the graph is
adjacent to s o m e vertex in D
Distributed Computing, COMP 4001 6 Coloring and Independent Sets
• Example 1 Graph has two maximal independent sets (MIS), but only one is a maximum independent set (MaxIS).
• Example 2
colored
In a
graph, t h e vertices
of a color form
anIS
.
Evangelos Kranakis, Carleton University, SCS (October 7, 2020)
Distributed Computing, COMP 4001 7
Coloring and Independent Sets
• There is a relation between independent sets and node coloring: – each color class is an independent set,
* ¥09
1
IS3 in.
⇒
1
o
⇐
Is
it::¥ with root : it has 5 leaves
– however, it is not necessarily a MIS.
Tree
Evangelos Kranakis, Carleton University, SCS (October 7, 2020)
Distributed Computing, COMP 4001 8
From Coloring to Independent Sets
• Starting with a coloring, one can derive a MIS algorithm:
1. We first choose all nodes of the first color.
2. Then, for each additional color we add “in parallel” (without conflict) as many nodes as possible.
Choose a
-0
color
112,- – – IC- I 2
x.
i÷oi÷
:O
Evangelos Kranakis, Carleton University, SCS (October 7, 2020)
Distributed Computing, COMP 4001 9
From Coloring to Independent Sets: Analysis
• Theorem 1 Given a coloring algorithm that needs C colors
and runs in time T, we can construct a MIS in time C + T. • Time complexity:
– the T in the time complexity comes from the coloring algorithm, and
– the C in the time complexity comes from the number of colors.
÷: ” in .
Evangelos Kranakis, Carleton University, SCS (October 7, 2020)
Tim e
Message Complexity :
CtT
Complexity
A = # of nodes of
color i XoX, +(XoTXc)Xzt(XothtXdXz
t
taking.ly”
..
–
X )c=X:number
is
(Hot- — t Conte
Xc chromatic
addition w e
need the
coloring alg
Message to:E¥kt¥÷÷*Hiae÷
In cost
of
the
.
do it messages :
0ft)
Troye: can’t w e
it
in YES
Distributed Computing, COMP 4001 10
-\
Related Topic: Set Cover (SC)
• Given a set of elements {1, 2, . . . , n} (called the universe) and a
collection S of m sets whose union equals the universe, the set
cover problem is to identify the smallest sub-collection of S
S-{-r-
}
whose union equals the universe.
–
Sig Ism
1. For example, consider the universe U = {1, 2, 3, 4, 5} and the collection of sets S = {{1, 2, 3}, {2, 4},{3,4},{4,5}}. Clearly the union of S is U However, we can cover all of the elements with the following, smaller number of sets:
I
{{1, 2, 3}, {4, 5}}.
2. A company needs to buy a certain amount of varied supplies
and there are suppliers that o↵er various deals for di↵erent combinations of materials (Supplier A: 2 tons of steel + 500 tiles for $x; Supplier B: 1 ton of steel + 2000 tiles for $y; etc.). You could use set covering to find the best way to get all the materials while minimizing cost.
Evangelos Kranakis, Carleton University, SCS (October 7, 2020)
Distributed Computing, COMP 4001 11
Issues
• Computing a maximum independent set (MaxIS) is a notoriously di cult problem.
– Equivalent to maximum clique on the complementary graph. – Both problems are NP-hard, in fact not approximable
within n1/2 ✏.
• MIS and MaxIS can have very di↵erent sizes.
– On a star graph MIS is ⇥(n) smaller than the MaxIS.
{His {1,21. – it)
:3! ma
‘
2
n leaves a central
MIS
3
Maxis .si:7?-4starnmnt.he,
6
c
5
node
Evangelos Kranakis, Carleton University, SCS (October 7, 2020)
Distributed Computing, COMP 4001 12
• Example 1
Examples: MIS
4
u
z
v
• Example 2
o
4 O
2
ma’Eas
site
n
Evangelos Kranakis, Carleton University, SCS (October 7, 2020)
Distributed Computing, COMP 4001 13
• Example 3
Examples: MIS
←
B
rats
A
• Example 4
i
Evangelos Kranakis, Carleton University, SCS (October 7, 2020)
Distributed Computing, COMP 4001 14
Computing MIS
• Computing a MIS sequentially is trivial:
1. Scan the nodes in arbitrary order.
2. If a node u does not violate independence, – add u to the MIS.
3. If u violates independence, – discard u.
*¥¥¥¥¥÷
Evangelos Kranakis, Carleton University, SCS (October 7, 2020)
Sequential
:
MINH)
Malu
I
—
–
Distributed Computing, COMP 4001 15
Algorithm: Lexicographic MIS(G)
• Previous algorithm sometimes stated as follows. Consider a graph G = (V, E) in which the vertices are lexicographically ordered.
1: 2: 3: 4: 5:
I = ;, V 0 = V whileV0 6=;do
Choose v 2 V 0 (in lexicographic order) I I [ {v}
V0 V0 \({v}[N(v))
Return I;
• With this simple greedy algorithm, we can find a MIS in
O(|V | + |E|) time.
• The main question is how to compute a MIS in a distributed manner.
6:
Evangelos Kranakis, Carleton University, SCS (October 7, 2020)
Distributed Computing, COMP 4001 16
Distributed
Evangelos Kranakis, Carleton University, SCS (October 7, 2020)
Distributed Computing, COMP 4001 17
Distributed Slow MIS
• Main idea is to give priority to nodes with higher ID. •
• Requires Node IDs
• Every node v executes the following code:
1. if all neighbors of v with larger identifiers have decided not
Slow MIS
to join the MIS then
2. v decides to join the MIS 3. end if
w
°
• HE.
d
°
queries its neighbor set Nlu)
Evangelos Kranakis, Carleton University, SCS (October 7, 2020)
Distributed Computing, COMP 4001 18
Complexity
• Theorem 2 Algorithm Slow MIS has time complexity of O(n)
and a message complexity of O(m).
• Slow MIS is not better than the sequential algorithm in the worst case, because there might be one single point of activity at any time.
Evangelos Kranakis, Carleton University, SCS (October 7, 2020)
Distributed Computing, COMP 4001 19 Issues
• Using Theorems 1 and 2°we get a distributed deterministic MIS algorithm for cycles (also for trees, and bounded degree graphs) with time complexity O(log n) (will cover this later in class).
÷÷ ⇤
conflict) as many nodes as possible.
.÷÷÷i
• With a lower bound argument one can show that this deterministic MIS algorithm for rings is asymptotically optimal.
– Because in the ring MIS is “essentially” the same as coloring.
• There have been attempts to extend the 6-Color Algorithm to more general graphs, however, so far without much success.
– First do the colouring in O(log⇤ n) rounds.
– Choose all nodes of the first color.
.
– For each additional color we add in parallel (without
..
.
.
.
Evangelos Kranakis, Carleton University, SCS (October 7, 2020)
Distributed Computing, COMP 4001 20
Is There a Faster Algorithm?
• Given that “Slow MIS” is not better than the sequential algorithm in the worst case
– Is there a faster MIS?
• In the sequel we give a probabilistic algorithm with O(log n) expected termination time.
Evangelos Kranakis, Carleton University, SCS (October 7, 2020)
Distributed Computing, COMP 4001 21
Goal: Find a parallel MIS algorithm
see ;¥¥¥÷
• Consider algorithms of the form
1. I = ;, V 0 = V
2. While G0 is not the empty graph
(a) Choose a random set of vertices S ✓ V by selecting each
vertex v independently with probability 1 , where dv is dv
the degree of v.
(b) For every edge (u, v) 2 E(G0) if both endpoints are in S,
then remove the vertex of lower degree from S (break
ties). Denote the set after this step as S0.
(c) Remove S0 and Neighbor(S0) and all adjacent edges from
G0.
(d) I I[S0
Evangelos Kranakis, Carleton University, SCS (October 7, 2020)
Distributed Computing, COMP 4001 22
Distributed Fast MISa
• Algorithm operates in synchronous rounds, grouped in phases.
• A single phase is as follows:
1. Each node v marks itself with probability 2d(v) , where d(v)
nat
ron
1
2(.a) If no higher degree neighbor of v is also marked, node v joins the MIS. /* Priority to nodes of higher degree */
(b) If a higher degree neighbor of v is marked, node v unmarks itself again.
/* If neighbors have same degree, ties broken by ID */
3. Delete all nodes that joined the MIS and their neighbors /* as they cannot join the MIS anymore. */
aA more general form of this algorithm assigns real numbers (in the range [0,1]) as weights at the nodes. An alternative version is to label the vertices with a random permutation.
is the current degree of v.
Evangelos Kranakis, Carleton University, SCS (October 7, 2020)
Distributed Computing, COMP 4001 23
Issues
• Correctness in the sense that the algorithm produces an independent set is relatively simple:
– Steps 1 and 2 make sure that if a node v joins the MIS, then v’s neighbors do not join the MIS at the same time.
– Step 3 makes sure that v’s neighbors will never join the MIS.
• The algorithm eventually produces a MIS, because the node
with the highest degree will mark itself at some point in Step 1.
• The only remaining question is how fast the algorithm terminates.
– This is not easy to figure out!
Evangelos Kranakis, Carleton University, SCS (October 7, 2020)
Distributed Computing, COMP 4001 24
Exercisesa
1. Show that any maximal matching is a 2-approximation of a
maximum matching.
2. Let G = (V, E) be the graph for which we want to construct
the matching. Define the auxiliary graph G0 as follows:
• for every edge in G there is a node in G0;
• two nodes in G0 are connected by an edge if their respective edges in G are adjacent.
Show that a (maximal) independent set in G0 is a (maximal) matching in G, and vice versa.
aDo not submit!
Evangelos Kranakis, Carleton University, SCS (October 7, 2020)