Consider the ring election algorithm Controlled Distances where instead of doubl
ID: 672785 • Letter: C
Question
Consider the ring election algorithm Controlled Distances where instead of doubling the distance at each step, the distance is increased as follows. Let k be a constant: in stage 1 the message travels distance k, in stage 2 it travels distance 2k, in stage 3 it travels distance 3k and, in general, in stage i it travels distance ik. As a function of k and n: how many stages are necessary to terminate ? How many messages per stage are exchanged, at most ? What is the overall message complexity ? (in order of magnitude, i.e., expressed as O(..)).
Explanation / Answer
distance travelled = k + 2k + 3k ...+ ik = k(i)(i+1)/2
So, when
i(i+1)/2 = n/k;
solve qudaratic for i, we get the number of stages necessary to terminate
k messages are exchanged max.
Overall message complexity = O(sqrt(n))