ADRC - Lecture Notes Summary

Lecture Info

Descrizione Modello Distribuito

• Eventi, Azioni e Comportamento di una Entità

• Messaggi e Topologia di Comunicazione

• Assiomi e Restrizioni

  • Communication Restrictions

  • Reliability Restrictions

  • Topological Restrictions

  • Time Restrictions

• Complessità di un Protocollo Distribuito

  • Message Complexity

  • Bit Complexity

  • Time Complexity

• Stato Globale di un Ambiente Distribuito

• Problemi e Soluzioni

Esempio di Esecuzione Distribuita

Lecture Info

Problema del Broadcast

Risolvere il Broadcast

• Protocollo 1

• Protocollo Flooding

  • Correttezza

  • Complessità

Lower Bound per il Broadcast

Lecture Info

Struttura ad Hypercube

Broadcast su Hypercube

• Hyperflood

  • Correttezza

  • Complessità

Overview Broadcast

Lecture Info

Problema del Wake Up

Protocollo WFLOOD

• Correttezza

• Complessità

• Esercizio: WFLOOD in un albero

Lower Bound per il Wake Up

Lecture Info

ST Construction Problem

Protocollo SHOUT

• Correttezza

• Complessità

Protocollo SHOUT+

• Complessità

• Terminazione Globale nello SHOUT+

Osservazioni Finali

• ST tramite Broadcast

• Lower Bound per la ST Construction

• Che tipo di ST Costruiamo?

• ST Construction con più Intiators

Lecture Info

Depth First Traversal (DFT)

Protocollo BACK

• Message Complexity

• Ideal Time Complexity

Protocollo BACK+

• Message Complexity

• Ideal Time Complexity

Ulteriori Modifiche

• Eliminazione dei messaggi \(\text{ACK}\)

• Eliminazione dei messaggi \(\text{Visited}\)

Lecture Info

La Tecnica della Saturazione (o Link Election)

• Protocollo FULL-SATURATION

  • Correttezza

  • Complessità

• Protocollo SATURATION PLUG-IN

Applicazioni della Saturazione

• Calcolo del Minimo

• Calcolo di Funzioni Distribuito

• Calcolo della Media

• Calcolo delle Eccentricità

  • Protocollo 1 (senza saturazione)

  • Protocollo 2 (con saturazione)

• Calcolo dei Centri

Lecture Info

Why do we need a Leader?

Election in Trees

Election in the Ring

• Protocol 1: All the Way!

• Protocol 2: As Far as it Can!

  • Message complexity

• Protocol 3: Stage Technique

  • Correttezza e Terminazione

  • Message Complexity

Lecture Info

Modello Probabilistico Distribuito

Leader Election Randomizzata

• Analisi Correttezza

• Random Bits Utilizzati

Concentrazione di Variabili Aleatorie

• Markov Inequality

• Chernoff Bounds

  • Esempio

Lecture Info

Majority Consensus Problem

• Cosa Vogliamo?

h-Majority Dynamics

• Analisi Dinamica

  • Caso \(h=1\)

  • Caso \(h=2\)

Lecture Info

Analisi 3-Majority

• Fase I - The Age of Fast Bias Growth

  • Incremento Esponenziale del Bias

  • Terminazione in \(O(\log n)\)

• Fase II - The Age of Fast Decrease of the Reds

  • Decrescità Esponenziale dei Rossi

  • Terminazione in \(O(\log n)\)

• Fase III - The Death of the Reds

Esercizio: 2-Majority Inerziale

Lecture Info

Protocollo RTA

Grado dei nodi in \(G_{\text{RTA}}\)

• Grado Medio

• Grado Massimo

• Grado Generale

Espansione di \(G_{\text{RTA}}\)

Diametro di \(G_{\text{RTA}}\)

Lecture Info

Information Spreading

Gossip Protocols

• Protocollo PULL

• Protocollo PUSH

• PULL vs PUSH

• Analisi PULL