DFS ClassicalDFS CidonDFS§1 CidonDFS§2 Bellman-Ford MIS
Search Fundamentals
Radu Nicolescu Department of Computer Science University of Auckland
31 July 2020
1/34
DFS ClassicalDFS CidonDFS§1 CidonDFS§2 Bellman-Ford MIS
1 Distributed DFS and BFS
2 ClassicalDFS
3 CidonDFS §1
4 CidonDFS §2
5 Bellman-Ford algorithm
6 Maximal Independent Set
2/34
DFS ClassicalDFS CidonDFS§1 CidonDFS§2 Bellman-Ford MIS
Distributed DFS
• Despite its sequential appearance, DFS can work faster on distributed networks!
• Classical DFS traverses each edge (tree and frond) twice, thus time complexity = message complexity = 2|E|
• Like other distributed versions, Cidon DFS traverses each tree edge twice (needed), but avoids all or most fronds, thus
time complexity = 2|V | − 2, but at the possible expense of increased message complexity = 3|E|
• Small error in Tel’s text: message complexity is not 4|E|…
• Cidon DFS was designed for async networks, thus also works for sync networks (even better).
4/34
DFS ClassicalDFS CidonDFS§1 CidonDFS§2 Bellman-Ford MIS
Distributed BFS
• For sync networks, Echo (aka SyncBFS) finds a BFS spanning tree; time complexity = 2D + 1, message complexity = 2|E |
• Despite its parallel appearance, BFS is harder to implement on async networks and does not get all the expected benefits (bad time or bad message complexity).
• In fact, on async networks, BFS looks like a “milder” version of Bellman-Ford: shows similar issues, but less severe
• AsyncBFS [Lynch]: messages = O(D|E|); time−pileups = O(D); time+pileups = O(D|V|)
• LayeredBFS [Lynch]: messages = O (D |V | + |E |); time−pileups = O(D2)
• We do not further follow these issues here…
5/34
DFS ClassicalDFS CidonDFS§1 CidonDFS§2 Bellman-Ford MIS
Cidon DFS
• Cidon DFS uses two types of tokens:
• One single classical tok token, sent on tree edges and,
occasionally, on fronds
• New vis notification tokens, used to mark possible fronds
• A vis token can be sent:
• ahead of tok
• together with tok (can be combined) • alone (on fronds only)
Read more: Tel §6.4, or Cidon’s original paper:
Yet Another Distributed Depth-First-Search Algorithm http://cidon.eew.technion.ac.il/files/var/448324- cidon_dfs_87.pdf
6/34
DFS ClassicalDFS CidonDFS§1 CidonDFS§2 Bellman-Ford MIS
Classical vs Cidon DFS – Examples
• In all cases, there is one single tok token, thus the time complexity sums the delays in this token’s delivery
• In classical DFS, frond edge {2, 4} is sequentially twice traversed by the tok token, which adds 2 time intervals
• In Cidon DFS §1, frond edge {2, 4} is twice traversed by vis tokens, in parallel with the progress of the tok token, which now saves 2 time intervals (while keeping messages count)
• In Cidon DFS §2, frond edge {2, 4} is overlappingly traversed
• in one direction, by the vis token, in parallel with the progress
of the tok token,
• in the reverse direction, by a pair of tok+vis tokens (vis is not
strictly necessary)
• this still saves 1 time interval (but increases messages count)
7/34
DFS ClassicalDFS CidonDFS§1 CidonDFS§2 Bellman-Ford MIS
Classical DFS
2
3
1
6
45
Time Units = 0 Messages = 0
9/34
DFS ClassicalDFS CidonDFS§1 CidonDFS§2 Bellman-Ford MIS
Classical DFS
{}
{}
2
3
{2}
16
{}
{}
{}
45
Time Units = 1 Messages = 1
9/34
DFS ClassicalDFS CidonDFS§1 CidonDFS§2 Bellman-Ford MIS
Classical DFS
{3} 2
{}
3
{2}
1
{}
6
{}
{}
45
Time Units = 2 Message = 2
9/34
DFS ClassicalDFS CidonDFS§1 CidonDFS§2 Bellman-Ford MIS
Classical DFS
{3}
{5, 6} 3
2
{2, 4} 1
{3, 5} 6
{1}
{6, 4}
45
Time Units = 10 Message = 10
9/34
DFS ClassicalDFS CidonDFS§1 CidonDFS§2 Bellman-Ford MIS
Classical DFS : 4 → tok → 2
{3}
{5, 6} 3
2
{2, 4}
{3, 5}
1
6
45
{1, 2}
{6, 4} Time Units = 11
Message = 11
9/34
DFS ClassicalDFS CidonDFS§1 CidonDFS§2 Bellman-Ford MIS
Classical DFS : 2 → tok → 4
{3, 4} 2
{5, 6} 3
{2, 4} 1
{3, 5} 6
{1, 2}
{6, 4}
45
Time Units = 12 Message = 12
9/34
DFS ClassicalDFS CidonDFS§1 CidonDFS§2 Bellman-Ford MIS
Classical DFS
{3, 4, 1} 2
{5, 6, 4, 2} 3
{2, 4}
{3, 5}
1
6
{1, 2, 3, 5}
45
{6, 4, 3}
Time Units = 18 = 2M Message = 18 = 2M
9/34
DFS ClassicalDFS CidonDFS§1 CidonDFS§2 Bellman-Ford MIS
Cidon DFS §1
2
3
1
6
45
Time Units = 0 Messages = 0
11/34
DFS ClassicalDFS CidonDFS§1 CidonDFS§2 Bellman-Ford MIS
Cidon DFS §1
{1} 2
{}
3
{2}
16
{}
45 {1}
Time Units = 1 Messages = 3
{}
11/34
DFS ClassicalDFS CidonDFS§1 CidonDFS§2 Bellman-Ford MIS
CidonDFS§1: 2→vis→4
{1, 3} {2}
2
3
{2}
16
{}
{1, 2}
45
Time Units = 2 Messages = 6
{}
11/34
DFS ClassicalDFS CidonDFS§1 CidonDFS§2 Bellman-Ford MIS
Cidon DFS §1
{1, 3}
2
{2, 5, 6}
3
{2}
{3, 5} 16
45
{1, 2, 3, 5} {3, 6, 4}
Time Units = 6 Messages = 16
11/34
DFS ClassicalDFS CidonDFS§1 CidonDFS§2 Bellman-Ford MIS
CidonDFS§1: 4→vis→2
{1, 3, 4} 2
{2, 5, 6, 4} 3
{2, 4}
{3, 5} 16
45
{1, 2, 3, 5} {3, 6, 4}
Time Units = 7 Messages = 20
11/34
DFS ClassicalDFS CidonDFS§1 CidonDFS§2 Bellman-Ford MIS
Cidon DFS §1
{1, 3, 4} 2
{2, 5, 6, 4} 3
{2, 4}
{3, 5} 1 6
45
{1, 2, 3, 5} {3, 6, 4}
Time Units = 10 = 2N – 2 Messages = 23 ≤ 3M
11/34
DFS ClassicalDFS CidonDFS§1 CidonDFS§2 Bellman-Ford MIS
Cidon DFS §2
2
3
1
6
45
Time Units = 0 Messages = 0
13/34
DFS ClassicalDFS CidonDFS§1 CidonDFS§2 Bellman-Ford MIS
Cidon DFS §2
{1} 2
{}
3
{2}
16
{}
45 {1}
Time Units = 1 Messages = 3
{}
13/34
DFS ClassicalDFS CidonDFS§1 CidonDFS§2 Bellman-Ford MIS
CidonDFS§2: 2vis4
{1, 3} {2}
2
3
{2}
16
{}
{1}
45
Time Units = 1 + ε Messages = 6
{}
13/34
DFS ClassicalDFS CidonDFS§1 CidonDFS§2 Bellman-Ford MIS
Cidon DFS §2
{1, 3}
2
{2, 5, 6}
3
{2}
{3, 5} 16
45 {1, 3, 5} {3, 6, 4}
Time Units = 1 + 5ε Messages = 16
13/34
DFS ClassicalDFS CidonDFS§1 CidonDFS§2 Bellman-Ford MIS
CidonDFS§2: 2vis4,4→tok+vis→2
{1, 3, 4} 2
{2, 5, 6, 4} 3
{2, 4}
{3, 5} 16
45 {1, 3, 5} {3, 6, 4}
Time Units = 1 + 6ε Messages = 20
13/34
DFS ClassicalDFS CidonDFS§1 CidonDFS§2 Bellman-Ford MIS
CidonDFS§2: 2→vis→4
{1, 3, 4} {2, 5, 6, 4}
2
3
{2, 4}
{3, 5} 16
45 4
{1, 2, 3, 5} {3, 6, 4}
Time Units = 2 Messages = 20
13/34
DFS ClassicalDFS CidonDFS§1 CidonDFS§2 Bellman-Ford MIS
Cidon DFS §2
{1, 3, 4} 2
{2, 5, 6, 4} 3
{2, 4}
{3, 5} 1 6
45 {1, 2, 3, 5} {3, 6, 4}
Time Units = 6 ≤ 2N – 2 Messages = 24 ≤ 3M
13/34
DFS ClassicalDFS CidonDFS§1 CidonDFS§2 Bellman-Ford MIS
Distributed Bellman-Ford algorithm
• Classical Bellman-Ford algorithm finds all shortest paths from a single source – like Dijkstra
• Advantage for Bellman-Ford: can cope with negative weights
• Classical Dijkstra: Time complexity = O ((|E | + |V |) log |V |)
• Classical Bellman-Ford: Time complexity = O(|V||E|)
• Distributed Dijkstra: more difficult distribution…
• Distributed Bellman-Ford ≈ a simple extension of Echo
15/34
DFS ClassicalDFS CidonDFS§1 CidonDFS§2 Bellman-Ford MIS
Distributed Bellman-Ford algorithm
• Sync Bellman-Ford (“Echo ++”): • Time complexity = O(|V|)
• Message complexity = O(|V||E|) • Async Bellman-Ford
• Message complexity: O(|V||V|) (terrible worst case, but often much lower in reality)
• Time complexity = O(|V|) – if any message is delivered in at most 1 time units – no FIFO [Tel]
• Time complexity = O(|V||V|) – if we consider the congestion (pileups) on FIFO channels [Lynch]
• Are these realistic? …
16/34
DFS ClassicalDFS CidonDFS§1 CidonDFS§2 Bellman-Ford MIS
Sync Bellman-Ford – Start
Problem: Find all shortest paths from node 3.
• red = active
• blue = unvisited • green = visited
17/34
DFS ClassicalDFS CidonDFS§1 CidonDFS§2 Bellman-Ford MIS
Sync Bellman-Ford – Round 1
Update formula: new distance = minimum between old distance and all newly (received distance + edge length)
• Nodes 4 and 2: update distances
18/34
DFS ClassicalDFS CidonDFS§1 CidonDFS§2 Bellman-Ford MIS
Sync Bellman-Ford – Round 2
• Nodes 5, 6, 1: update distances
19/34
DFS ClassicalDFS CidonDFS§1 CidonDFS§2 Bellman-Ford MIS
Sync Bellman-Ford – Round 3
• Node 1:
update distance (recalculation!)
20/34
DFS ClassicalDFS CidonDFS§1 CidonDFS§2 Bellman-Ford MIS
Sync Bellman-Ford – Round 4
• Node 2:
no recalculation (but could have been)
21/34
DFS ClassicalDFS CidonDFS§1 CidonDFS§2 Bellman-Ford MIS
Distributed Bellman-Ford – termination?
All nodes have successfully terminated
We can see this, but the nodes don’t know this yet
How to detect and, optionally, disseminate the termination info?
• For Sync and Async Bellmann-Ford: by convergecast and, optionally, a subsequent broadcast (like Echo)
• For Sync Bellmann-Ford: by attaching a time-to-live (TTL) to the broadcast token
• Initially equal to the number of nodes |V | (if this is known)
• After receiving it, each node decrements this by 1, at each
round (thus sync mode required)
• When TTL = 0, each node knows that the algorithm has terminated (guaranteed)
22/34
DFS ClassicalDFS CidonDFS§1 CidonDFS§2 Bellman-Ford MIS
Async Bellman-Ford – worst case (sketch, cf. Lynch §15.4)
Sketch for
• k = 3 (can be any number) • N=2k+2=8nodes
• M=3k+1=10edges
Costs: as indicated or 0 (default)
Initiator: left-most node
Green: fast link; Red: slow link; Black: slow & critical if FIFO
22 21 20
23/34
DFS ClassicalDFS CidonDFS§1 CidonDFS§2 Bellman-Ford MIS
Async Bellman-Ford – worst case (cont)
22 21 20
22 21 20
22 21 20
22 21 20
1112
1102
1012
1002
22 21 20
22 21 20
22 21 20
22 21 20
0112
0102
0012
0002
Dotted blue arrows : messages still in transit
1:1
Shapes of the shortest-so-far cost paths ←→ base 2 num√bers Exponential message complexity ≥ 2k = 2(N−2)/2 = Ω( 2N) Exponential time complexity if FIFO – congestion on black edge
24/34
DFS ClassicalDFS CidonDFS§1 CidonDFS§2 Bellman-Ford MIS
Async Bellman-Ford – worst case
• How to explain the time complexity?
• Time complexity without FIFO pileups = O(|V|)?
• Time complexity with FIFO pileups = exponential?
• If the last edge, before the rightmost node, is slow enough, say t, then all 2k messages can pile-up in this segment
• If we consider congestion, then these piled-up messages can be successively delivered at t intervals
• Total delivery time on the last edge: 2kt = 2O(N) time units, i.e. exponential time complexity [Lynch §15.4]
• This argument fails, if we do NOT consider FIFO congestion, because then even the slowest message will not be affected by the others, and will only take a maximum 1 time unit.
25/34
DFS ClassicalDFS CidonDFS§1 CidonDFS§2 Bellman-Ford MIS
Echo and Bellman-Ford – complexity highlights
• Sync Echo (aka Sync BFS) : BFS ST, no link changes, fast • Async Echo : arbitrary ST, no link changes, but not so fast • Sync BF : shortest paths ST, many link changes, not so fast • Async BF : shortest paths ST, exponential link changes
• if FIFO: worst case exponential time
• Why the worst case argument does NOT apply to Sync BF?
• emulating slow links by extra edges exponentially increases V !
• the formula is still exponential on k, but not anymore on N = exp(k)!
22 21 20
26/34
DFS ClassicalDFS CidonDFS§1 CidonDFS§2 Bellman-Ford MIS
Maximal Independent Set
• Independent = no two neighbours
• Maximal = cannot be extended
• Maximal is not necessarily largest
• Here we assume that nodes do not have IDs
• Impossible to solve with conventional means in an absolutely symmetric case!
• Luby’s algorithm can still break the ties with randomization techniques
28/34
DFS ClassicalDFS CidonDFS§1 CidonDFS§2 Bellman-Ford MIS
Luby’s algorithm
• Sync algorithm, which works in stages, each consisting of the following 3 rounds
1 Each processes chooses a new random value and sends it to its neighbours. Processes that have values greater than all their neighbours become winners
2 Winners notify their neighbours. Processes that receive such messages from their neighbours become losers
3 Losers notify their neighbours. All processes make a conceptual reshaping of the graph. Both winners and losers are conceptually disconnected from further participation. Remaining nodes are still competing and will regenerate new random values in their next stage!
29/34
DFS ClassicalDFS CidonDFS§1 CidonDFS§2 Bellman-Ford MIS
Luby’s algorithm
• Luby’s algorithm will stop with probability 1, expected O(log n) rounds -– proof quite hard
• The random values are best chosen in the range 1, 2, …N4, will be likely distinct (but this is not necessary)
• Our diagrams will be sketched only, we won’t detail all these rounds individually
30/34
DFS ClassicalDFS CidonDFS§1 CidonDFS§2 Bellman-Ford MIS
MIS – Example
• One possible solution, formed by {5, 2}
• Another solution could be {5, 1, 3} (which is larger)
31/34
DFS ClassicalDFS CidonDFS§1 CidonDFS§2 Bellman-Ford MIS
Luby – Stage #1, Round #1
• green = hopeful
• blue = loser
• red = winner
• we only show most relevant messages
32/34
DFS ClassicalDFS CidonDFS§1 CidonDFS§2 Bellman-Ford MIS
Luby – Stage #1, Rounds #2
• one winner so far: 5
• losers: 4 and 5
• losers notify their neighbours
• winners and losers are conceptually disconnected
• still competing: 1, 2 and 3
33/34
DFS ClassicalDFS CidonDFS§1 CidonDFS§2 Bellman-Ford MIS
Luby – Stage #2
• a new winner: 2
• winners’ neighbours,
here 4 and 5, lose
• new losers: 1 and 3
• the end
34/34