Distributed Algorithms (236357) Winter 2000

Home assignment # 1

Question 1.

Node v is called a center of a non-directed tree T if the maximal distance from it to any other node in the tree is the minimum between the tree's nodes.  (Note that the tree does not have a root.)
  1. Prove that there are at most two centers in a tree.
  2. Present a simple synchronous algorithm that finds the center(s) of the tree. Prove its correctness and analyze complexity.
  3. * Present an asynchronous algorithm that finds the center(s) of the tree. Prove its correctness and analyze complexity.

Question 2.

Is leader election possible in a synchronous ring in which all but one processor have the same identifier?
Either give an algorithm or prove an impossibility result.
 

Question 3.

Consider the following algorithm for leader election in an asynchronous ring: Each processor sends its identifier to its right neighbor; every processor forwards a message (to its right neighbor) only if it includes an identifier larger than its own.

Prove that the average number of messages sent by this algorithm is O(n log n), assuming that identifiers are uniformly distributed integers.

Submission date: 27/11/2000