Indice

• compito 1    Ultima modifica: 18/11/03 ore 15:25
• compito 2    Ultima modifica: 25/11/03 ore 15:45
• compito 3
• compito 4

• Esercizio 1. Si applichi una semplice modifica al protocollo randomico visto in classe (e presente nelle dispense) per il Consenso in modo che esso soddisfi alla condizione di Limited Bureacracy.

• Esercizio 2. Sia data una rete sincrona a forma di anello in cui non si verificano guasti ed i cui i processori sono dotati di un numero di identificazione unico. Ogni processore può comunicare solo con i suoi due vicini.
  Si dia un protocollo per eleggere un leader. Vale a dire, al termine del protocollo ogni processore deve decidere se essere leader oppure no. Inoltre, il leader deve esistere ed essere unico.
• Esercizio 3. Il protocollo di BenOr può tollerare 1 guasto bizantino?

• Esercizio 4.Si consideri il seguente protocollo randomico per il consenso in ambienti asincroni e guasti di tipo fail-stop:

  proposal := input-bit; round := 1;
  repeat
      send (proposal, round) to all
      let A be the multiset of the first n-f messages with timestamp equal to round
      if all A values are the same bit b then decide(b) and set proposal := b
      else if a value b appears n-2f times in A then set proposal := b
      else set proposal at random to 0 or 1 with equal probability
      round := round +1
  forever
  

  • Si dimostri che questo protocollo è f-resistente se n > 4f, per guasti fail-stop.
  • Si dimostri invece che esso non funziona se n < 4f + 1 dando un controesempio per n = 4f

• Esercizio 5. Quali di queste due definizioni è corretta?
  • Un protocollo P per il Consenso non è t-resistente se esiste un modo di guastare k <= t processori tale che P viola una delle tre condizioni (Limited Bureacracy, Agreement, Non Triviality);
  • Un protocollo P per il Consenso non è t-resistente se per ogni modo di guastare k <= t processori P viola una delle tre condizioni.

• Esercizio 6. Dimostrare il seguente lemma, enunciato in classe nel contesto della dimostrazione di impossibilità del consenso per sistemi asincroni.

  COMMUTATIVITY LEMMA. Sia A una configurazione e siano s,r due sequenze di eventi relativi rispettivamente a due insiemi di processi S ed R. Siano inoltre S ed R disgiunti. Allora, rs(A) = sr(B).

• Esercizio 7. Si dimostri che il protocollo per BCAST e ACCEPT visto in classe e descritto nelle dispense soddisfa alla condizione di relay.

• Esercizio 8. Cosa c'è che non va in questa dimostrazione?

  TEOREMA. Per nessun t>0 esiste un protocollo per il Consenso che sia t-resistente rispetto a guasti bizantini.
  DIMOSTRAZIONE. Supponiamo per assurdo che esista un protocollo per t=1 e supponiamo per fissare le idee che sia n=15. Sia P il protocollo per t=1 ed n=15. Facciamo vedere come l'esistenza di P implica l'esistenza di un protocollo P' per t=1 ed n=3, che come sappiamo è un assurdo. Consideriamo un sistema di 3 processori A,B,C in cui A simula uno dei 15 processori, mentre B e C ne simulano 7 ciascuno. P' simula P via software, come nella dimostrazione vista in classe. Se guastiamo A sappiamo che il resto del sistema deve continuare a funzionare, perchè P &grave 1-resistente. Pertanto B e C giungeranno ad un accordo, ma questo è assurdo. QED

• Esercizio 9. Si consideri il seguente problema, detto del k-set consensus. Abbiamo un sistema message-passing con n processi soggetti a guasti di tipo fail-stop (sporchi); la topologia sottostante è quella di un grafo completo. Ogni processore p ha un suo valore di input x(p) preso dall'insieme {0,1, ..., n-1}. L'insieme degli input dati ai processi viene denotato con X. Si vuole un protocollo che, per ciascun processore p, produca un valore di output y(p) in modo che le seguenti condizioni siano verificate:
  • Limited Bureaucracy.
  • k-Agreement: sia Y l'insieme dei valori di decisione, allora |Y| < k+1.
  • Non-triviality: Y deve essere un sottoinsieme di X.
  Si dia un protocollo (k-1)-resistente per sistemi asincroni.

• Fare gli esercizi di algebra lineare delle dispense [postscript]   [pdf]  

