Dany Shaanan spiega con il seguente articolo il concetto di tempo di rimescolamento secondo la markov chain.

Quando le mie nipoti gemelle di 8 anni mi hanno chiesto cosa faccio nel mio nuovo lavoro, ho raccontato loro una storia: “Immaginate di incontrare una persona che viaggia per tutto il mondo. Se ti ha detto che ha iniziato a viaggiare un’ora fa, immagina che abbia iniziato nella stessa città in cui ti trovi. Se, tuttavia, ha iniziato un giorno fa, potrebbe aver già viaggiato tra le città, ma si potrebbe ancora intuire che è partito dal paese in cui ti trovi. In una settimana potrebbe aver attraversato diversi paesi, ma forse non ha attraversato i continenti. Se la persona vi dicesse che ha viaggiato per un anno, sarebbe davvero difficile indovinare da dove sono iniziati i suoi viaggi. Il mio lavoro è quello di scoprire quanto tempo ci vuole perché tu non abbia idea di dove ha iniziato il suo viaggio”. Sono stato felice di essere riuscito a semplificare il concetto di ‘mixing time’ per i bambini di 8 anni, ma immagino che tu, il lettore, possa essere un po’ più grande delle mie due giovani nipoti.

Questa semplificazione si applica sia al termine della teoria probabilistica matematica di tempo di rimescolamento (che non discuteremo qui) sia al tempo di rimescolamento nel contesto della rete Tangle.

La necessità di un termine del genere nel nostro contesto deriva da limitazioni delle prestazioni nel mondo reale. L’algoritmo predefinito di selezione del tip (in inglese) utilizza una passeggiata aleatoria che inizia da una data transazione chiamata punto di partenza. Quando nuove transazioni si uniscono al Tangle, la distanza di un punto di partenza dai tips cresce costantemente. Maggiore è questa distanza, maggiori sono le risorse computazionali richieste.

Con il passare del tempo, un nodo vorrebbe quindi sostituire un vecchio punto di partenza con uno nuovo, senza degradare la qualità del suo processo di selezione dei tip. Se un nodo sceglie un cattivo punto di partenza, è probabile che alleghi transazioni che non sarebbero selezionate rapidamente da altri nodi. Scegliere un nuovo punto di partenza che selezioni gli stessi tip di quello vecchio è desiderato. Per fortuna, si scopre che più vecchi sono i due possibili candidati quali punti di partenza, più è probabile che selezionino gli stessi tip. Così ci siamo: Il tempo di rimescolamento di un Tangle è quanto lontano si deve tornare indietro prima che i due possibili candidati quali punti di partenza si comportino allo stesso modo.

Ora abbiamo una definizione approssimativa di tempo di rimescolamento.

Ci sono, naturalmente, definizioni più formali dietro parole come “candidato”, “si comportano” e “lo stesso”, ma per risparmiare ai lettori dettagli inutili, salteremo quelle e passeremo alle parti più interessanti.

Quando il processo di selezione dei tip di un nodo diventa richiede troppe risorse, il nodo può sostituire il vecchio punto di partenza con qualsiasi candidato quale punto di partenza che sia vecchio almeno quanto il tempo di rimescolamento! Ora abbiamo solo bisogno di capire qual è il tempo di rimescolamento per ogni Tangle specifico. Risulta che produrre un modello analitico per il tempo di rimescolamento è impossibile a causa della complessità del problema. Inoltre, mentre il calcolo del tempo di rimescolamento per un Tnagle è possibile, è troppo complicato per essere eseguito costantemente dai nodi. Possiamo, tuttavia, eseguire esperimenti numerici sui nodi simulati ed analizzare i risultati per cercare di capire e prevedere il comportamento del tempo di rimescolamento.

Abbiamo costruito un simulatore numerico per creare Tangles con velocità di arrivo della transazione di λ per unità di tempo e con selezione del tip che segue l’algoritmo di passeggiata aleatora con il parametro α, e calcolato i loro rimescolamenti del tempo.

Per uno di questi Tangle, con λ di 512, α di 0.00069, e circa 100.000 transazioni, abbiamo tracciato ciascuna delle sue transazioni su un grafico bidimensionale, dove l’asse x mostra l’età della transazione, e l’asse y mostra quanto vicino ai vecchi punti di partenza si comporta. (dove 1 indica lo stesso comportamento, e 0 indica un comportamento completamente diverso).

