Exercise 4.4 Greg Hudson ------------ The message alphabet M is the uids. STATES[i] is: U, a uid, initially i's uid MAX-UID, a UID, initially U STATUS, one of {unknown, leader, non-leader}, initially unknown ROUNDS, an integer, initially 0 NEW-INFO-SENDERS, a set of processes, initially {i} MSGS[i] is if ROUNDS < DIAM and NEW-INFO-SENDERS is non-empty then send MAX-UID to all j in OUT-NBRS - NEW-INFO-SENDERS TRANS[i] is ROUNDS := ROUNDS + 1 Let S be the set of uids that arrived from processes in IN-NBRS if S is non-empty then Let V be the maximum of S Let NEW-INFO-SENDERS be the set of senders that sent V if V > MAX_UID MAX-UID = V else NEW-INFO-SENDERS := {} if ROUNDS = DIAM then if MAX-UID = U then STATUS := leader else STATUS := non-leader Note the stylistically questionable fake-out in the first round, where NEW-INFO-SENDERS is set to {i} so that it will be empty, but OUT-NBRS - {i} = OUT-NBRS so it doesn't exclude any messages from being sent on the first round. Proof of correctness: Run this algorithm (call it Flood2) side-by-side with OptFloodMax. I claim the following lemma: * Whenever NEW-INFO is true on a processor i in OptFloodMax, NEW-INFO-SENDERS is non-null in Flood2. * All other variables are always the same between OptFloodMax and Flood2. Proof: At the beginning of the first round, NEW-INFO in each process of OptFloodMax is true and NEW-INFO-SENDERS in each process of Flood2 is non-empty. All other variables are the same. Now assume that the lemma is true at the beginning of a round. At the end of the round, each processor i of Flood2 receives uid messages from each of the same incoming neighbors j as in OptFloodMax unless i was one of the processes which sent the j's MAX-UID to it in the previous round, in which case i's MAX-UID is at least as high as the j's and the message from j would have no effect (either i receives no new information, or the information it does receive is higher than j's uid and j's message is irrelevant in either algorithm). At the end of the round, all the variables other than NEW-INFO and NEW-INFO-SENDERS are the same in Flood2 as in OptFloodMax (since the code is equivalent for the other variables given that the maximum uid received is always the same). NEW-INFO is true in OptFloodMax iff MAX-UID increases, and NEW-INFO-SENDERS is non-empty iff MAX-UID increases. So the lemma holds at the end of the round, and therefore after every round by induction. Since the lemma is true, the algorithm must be correct (since OptFloodMax is correct), since STATUS is always the same in all processes. Exercise 4.8 Greg Hudson ------------ Assume that IN-NBRS[i] = OUT-NBRS[i] for all i (i.e. the graph is undirected). Call the neighbors NBRS[i] for short. The message alphabet M is {search:M', ack, nack} where M' is some message (call it "content-message") to be broadcast. STATES[i] is, for i != 0: U, a uid, initially i's uid MARKED, a boolean, initially false ACKSLEFT, an integer, initially 0 PARENT, an integer, initially U CHILDREN, a set of integers, initially {} SEARCHSENDSET, a set of processes, initially {} NACKSENDSET, a set of processes, initially {} SENDACK, a Boolean, initially false M, a content-message, initially null STATES[0] is like STATES[i] for i != 0 except that: ACKSLEFT initially |NBRS| SEARCHSENDSET is initially NBRS M is initially the content-message to be broadcast MSGS[i] is: Send the message search:M to all processes in SEARCHSENDSET Send the message nack to all processes in NACKSENDSET if SENDACK = true then Send the message ack to PARENT TRANS[i] is: SEARCHSENDSET := {} NACKSENDSET := {} SENDACK := false Let S be the subset of NBRS which sent messages for each j in the subset of S which sent search:MSG do if MARKED = false then MARKED := true PARENT := j M := MSG SEARCHSENDSET := NBRS - S ACKSLEFT := |SEARCHSENDSET| if ACKSLEFT = 0 then SENDACK := true else NACKSENDSET := NACKSENDSET + {j} for each j in the subset of S which sent ack CHILDREN := CHILDREN + {j} for each j in the subset of S which sent ack or nack ACKSLEFT := ACKSLEFT - 1 if ACKSLEFT = 0 then SENDACK := true As in SynchBFS, the search message will propagate to all of the processes; each process which gets a search message for the first time sends it out to all of its neighbors which did not send messages. (It is easy to see that a process which sends a message has already received a search message, since processes only get ack messages when they send out search messages, and only send out search messages after they get their first search message). When a process receives a search message for the first time, it also receives the content-message being broadcast. Each process also maintains a count of the acks and nacks it needs to receive from its children. To avoid deadlock, processes send nacks immediately, but don't send acks until they receive nacks or acks from all of the processes they sent search messages to. Thus, a process will only be waiting for its children in the spanning tree (so deadlock cannot happen), but will delay sending an ack to its parent until it gets messages from all of its children, so process 0 cannot get all of its acks until all of the processes have received search messages. A search message and either an ack or nack message is sent across each edge, so this algorithm uses O(|E|) messages. It takes O(diam) rounds to propagate the search messages to the leaf processes. The leaf processes will receive nack messages in the round immediately following the round they sent out the search messages, and it will take O(diam) rounds for the acks to propagate back to the original processor, so this algorithm takes O(diam) rounds. This algorithm calculates children sets at each processor even though it wasn't required. If you remove that feature, you can have only one kind of ack message, but you still have to send ack messages immediately to processes which aren't your parent. Exercise 4.11 Greg Hudson ------------- Part A: If the graph is undirected, we can use a modification of the leader election algorithm described on page 58: each process initiates a BFS (in parallel with all the others) with acknowledgements from children (e.g. using the algorithm in my solution to exercise 4.8, which makes a children list as well). Then, each process uses a global computation to determine the sum of the function with constant value 1 on all the nodes of the network. This gives the number of nodes on the network. Just like the leader election algorithm (which also involves every node initiating a SynchBFS and a global computation), this algorithm takes time O(diam) and uses O(n|E|) messages (with many of the messages being sent in parallel with other messages, of course, for O(n|E|b) communication bits. If bidirectional communication is not allowed, we can use the same algorithm (broadcasting to get messages to parents instead of sending them directly), but the convergecasts in both SynchBFS with acknowledgements and global computation will be much more expensive and will dominate the time and number of messages taken. In this case, the time taken is O(diam^2), and the number of messages is O(n|E|^2) with many of the messages being sent in parallel, for O(n|E|^2b) communication bits.