Principios de Computación Distribuida
Curso impartido en la UNAM en la
Licenciatura en Ciencias de la Computación
de la Facultad de Ciencias
y en el Posgrado
en Ciencia e Ingeniería de la Computación .
Descripción de una versión anterior del curso en:
Semestres en
que se ha impartido el curso:
Objetivos Generales
1. Formar alumnos que puedan resolver problemas complejos de
cómputo
distribuido, crítica y creadoramente. 2. Profundizar el
entendimiento de aspectos distribuidos, de concurrencia y
tolerancia a fallas de: sistemas operativos, bases de datos, redes de
computadoras e Internet. 3. Contribuir a la formación
del alumno en teoría de computación y a
aumentar
su comprensión de los fundamentos de la
computación.
Objetivos
Particulares
El material cubre principios fundamentales
subyacentes no solo a las tecnologías del momento, sino a
otras
que aparezcan en el futuro. Esto es especialmente importante en vista
de que se trata de un área con un vertiginoso avance, y
debido a
la enorme complejidad de un sistema
distribuido. Los principios fundamentales son los relacionados a:
- comunicación: protocolos de enlace, problemas de
ruteo,
congestión, etc.
- sincronización: exclusión mutua,
relojes, abrazos
mortales, etc.
- manejo de procesos: administración de recursos,
threads,
tiempo-real, calendarización, etc.
- tolerancia a fallas
- uso compartido de memoria
- especificación, modelado y verificación
- complejidad y análisis de algoritmos
- problemas de sistemas de archivos,
bases de datos y sistemas operativos distribuidos
- problemas de redes, Internet y el WEB: caching, P2P,
topología de la red, manejo de grupos, etc.
- redes de interconexión: árbol,
hipercubo, mariposa, fat-tree,
CCC, etc.
En un solo semestre es imposible cubrir todos estos temas, y otros
relacionados de gran importancia, como seguridad. Además,
algunos de ellos son demasiado avanzados para
presentarse en un
primer curso. Por otro lado, siendo un área tan nueva,
todavía
no hay un consenso absoluto de cuales son los resultados mas
importantes. El material que se describe a continuacion se
eligió de
manera que hubiera alguna relación entre los distintos
temas,
presentando una visión general lo más
coherente posible.
Requisitos
Madurez matemática y en Ciencias de la
Computación.
Experiencia equivalente a los cursos de la Facultad de Ciencias de
Teoría de la Computación,
Análisis de Algoritmos
I, Arquitectura de Computadoras, Redes de Computadoras y Sistemas de
Bases de Datos.
Regresar a Contenido
En la primera parte del curso se presentan algoritmos y
técnicas
básicas de desarrollo y análisis de
algoritmos
distribuidos. El
paradigma subyacente es el de difusión
de información en
una red. Se enfatiza el modelo de envío de mensajes, y la
complejidad de comunicación (cotas superiores, y algo de
inferiores), sobre el número de mensajes enviados por un
algoritmo.
En la segunda parte se estudian problemas de tiempo y
sincronización. Aqui las ideas pasan a ser
más abstractas
y
generales, después de haber estudiado diversos algoritmos
concretos
en la primera parte. En la tercera parte, se introduce el modelo de
memoria compartida. En esta parte se comienzan presentando varios
problemas y algoritmos que los resuelven, encaminándose
hacia el
problema fundamental de tolerancia a fallas, consenso.
Horas por semestre: 64
- Introdución (6 horas)
- Modelos de un sistema distribuido.
- Análisis de correctez y complejidad
- Fundamentos (20 horas)
- Protocolos de enlaze.
- Difusión de información por ficha.
- Busqueda en profundidad (DFS),
- Conexidad: certificados y otros algoritmos de ficha,
- Algoritmo de difusión sin respuesta (PI) y con
respuesta
(PIF),
- elección de líder en anillos y en
gráficas
arbitrarias,
- Arbol generador de peso mínimo
- Tiempo (18 horas)
- Causalidad, relojes escalares y relojes vectoriales,
- Detección de estados globales
- Tiempo real y sincronización de relojes
- Memoria Compartida (20 horas)
- Modelos de memoria compartida.
- Problemas de consenso solucionables y no solucionables.
- Problema de los conjuntos ordenados y el modelo de la foto
atómica
inmediata,
- Imposibilidad de consenso y estructura topológica
del
cómputo libre de espera
Regresar a Contenido
Básica
- Hagit Attiya,
Jennifer Welch, Distributed
Computing: Fundamentals, Simulations, and Advanced Topics,
McGraw-Hil, 1998.
- Nancy Lynch, Distributed
Algorithms, Morgan Kaufman Pub, 1996.
Complementaria
- Gerard Tel, Introduction to
Distributed Algorithms, Cambridge University Press,
1994.Prentice
Hall
- Bernstein, P. and Hadzilacos, V. and Goodman, N, Concurrency Control and Recovery in
Database Systems, Addison-Wesley, 1986.
- Andrew Tanenbaum, Distributed
Systems: Principles and Paradigms, Prentice Hall, 2002.
- George Coulouris, Jean Dollimore, Tim
Kindberg, Distributed Systems
- Concepts and Design, Addison-Wesley, 2001.
- David Peleg, Distributed Computing: A Locality-Sensitive
Approach, SIAM, Philadelphia, PA, 2000.
- Vijay K. Garg, Elements of Distributed Computing,
John Wiley & Sons, 2002.
- Shlomi Dolev, Self-stabilization, MIT Press,
2000.
Regresar a Contenido
Regresar a Contenido
- Distributed
Algorithms por Hagit Attiya, Technion
- Time
por Hagit Attiya, Technion
- 6.852
Distributed Algorithms por Nancy Lynch, MIT
- CPSC
629, Analysis of Algorithms por Jennifer Welch, Texas A&M
- CSC
2415 - Advanced topics in distributed computing. por Vassos
Hadzilacos, Toronto
- CS176: multiprocessor
synchronization por Maurice Herlihy, Brown University
- Comp
232, Real-time Systems por James Anderson, U. North Carolina at
Chapel Hill
- Models Of
Computation por John E. Savage, Brown University. Curso
básico de fundamentos de la Computación a
nivel
licenciatura
Regresar a Contenido
- Software Package of
Distributed Algorithms
- VEDA
simulador orientado al desarrollo de algoritmos distribuidos
- LaTeX: procesador de
palabras profesional ideal para escribir documentos
técnicos
- emacs :editor
profesional ideal para escribir en LaTeX
- D.Knuth, T.Larrabee, P. Roberts, "Mathematical writing",
Mathematical
Association of America, Notes Number 14, Mathematical Association of
America,
1989. Buen libro que describe la manera en que un
científico
computacional debe escribir
- S.Krantz, "A primer of mathematical writing: being a disquisition
on
having your ideas recorded, typeset, published, read &
appreciated",
AMS Press 1997. Referencia excelente sobre escritura en
matemáticas, no solo para ciencia de la
computación
Regresar a Contenido
El curso se evalua mediante tareas y uno o
dos
examenes.
Las tareas se asignan aproximadamente cada dos semanas, y consisten en
resolver problemas y lecturas complementarias (no
programación).
Las tareas pueden entregarse
en equipos de dos o individualmente. El examen se basa en los
problemas de las tareas principalmente.
Regresar a Contenido
Profesor:
Regresar a Contenido
rajsbaum@matem.unam.m
Última
modificación:
junio 16, 2004