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.
Evangelos Kranakis, Carleton University, SCS (October 7, 2020)
Distributed Computing, COMP 4001 5
Independent Set (IS)
• AnISisasetofnodesofthegraphsuchthatanytwoofthem are not adjacent.
• We also have maximal and maximum independent sets.
• 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.
Evangelos Kranakis, Carleton University, SCS (October 7, 2020)
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
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,
– however, it is not necessarily a MIS.
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.
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.
Evangelos Kranakis, Carleton University, SCS (October 7, 2020)
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 whose union equals the universe.
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:
{{1, 2, 3}, {4, 5}}.
2. A company needs to buy a certain amount of varied supplies and there are suppliers that offer various deals for different 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 difficult 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 different sizes.
– On a star graph MIS is Θ(n) smaller than the MaxIS.
Evangelos Kranakis, Carleton University, SCS (October 7, 2020)
Distributed Computing, COMP 4001 12
• Example 1
Examples: MIS
• Example 2
Evangelos Kranakis, Carleton University, SCS (October 7, 2020)
Distributed Computing, COMP 4001 13
• Example 3
Examples: MIS
• Example 4
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)
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 ′ = V whileV′ ̸=∅do
Choose v ∈ V ′ (in lexicographic order) I ← I ∪ {v}
V ′ ← V ′ \ ({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 to join the MIS then
2. v decides to join the MIS 3. end if
Slow MIS
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).
– 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 conflict) as many nodes as possible.
• 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.
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
• Consider algorithms of the form
1. I = ∅, V ′ = V
2. While G′ 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) ∈ E(G′) if both endpoints are in S,
then remove the vertex of lower degree from S (break
ties). Denote the set after this step as S′.
(c) Remove S′ and Neighbor(S′) and all adjacent edges from
G′.
(d) I ← I ∪ S′
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 1 , where d(v)
is the current degree of v.
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.
2d(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 G′ as follows:
• for every edge in G there is a node in G′;
• two nodes in G′ are connected by an edge if their respective edges in G are adjacent.
Show that a (maximal) independent set in G′ is a (maximal) matching in G, and vice versa.
aDo not submit!
Evangelos Kranakis, Carleton University, SCS (October 7, 2020)