I protocolli di discretizzazione dinamica

Come anticipato nel sottoparagrafo precedente, i protocolli di discretizzazione regolano due scenari fondamentali di questo sistema: la creazione e l’eliminazione di un livello di discretizzazione. Essi governano quindi la dinamicità del sistema.

Quando creare un nuovo livello di discretizzazione?

La risposta a questa domanda risulta immediata: dato che vogliamo ridurre il più possibile il numero di falsi positivi che un utente riceve, e dato che la probabilità di ricevere un falso positivo è direttamente proporzionale al rapporto tra le dimensioni di un sottospazio ed una sottoscrizione coperta da esso, un nodo decide di discretizzare il sottospazio, e cioè di ridurne le dimensioni, quando riceve troppi falsi positivi, o in altre parole, quando il sottospazio è così grande da generare un numero eccessivo di falsi positivi. Quindi, la creazione di un nuovo livello di discretizzazione si basa sul rapporto tra il numero di falsi positivi ed il numero totale di eventi ricevuti, cioè sulla percentuale di falsi positivi ricevuti: quando questa percentuale supera una determinata soglia stabilita dall’utente, la quale rappresenta la percentuale massima di falsi positivi tollerati, il nodo decide di aggiungere un nuovo livello di discretizzazione agli alberi DT ed ST

Capitolo 3: Trasformare un sistema topic-based in content-based

Formalmente possiamo così definire la condizione di discretizzazione:

Dato un sottospazio T che contiene un insieme non vuoto di sottoscrizioni, e definiti i falsi positivi di un sottospazio come quegli eventi che risultano essere falsi positivi per tutte le sottoscrizioni contenute in esso:

𝑓𝑎𝑙𝑠𝑒 𝑝𝑜𝑠𝑖𝑡𝑖𝑣𝑒_𝑇 = 𝑥 ∈ 𝑇 ∶ ∀ 𝑠𝑢𝑏𝑠𝑐𝑟𝑖𝑝𝑡𝑖𝑜𝑛 𝑠 𝑖𝑛 𝑇, 𝑥 ∈ 𝐹𝑃𝑠

Quindi, data una soglia di discretizzazione, T deve essere discretizzato quando

#_𝑇𝑓𝑎𝑙𝑠𝑒 𝑝𝑜𝑠𝑖𝑡𝑖𝑣𝑒𝑠

#_𝑇𝑡𝑟𝑢𝑒 𝑝𝑜𝑠𝑖𝑡𝑖𝑣𝑒𝑠 + #_𝑇𝑓𝑎𝑙𝑠𝑒 𝑝𝑜𝑠𝑖𝑡𝑖𝑣𝑒𝑠^{> 𝐷𝑖𝑠𝑐𝑟𝑒𝑡𝑖𝑧𝑎𝑡𝑖𝑜𝑛 𝑡ℎ𝑟𝑒𝑠ℎ𝑜𝑙𝑑}

In particolare, ogni nodo utilizza una serie di contatori per memorizzare il numero di eventi ricevuti, sia falsi positivi che veri, in modo da poter controllare, ogni volta che arriva un nuovo evento, se la condizione precedente è soddisfatta, e quindi richiedere la discretizzazione. Entrando ancora di più nei dettagli, ogni nodo memorizza per ogni sottospazio a cui è sottoscritto, un contatore per i veri positivi ed una serie di contatori per i falsi positivi, uno globale al sottospazio e poi uno per ogni dimensione del modello dei dati, questo perché, come anticipato nel paragrafo 3.2.1, la discretizzazione viene effettuata su una sola dimensione, quella associata al contatore con il valore maggiore.

Questo è ciò che deve implementare un attore del sistema di tipo subscriber, in quanto tali contatori sono necessari per controllare il superamento della soglia ed eventualmente scegliere la dimensione pivot per un nuovo livello.

