L’iniziatore manda una richiesta a tutti i suoi vicini dicendo: vuoi essere mio vicino nel ST?

Dopo di che l’iniziatore aspetta le risposte praticamente.

Come risposte potrebbe avere Si e No.

• Si se non sono nello ST e mi unisco e inoltro la domanda ai miei vicini
• No se sono già nello ST e non devo andare a fare nulla, non accetto di nuovo una richiesta da qualcun altro e se accettassi di nuovo andrei a formare dei cicli

Come faccio adesso a scrivere l’idea in maniera più precisa e protocollare? Che possibili stati potrei andare a considerare?

Come finisce il protocollo per un nodo? Se dico no sti cazzi, se dico “sì” devo aspettare tutte le risposte dai miei vicini (tranne da chi mi ha mandato la domanda). Ho quindi un altro stato chiamato active da quando hanno iniziato il protocollo prima di aver finito (che è quando aspetto le risposte).

state = {initiator, idle, active, done}

signal init = {initiator, idle} → possible internal states

signal term = {done} → termination state

INITIATOR
spontaneously
	root = true
	Tree-neighbours (x) = {}
	send Q to N(x)
	counter = 0
	become(ACTIVE)

IDLE
receving(Q)
	root = false
	parent = sender
	Tree-neighbours(x) = {sender}
	send YES to parent
	counter = 1
	if counter = |N(x)|
		then
			become(DONE)
		else
			send Q to N(x)-{sender}
			become(ACTIVE)

ACTIVE
receiving(Q)
	send NO to sender

receiving(YES)
	Tree-neighbours(x) = Tree-neighbours(x) u {sender}
	counter = counter + 1
	if counter = |N(x)|
		then
			become(DONE)

receiving(NO)
	counter = counter + 1
	if counter = |N(x)|
		then
			become(DONE) 

Potrebbe arrivarmi un’altra Q in una situazione di triangolo, in cui il vertici superiore manda a quelli inferiori dei messaggi e questi poi si mandano delle questions a vicende perché giustamente non sono father tra di loro.

Correttezza e Costi + Considerazioni

Ogni nodo risponde yes una volta sola, se il padre rispondo yes allora c’era qualcun altro. Ogni nodo ha un padre solo e non posso andare a formare dei cicli. Costruisco lo spanning tree. Termina ovviamente quando diventiamo tutti quanti DONE.

C’è una terminazione solamente locale, sa quando finisce lui e basta.

Complexity

Quanto mi costa tutto ciò? Se ci pensiamo le Q viaggiano come i messaggi del broadcast della volta scorsa. Mi aspetto almeno il numero di messaggi di broadcast, però mi aspetto anche delle risposte di ritorno. Quindi alla fine posso immaginare un doppio costo.

Facciamo un conto, ci proviamo: posso andare a cercare di capire quali sono i possibili messaggi che passano in entrambe le direzioni e cerchiamo di capire che combinazioni ci sono e quelle che non capiteranno mai.