ADRC - Lesson 02

Come già detto, ogni entità (o nodo) della rete ha delle capacità computazionali, le quali sono definite come un insieme di operazioni possibili, quali:

• local storage e processing ovvero la capacità di conservare informazioni di processarle in maniera locale
• scambio di messaggi con altri nodi della rete
• (re-)impostare il clock. Ogni nodo ha un clock interno che standisce come eseguire le sue azioni, il quale può essere impostato
• cambiare il valore dei regitstri. Ogni nodo ha dei registri usati per eseguire le operazioni e/o mantere uno stato¹

Il comportamento di ogni entità é reattivo, ovvero scaneta in seguito all'avvenire di eventi Alcuni esempi di eventi possono essere:

• il tick del clock (evento interno al nodo)
• la ricezioni di un messaggio (evento esterno al nodo)
• un impulso esterno alla rete

Anche se in un contesto reale gli eventi avvengono su una linea temporale discreta³, essi verranno considerati essere avvenuti in maniera sequenziale (o ordinata). Questo perché in un intervallo di tempo continuo, la probabilità che due eventi indipendenti occorrano nello stesso identico istante è pari a 0. nnnnn

Come accennato, un'entità reagisce in seguito a un evento. In realtà l'azione che compie in risposta a un evento dipende anche dal suo stato interno nel momento dello stimolo. \[ \mbox{State } \times \mbox{ Evento} \mapsto \mbox{ Action} \] In realtà per azione si intende una sequenza di task (o attività) da svolgere (non necessariamente una sola) come per esempio

• computare un algoritmo
• mangare un messaggio
• cambiare stato

Un'azione è considerata essere atomica, ovvero una volta avviata non può essere interrotta in alcuna maniera. Inoltre è importante specificare che nel nostro modello le azioni terminano sempre in un tempo finito.

Come detto in precedenza, per ogni coppia di stato ed evento corrisponde un'azione. Questa associazione è dette regola.

Più in generale possiamo definire un comportamento di un'entità come un insieme di regole. Quindi, dato un'entità \(x\), sia \(\Sigma\) il suo insieme di stati possibili, \(\mathcal{E}\) l'insieme degli eventi ed \(A\) l'insieme delle azioni che può eseguire. Il suo comportamento \(B(x)\) è la funzione \[ B(x) : \Sigma \times \mathcal{E} \mapsto A \] tale che è deterministica e completa \[ \forall (s,e) \in \Sigma \times \mathcal{E} \;\; \exists ! a \in A \]

Raggruppando tutti i comportamenti delle entita di un sistema è possibile definire il cosidetto protocollo (o algoritmo) distribuito.
Più formalmente un protocollo è l'insieme \[ B := \lbrace B(x) : x \mbox{ è un'entità del sistema} \rbrace \] Un sistema si dice simmetrico (o omogeneo) se ogni entità ha uno stesso comportamento \[ \forall x,y \mbox { entità} \left[ B(x) \equiv B(y) \right] \] In realtà è possibile trasformare ogni sistema in un sistema simmetrico.
Consideriamo un sistema dove esistono due tipi di entità, entità server ed entità client. Per ogni entità definiamo un ruolo, e in base ad esso eseguiamo l'azione corrispondete.

class Entity:
    def __init__(self, role):
	self.role = role

    def action(self, state, event):
	if self.role == 'server':
	    server_action(self, state, event)
	else:
	    client_action(self, state, event)

Le entità di una rete distribuita possono (e devono) interagire tra di loro. Il modo in cui interagiscono è tramite uno scambio di messaggi (o message passing), dove un messaggio è inteso essere una sequenza finita di bit.

I messaggi viaggiano su una rete di comunicazione, ovvero un grafo diretto che specifica quali nodi possono scambiarsi messaggi.

Importante specificare che i nodi della rete non hanno una visione globale⁴ della rete, bensì hanno la sola visione locale. Più formalmente questo significa che ogni nodo può vedere solamente due gruppi di porte logiche, quelle dalle quali arriveranno i messaggi in entrata, e quelle dalle quali usciranno i messaggi in uscita.

• \(N_{out}(x) \subset V\) = out-neighbors of entity \(x \in V\)
• \(N_{in}(x) \subset V\) = in-neighbors of entity \(x \in V\)

Secondo questa definizione il vicinato di un nodo \(x\) sarà l'insieme \(N(x) \equiv N_{out}(x) \cup N_{in}(x)\).
Perciò un nodo può mandare i messaggi solamente ai suoi out-neighbors in \(N_{out}(x)\)

e ricevere messaggid dai suoi in-neighbors in \(N_{in}(x)\)

Per tutto il corso, ogni argomento verrà trattato sotto le seguenti ipotesi fondamentali

Spesso si definiscono protocolli secondo l'assunzioni di ulteriori restrizioni. Ovviamente più restrizioni ci sono, più il protocollo è debole, in quanto togleindo tali restrizioni il protocollo potrebbe non funzionare. Un protocollo con meno restrizioni, risulta invece più generale, e perciò più forte.

Di seguito alcune tipologie di restrizioni

In un sistema distribuito non ha sempre senso parlare di complessità temporale, in quanto non è detto che il tempo di trasmissione di un messaggio sia sempre lo stesso, e soprattutto non è detto che il clock sia uguale per tutti. Per far sì che abbia senso parlare di time complexity si necessitano di due restrizioni: la synchronized clocks restriction e la Bounded Communication Delay restricion. Idelmente, tutti i messaggi dovrebbero viaggiare con uno stesso delay unitario.

Un'altro tipo di complessità che verrà quasi sempre analizzata è la cosidetta message complexity, ovvero una complessità che tiene conto del numero di messaggi trasmessi prima che un protocollo termini un suo task. Notare che, se un messaggio per arrivare dal nodo \(a\) al nodo \(b\) necessita di essere instradato 4 volte, allora verranno contante tutte e 4 le trasmissioni fatte prima di arrivare a \(b\), anche se il messaggio è uno solo.