Sistemas Distribuidos

Primavera 2021

Presentación

15-440 es un curso de introducción a los sistemas distribuidos. Se hará hincapié en las técnicas para crear sistemas distribuidos funcionales, utilizables y escalables. Para concretar los temas, la clase incluye varios proyectos de varias semanas que requieren un diseño e implementación significativos

Los objetivos de este curso son dos. En primer lugar, que los estudiantes adquieran una comprensión de los principios y técnicas que subyacen al diseño de sistemas distribuidos, como el bloqueo, la concurrencia, el almacenamiento en caché, la precarga, la programación y la comunicación a través de la red. En segundo lugar, para que los estudiantes adquieran experiencia práctica en el diseño, implementación y depuración de sistemas distribuidos reales.

Los principales temas que este curso enseñará incluyen:

• Escasez de recursos, programación, y concurrencia
• Latencia y ancho de banda de las comunicaciones
• Nombramiento
• Abstracción y modularidad
• Comunicación imperfecta y otros tipos de fallos
• Protección contra daños accidentales y maliciosos
• Optimismo
• Consenso
• Uso de instrumentación, monitorización y herramientas de depuración en la resolución de problemas.
• Diseño, implementación y depuración de proyectos de programación sustanciales que abarquen los temas anteriores

Calificación

Todo el trabajo del curso se realiza de forma individual. No hay equipos ni compañeros de proyecto. Para las ofertas presenciales de este curso (pre-COVID y, con suerte, post-COVID) la evaluación se basó en proyectos (45%), conjuntos de problemas (20%), examen parcial (15%) y examen final (20%). Para la oferta de primavera de 2021 del curso, debido a las limitaciones de COVID, los exámenes se sustituyen por conjuntos de problemas acumulativos. Estos son como los exámenes a libro abierto, pero sin la presión del tiempo. Como su nombre indica, incluyen todo el material cubierto en clase hasta ese momento. A los demás conjuntos de problemas los denominamos conjuntos de problemas temáticos, ya que se centran en temas. Así pues, la evaluación de primavera de 2021 será la siguiente (todas las ponderaciones son aproximadas, dentro de un rango del 5%):

• 45% para 4 proyectos, igualmente ponderado
• 20% para 4 conjuntos de problemas tópicos, igualmente ponderado
• 15% para el conjunto de problemas acumulativos de mitad de semestre
• 20% para el conjunto de problemas acumulativos finales.

Resultados de aprendizaje

Esperamos que los estudiantes obtengan una comprensión profunda, fluidez en el razonamiento y habilidades de implementación práctica de los siguientes conceptos de sistemas centrales en sistemas distribuidos:

1. • Comunicación y llamada a procedimientos remotos
   • Semántica de control y limitaciones del lenguaje
   • Exactamente una vez, como máximo una vez, at-least-once
   • Serialización y de-serialización
   • Argumentación end-to-end y su aplicación a sistemas reales
   • Integración con threading
   • Concurrencia de operaciones
2. • Caché de datos y semántica one-copia
   • Protocolos de consistencia de la caché y compensaciones de implementación
   • Orígenes de la localidad temporal y espacial
   • Métricas de calidad de la caché
   • Protocolos de consistencia específicos de la aplicación
   • Prefetching: beneficios y riesgos
   • Extracción de pistas
   • Buffer bloat
3. Fallos en sistemas distribuidos: orígenes y estudios empíricos
4. Fallos rápidos y fallos bizantinos
5. Límites fundamentales de la resiliencia a fallos
6. • Tolerancia a fallos: transacciones atómicas; propiedad ACID
   • Desafíos de implementación
   • Sombra, listas de intenciones y registro de escritura anticipada
   • Diferencias en el registro físico y el registro de operaciones
   • Transacciones anidadas
   • Transacciones distribuidas
7. • Consenso y blockchain: unanimidad (commit en dos fases)
   • Mayoría (elección del líder, Paxos)
   • Bizantina (single-shot y Dolev-Strong)
   • Replicación de máquinas de estado y Streamlet
   • Bitcoin

8. Paradigmas de programación comunes como Map-Reduce, MPI y GraphLab

9. (Sólo si el tiempo lo permite):
   • Conseguir alta disponibilidad: preservación basada en la votación de la semántica de una copia
   • Taxonomía de estrategias de replicación: enfoques pesimistas y optimistas
   • Conflictos de lectura-escritura y escritura-escritura
   • Estrategias servidor-cliente y peer-to-peer
   • Caché y operación desconectada; resolución de conflictos
   • Aprovechamiento del bajo ancho de banda para mejorar la disponibilidad

