6.852 Lecture 3●Algorithms in general synchronous networks (continued)–breadth-first search–broadcast, convergecast–shortest paths–minimum-weight spanning treeLast lecture●Lower bound for comparison-based leader election in a ring●Leader election in general synchronous networks–flooding–reducing message complexity–simulationsBreadth-first search●Assume–strongly connected digraph, UIDs–no knowledge of size, diameter of network–distinguished source node i0●Required: breadth-first spanning tree–spanning: contains every node–breadth-first: node at distance d from i0 appears at depth d in tree–output: parent of each node (except i0)Breadth-first search154326Breadth-first search154326Breadth-first search●“Mark” nodes as they get incorporated into tree–initially only i0 is marked–round 1: i0 sends “search” to out-nbrs–every round: unmarked nodes that receive “search”●marks self●designates one process that sent “search” as parent●send “search” to out-nbrs next roundBreadth-first search●“Mark” nodes as they get incorporated into tree–initially only i0 is marked–round 1: i0 sends “search” to out-nbrs–every round: unmarked nodes that receive “search”●marks self●designates one process that sent “search” as parent●send “search” to out-nbrs next roundWhat state variables do we need?Breadth-first search154326Round 1 (start)Breadth-first search154326Round 1 (msgs)sBreadth-first search154326Round 1 (trans)sBreadth-first search154326Round 2 (start)Breadth-first search154326Round 2 (msgs)ss??Breadth-first search154326Round 2 (trans)ssBreadth-first search154326Round 3 (start)Breadth-first search154326Round 3 (msgs)sssssBreadth-first search154326Round 3 (trans)sssssBreadth-first search154326Round 4 (start)Breadth-first search154326Round 4 (msgs)sssBreadth-first search154326Round 4 (trans)sssBreadth-first search154326Round 5 (start)Breadth-first search154326Round 5 (msgs)Breadth-first search154326Round 5 (trans)Breadth-first search●“Mark” nodes as they get incorporated into tree–initially only i0 is marked–round 1: i0 sends “search” to out-nbrs–every round: unmarked nodes that receive “search”●marks self●designates one process that sent “search” as parent●send “search” to out-nbrs next round–need flag to keep track of when to send●Complexity: time = diameter+1; msg = |E|Breadth-first search●Child pointers?–easy with bidirectional communication–what if not?●message bit complexity●Termination?–with bidirectional communication?●“convergecast”–with unidirectional communication?Applications of BFS●Message broadcast–“piggyback” (watch message bit complexity)–complexity: time = O(diameter); msg = O(n)●Global computation–sum, or any accumulation: convergecast–complexity: time = O(diameter); msg = O(n)●Leader election (without knowing diameter)–everyone start BFS, finds max UID–complexity: time = O(diam); msg = O(n |E|) or O( diam |E|)●Compute diameter–all do BFS; convergecast to find height of each BFS tree; convergecast to find max of all heightsShortest paths●Generalization of BFS–assume weighted digraph, UIDs, i0●weights represent some (communication) cost (known)●all nodes know n (need for termination!)–require shortest-paths tree rooted at i0●paths should have min weight●output parent, “distance” from root (by weight)Shortest paths1543267864392511101Shortest paths15432630786439251110110629Shortest paths●Bellman-Ford (adapted from sequential alg)–“relaxation algorithm”–nodes maintain: dist, parent (best so far), round#●initially i0 has dist 0, all other ∞; parents all null–each round all nodes:●send dist to all out-nbrs●relaxation: compute new dist = min(dist, minj(dj+wji))–update parent if dist changes–stop after n-1 roundsShortest paths154326∞07864392511101∞∞∞∞Round 1 (start)Shortest paths154326∞07864392511101∞∞∞∞Round 1 (msgs)∞∞∞∞∞∞∞∞∞00Shortest paths154326∞0786439251110111∞2∞Round 1 (trans)∞∞∞∞∞∞∞∞∞00Shortest paths154326∞0786439251110111∞2∞Round 2 (start)Shortest paths154326∞0786439251110111∞2∞Round 2 (msgs)∞∞2∞2∞∞∞1100Shortest paths154326307864392511101116219Round 2 (trans)∞∞2∞2∞∞∞1100Shortest paths154326307864392511101116219Round 3 (start)Shortest paths154326307864392511101116219Round 3 (msgs)6623233191100Shortest paths15432630786439251110110629Round 3 (trans)6623233191100Shortest paths15432630786439251110110629Round 4 (start)Shortest paths15432630786439251110110629Round 4 (msgs)662323391000Shortest paths15432630786439251110110629Round 4 (trans)662323391000Shortest paths15432630786439251110110629Round 5 (start)Shortest paths15432630786439251110110629Round 5 (msgs)662323391000Shortest paths15432630786439251110110629Round 5 (trans)662323391000Shortest paths15432630786439251110110629End configurationShortest paths●Complexity: time = n-1; msg = (n-1) |E|–can we reduce time complexity? diameter?–what about message complexity?●Proof?Shortest paths●Complexity: time = n-1; msg = (n-1) |E|–can we reduce time complexity? diameter?–what about message complexity?●Proof?●Correctness condition?Shortest paths●Complexity: time = n-1; msg = (n-1) |E|–can we reduce time complexity? diameter?–what about message complexity?●After round n-1, for each process i–disti = shortest distance from i0–parenti = predecessor on shortest path from i0●Proof?Shortest paths●Invariant: after r rounds:–every process i has its dist (& parent) corresp to shortest path from i0 to i with at most r edges●Proof (by induction):–base case: trivial for r = 0–inductive step:●fix i, let p be pred on shortest path from i0 with ≤ r edges●by ind hyp, after round r-1, distp and parentp corresp to shortest path from i0 to p with at most r-1 edges●disti(r) = distp(r-1) + wpi correct by “optimal substructure”Minimum spanning tree●Another classic problem (lots of seq algs)●Assume–weighted undirected graph (bidirectional comm)●all weights nonnegative–processes have UIDs–know weights of incident edges, bound on n●Require–each process knows which incident edge is in MSTMinimum spanning tree●Graph theory definitions (for undirected graphs)–tree: connected acyclic graph–spanning: property of a subgraph that it includes all nodes of a graph–forest: an acyclic