Blog

CS 9668/4438 Internet Algorithmics
Assignment 4: Graduate and Undergraduate students
Due date: November 23
1. Consider a synchronous distributed system in which n processors are connected in a com-
plete communication network (so there is an edge between every pair of processors). Initially
each processor pi in the system has an integer value vi. Consider the following synchronous
distributed algorithm for the consensus problem with processor failures:
Algorithm consensus(id, r, f)
Input: Processor’s id, number r of rounds, and maximum number f of processors
that can fail
Output: Value selected by the processor.
mssg hvidi //vid is the value initially selected by this processor
rounds 0
vselected vid
loop {
if mssg 6= null then send mssg to all neighbours.
mssg null
for every message hvi received do if v < vselected then vselected v rounds rounds+1 if rounds = r then return vselected else mssg hvselectedi } Assume that while executing this algorithm processors might exhibit receiving failures. This means that during a round of the algorithm a processor will first send all its messages and then while receiving messages from other processors the bu er where these messages are being stored is corrupted, so the processor might not receive all the messages that the other processors sent it during that round. Receiving failures a ect a processor for one round only, so in the following rounds the processor might or might not experience additional receiving failures. For example, consider a complete network with 3 processors p1, p2, p3 that execute the above algorithm. Assume that during the first round p1 exhibits receiving failures that cause it to only receive a message from p3 but no message from p2. If p2 and p3 experiment no failures, then both of them will receive in the first round the 3 values selected by the 3 processors. In the second round if no processor fails, then all of them will receive all the values. (i) (10 marks) If the above algorithm is invoked on each processor as consensus(id, 1, 3), i.e. if up to 3 processors can have receiving failures and the algorithm performs only one iteration of the loop, what is the maximum number of di erent values that could be selected by all the processors at the end of the execution of the algorithm You need to explain your answer. For example, consider a system with four processors, p1, p2, p3, and p4, where each processor pi selects a value vi. If processor p1 receives v2 and v3 and then fails to receive v4, and processor p2 receives v1 and v3 and then fails to receive v4, then at the end of the execution of the algorithm p1 and p2 will select the value min{v1, v2, v3} and p3 and p4 will select min{v1, v2, v3, v4} and so if v4 < v3, v2, v1 then the processors will select 2 di erent values. (ii) (20 marks) In the quarter-consensus problem it is required that at least one fourth of the processors select the same value. Prove that invoking algorithm consensus(id, f4 + 1, f) on all processors solves the quarter-consensus problem when at most f processors can exhibit receiving failures. You can assume that the number f of processors that can fail is a multiple of 4. 2. (15 marks) Consider the consensus problem on a synchronous system with n processors in which each processor pi selects a value vi from the set U = {u1, u2, u3}. All processors know that the only valid selections made by other processors must be values from set U . Assume that processors can experience Byzantine failures. The following algorithm is used to solve the consensus problem: Algorithm consensus2(id, r, U) Input: Processor’s id, number r of rounds, and set U of possible values chosen by the processors Output: Value selected by the processor. mssg hvidi //vid is the value initially selected by this processor rounds 0 vselected vid loop { if mssg 6= null then send mssg to all neighbours. mssg null for every message hvi received do if v 2 U and v < vselected then vselected v rounds rounds+1 if rounds = r then return vselected else mssg hvselectedi } Suppose that one processor exhibits Byzantine failures. What is the minimum number of rounds that the above algorithm needs to execute to ensure that all the non-failing processors will select the same value You must explain your answer. 3. (i) (20 marks) In the lectures we studied the use of consistent hashing in Chord for finding keys in a peer-to-peer network. Assume that each processor pi has a finger table that allows it to store its own address plus the addresses of two other processors. Furthermore assume that the number of processors in the P2P network is 10000 and that the size of the ring of identifiers is 106. Which addresses must be stored in the finger table of each processor pi so as to minimize the number of messages needed to find a key (or to decide that a key is not stored in the system), while ensuring that every key can be found You must explain your answer. Your answer must be in the form fingerTable[0] = successor (...), fingerTable[1] = successor (...). Assume that hp(proc id) is the hash function used to map processor ids to ring identifiers and that this hash function maps processor ids uniformly across the entire ring. (ii) (5 marks) Show that with your choice of fingers any key stored in the system can be found and compute the maximum number of messages that need to be sent to either find a key or to determine that the key is not stored in the system. 4. (i) (30 marks) In the lectures we described the algorithm that is used by Chord to either find the document with a given key or to determine that such document is not stored in the system assuming that the processor hash function hp(id) maps each processor to a unique ring identifier. Assume that two or more processors pi1, pi2, . . . , pi` are mapped to the same ring identifier by the processor hash function hp(id). In such a case the keys that are mapped to the segment of the ring between the ring identifier of these processors and that of their predecessor are distributed evenly among the processors that caused the collision. For simplicity assume that none of the other processors in the system will have the addresses of processors pi2, . . . , pi` in their finger tables, but the address of processor pi1 can appear in those processor’s finger tables. The first finger of pi1 is pi2, the first finger of pi2 is pi3, and so on; the first finger of pi` is the successor of (hp(pi`) + 1) Complete the provided Java class Find.java by writing a synchronous distributed algorithm to find a given set of keys in a Chord P2P system. Your algorithm must use finger tables to find the keys. To find a key your algorithm cannot simply send messages to the successors until the key is found. The finger table must be searched to find the processor closest to the position of the desired key; a message must then be sent to such a processor (please review the lectures on Chord). You will be given code to fill-out the finger tables and to compute the hash functions hp(id) and hk(key); you only need to write code to search for the keys To test your implementation we will use the simulator for distributed algorithms. For simplicity we will assume that only one processor P needs to find keys; upon termination the algorithm for this processor must return a string of the form "k1 : p1 k2 : p2 · · · kr : pr" where k1, k2, . . . , kr are the keys that processor P needs to find and pi is either the processor storing key ki or ”not found”, for each i = 1, 2, . . . . , r. Before terminating, processor P will send an END message to its successor. An END message will pass from each node that receives it to its successor to ensure that all processors receive it. Processors other than P upon termination will return an empty string "". Since the simulator was not originally designed to simulate peer-to-peer systems, in the network configuration file we will use the DataKeys command to specify (a) the keys to store in the processors (these are negative numbers), (b) the keys that the processor P needs to find (these are positive numbers smaller than 1000), and (c) the processor addresses in the finger table (these are positive numbers larger than 1000). To help you out, you are provided with two Java programs. One program is called FindSim- pler.java, this is a search algorithm that does not use the finger tables, but to find keys it only sends messages to the successors. Study the code to learn how to determine whether a processor has keys that it needs to find. A sample configuration file for this program called configFindSimpler.txt is also provided. The second Java program is called FindFingerTable.java that shows how to read the configura- tion file to construct the processors finger tables. A sample configuration file for this program is configFingerTable.txt. Two sample configuration files are also provided for you to test your implementation of the Find.java class: netPeer1.txt and netPeer2.txt. If you cannot write a program in Java, you will be allowed to submit a solution in pseudocode. However, you are strongly encouraged to write your algorithm in Java.