本次加拿大代写是关于对分布式计算相关的一个Assignment

1 [10 pts]

The local leader election algorithm requires that the nodes compute the bi-nary representation of their identifiers.

1. [8 pts] Give an efficient algorithm to compute the binary representation of an integer n. Write the pseudocode and prove its correctness.

2. [2 pts] Computing the binary representation should count as part of processing for the leader election algorithm. What are the running and

processing times of the local coloring algorithm if the IDs are in the range 1 to n? Explain and prove your claims.

2 [10 pts]

A graph which can be represented in the plane with non-crossing edges is called planar (e.g., trees, rings, square grids, etc). Give a distributed algo-rithm to 6-color a planar graph.1 Assume the graph has n nodes and m edges. Your proof should be based on the following steps.

1. [3 pts] Assume Euler’s Inequality2 which states that if n ≥ 3 then m ≤ 3n − 6. Use this and the handshake theorem to show that in any planar graph there is always a vertex of degree at most 5.

2. [7 pts] Use Part 1 above to give distributed coloring algorithm. Hint: Make use of the vertices of degree at most 5.

3 [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 function of x1,x2) assuming that r = 1/2.

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?

1The celebrated four color theorem states that planar graphs are 4-colorable. 2You do not have to prove this inequality

4 [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. [2 pts] Formulate the algorithm in pseudo-code starting from a given node.

2. [4 pts] 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. [4 pts] Determine an upper bound (formula) on the number of mes-sage transmissions 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|.

5 [10 pts]

Consider a complete binary rooted tree of n nodes. Each leaf v holds a certain integer value xv ≥ 0. Give an efficient distributed algorithms so that all the nodes of the tree learn the correct value of max{xv : v is a leaf}.

1. [2 pts] Give a description of the algorithm, the pseudocode, and prove correctness.

2. [2 pts] Analyze the number of rounds.

3. [1 pts] Analyze the total number of messages.

4. [1 pts] Analyze the total number of bits.

5. [4 pts] Extend the algorithm to arbitrary rooted trees.

6 [10 pts]

Show that if all edges of a graph G have pairwise distinct weights, then there is exactly one MST for G.

7 [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.

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.)

8 [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.)