• Esercizio 1. Nel problema del Generale Bizantino abbiamo un generale G ed n luogotenenti. G spedisce un bit ai luogotenenti i quali devono mettersi d'accordo su un bit di decisione, soddisfacendo i requisiti seguenti:
  • Agreement: i luogotenenti devono prendere la stessa identica decisione;
  • Loyalty: se il generale è leale la decisione deve coincidere col bit inviato dal generale (Il generale è leale se spedisce lo stesso bit ai luogotenenti).
  Un protocollo si dice t-resilient se esso è in grado di tollerare t guasti. Supponendo di disporre di un protocollo t-resilient per il consenso con guasti bizantini, si dia un protocollo per il problema del Generale Bizantino cercando di ottenere il massimo della fault-tolerance.

• Esercizio 2. Tolto perchè uguale al Nr.7, compito 1.

• Esercizio 3. Nel protocollo seguente ogni processore p mantiene un vettore V(p) le cui coordinate possono assumere i valori 0, 1, NIL. V(p)[q] = NIL significa che p non conosce il bit di input di q, mentre V(p)[q] = v significa che p conosce il bit di input di q e che questi è uguale a v.

  protocollo per p

  V[q] := NIL, for all q <> p
  V[p] := input-bit
  for round := 1 to f+1 do
        send V to all
        Collect all vectors sent by other proceses
        update V's coordinates
        end-for
  decision := majority value of V (breaking ties arbitrarily)

  • Il protocollo è f-resistente per guasti di tipo fail-stop? Si dia una dimostrazione od un controesempio.
  • Si dimostri che nel caso di guasti bizantini il protocollo non funziona.
  • Si supponga di modificare il protocollo in questo modo. Oltre a NIL, 0, 1 le coordinate del vettore possono assumere il valore RIP che denota che il processore relativo è defunto. L'aggiornamento delle coordinate con valore RIP avviene secondo queste regole:
    • Se al round corrente p non riceve un messaggio da q allora V(p)[q] := RIP;
    • Se al round corrente uno dei vettori ricevuti da p ha la coordinata q-esima posta a RIP allora V(p)[q] := RIP.
    Una volta che una coordinata assume il valore RIP il suo valore non cambia più. Il protocollo funziona ancora?

• Esercizio 4. In classe è stato enunciato il seguente teorema.

  TEOREMA. Il consenso per n processi e t guasti bizantini è risolubile se e solo se: (a) t < n/3 e (b) la topologia sottostante è un grafo 2t+1 connesso.

  Si dimostri che la condizione sulla connessione è necessaria per il caso particolare t=1 ed n=4. Per la sufficenza dare invece un argomentazioe intuitiva.

• Esercizio 5. Si dia un protocollo per il problema del Generale Bizantino nei casi seguenti:
  • solo il generale può guastarsi;
  • solo un luogotenente può guastarsi;
  • un solo guasto ma questi può essere sia il generale che un luogotenente;
  • due guasti.
  Nel risolvere l'esercizio non potete fare uso del protocollo per il consenso visto in classe e descritto nelle dispense.

• Esercizio 6. Supponendo di disporre di un protocollo t-resilient per il Generale Bizantino (con guasti bizantini), si dia un protocollo per il problema del Consenso per guasti bizantinicercando di ottenere il massimo della fault-tolerance. Il sistema è sincrono.

Per la definizione dell'attacco coordinato si fa riferimento alle dispense.

• Esercizio 1. Si dia una dimostrazione del fatto che non può esistere un protocollo per l'attacco coordinato che scambia zero messaggi.

• Esercizio 2. Esiste un protocollo per l'attacco coordinato le cui condizioni sono modificate come segue?
  • Limited Bureacracy
  • Non-Triviality
  • Agreement: y(A)=y(B), i.e. la decisione deve essere la stessa ma non necessariamente deve essere presa simultaneamente.

  Come sempre si suppone che l'avversario sia fair ed il sistema sincrono.

• Esercizio 3. Esiste un protocollo per l'attacco coordinato per sistemi asincroni?

• Esercizio 4. Esiste un protocollo per l'attacco coordinato le cui condizioni sono modificate come segue?
  • Non-Triviality
  • Agreement
  • Limited Dithering (Tentennamento Limitato): la decisione deve essere presa entro un numero finito di passi, ma il protocollo può funzionare all'infinito.

  In particolare ad un processo è consentito di continuare a spedire messaggi dopo aver deciso. Un tale protocollo si dice dormiente (quiescent). Come sempre si suppone che l'avversario sia fair ed il sistema sincrono.

• Esercizio 5. Si dia un protocollo (diverso da quello visto in classe) per il problema del consenso per guasti bizantini in sistemi sincroni che funzioni correttamente per t=1 ed n=10.

• Esercizio 6. Si dia un protocollo per il problema del consenso per guasti fail stop di tipo pulito per sistemi sincroni. Per quale valore di f esso è f-resistente?

• Esercizio 7. Si dimostri che il protocollo visto in classe per il consenso per guasti di tipo fail stop e sistemi sincroni non funziona se i suoi round di comunicazione sono f anzichè f+1.