DISTRIBUTED COMPUTING

Q1 [10 pts] What is the competitive ratio of the zig-zag linear search algorithm for one robot when the expansion factor is some fixed value a > 1. Give the “formal” argument and explicit formula as in the lecture (Recall that in class we used the expansion factor a = 2.) Q2 [10 pts] What are the competitive ratios for two robot evacuation when the exit is on the perimeter of a disk of unit radius (position unknown to the robots) and the robots start co-located at the center of the disk for the following two algorithms? (The communication model is wireless.) 1. In the first algorithm, the robots start at the center and go in antipodal positions on the perimeter. 2. In the second algorithm, the robots 1) go together to the perimeter, 2) they go in opposite direction on the perimeter, 3) and continue until they meet on the perimeter again, 4) they go together to the exit (note that one of the robots must have found the exit). (Provide the pseudo-code of your algorithms and indicate with pictures the worst-case behaviour.) Q3 [10 pts] Consider linear search for two co-operating robots starting at the origin at the same time. Assume the robots can communicate wirelessly and that one robot r1 can move with speed 1 and the other rv with speed v > 1. Give a linear search algorithm and analyze its competitive ratio. (Provide the pseudo-code of your algorithms.) Q4 [10 pts] Give an algorithm for three robots (all three moving with speed 1) to patrol a star graph with five edges (each of length 1) and provide the patrolling time. The robots start together at the center of the star but can otherwise move independently. The better the patrolling time the better the mark. Q5 [10 pts] Consider networks of n nodes labeled 1, 2, . . . , n. In each of the graphs below describe the triple N = (V, P, p), of vertices V , vertex-port pairs P, and port function p that define the networks. 1. Unidirectional Ring 2. Bidirectional Ring 3. Complete binary tree. Q6 [10 pts] Prove that the three graphs depicted below are isomorphic by exhibiting the one-to-one correspondence of vertices. You can show this by drawing the correspondence.