Logística del curso

Profesores

Nombre	Horas de oficina	Oficina	Teléfono	Andrew email
Mahadev Satyanarayanan (Satya)	Martes 1:00 – 3:00 pm	GHC-9123	x8-3743	satya
Padmanabhan Pillai (Babu)	Miércoles 11:00 am – 1:00 pm	GHC-9232		pspillai
Runting Shi (Elaine)	Lunes 4:00 – 6:00 pm	CIC-2217		Contactar a través de Canvas

Asistentes de cátedra

Nombre	Horas de oficina	Andrew email
Nathan Ang	Thu 2:00-4:00 pm	nathanan
Junwon Chang (Joseph)	Sábado 9:00-11:00 am	junwonc
Wenxin Ding (Freda)	Viernes 10:00-12:00	wenxind
Timothy Ganger	Sábado 4:00-6:00 pm	tganger
Ziying He	Viernes 5:00-7:00 pm	ziyingh
Roger Iyengar	Sábado 1:00-3:00 pm	raiyenga
Ishaan Jaffer	Thu 4:00-6:00 pm	ijaffer
Ibnul Jahan	Tue 4:00-6:00 pm	iej
Chen Jin (Crystal)	Viernes 8:00-10:00	chenj
Yajin Li	Lunes 10:00-12:00 pm	yajinl
Diego San Miguel	Viernes 2:00-4:00 pm	dsanmigu
Riccardo Santoni	Lunes 8:00-10:00 pm	rsantoni
Yiwen Song (Victor)	Thu 9:00-11:00 pm	yiwenson
Haithem Turki	Miércoles 3:00-5:00 pm	hturki
Clarissa Xu	Miércoles 6:30-8:30 pm	csxu

Clases

• Martes y jueves, 10:40 am – 12:00 noon
• Enlaces de zoom y grabaciones de vídeo: En la página de Canvas de este curso
• No hay clase: Martes 23 de febrero (Día de Receso), Jueves 15 de abril (Carnaval de Primavera)
• Última clase: Jueves 6 de mayo

Recitaciones

• Hora: miércoles 7:00 – 7:50pm (Sección A), 8:00 – 8:50pm (Sección B)
• Enlaces de zoom y grabaciones de video: En la página de Canvas de este curso

Apuntes del curso

Se colocarán en el área de AFS del curso en: /afs/andrew/course/15/440/classnotes después de cada clase.Estos apuntes son para su uso personal. Por favor, no los distribuya.

Libros de texto y lecturas opcionales

No hay libros de texto obligatorios. Aquí hay tres buenas referencias para usar como lectura opcional:

• «Distributed Systems: Principles and Paradigms» de Andrew S. Tanenbaum y Maarten Van Steen, Tercera (2017) Edición, Prentice Hall
• «Guide to Reliable Distributed Systems» de Kenneth P. Birman, Springer
• «Foundations of Distributed Consensus and Blockchains» de Elaine Shi (2020, Libro manuscrito)

Además, en el enlace «Lecturas» de la parte superior de esta página web hay algunas lecturas opcionales específicas que mencionaremos en diferentes momentos de las clases. Los pdf’s de estas lecturas opcionales están disponibles en la página web de este curso.

Políticas del curso

Requisitos previos

Debido a que este curso tiene un gran componente de proyectos, debe ser competente en programación C y Java en sistemas UNIX. Se requiere que usted haya tomado 15-213 y obtenido una «C» o superior ya que muchas de las habilidades de programación que necesitará se enseñan en ese curso. Si usted recibió una C en 15-213, debe reunirse con su asesor académico para discutir sus antecedentes antes de tomar 15-440, tal vez tomando un curso adicional para afinar sus habilidades de sistemas.

Política de Integridad Académica

La Política de Integridad Académica de la Universidad Carnegie Mellon se aplica a este curso. Se espera que todos los estudiantes revisen cuidadosamente esta política y se adhieran a ella para todos los aspectos de este curso.

Orientación sobre la colaboración:

• Se anima a los estudiantes a hablar entre ellos, con los TAs, con los instructores, o con cualquier otra persona sobre cualquiera de las tareas. Cualquier ayuda, sin embargo, debe limitarse a la discusión del problema y a esbozar enfoques generales para una solución.
• Cada estudiante debe escribir sus propias soluciones a los conjuntos de problemas. Todos los proyectos deben hacerse individualmente.
• Está prohibido consultar la solución de otro estudiante, y las soluciones presentadas no pueden ser copiadas de ninguna fuente. Estas acciones constituyen una trampa.
• Si tiene alguna duda sobre si alguna actividad constituye una trampa, no dude en preguntar a los instructores.

