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

Octavo Semestre, Computación Concurrente

La presentación del curso se efectuará el Lunes 8 de Agosto del 2016 a las 16:00 hrs. Se proporcionarán las indicaciones para ingresar al sitio que se servirá como apoyo para este curso:

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

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. Modelos de cómputo y 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. Propiedades de justicia
4. Recursos múltiples
   1. Prevención e impedimento de abrazos mortales
   2. El problema de los filósofos comensales
   3. Propiedades de robustez y concurrencia
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

• 7 u 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. En su momento se determinará si la modalidad de reposiciones es oral o escrita. En su defecto, se puede presentar un examen final, con el cual se renuncia a las calificaciones 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 impresa la forma de evaluación y las normas adicionales mencionadas firmadas de conformidad a más tardar el 23 de Agosto de 2016, para tener derecho a calificación.

La única forma de que se asigne NP como calificación a un(a) alumno(a) es que no entregue nada. La falta de entrega de las normas adicionales implica la asignación automática de NP.

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

Referencias

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

[2] M. Raynal. Concurrent Programming: Algorithms, Principles, and Foundations. Springer-Verlag, 2013.

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

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

[5] 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 cuatro últimas referencias, así como de artículos que en su momento se indicarán.