Per quanto riguarda un attore di tipo publisher invece, esso deve memorizzare gli eventi pubblicati in ogni nodo foglia, in quanto, come vedremo a breve, il protocollo inverso a quello di creazione di un nuovo livello, ovvero quello di controllo di necessit{ di un livello, si basa sull’analisi della distribuzione passata degli eventi, distribuzione che viene appunto memorizzata dai publisher, per poi essere inviata ai subscriber ogni E secondi (E rappresenta la durata di un’epoca, ovvero ogni quanti secondi viene avviato l’algoritmo di controllo di

Capitolo 3: Trasformare un sistema topic-based in content-based

necessità). Analizzeremo ora i due protocolli appena citati: il protocollo di creazione di un nuovo livello, costituito da due algoritmi, controllo soglia e creazione vera e propria di un nuovo livello, ed il protocollo per il controllo di necessità di un livello.

Il protocollo che regola la creazione di un nuovo livello negli alberi DT e ST è basato sui due algoritmi seguenti:

ALGORITMO 1 (controllo superamento soglia)

ogni volta che un nodo riceve un evento e coperto dal sottospazio T: 1.

a. Se e è un vero positivo, il nodo incrementa il singolo contatore associato al sottospazio T.

b. Altrimenti, se e è un falso positivo di T, il nodo incrementa il contatore globale dei falsi positivi di T, e poi verifica, per ogni sottoscrizione contenuta in T, quali vincoli della sottoscrizione non sono soddisfatti, incrementando quindi solo i contatori associati alle dimensioni su cui non sono soddisfatti i vincoli.

2. Dopo aver aggiornato i contatori, il nodo verifica se la condizione di discretizzazione è soddisfatta.

3. In caso positivo, il nodo avvia il processo di discretizzazione del sottospazio in questione, inviando sul topic associato al nodo dell’albero ST associato al sottospazio T un messaggio di richiesta di discretizzazione per il sottospazio

T, indicando come dimensione pivot quella associata al contatore con valore

maggiore.

Analizzando l’algoritmo appena descritto, ed in particolare focalizzandoci sul punto 1.b, possiamo notare che, per quanto riguarda i contatori di dimensione, un falso positivo viene contato tante volte quante sono le sottoscrizioni che non sono soddisfatte. In prima analisi, questo potrebbe sembrare un errore, in quanto un unico falso positivo potrebbe generare un incremento più che

Capitolo 3: Trasformare un sistema topic-based in content-based

unitario dei contatori. In realtà questo incremento multiplo serve a tener traccia del fatto che, nonostante ci siano più sottoscrizioni in un sottospazio, e quindi una minore regione non coperta da sottoscrizioni, e quindi una minore probabilità di ricevere un falso positivo, il sistema ha comunque notificato un evento che è falso per più sottoscrizioni. Con questi incrementi multipli quindi, riusciamo a determinare con maggiore precisione su quale dimensione è necessario effettuare una discretizzazione in modo da ridurre il più possibile i falsi positivi del sottospazio.

L’algoritmo invece che viene attivato ogni volta che viene ricevuto un messaggio di richiesta di discretizzazione generato dall’algoritmo precedente, e che crea un nuovo livello negli alberi DT ed ST è il seguente:

ALGORITMO 2 (ricezione messaggio di richiesta di discretizzazione)

ogni volta che un nodo riceve una richiesta di discretizzazione nel topic ST (topic di sistema associato al sottospazio T):

1. Si procede a realizzare il nuovo livello di discretizzazione creando negli alberi DT ed ST K nuovi figli (con K parametro di sistema) per i nodi del DT e del ST associati al sottospazio T.

2. Per ogni nuovo nodo di interesse, ovvero associato ad un sottospazio che copre almeno una sottoscrizione o un advertisement, si effettua la sottoscrizione al topic di sistema (quello associato all’ST) e, se l’attore che esegue l’algoritmo è un subscriber, si effettua la sottoscrizione anche al topic dati (quello associato al DT)

3. Terminata l’analisi sui nuovi figli, se l’attore che esegue l’algoritmo è un subscriber, si procede all’annullamento della sottoscrizione al topic dati associato al nodo padre del DT appena discretizzato.

4. Una volta terminato il processo di discretizzazione, il sottospazio T è discretizzato in K sottospazi (dove K è un parametro di sistema), e se l’attore che sta eseguendo l’algoritmo è un publisher, allora esso trasferisce la

Capitolo 3: Trasformare un sistema topic-based in content-based

distribuzione che aveva memorizzato per il nodo associato al sottospazio T ai nuovi figli, ovvero alle nuove foglie.

Come possiamo vedere, la creazione di un nuovo livello risulta semplice da gestire: fondamentalmente è composta da due fasi distinte, l’aggiornamento dei contatori, e la verifica della condizione di discretizzazione. Completamente differente, invece, è l’eliminazione di un livello, che necessita di un’analisi più complessa.

Quando un livello di discretizzazione non è più necessario?

Per rispondere a questa domanda possiamo percorrere a ritroso il processo che ha portato alla creazione di un nuovo livello e quindi chiederci: se annullassimo tale livello, qualche sottoscrittore chiederebbe nuovamente di discretizzare? Se la risposta è no, allora si può procedere all’eliminazione. La soluzione adottata si basa quindi sull’analisi della distribuzione degli eventi all’interno del livello in questione, e su come essa sia percepita dai sottoscrittori interessati. In particolare, quando la distribuzione degli eventi è tale per cui il livello di discretizzazione non è più indispensabile per ogni singolo sottoscrittore coinvolto, allora si può procedere all’eliminazione di questo livello di discretizzazione. In altre parole, un livello viene eliminato quando la nuova configurazione dell’albero che si andrebbe a creare è tale per cui ogni sottoscrittore non riceverà un numero di falsi positivi tale da soddisfare la condizione di discretizzazione.

L’algoritmo di controllo, attivato ogni volta che scatta un timeout (parametro di configurazione del sistema), si basa su uno scambio di messaggi nei topic di sistema associati alle radici dei sottoalberi di altezza unitaria dell’albero di sistema ST (ad esempio i nodi 1.2 e 2.2 in figura 5), il cui scopo è quello di far conoscere ai sottoscrittori la distribuzione degli eventi.

Capitolo 3: Trasformare un sistema topic-based in content-based

Il protocollo di controllo della discretizzazione è il seguente:

PROTOCOLLO 1 (CONTROLLO DI NECESSITA’ DI UN LIVELLO DI DISCRETIZZAZIONE)

ogni E secondi (che rappresentano un epoca)

1. I pubblicatori inviano sui topic di sistema un messaggio contenente il numero di eventi pubblicati nei nodi foglia e attendono un tempo pari a 5t, dove t è un tempo stimato che indica il tempo massimo necessario per ricevere un messaggio. Scaduto questo tempo, i pubblicatori eseguono l’ultimo passo dell’algoritmo.

2. Se un nodo riceve un messaggio inviato da un pubblicatore al passo 1 contenente una distribuzione di eventi relativa ad un sottoalbero che per lui non è ad altezza unitaria, risponde immediatamente con un NOK e termina l’algoritmo.

3. Quando un pubblicatore riceve un messaggio inviato al passo 1 da un altro pubblicatore e non ha ancora avviato l’algoritmo, lo avvia immediatamente. Invece i sottoscrittori, alla ricezione del primo messaggio, attendono 2t prima di procedere al passo successivo, tempo sufficiente per ricevere da tutti gli altri pubblicatori coinvolti i messaggi contenenti le distribuzioni degli eventi.

4. Dopo il tempo 2t, i sottoscrittori, avendo a disposizione la distribuzione degli eventi corrente all’interno dei sottospazi di altezza 1 (quelli con un solo livello di discretizzazione), controllano, per ogni sottospazio, se la soglia di discretizzazione è superata, considerando come veri positivi gli eventi pubblicati nelle foglie a cui sono sottoscritti, e come falsi positivi gli eventi nelle foglie rimanenti. Nel caso in cui la soglia non viene superata, il sottoscrittore invia un OK.

5. Dopo aver deciso, un sottoscrittore attende per altri 2t (tempo sufficiente per ricevere eventuali NOK del passo successivo).

Capitolo 3: Trasformare un sistema topic-based in content-based

6. Se un sottoscrittore che ha deciso per il no, perché la soglia è superata, riceve un OK, invia un NOK e termina l’algoritmo.

7. Se un nodo riceve un NOK, termina l’algoritmo.

8. Quando i pubblicatori ed i sottoscrittori superano rispettivamente i 5t del passo 1 ed i 2t del passo 4 senza ricevere NOK, questo può rappresentare due scenari differenti:

a) Tutti i sottoscrittori che stanno eseguendo l’algoritmo hanno deciso per il NO al passo 4 e quindi nessuno ha inviato un OK. In questo caso il livello non viene eliminato.

