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

- Prove that there are at most two centers in a tree.
- Present a
*simple*synchronous algorithm that finds the center(s) of the tree. Prove its correctness and analyze complexity. - * 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.