The aim of this exercise is to investigate the effect of selective delays in Archimedean networks. Let a network be given with Archimedean ratios.
Election is performed by applying extinction to a traversal algorithm with message complexity W. Each message of process p is delayed by f (p) - 1 clock ticks in each process. A separate wake-up procedure ensures that each process launches its traversal within Du time units after the start of the algorithm.
(1) Prove that the algorithm terminates within D.u + W.u.f (po ) time units, where Po is the process with the smallest identity.
(2) Prove that the token of process p is sent at most 1 + t/ (f (p) - 2) times during a time interval of length t.
(3) Derive a formula for the worst-case message complexity of the algo rithm.
(4) Show, by varying f, that a linear message complexity can be obtained.
Text Book: Introduction to Distributed Algorithms By Gerard Tel.