Orientación para compartir: Usted no puede suministrar el trabajo que complete durante el 15-440 a otros estudiantes en futuras instancias de este curso o para su uso en futuras instancias de este curso (al igual que usted no puede utilizar el trabajo completado por los estudiantes que han tomado el curso anteriormente).

Grabaciones

Para la primavera de 2021, las sesiones de Zoom de cada conferencia y recitación serán grabadas por los Servicios de Computación de CMU y publicadas en la página de Canvas para este curso. Todas las demás grabaciones están prohibidas.

Límite en el uso del tiempo del TA

Para ser justos con todos, especialmente cuando hay una larga fila de estudiantes esperando la atención de un TA, habrá un límite de 10 minutos en todas las consultas. Si un estudiante no ha terminado al final de los 10 minutos, vuelve al final de la fila antes de conseguir más tiempo con el TA. Prepárate antes de reunirte con un TA. Si necesita ayuda para encontrar un error, reduzca y simplifique el problema antes de reunirse con el TA.

Política de Piazza

Este curso utiliza el sitio web Piazza para responder a las preguntas: aquí está la página de Piazza para este curso.

Piense en piazza como si levantara la mano en clase y formulara una pregunta. Ninguna pregunta es demasiado estúpida, así que no tengas miedo. Por cada persona que hace una pregunta, probablemente hay muchas otras a las que ya les ha surgido la misma pregunta o les surgirá pronto. La respuesta a tu pregunta puede beneficiarles a ellos también. Además, puede haber algunas personas a las que no se les haya ocurrido su pregunta. Al hacer la pregunta, les ayudas a ver una sutileza que quizá no hayan visto antes. Los correos electrónicos directos a los instructores no serán contestados.

En todo momento, esperamos que uses tu buen juicio en tus publicaciones en Piazza (tanto en las preguntas como en las respuestas a las preguntas de los compañeros). Parte del proceso de aprendizaje consiste en esforzarse con el material hasta llegar a la visión correcta para entenderlo. Publicar demasiados detalles en respuesta a una solicitud de ayuda puede perjudicar el aprendizaje. Por otro lado, a veces es estupendo que te den un empujón en la dirección correcta cuando no eres capaz de salir de un atolladero. Y, por supuesto, los malentendidos sobre la tarea o las herramientas disponibles deben ser ayudados rápidamente. Por favor, utilice su mejor criterio al publicar en el sitio de Piazza, como si estuviera colaborando con sus amigos en persona. Algunas pautas aproximadas:

Ejemplos de cosas buenas para publicar y responder:

• Misunderstandings de la asignación
• Clarificaciones sobre los requisitos
• Bugs en la especificación de la asignación o la implementación de referencia o las pruebas
• Preguntas pequeñas y detalladas sobre el funcionamiento de las llamadas al sistema, funciones, etc.
• Cosas que parecen ir en un FAQ para la asignación

Ejemplos de cosas malas para publicar o responder:

• Más de unas pocas líneas de código
• Explicaciones en profundidad de cómo funciona su sistema
• Preguntas sobre el mejor enfoque para la arquitectura del sistema a alto nivel
• Preguntas sobre su calificación

Esperamos que haya hecho un esfuerzo razonable para pensar por sí mismo antes de publicar una pregunta de piazza. Esto es especialmente cierto con respecto a la depuración de su código. ¿Probó las páginas del manual? ¿Hizo una búsqueda en Google de recursos posiblemente relevantes? ¿Has mirado las preguntas anteriores que la gente ya ha hecho, y las respuestas que se han dado? ¿Insertaste printf’s y trataste de entender lo que está pasando con tu código?

No uses autolab como una herramienta de depuración. Esperamos que hayas hecho un esfuerzo razonable para depurar tu código antes de enviarlo a autolab. La creación de casos de prueba y las pruebas de estrés de su código es parte de lo que es un proyecto. Si no haces ese esfuerzo, estás perdiendo una parte importante de la oportunidad de aprendizaje en el curso. El envío al autolab debería ser el último paso de un proceso en el que has probado, depurado y mejorado tu código hasta el límite de tus posibilidades. Enviar un volcado de autolab en un post de piazza y decir «por favor, ayuda» es una violación atroz de la etiqueta de piazza.

