DISTRIBUTED COMPUTING
COMP 4001
Evangelos Kranakis November 15, 2020
Solve the problems below. Your answers do not have to be long, but they should be complete, precise, concise and clear. Write the solutions on your own and acknowledge your sources in case you used “library” material. Look in the course web page on how to avoid plagiarism and for submission details (where/when/how). Exercises marked with (⋆) are usually more challeng- ing. NB: some of the exercises may require material that will be covered in forthcoming lectures while others marked with (⋆) may involve additional material not covered in class. It is preferred that you type your work using your favourite software package but you submit only in pdf. Two excellent and free packages are LATEX (for typesetting mathematics) and Ipe (for drawing pictures).
Assignment C
1 [10 pts]
A sensor of range r > 0 is modelled as an interval [x − r, x + r] centered at a point x, where x ∈ [0,1]. Two sensors s1,s2 are dropped in the unit interval [0, 1]: one occupies position x1 and the other position x2 such that 0 ≤ x1, x2 ≤ 1. We want to move the sensors (if needed) to ensure that every point in the unit interval is within the range of a sensor (i.e., the interval is covered by the two sensors).
1. [3 pts] Give an optimal algorithm to accomplish this coverage task which minimizes the sum of the movements of the two sensors (as a
1
2
2.
function of x1, x2) assuming that r = 1/2.
[7 pts] (⋆) Now suppose the two sensors are dropped at random in the unit interval. What is the expected sum of the movements of the two sensors for the algorithm you designed?
[10 pts]
Consider the flooding algorithm in an arbitrary network G = (V, E): 1) Each node acts as both a transmitter and a receiver, and 2) Each node tries to forward every message to every one of its neighbors except the source node.
1. Formulate the algorithm in pseudo-code starting from a given node.
2. Prove that your algorithm is correct in that it terminates within finite time, and all entities will receive the information held by the initiator.
3. Determine an upper bound (formula) on the number of message trans- missions required by the algorithm (Your answer should be expressed in terms of parameters: number n of vertices, number m of edges).
Hint: Use handshake theorem in graph theory, namely the formula that the sum of the degrees of all the nodes is equal to 2|E|.
3 [10 pts]
If all edges of a graph G have distinct weights, then there is exactly one MST for G.
4 [10 pts] (⋆)
A forgetful (i.e., has no memory) mobile robot hops on the nodes of a n-node complete network. If the robot is at a given node it moves to any of the other n − 1 nodes with the same probability. Next time it moves it does not remember its previous move or position. Let N = # of steps until all nodes are visited. Let Xi = # of steps required to visit one more node when i nodes have already been visited, i = 0,1,2,3,…,n−1. Note: X0 = X1 = 1.
2
1. [4 pts] Compute E[Xi] for each i.
2. [2pts]ShowthatN=X0+X1+X2+X3+···+Xn−1.
3. [4 pts] Use the previous formula and pass to the expectation to con- clude E[N] = nlogn
5 [10 pts]
A robot r can race at max speed 1 and wants to catch a bandit B racing at max speed c such that c < 1; the bandit is racing at unknown–to the robot–but same direction during the chase.
Br
The robot does not know neither the starting position of the bandit (could be left or right of r) nor its direction of movement. Assume the initial distance of the robot and the bandit is D. Give an algorithm for catching the bandit assuming the robot knows the initial distance D and analyze how long it takes your algorithm to catch the bandit. The better the algorithm the better the mark. (Assume that c is known to the robots.)
6 [10 pts] (⋆)
Consider a set of points in the plane. Form n sets A1, A2, . . . , An on the plane
each of which has k points.
The sets are arbitrary and may share points. Assume that n < 2k. Show that If n < 2k then it is possible to color each point red or blue in such a way that every set Ai has both colors. Hint: Color each of the n points independently choosing red or blue with equal probability and use the probabilistic method discussed in the traversals lecture..
3
7 [10 pts]
Two robots R1,Rc are initially located at the center of a unit disk and can move with speeds 1 and c, respectively, where c > 1. Consider the following Joint Exploration Algorithm (JEA). Both robots start at the same time and go together to a point P on the perimeter and traverse the perimeter in opposite direction. (Assume the exit is at a point E at distance d from P–measured along the arc.)
8
1. 2. 3. 4.
At what time does robot R1 reach the exit?
At what time does robot Rc reach the exit?
What is the evacuation time of the algorithm?
Show that if c > 2π + 1 then the slow robot R1 can never reach the exit before the fast robot Rc does.
[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 for evacuation and analyze its competitive ratio. (Provide the pseudo-code of your algorithms.)
4