Ciencias de la Computación (plan 2013) 2016-1

Octavo Semestre, Computación Concurrente

La presentación se efectuará el Lunes 10 de Agosto a las 16:00 horas y el sitio de apoyo al curso puede ser accedido por alumnos inscritos mediante el siguiente enlace:

https://sites.google.com/site/computacionconcurrente/home

Objetivo

Contenido del curso

1. Fundamentos
   1. Computación concurrente y distribuida
   2. Procesos y tipos de sincronización
   3. Hilos de ejecución y calendarización de procesos
   4. Medidas de complejidad
2. El problema de exclusión mutua
   1. Propiedades de algoritmos
   2. Espera ocupada
   3. Algoritmos adaptivos
   4. Tolerancia a fallas
3. Primitivas de sincronización
   1. Atomicidad
   2. Impedimento de colisiones
   3. Primitivas fuertes de sincronización
   4. Estructuras de datos concurrentes
   5. Justicia
4. Recursos múltiples
   1. Prevención e impedimento de abrazos mortales
   2. El problema de los filósofos comensales
5. Problemas clásicos de sincronización
   1. Productores y consumidores
   2. Lectores y escritores
   3. El barbero dormilón
   4. El fumador de cigarrillos
6. Problema del consenso
   1. Deficiones y variantes del problema
   2. Modelos de cómputo y algoritmos
   3. Resultados de imposibilidad
   4. El poder relativo de las primitivas de sincronización
   5. Universalidad del consenso
7. Temas selectos
   1. Intercambio de mensajes
   2. Fallas bizantinas

Evaluación

• 8 Tareas 50%
• 3 Exámenes 20%
• 7 Prácticas 30%
• Asistencias +/- 10%

Las tareas consisten de ejercicios para reforzar el material visto en clases o ayudantías, así como resúmenes y trabajos de investigación. Pueden efectuarse a mano o a máquina pero la entrega es impresa. Las tareas pueden presentarse de forma individual o en equipos de hasta dos personas y las fechas de entrega son estrictas, salvo por causas de fuerza mayor que sean comprobables documentalmente.

Los exámenes requieren del reconocimiento y la comprensión de conceptos teóricos, así como del análisis de procesos descritos en pseudocódigo. Se presentan de forma individual y en fecha única, salvo por causas de fuerza mayor que sean comprobables documentalmente.

Las prácticas consisten de la implementación de algoritmos para los problemas estudiados durante el curso, así como de algunas simulaciones. Se utilizará Java como lenguaje de programación base y se introducirá el uso de otros lenguajes con bibliotecas para el soporte de concurrencia. Los lineamientos de entrega de prácticas por correo se definirán en la primera sesión de laboratorio. Las prácticas pueden entregarse de manera individual o en equipos de dos personas y una vez establecida la fecha de entrega, se cuenta con un máximo de cuatro días adicionales para efectuar la entrega, incurriendo en una penalización de dos puntos por día de retraso a partir de la fecha estipulada.

Ocasionalmente se pasará lista en sesiones de clase, ayudantía o de laboratorio. Dependiendo de cómo sea el número de asistencias registradas con respecto al de inasistencias se asignará a cada alumno(a): un incremento de puntuación si el primer número es superior al segundo, un decremento si el primer número es inferior y cero si ambos números son iguales. En particular, si un(a) alumno(a) tiene todas las asistencias, obtendrá un punto adicional sobre la calificación final obtenida y en caso de que no tenga ninguna asistencia registrada, perderá un punto a partir de dicha calificación.

Normas adicionales sobre la evaluación

Se puede presentar la reposición de ejercicios correspondientes a dos tareas, o bien, un examen final, con el cual se renuncia a las calicaciones obtenidas en las tareas y exámenes. En este caso, la evaluación considera los siguientes rubros:

• Examen final 70%
• Prácticas 30%

Cada alumno(a) debe entregar la forma de evaluación y las normas adicionales mencionadas firmadas de conformidad a más tardar dos semanas después del día que comienza el semestre, para tener derecho a calificación.

La única forma de que se asigne NP como calicacion a un(a) alumno(a) es que no entregue nada, en particular, la firma de conformidad de la forma de evaluación del curso.

No se puede renunciar a la calificación final.

Referencias

[1] G. Taubenfeld. Synchronization algorithms and concurrent programming. Prentice Hall, 2006.

[2] M. Herlihy y N. Shavit. The Art of Multiprocessor Programming. Morgan Kaufmann, 2008.

[3] N. Lynch. Distributed Algorithms. Morgan Kaufmann, 1996.

[4] H. Attiya y J. Welch Distributed Computing: Fundamentals, Simulations and Advanced Topics. Morgan Kaufmann, 1998.

Aclaraciones sobre las referencias

Usaremos la primer referencia como texto para el curso y de forma complementaria nos apoyaremos en las tres últimas referencias, así como de artículos que en su momento se indicarán.