anonymous-networks.md (4497B)
1 +++ 2 title = 'Anonymous networks' 3 +++ 4 # Anonymous networks 5 Anonymous network: processes and channels have no unique ID 6 7 Many reasons: 8 - transmitting/storing is too expensive 9 - they don't want to reveal ID 10 - they don't have unique hardware ID 11 12 ## Election 13 There is no election algorithm for anon rings that always terminates. 14 15 An execution is fair if each event that's applicable in infinitely many configurations occurs infinitely often in computation. 16 - each election algorithm for anon rings has fair infinite execution 17 18 Probabilistic algorithm: process flips a coin and performs event based on the outcome 19 - Las Vegas: if probability that terminates is greater than zero & all terminal configurations are correct 20 - Monte Carlo: always terminates, probability that a terminal configuration is correct is greater than zero 21 22 ### Itai-Rodeh algorithm 23 Given anonymous directed ring. 24 25 Adopt Chang-Roberts algorithm: 26 - each initiator sends out ID, random from {1...N} 27 - largest ID is only one making a round trip 28 - each message supplied with hop count 29 - message that arrives at its source has hop count N 30 - if several processes select same ID, they start new election round, with higher round number 31 32 Steps: 33 - in round 0, initiators active, noninitiators passive 34 - let p be active. at start of election round n: 35 - p randomly selects id(p) 36 - and sends [n, id(p), 1, false] = [round, ID, num hops, bool has encountered another process with same ID] 37 - if p receives: 38 - n' > n, or n' = n and i > id(p) 39 - then p becomes passive and sends (n', i, h+1, b) 40 - n' < n, or n' = n and i < id(p) 41 - then p dismisses the message 42 - hops < N 43 - then p sends (n, id(p), hops+1, true) 44 - bool true, hops N 45 - then p proceeds to round n + 1 46 - bool false, hops N 47 - then p becomess the leader 48 - passive processes pass on messages, increasing hop count by 1 49 50 Complexity: 51 - average-case message: O(N·log N) 52 53 ### Election in arbitrary anon networks 54 Echo algorithm with extinction, with random selection of IDs, can be used for election in anon undirected networks, in which *all processes know network size*. 55 56 In round 0, initiators active, noninitiators passive. 57 58 Each active process selects random ID, and starts a wave, tagged with its ID and round number 0. 59 60 Let process p in wave i of round n be hit by wave j of round n': 61 - if n' > n, or n' = n and j > i 62 - then p adopts wave j of round n', and treats message according to echo algorithm 63 - if n' < n, or n' = n and j < i 64 - then p dismisses the message 65 - if n' = n and j = i 66 - then p treats the message according to echo algorithm 67 68 Each message sent upwards in constructed tree reports size of it subtree. 69 All other messages report 0. 70 71 When process *decides*, it computes size of constructed tree. 72 - if tree covers network, it becomes the leader 73 - else, selects new ID, initiates new wave in the next round 74 75 No Las Vegas algorithm to compute size of anon ring (⇒ no Las Vegas algorithm for election in anon ring *if processes don't know ring size*) 76 77 ### Itai-Rodeh ring size algorithm 78 Each process p has estimate est(p) of ring size. 79 Initially est(p) = 2. 80 81 p initiates estimate round at start of algorithm, and at each update of est(p). 82 83 Each round, p selects random id(p) in {1..R}, sends [est(p), id(p), 1], and waits for message [est, id, h] 84 - est < est(p) 85 - then p dismisses message 86 - est > est(p) 87 - h < est 88 - then p sends [est, id, h+1], and est(p) = est 89 - h = est 90 - then est(p) = est + 1 91 - est = est(p) 92 - h < est 93 - then p ends [est, id, h+1] 94 - h = est and id ≠ id(p) 95 - then est(p) = est + 1 96 - h = est and id = id(p) 97 - then p dismisses the message 98 99 Complexity: 100 - worst-case message: O(N³) 101 102 ### IEEE 1394 election algorithm 103 IEEE 1394 standard is serial multimedia bus, connecting digital devices which can be added/removed dynamically. 104 Anonymous because transmitting/storing IDs is too expensive. 105 Network size is unknown to process. 106 Tree algorithm for undirected acyclic networks is used. 107 Networks that contain cycle give a timeout. 108 109 - when process has one possible parent, it sends parent request to this neighbor 110 - if accepted, an ack is sent back 111 - last two parentless processes can send parent requests to each other simultaneously ("root contention") 112 - each of them randomly decides to either immediately send another request, or wait some time before request