index.md (6554B)
1 +++ 2 title = 'Trees & deadlock' 3 +++ 4 5 # Wave algorithms 6 decide event: special internal event 7 8 In wave algorithm, each computation (wave) satisfies: 9 - termination: it's finite 10 - decision: contains one or more decide events 11 - dependence: for each decide event e and process p, f is before e for event f at p 12 13 ## Traversal algorithms for spanning trees 14 Centralised wave algorithms. 15 16 Initiator sends around token: 17 - in each computation, token first visits all processes 18 - token returns to initiator who performs decide event 19 20 Build spanning tree: 21 - initiator is root 22 - each noninitiator has as parent the neighbor from which it first received token 23 24 ## Spanning trees 25 ### Tarry's algorithm 26 Undirected network. 27 28 restrictions: 29 - process never forwards token through same channel twice 30 - noninitiator only forwards token to its parent when there's no other option 31 - to get depth-first search: when process receives token, it immediately sends back through same channel, if allowed by other restrictions 32 - to prevent transmission through frond edge: visited processes are included in token, token isn't forward to processes in this list (unless back to parent) 33 - but gives you message complexity 2·N - 2 (for N processes) and time complexity ≤ 2·N - 2 time units 34 - each tree edge carries 2 tokens 35 36 token travels through each channel both ways, end up at initiator 37 38 the parent-child relation is reversal of solid arrows. 39 - tree edges are solid 40 - frond edges (not part of spanning tree) are dashed 41 42 complexity: 43 - message: 2·E messages 44 - time: ≤ 2·E time units 45 46 ### Awebuch's algorithm 47 - process holding token for first time informs its neighbours, except parent and process to which it forwards 48 - token only forwarded when all neighbours acknowledged reception 49 - token only forward to processes not yet visited (except when back to parent) 50 51 complexity: 52 - message: ≤ 4·E messages 53 - frond edge carries 2 info and 2 ack 54 - tree edge carries 2 tokens and maybe 1 info/ack pair 55 - time: ≤ 4·N - 2 time units 56 - tree edge carries 2 tokens 57 - each process waits at most 2 time units for acks to return 58 59 ### Cidon's algorithm 60 Awerbuch's but without acks. 61 - token forwarded without delay 62 - each process records to which process it forwarded the token last 63 - if p receives token from process to which it didn't last forward, then p marks the corresponding edge as frond and dismisses the token 64 - if q receives info message from p to which it last forwarded, then q marks corresponding edge as frond and continues forwarding 65 66 complexity: 67 - message: ≤ 4·E messages 68 - each channel carries max 2 info messages and 2 tokens 69 - time: ≤ 2·N - 2 time units 70 - tree edge carries 2 tokens 71 - at least once per time unit, token forwarded through tree edge 72 73 ## Tree algorithms 74 Decentralised wave algorithm for undirected acyclic networks. 75 76 Local algorithm at process p 77 - p waits until received messages from all neighbours except one, who becomes its parent 78 - sends message to that parent 79 - if p receives message from its parent, it decides and sends decision to its neighbours except parent 80 - if p receives decision from parent, it passes on to its other neighbors 81 82 Always two neighboring processes decide. 83 84 ## Echo algorithm 85 Centralised wave algorithm for undirected networks. 86 - initiator sends message to all neighbours 87 - when noninitiator receives message for first time, make sender its parent and sends message to all neighbors except parent 88 - when noninitiator has received message from al neighbors, sends message to its parent 89 - when initiator received message from all neighbors, it decides 90 91 Complexity: 92 - message: 2·E 93 94 To determine largest process ID in network: 95 - each process runs echo algorithm tagged by its ID 96 - processes only participate in largest wave they've seen so far 97 - the one that decides is the one with the largest ID 98 99 # Deadlocks 100 Deadlock if cycle of processes waiting until 101 - communication deadlock: another process on cycle sends some input 102 - resource deadlock: resources held by other processes on cycle are released 103 104 Both captured by N-out-of-M model: process can wait for N grants out of M requests. 105 106 ## Wait-for graph 107 - Non blocked process can issue request to M other processes and becomes blocked until N of them granted. 108 - Then it becomes unblocked and cancels remaining M-N requests 109 - Only non-blocked processes can grant request 110 111 Directed wait-for graph capturing these dependencies: 112 - edge p→q if p sent request to q not yet canceled by p or granted by q 113 114  115 116 During execution of basic algorithm, snapshot is taken of graph. 117 Static analysis may reveal deadlocks 118 - non-blocked nodes can grant requests 119 - when request granted, corresponding edge removed 120 - when N-out-of-M request received N grants, requester becomes unblocked (remaining M-N outgoing edges canceled) 121 - when no more grants possible, nodes remaining blocked are deadlocked in this snapshot 122 123 ## Bracha-Toueg deadlock detection algorithm 124 Given undirected network and basic algorithm 125 - process suspecting it's deadlocked initiates Lai-Yang snapshot 126 - each node takes local snapshot of 127 - requests it sent or received not yet granted/canceled 128 - grant and cancel messages in edges 129 - each node computes 130 - out: nodes it sent a request to (not granted) 131 - in: nodes it received a request from (not canceled) 132 - every node u keeps track of number of grants u requires to become unblocked 133 - when u receives grant message, decrements counter 134 - if counter becomes zero, sends grant messages to all nodes in 'in' set 135 - if after termination of deadlock detection run, counter > 0 at initiator, then it's deadlocked in basic algorithm 136 137 Initially notified = false and free = false at all nodes 138 - initiator starts deadlock detection run by executing Notify: 139 1. notified(node) = true 140 2. for all w ∈ out_set(node) send notify to w 141 3. if requests(node) == 0 then Grant(node) 142 4. for all w ∈ out_set(node) await done from w 143 - grant: 144 1. free(node) = true 145 2. for all w ∈ in_set(node) send grant to w 146 3. for all w ∈ in_set(node) await ack from w 147 - let u receive notify: 148 - if notified(u) == false, then u executes Notify(u) 149 - u sends back done 150 - let u receive grant: 151 - if requests(u) > 0, then decrement requests(u) 152 - if requests(u) becomes 0, then execute Grant(u) 153 - u send back ack 154 - when initiator received done from all nodes in its out set, checks value of its free field 155 - if still false, initiator concludes it's deadlocked