Algorismes Distribuits (AD)
| Professors Responsables: |
JOAQUIM GABARRÓ VALLÉS (gabarro lsi.upc.edu)
|
|
Crèdits: 4.5 (3.0 T 1.5 P 0.0 L)
| |
Departament:
LSI
|
Tipus d'assignatura
Optativa per la EI
Requisits de l'assignatura
|
EA
- Pre-correquisit per la EI
|
|
|
PC
- Pre-requisit per la EI
|
|
Objectius docents
L'estudi dels algorismes distribuïts ha començat ja a l'assignatura
de Programació Concurrent. Aquest curs aprofundeix en aquest estudi,
tractant-se els algorismes més importants.
A més a més s'aprofondeix en l'estudi de Java.
Programa
1. Autòmats I/O
- Definicions i exemples.
- Equitat (en anglès fairness).
- Seguretat i vivacitat (en anglès safety i liveness).
2. Temps lògic
- Temps lògic de Lamport.
- Temps lògic de Welch.
- Aplicacions.
3. Fotos (en anglès snapshots)
- Fotos i talls.
- Algoritme de Chandy-Lamport.
- Propietats estables.
4. Encaminament i camins més curs
- Arbre de destí òptim.
- Algoritme de Toueg.
- Algoritme de Chandy-Misra.
5. Elecció
- Anells i algoritme de Chang-Roberts.
- Algoritme de Peterson.
- Algoritme de Gallager-Humblet-Spira.
6. Sincronitzadors en Xarxes
- Algoritmes de retard fitat.
- Sincronitzadors alfa, beta, gamma.
7. Tolèrancia a fallides
- Fallides "crash": algorisme de Bracha i Toueg.
- Fallides bizantines: algorisme de Bracha i Toueg.
- El problema dels generals bizantins.
Avaluació
La nota consistirà en la suma de dues parts: l'avaluació de
coneixements bàsics i la de domini de l'assignatura.
L'avaluació de coneixements bàsics es realitzarà a partir
de l'entrega (optativa) d'escrits que contribueixin al desenvolupament de
l'assignatura (participació en les classes de problemes, classes de laboratori,
presentació de solucions de problemes, treballs d'estudi
bibliogràfic, pràctiques...) i/o mitjançant l'examen final
de coneixements bàsics, que es realitzara simultaneament amb
l'examen final de domini de l'assignatura.
Bibliografia
Bibliografia bàsica
- TEL, G Introduction to Distributed Algorithms Cambridge University
Press, 1994
- LYNCH, N A Distributed Algorithms Morgan Kaufmann, 1996
- ARNOLD, K, GOSLING, J The Java programming Language, Second Edition Addison Wesley , 1998
- LEA, D Concurrent programming in Java Addison Wesley, 1996
- Articles recents a revistes especialitzades.
,
Informació complementària
- Hi haurà unes 14 sessions de teoria-exercicis-pissarra de 2 hores.
- Hi haurà 7 sessions d'exercicis-Java en el laboratori de 2 hores.
|
