ADRC - Lesson 09

Osserviamo che sia nel protocollo as-far che nel protocollo all-the-way le etichette viaggiano lungo l'anello in maniera incontrollata. In particolare nel protocollo as-far viaggiano finché non vengono filtrati da un nodo con etichetta più bassa, mentre nel protocollo all-the-way addirittura viaggiano lungo l'intero anello. L'idea sarebbe quindi quella di controllare la trasmissione di una etichetta ad una distanza limitata, e di avere dei feedback per eventualmente bloccare o estendere la trasmissione di una etichetta.

Più precisamente un nodo attivo \(x\) esegue il protocollo a stages, dove nello stage \(i\)-esimo esso inoltrerà a destra e a sinistra la sua etichetta \(id(x)\) fino a un massimo di distanza \(2^{i-1}\). Così facendo l'etichetta avrà ricoperto un numero di nodi pari a \(2^i\), ovvero \(2^{i-1}\) nodi a destra e \(2^{i-1}\) nodi a sinistra.

Quando un nodo \(y\) riceve l'etichetta di \(x\) la inoltrerà solamente se \(id(y) > id(x)\). Nel caso in cui \(y\) inoltrerà \(id(x)\) allora vorrà dire che certamente \(y\) non sarà mai eletto leader, e quindi passerà in uno stato di defeated in cui potrà solamente inoltrere le etichette degli altri.

Se l'etichetta \(id(x)\) arriva a distanza \(2^{i-1}\) allora essa verrà rispedita indietro come messaggio di feedback. Se il nodo \(x\) riceverà un feedback da entrambi i lati vorrà dire che tutti i nodi a distanza \(2^{i-1}\) da lui avranno etichette maggiori, e quindi dovrà inoltrere l'etichetta più lontano. In questo caso diciamo che \(x\) è sopravvissuto allo stage \(i\) e quindi potrà passare allo stage \(i+1\).

Notiamo che se \(x\) non riceve il feedback da uno o tutti e due i lati, vuol dire che esiste almeno un nodo \(z\) entro \(2^{i-1}\) passi con etichetta minore \(id(z) < id(x)\), e quindi prima o poi \(x\) verrà battuto (defeat) dall'etichetta \(id(z)\).

Infine, quando un nodo \(x^\star\) riceverà da destra il messaggio che aveva inviato a sinistra, oppure da sinistra quello che aveva invato a destra, allora \(x^\star\) potrà affermare di essere il leader. A questo punto \(x^\star\) manderà in broadcast un messaggio di notifica, che farà terminare globalmente il protocollo, facendo passare tutti i nodi nello stato defeated allo stato follower.

Ricapitolando:

1. in ogno stage \(i\) c'è un insieme di nodi candidati al ruolo di leader.
2. ogni candidato manda la sua etichetta a destra e a sinistra.
3. l'etichetta viaggia finché non incontra un nodo con etichetta più piccola oppure finché non arriva a distanza \(2^{i-1}\).
4. se l'etichetta non incontra nessun nodo con etichetta più piccola allora essa tornerà indietro.
5. se un nodo riceverà indietro le etichette da entrambi i lati allora potrà passare allo stage successivo.

In aggiunta ci sono altre tre meta-regole:

1. se un nodo nello stato candidato riceverà un'etichetta da lato opposto a quello da cui l'ha mandata, allora diventerà leader e lo notificherà ai suoi vicini.
2. se un nodo candidato riceverà un'etichetta minore della sua allora passerà allo stato defeated.
3. un nodo nello stato defeated potrà solamente inoltrare i messaggi di altri nodi, e passerà allo stato follower quando riceverà la notifica dal leader.

Definiamo ora formalmente gli stati del protocollo e una sua possibile implementazione

def limit(i):
    assert i > 0
    return 2**(i+1)

def initialize(self):
    self.stage = 1
    self.limit = limit(1)
    self.count = 0
    send("FORTH", self.id, self.stage, self.limit, direction=1) to self.neigh(direction=1)  # 1 = right
    send("FORTH", self.id, self.stage, self.limit, direction=0) to self.neigh(direction=0)  # 0 = left

def process(self, msg):
    msg.limit -= 1
    if msg.limit == 0:
	self.send("BACK", msg.id, direction = not msg.direction) to msg.sender
    else:
	self.send("FORTH", msg.id, msg.state, msg.limit) to self.neigh(direction=msg.direction)


def notify(self):
    send("NOTIFY", leader=self.id, direction=1)

def check(self):
    self.count += 1
    if self.count == 2:
	self.count = 0
	self.stage += 1
	self.limit = limit(self.stage)
	send("FORTH", self.id, self.stage, self.limit, direction=1) to self.neigh(direction=1)  # 1 = right
	send("FORTH", self.id, self.stage, self.limit, direction=0) to self.neigh(direction=0)  # 0 = left

LEADER = None

if self.state == "ASLEEP":
    spontaneously:
	self.initialize()
	self.state = "CANDIDATE"

    receiving(msg):
	if msg.id < self.id:
	    self.process(msg)
	    self.state = "DEFEATED"
	else:
	    self.initialize()
	    self.state = "CANDIDATE"

elif self.state == "CANDIDATE":
    receiving(msg):
	if msg.type == "FORTH":
	    if msg.id < self.id:
		self.process(msg)
		self.state = "DEFEATED"
	    elif msg.id == self.id:
		LEADER = self.id
		self.notify()

	if msg.type == "BACK":
	    if msg.id == self.id:
		self.check()

	if msg.type == "NOTIFY":
	    LEADER = msg.id
	    send(msg) to self.neigh(direction=msg.direction)
	    self.state = "FOLLOWER"

elif self.state == "DEFEATED":
    receiving(msg):
	send(msg) to self.neigh(direction=msg.direction)
	self.state = "FOLLOWER"