Per il discorso della pagine precedente dovrebbe venire fuori qualcosa che assomigli ad una BFS, MA per i ritardi meccanici e software succede che in realtà non ne ho idea precisamente di che cosa potrebbe succedere. Posso anche andare a fare situazioni che siano praticamente delle DFS per colpa dei ritardi.
Possiamo fare una costruzione By Traversal, simulando una visita sequenziale per costruire un albero di una visita. Lo facciamo andando a visitare ogni nodo uno alla volta, simulando una BFS.
Per fare questa cosa in distribuito devo sequenzializzare qualcosa in contesto distribuito si usa un token che può essere posseduto solamente da uno in ogni momento ed è l’unico che può fare computazione in quel momento. In questo caso la computazione diventa linearissima praticamente.
Costruiamo un albero con la BFS
Ci sarà un nodo initiator che avrà il token in partenza.
Immaginiamo di fare la visita in profondità, partiamo dalla radice che prende il primo vicino e gli passo il token e questo fa uguale. Questo arco back edge è riferito a chi ho già visitato, praticamente sono andato da un discendente ad un antenato, diciamo così, che non devo prendere altrimenti avrei un ciclo.
Ho la necessità di distinguere che cosa voglia dire token. Quando sono un nodo che non sono initiator, per un po’ sono lì che aspetto poi succede qualcosa: mi arriva un token di scoperta → forward token. Quando ho io il controllo devo passare a mia volta il token al vicino. Mi serve ricordarmi chi me lo ha mandato perché così riesco a tornare indietro.
Il token potrebbe essere un token → traversal oppure →token traversal (ho scritto due volte la stessa cosa, devo capire che tipo di token intendessi, forse una cosa tipo token di ritorno), è sempre lo stesso token ha solo due nomi diversi in base a come gira essenzialmente.
Potrei avere anche un terzo tipo di token → back edge token, ovvero quando scopro un nodo già stato scoperto. A questo tipo di nodo non mando MAI un forward token altrimenti è un bordello.
Se mi arriva da uno di questi un token back edge vuol dire che io sono un antenato(?), cioè qualcuno ha provato a contattarmi ma non posso unirmi a lui.
E’ difficile qua perché devo considerare tutti quanti i casi possibili! Devo mettermi nei panni di tutti. Se mi ritorna un back edge token, vuol dire che ho mandato un forward ma sono già nell’albero, io sono un tuo antenato e tu sei un mio discendente (quello che ha ricevuto il forward token che avevo mandato inizialmente).
Vedi l’esempio nelle slide con il token che naviga
Gli archi sono quelli su cui ha viaggiato forward e return, mentre tutti gli altri sono back edge. Il mio ST esclude obv i backedge.
La root è l’ultimo a ricevere il token
Il padre di un nodo X è quello a cui ridò il token
I figli sono i forward token
Avrò bisogno di un altro stato intermedio sicuramente, quindi ho gli stessi stati i prima
State S = {initiator, idle , visited}
signal init = {initiator, idle}