b) Tutti i sottoscrittori hanno deciso per il SI al passo 4, quindi è stato inviato almeno un OK, il quale è stato ricevuto anche da tutti i pubblicatori coinvolti. In questo caso, tutti i nodi coinvolti procedono all’eliminazione del livello in questione.

Figura 3.7: un esempio di esecuzione dell’algoritmo di controllo della discretizzazione

Nell’esempio di figura 3.7 abbiamo 5 nodi coinvolti: due pubblicatori, P1 e P2, e tre sottoscrittori, S1, S2 e S3. Nello scenario mostrato abbiamo che P1 invia il messaggio contenente gli eventi pubblicati, poi P2, non avendo ancora iniziato l’algoritmo, quando riceve il messaggio da P1 inoltra anche la sua distribuzione.

Capitolo 3: Trasformare un sistema topic-based in content-based

Dopo un periodo di tempo che va da 2t a 3t, a seconda di quando i sottoscrittori ricevono il primo messaggio, ogni sottoscrittore decide se per lui il livello può essere eliminato oppure no. A questo punto, il nodo S1 decide di si e quindi invia un OK. Quando S2, che ha deciso di no, riceve un OK, invia immediatamente un NOK e termina l’esecuzione, così come terminano gli altri quattro nodi.

Una precisazione importante da evidenziare, che riguarda l’invio dei messaggi OK e NOK nell’algoritmo precedente, e che influenza l’overhead introdotto dal sistema, è la seguente: ogni nodo che deve inviare un OK o un NOK, programma l’invio del messaggio posticipato di un ritardo random (tra 0 e 10), in modo tale che, se nell’intervallo di tempo tra il momento della programmazione dell’invio e l’invio stesso, l’esecutore dell’algoritmo riceve un messaggio semanticamente uguale (un OK o un NOK per lo stesso nodo dell’albero), allora annulla il suo invio, dato che qualcun altro ha già provveduto, inviando nello stesso topic lo stesso messaggio.

Come si può capire da quanto detto fino ad ora, ogni nodo costituente il sistema Publish-Subscribe distribuito ha la necessità di conoscere lo stato degli alberi DT ed ST, almeno per quel che riguarda le porzioni di interesse, cioè quelle contenenti le foglie associate a sottospazi che coprono le proprie sottoscrizioni o advertisement.

Data la completa distribuzione degli alberi DT ed ST che caratterizza il nostro sistema, il paragrafo successivo presenta le soluzioni adottate per garantire la consistenza tra le copie locali degli alberi che ogni nodo del sistema costruisce in base alle proprie necessità.