election-algorithms.md (8332B)
1 +++ 2 title = 'Election algorithms & minimum spanning trees' 3 +++ 4 # Election algorithms 5 Often leader process needed to coordinate distributed task. 6 In election algorithm, each computation terminates in configuration where one process is leader. 7 8 Assumptions: 9 - decentralised algorithm, initializers are non-empty set of processes 10 - all processes have same local algorithms 11 - process IDs are unique, from totally ordered set 12 13 ## Chang-Roberts algorithm 14 directed ring 15 16 Initially only initiators active, send message with their ID 17 18 Let active process p receive message q 19 - if q < p, p dismisses the message 20 - if q > p, becomes passive, and passes on message 21 - if q = p, p becomes leader 22 23 Passive processes pass on messages. 24 25 Complexity: 26 - worst-case message: O(N²) 27 - average-case message: O(N·log N) 28 29 ## Franklin's algorithm 30 Undirected ring. 31 32 Each active process p repeatedly compares own ID with IDs of nearest active neighbors on both sides. 33 34 If such a neighbor has larger ID, then p becomes passive. 35 36 Initially, initiators are active, noninitiators passive. 37 38 Each round, active process p 39 - sends its ID to its neighbors on either side 40 - and receives IDs q and r 41 - if max{q,r} < p, then p starts another round 42 - if max{q,r} > p, then p becomes passive 43 - if max{q,r} = p, then p becomes leader 44 45 Complexity: 46 - worst-case message: O(N·log N) 47 48 ## Dolev-Klawe-Rodeh algorithm 49 Directed ring. 50 Comparison of IDs of active process p and its nearest active neighbors q and r is performed at r. 51 52 - if max{q,r} < p, then r changes its ID to p, and sends out p 53 - if max{q,r} > p, then r becomes passive 54 - if max{q,r} = p, then r announces this ID to all processes. 55 56 The process that originally had ID p becomes the leader. 57 58 Since message can overtake another message from earlier round, processes maintain round numbers and attach these to their messages. 59 60 Complexity: 61 - worst-case message: O(N·log N) 62 63 ## Tree election algorithm for acyclic networks 64 Start with wake-up phase, driven by initiators 65 - initially, initiators send wake-up message to all neighbors 66 - when noninitiator receives first wake-up message, it wakes up and sends a wake-up message to all neighbors 67 - when processes has received a wake-up message from all its neighbors, it starts the election phase 68 69 Election phase (local at process p): 70 - p waits until it received IDs from all neighbors except one, which becomes its parent 71 - p computes largest ID maxp among received IDs and its own ID 72 - p sends parent request to its parent, tagged with maxp 73 - if p receives parent request fromits parent, tagged with q, it computes maxp' (the maximum of maxp and q) 74 - next p sends info message to all neighbors except its parent, tagged with maxp' 75 - this info message forwarded through network 76 - process with id maxp' becomes leader 77 78 Complexity: 79 - message: 2.MN - 2 messages (without wake-up phase) 80 81 ## Echo algorithm with extinction 82 Each initiator starts a wave, tagged with its ID 83 84 Noninitiators join the first wave that hits them. 85 86 At any time, each process takes part in at m ost one wave. 87 88 When process p in wave q is hit by wave r: 89 - if q < r, then p changes to wave r, abandoning all earlier messages 90 - if q > r, p continues with wave q, dismissing incoming message 91 - if q = r, then incoming message is treated according to echo algorithm of wave q 92 93 If wave p executes a decide event at p, then p becomes the leader. 94 95 Complexity: 96 - worst-case message: O(N·E) 97 98 # Minimum spanning trees 99 Undirected weighted network. 100 101 Assume different edges have different weights. 102 103 In minimum spanning tree, sum of weights of edges in spanning tree is minimal. 104 105 ## Fragments 106 Let F be a fragment, i.e. a connected subgraph of minimum spanning tree M. 107 108 Let e be lowest-weight outgoing edge of F. 109 Then e is in M. 110 111 ## Kruskal's algorithm 112 Uniprocessor algorithm for computing minimum spanning trees. 113 - initially, each node forms separate fragment 114 - in each step, lowest-weight outgoing edge of fragment is added to spanning tree, joining two fragments 115 116 Also works when edges have same weight, though then minimum spanning tree may not be unique. 117 118 ## Gallager-Humblet-Spira algorithm 119 Undirected weighted network in which different edges have different weights. 120 121 Distributed computation of min spanning tree: 122 - initially, each process forms a separate fragment 123 - processes in fragment F together search for lowest-weight outgoing edge ef 124 - when ef has been found, fragment at other end is asked to collaborate in a merge 125 126 Complexity: 127 - worst-case message: O(E + N·log N) 128 129 ### Level, name, core edge 130 Each fragment carries unique name fn and level l. 131 132 Its level is maximum number of joins any process in fragment has experienced. 133 134 Neighboring fragments F(fn, l) and F' = (fn', l') can be joined: 135 - l < l' ∧ F →ef F': F ∪ F' = (fn', l') 136 - l = l' ∧ ef = ef': F ∪ F' = (weight ef, l+1) 137 138 Core edge of fragment is last edge that connected two sub-fragments at same level, its end points are core nodes. 139 Name is the weight. 140 141 ### Parameters of process 142 Its state: 143 - sleep (for noninitiators) 144 - find (looking for lowest-weight outgoing edge) 145 - found (reported a lowest-weight outgoing edge to core edge) 146 147 Status of its channels: 148 - basic edge (undecided) 149 - branch edge (in spanning tree) 150 - rejected (not in spanning tree) 151 152 Name and level of its fragment. 153 154 Its parent toward the core edge. 155 156 ### Initialization 157 Noninitiators wake up when they receive a connect or test message. 158 159 Each initiator, and noninitiator after it has woken up 160 - sets its level to 0 161 - sets its lowest-weight edge to branch 162 - sends (connect, 0) into this channel 163 - sets its other channels to basic 164 - sets its state to found 165 166 ### Joining two fragments 167 Let fragments F = (fn, l) and F' = (fn', l') be joined via channel pq 168 - if l < l', then p sent (connect, l) to q 169 - q sends (initiate, fn', l', find/found) to p 170 - F ∪ F' inherits core edge of F' 171 - if l = l', then p and q sent (connect, l) to each otehr 172 - they send (initiate, weight(p,q), l+1, find) to each other 173 - F ∪ F' gets core edge pq 174 175 At reception of (initiate, fn, l, find/found), a process stores fn and l, sets its state to find or found, an adopts sender as its parent 176 - it passes on the message through its other branch edges 177 178 ### Computing lowest-weight outgoing edge 179 In case of (initiate, fn, l, find), p checks in increasing order of weight one of its basic edges pq is outgoing, by sending (test, fn, l) to q. 180 181 While l > level(q), q postpones processing incoming test message. 182 183 Let l ≤ level(q) 184 - if q is in fragment fn, then q replies reject 185 - in this case p and q set pq to rejected 186 - else, q replies accept 187 188 When basic edge accepted, or there are no basic edges left, p stops the search and sets its state to found. 189 190 ### Reporting to core nodes 191 - p waits for all its branch edges, except its parent, to report 192 - p computes minimum λ of (1) these reports and (2) the weight of its lowest-weight outgoing basic edge (or ∞ if no such channel found) 193 - p sends (report, λ) to its parent 194 - if λ < ∞, p stores either branch edge that sent λ, or its basic edge of weight λ 195 196 ### Termination or changeroot at core nodes 197 Core nodes receive reports through all their branch edges, including core edge. 198 - ifemin reported value μ = ∞, the core nodes terminate 199 - if μ < ∞, the core node that received μ first sends changeroot toward lowest-weight outgoing basic edge (the core edge becomes a regular branch edge) 200 201 Ultimately changeroot reaches the process p that reported the lowest-weight outgoing basic edge. 202 203 p sets this channel to branch, and sends (connect, level(p)) into it 204 205 ### Starting join of two fragments 206 If q receives (connect, level(p)) from p, then level(q) ≥ level(p) 207 208 Namely, either level(p) = 0, or q earlier sent accept to p. 209 210 - if level(q) > level(p), then q sets qp to branch and sends (initiate, name(q), level(q), find/found) to p 211 - as long as level(q) = level(p) and qp isn't branch edge, q postpones processing connect message 212 - if level(q) = level(p) and qp is branch edge, then q sends (initiate, weight(qp), level(q) + 1, find) to p, and vice versa 213 - pq becomes core edge 214 215 ### For election 216 By two extra messages at very end, core node with largest ID becomes leader. 217 218 So this induces an election algorithm for general undirected networks. 219 We must impose an order on channels of equal weight.