No se admiten posts privados en Piazza. Esta es una decisión de política para esta clase. Recuerde que publicar en piazza es similar a levantar la mano y hacer una pregunta. Los demás estudiantes se benefician de tu pregunta y de la respuesta del profesor. Permitimos que tus mensajes sean anónimos para tus compañeros, si así lo deseas. Eso ya es un grado de privacidad más allá de lo que es posible cuando se hace una pregunta en clase. Para las raras ocasiones en las que necesite hacer una petición privada que no esté relacionada con el contenido del curso, se ha creado una lista de correo privada especial.

Para las peticiones que realmente necesitan ser privadas, envíe un correo electrónico a[email protected]y uno de los instructores le responderá. Los correos electrónicos a esta lista que tengan que ver con el contenido del curso (por ejemplo, aclaraciones al material de la clase) serán ignorados; usted debe publicar tales preguntas en Piazza.

Política sobre las entregas tardías

Para los proyectos:

• Cada estudiante dispondrá de cinco días de retraso a lo largo del semestre. Estos días de retraso están pensados para tener en cuenta las vacaciones, los viajes, las entrevistas, un resfriado y otras situaciones similares. Usted es libre de utilizarlos por cualquier motivo, sin pedir permiso a los instructores. Puede utilizar como máximo dos días de retraso en cualquier fecha de vencimiento (es decir, para proyectos con múltiples puntos de control, puede utilizar hasta dos días de retraso para cada punto de control). Los días de retraso se aplicarán automáticamente en orden cronológico, por lo que no puede optar por aplazar el uso de un día de retraso para una tarea futura de mayor peso.

• Un día de retraso = (0,24] horas después de la fecha de vencimiento; dos días de retraso = (24, 48] horas después de la fecha de vencimiento; etc.

• Si utiliza todos sus días de retraso, puede presentar el trabajo tarde con una penalización del 15% por día, durante un máximo de dos días. En otras palabras, si ha utilizado todos sus días de retraso, todavía puede presentar los dos días siguientes, incurriendo en una penalización del 15% por cada uno de esos días (días de gracia).

• No puede combinar los días de retraso y los días de gracia para presentar más de dos días de retraso.

Para los conjuntos de problemas: No se aceptan entregas tardías, con o sin penalización. Asegúrese de presentar a tiempo.

Guía de estilo para los proyectos

Además de comprobar la funcionalidad de su código, también reservaremos una parte de los puntos de cada proyecto para su estilo y legibilidad. Lo más importante es un estilo coherente y legible. Nos interesa sobre todo que elijas un estilo legible y razonable, y que utilices el mismo estilo de forma coherente a lo largo de todo el proyecto.Utiliza el sentido común: no tengas líneas de código de 500 caracteres, no llames a tus variables foo (a menos que tenga sentido en su contexto), y evita mezclar convenciones de mayúsculas y minúsculas al azar.

Estaremos buscando las siguientes cosas:

Documentación Una buena documentación es importante: para ti mismo en el futuro, para otros mantenedores del código, y en este contexto, para los calificadores que estarán mirando tu código. No sientas la necesidad de documentar cada línea de código (ya que el buen código también debería autodocumentarse en cierto sentido), pero suele ser bueno destacar el uso general y el propósito de cada función, así como los bloques de código grandes o complejos. También es una buena práctica incluir una cabecera en cada archivo, detallando cómo encaja ese archivo en la estructura del proyecto en su conjunto. Espacios en blanco Por favor, sea coherente. Por favor, no utilices el tabulador a 2 espacios en algunos lugares y a 4 en otros. Sea razonable y utilice los espacios en blanco para que su código sea legible. Longitud de la línea Seremos razonables en cuanto a la longitud de la línea, siempre y cuando sea coherente y sus límites de línea sean razonables (500 caracteres no lo son… 80 o 120 caracteres son comúnmente utilizados y aceptados). Nombres de las variables Sus nombres de las variables deben dar una clara indicación de lo que representan o su caso de uso. Código muerto/de prueba Intente no enviar código plagado de declaraciones de impresión de depuración o grandes trozos de código comentados. Disminuye la legibilidad y distrae del código que realmente se ejecutará en producción. Diseño Intente diseñar su código y sus proyectos de manera que sean razonablemente modulares. Las funciones de 5000 líneas son generalmente un signo de mal diseño y le darán dolores de cabeza más adelante.

Aquí hay una guía de estilo de Google que puede ser útil.

Bienestar

Aquí hay algunos consejos para el bienestar.