Itai-Rodeh algorithm

The Itai-Rodeh algorithm is a selection algorithm of the Las Vegas-class for anonymous unidirectional rings and builds on the Chang and Roberts algorithm on.

requirements

• unidirectional ring
• Ring size (number of nodes ) known ${\displaystyle n}$

procedure

The algorithm runs in phases (ballots).

First phase

In the first phase all nodes choose a random identification number , . Then each node sends a message consisting of its own ID , hop counter ( hopcount , indicates how often the message was forwarded), a marker ( flag ) and the current phase . Initially applies . ${\displaystyle \mathrm {ID} >0}$ ${\displaystyle i}$ ${\displaystyle h}$ ${\displaystyle f}$ ${\displaystyle p}$ ${\displaystyle h=1,f=1,p=1}$

• when a message is received: ${\displaystyle \langle i,h,f,p\rangle }$
  • if is less than the current phase at the recipient, the message is not forwarded ("swallowed" according to Chang and Roberts ) ${\displaystyle p}$
  • if so , the message is forwarded as ${\displaystyle i>\mathrm {ID} }$ ${\displaystyle \langle i,h+1,f,p\rangle }$
  • if so , the message will not be forwarded ${\displaystyle i<\mathrm {ID} }$
  • if ${\displaystyle i=\mathrm {ID} }$
    • if is to set (the flag noted that the ID is assigned more than once) and the message as forwarded ${\displaystyle h\neq n}$ ${\displaystyle f}$ ${\displaystyle 0}$ ${\displaystyle \langle i,h+1,0,p\rangle }$
    • if and has the node won the selection (notification to all others via a special message) ${\displaystyle h=n}$ ${\displaystyle f=1}$
    • if and there are several winners. ${\displaystyle h=n}$ ${\displaystyle f=0}$

Further phases

If there are several winners from the first or previous phase, this group starts another run of the algorithm . The process is exactly the same as in the first phase, but with a reduced number of participants. Passive nodes only forward messages; only the jump counter is increased. ${\displaystyle p=p+1}$ ${\displaystyle h}$

Message complexity

Messages are required for the first phase . Since the number of phases is theoretically unlimited, the message complexity approaches infinity. In practice, however, this case is very unlikely. So for each further phase, fewer than messages are added. ${\displaystyle n}$ ${\displaystyle n}$

The expected value for the number of ballots (if ): ( is Euler's number ) ${\displaystyle E}$ ${\displaystyle \forall ID:ID\in [1,...,n]}$ ${\displaystyle E\leq e\left({\frac {n}{n-1}}\right)}$ ${\displaystyle e}$

swell

• Lecture on distributed systems at the TU Berlin
• A. Itai and M. Rodeh. Symmetry breaking in distributed networks, In Proceedings of the 22nd IEEE Symposium on Science , pages 150-158. IEEE Press, 1981.