Principios de Computación Distribuida
Semestre 2006-2, UNAM
Febrero 14 a junio 8, 2006
Página principal del curso
Ayudante: Daniel
Estévez Fuentes
Curso impartido a alumnos de la Maestría
en Ciencia e Ingeniería de la Computación como
Sistemas Distribuidos y Verificación.
Lugar: Salón 3 del Instituto de Matemáticas.
Horario: Martes y Jueves, de 11:30 a 13:00 hrs.
Contenido de esta página
Durante el curso se dejarán tareas y consistirán en
ejercicios relacionados con los temas tratados en clase. Cada tarea
tendrá que ser resuelta en un plazo fijo. La fecha de
entrega es estricta.
Profesores:
Ayudante:
- Daniel Estévez Fuentes
Oficina: ?
email: daniel.ef@gmail.com
Las tareas estarán disponibles conforme se vayan dejando
durante el curso. La fecha de
entrega es estricta.
- Tarea
1: 23 febrero 2006, fecha entrega: 9 de marzo
- Tema: two-phase commit;
consenso con entradas restringidas
- Tarea 2: 9 de marzo 2006, fecha entrega:
23 de marzo
- Tema: cotas inferiores para el problema de consenso; detectores
de fallas y el modelo de sincronía parcial
- Tarea 3: 28 de marzo 2006, fecha
entrega: 6 de abril
- Tema: consenso usando Omega; implementación de consenso
multi-valuado
- Tarea 4: 2 de mayo 2006, fecha
entrega: 11 de mayo
- Tema: causalidad y sincronización de relojes
- 1er Examen Parcial, fecha: ??
- Examen final, fecha: ??
Clases
- Primer día de clases, febrero 14, 2006: El protocolo
two-phase commit, una introducción a los principios de
cómputo distribuido (impartida por Sergio)
- jueves febrero 16: Modelos distribuidos, ataque coordinado,
consenso (impartida por Sergio)
- martes febrero 21 y jueves 23: (impartida por Sergio)
- martes febrero 28 y jueves marzo 2: algoritmos de consenso
síncorno (impartidas por Manuel)
- referencia: Michel Raynal, "Consensus in sychronous systems: A
concise guided tour," IEEE 2002 Pacific Rim International Symposium on
Dependable Computing (PRDC'02) p. 221.
- martes marzo 7 y jueves marzo 9: cota inferior para el
número de rondas del
consenso uniforme síncrono
- martes marzo 14 (marzo 14 comienza Sergio, marzo 16 no da Sergio
clase por manifestación, marzo 23 Manuel no da por enfermedad,
marzo 28 continúa Sergio con la presentación): el modelo
de sincronía parcial,
detectores de fallas y algoritmos de consenso. Introducción a
Paxos.
- Clase 6 presentación en powerpoint
- referencias:
- A. Mostéfaoui and M. Raynal. Leader-based consensus.
Parallel Processing Letters 11(1):95--107 2001.
- A. Mostéfaoui, M. Raynal: Solving Consensus Using
Chandra-Toueg's Unreliable Failure Detectors: A General Quorum-Based
Approach. DISC 1999: 49-63
- L. Lamport: Paxos Made Simple, SIGACT News
Distributed Computing Column, Volume 32, Number 4, (Whole Number
121), December 2001.
- Romain Boichat, Partha Dutta, Svend Frolund, and Rachid
Guerraoui: Deconstructing Paxos, SIGACT News
Distributed Computing Column, Volume 34, Number 2, (Whole Number
127), August 2003.
- martes abril 4 (impartida por Sergio): relojes lógicos
- referencias:
- Leslie Lamport: Time,
Clocks, and the Ordering of Events in a Distributed System. Commun.
ACM 21(7): 558-565 (1978)
- Fred B. Schneider: Implementing Fault-Tolerant Services Using
the State Machine Approach: A Tutorial. ACM Comput. Surv. 22(4):
299-319 (1990)
- Michel Raynal, Mukesh Singhal: Logical Time: Capturing
Causality in Distributed Systems. IEEE Computer 29(2): 49-56 (1996)
- martes abril 11, jueves abril 13: Semana Santa
- martes abril 18. (impartida por Manuel): Relojes vectoriales,
cortes consistentes. Algoritmo para obtener el corte máximo
consistente y snapshot distribuido
- jueves abril 20 (impartida por Manuel): Sincronización de
relojes físicos
- martes abril 25 (impartida por Manuel): Sincronización de
relojes físicos (cont.)
- jueves abril 28 (impartida por Manuel): Gráficas de
sincronización y ejemplos de uso
- martes abril 2 (impartida por Manuel): Demostración de los
teoremas principales en sincronización de relojes
Autor: Sergio Rajsbaum
Última modificación: marzo 6, 2006