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 us- ing your favourite software package but you submit only in pdf.  At the discretion of the TA a 5% bonus will be added if carefully typed and rigor- ously explained. Two excellent and free packages are LATEX (for typesetting mathematics) and Ipe (for drawing pictures).

Assignment 2

1    [10 pts]

Label the vertices {1, 2, . . . , n} of an n node line graph with a permutation σ of the set {1, 2, . . . , n}, i.e., node i is assigned the label σ(i).   Call i a hill if σ(i) is bigger than the label(s) assigned to its immediate neighbor(s). Consider the distributed coloring algorithm “REDUCE” discussed in class

1.  [1 pt] Show that if i is a hill then  “REDUCE” colours i in the first round of the algorithm.

2.  [4 pts] If i and j are two consecutive hills then how many steps does “REDUCE” take for all the nodes between i and j to be colored?

3.  [5 pts] Give two permutations σ for which the distributed algorithm REDUCE requires n rounds to complete. Prove your claim.

2    [10 pts]

The way IDs are assigned can make a difference in the performance of a distributed algorithm (as this is measured by its termination time). Consider the clockwise leader election algorithm in the ring topology (graph).

1.  Give an assignment of identifiers to the nodes for which O(n2 ) messages are sent. Draw a picture of the assignment and prove your claim.

2.  Give an assignment of identifiers to the nodes for which only O(n) messages are sent.  Draw a picture of the assignment and prove your claim.

3    [10 pts]

An Independent Set (denoted IS) is a set I C V in an arbitrary graph G = (V, E) such that for any u, v e I , {u, v} \e E . If an IS is maximal it is called Maximal Independent Set (denoted MIS).

1.  [4  pts]  Consider a ring of size n.   Assume you have a distributed algorithm solving the MIS problem in Tn  rounds.  Show how to use it in order to to solve the colouring problem with O(1) additional rounds (this constant is small!).

2.  [6 pts] Consider an arbitrary graph G = (V, E).  Show that given a coloring algorithm that needs C colors and runs in time T, we can construct a MIS in time C + T.  Analyze the message complexity of your algorithm.

4    [10 pts]

Prove that the three graphs depicted below are isomorphic by 1) labeling the vertices, of the graphs and 2) exhibiting the one-to-one correspondence between vertices.

5    [10 pts]

Two nodes u, v are connected by a link and they each have a fair coin (A fair coin has equal probability of Head or Tail.) In synchronous rounds: each node flips a fair coin randomly and independently and sends the outcome to the other node.

u                                                                    v

1.  [4  pts] What is the probability that after k rounds the nodes have produced the same sequence of bits?

2.  [6 pts] (★) Assume that leader is elected as the node whose sequence of bits represents the biggest integer in base 2.  What is the expected number of rounds until a leader is elected?

6    [10 pts]

Two robots r1 , rv  can move with respective speeds 1 and v, where v > 1.

d

r1                       

Initially, they are placed at distance 0 < d < 1 on a cycle with perimeter length equal to 1.  Independently of each other they choose to move either CW or CCW each with probability  .  Derive a formula for the expected rendezvous time  (this is the time it takes the robots to meet) of the two robots. Give details of your derivation.

7    [10 pts] (★)

A treasure T is placed at the center of a circle of radius d.   Two robots R1 , R2  with respective speeds v and 1, where v > 1, are supposed to move the treasure to the perimeter (anywhere on the perimeter).

The robots R1 , R2  know each other’s and their own starting position (and hence their respective distances d1 , d2  from the treasure).   Any robot can carry the treasure and pass it on to the other robot if needed provided they are co-located.  Carrying the treasure does not affect a robot’s speed.  Give an optimal time distributed algorithm to carry the treasure to the perimeter in optimal time.

8    [10 pts]

Periodic sequences are often used in distributed algorithms to elect a leader. A sequence over an alphabet set A (e.g., A = {0, 1} or A = set of letters of Latin alphabet) is an infinite list a = a0 a1 a2 . . .  of elements of A.  The sequence a is called periodic if there exists an integer T > 0 so that

ai  = ai+T , for all i = 0, 1, 2, . . ..                               (1)

A number T which satisfies Equations (1) is called a period of the sequence a. The least T which satisfies Equations (1) is called the period, or sometimes the least period, of a.  The sequence a is called eventually periodic if there exist N > 0 and T > 0 so that Equation (1) holds for all i > N .  A period (resp. the least period) of an eventually periodic sequence refers to a period (resp. least period) of the periodic part of a. Consider the following.