Similitudine rispetto all’età per λ=512, α=0.00069

Possiamo vedere che in questo Tangle, tutte le transazioni più vecchie di 69 sono molto simili al vecchio punto di partenza, quindi, selezionando una qualsiasi di queste transazioni come il nuovo punto di partenza non si tradurrà in un notevole cambiamento nella futura selezione dei tip!

Tuttavia, non tutti i Tangles sono così belli. Per esempio, ecco un Tangle con λ di 32, e α di 0.0441:

Similitudine rispetto all’età per λ=32, α=0.0441

Qui non tutte le transazioni raggiungono la cima del grafico. Possiamo vedere in basso le transazioni che sono ‘abbandonate’, e quindi diventano pessimi punti di partenza, (dato che non c’è un posto dove camminare in avanti in una passeggiata aleatoria che inizia lì). Fortunatamente, possiamo identificare facilmente queste transazioni ed escluderle come candidati punti di partenza. Una volta escluso, il tempo di rimescolamento rimane valido – ogni rimanente punto di partenza del candidato più vecchio del tempo di rimescolamento conserverà il comportamento della nostra selezione dei tip.

Il rapporto tra le transazioni che rimangono validi candidati è già stato discusso qui nel post del blog ‘Confirmation rates in the Tangle(in inglese). Il tasso di conferma del Tangle nel primo grafico è 1 (nessuna transazione viene abbandonata), e 0,95 per il secondo grafico (5% di transazioni abbandonate).

Valutando sia il tempo di rimescolamento che il tasso di conferma per più di 200 Tangles con diversi valori λ e α si ottiene questa tabella:

Tempo di rimescolamento e fiducia di conferma per diversi Tangles

In questa tabella, ogni riga rappresenta un certo valore α e ogni colonna rappresenta un certo valore λ. Ogni Tangle è rappresentato da due numeri – il tasso di conferma a sinistra e il tempo di rimescolamento a destra. Colorando questi valori possiamo notare le tendenze e fare osservazioni sulle relazioni tra α, λ, il tempo di miscelazione e il tasso di conferma:

  • I Tangle costruiti con valori α più bassi sono più “sani” in termini di tasso di conferma – ci sono meno transazioni che vengono abbandonate per non essere mai confermate. Questo significa che saremmo felici se tutti usassero valori α bassi, ma ci sono altre considerazioni in gioco (che sono oggetto di ulteriori ricerche e di un post sul blog completamente nuovo).
  • Il tempo di rimescolamento cresce con il tasso di transazione in entrata λ, ma ad un ritmo molto più lento. Moltiplicando λ per 100 si aumenta il tempo di rimescolamento di circa 2, almeno per valori α inferiori. Il lavoro futuro includerà simulazioni con valori λ più grandi, per vedere come questa tendenza continua.
  • I tempi di rimescolamento più alti sono di Tangles con valori λ elevati e valori α moderati. Cosa c’è di speciale in questo intervallo di valori α? Come si comporterebbe per valori di λ ancora più alti?

Abbiamo progredito molto ed oltre la storia del viaggiatore mondiale, abbiamo prodotto dati interessanti e domande stimolanti. Ulteriori analisi e risposte sono necessarie per definire un metodo di sostituzione del punto di partenza e per migliorare la nostra comprensione dell’intricato comportamento del Tangle.


Il testo originale in lingua inglese si trova qui: https://blog.iota.org/mixing-time-in-the-tangle-439c2ba2ab31


È possibile supportarmi su Patreon https://www.patreon.com/antonionardella

Per ulteriori informazioni in italiano o tedesco trovate i miei contatti a questa pagina.
Se avete trovato utile la mia libera traduzione, accetto volentieri delle donazioni 😉

IOTA:
QOQJDKYIZYKWASNNILZHDCTWDM9RZXZV9DUJFDRFWKRYPRMTYPEXDIVMHVRCNXRSBIJCJYMJ9EZ9USHHWKEVEOSOZB
BTC:
1BFgqtMC2nfRxPRge5Db3gkYK7kDwWRF79

Non garantisco nulla e mi libero da ogni responsabilità.


Also published on Medium.