Sistemas distribuidos de gran escala

Anuncios

Recuerden chequear esto regularmente

Fechas

Del 18 de Junio al 13 de Julio, 2012.

Descripción del Curso

Durante la última década hemos presenciado el crecimiento explosivo de sistemas distribuidos de gran escala, con cientos, miles o millones de usuarios conectados. Desde telefonía y televisión sobre IP hasta juegos online y redes sociales, estas aplicaciones se han movido con vertiginosa velocidad de narrativas de ciencia ficción y bosquejos de diseño a componentes asumidos de nuestro contexto diario. La creciente inter-conexión y la capacidad potencialmente ilimitada de nuestros dispositivos computacionales han redefinido el “borde” de la red de estos sistemas, de universidades y laboratorios de investigación, a nuestras casas, autos y bolsillos. Este curso revisa ideas y proyectos investigando las implicaciones de estos cambios “demográficos”, incluyendo los retos que presentan a nuestras ideas sobre el diseño, implementación y evaluación de sistemas distribuidos. El objetivo principal del curso es prepararlos para hacer investigación en el área general de sistemas distribuidos y redes; con esto en mente, el curso cubre también temas generales tales como formas de leer y presentar artículos, la generación, critica, y comunicación de ideas de investigación, comunidades y sus conferencias, etc.

Programa

  1. Introducción a sistemas distribuidos — Definición, caracterización, ejemplos, retos.
  2. Modelos de sistemas — Modelos de arquitectura, modelos fundamentales incluyendo sincronización, fallas y seguridad.
  3. Arquitectura de la Internet — Arquitectura y detalles operacionales, protocolos.
  4. Comunicación y coordinación de procesos — RPC, RMI, eventos y notificaciones, comunicación grupal.
  5. Medición y experimentación — Plataformas, aspectos temporales, mediciones a través de protocolos.
  6. Nombrando y encontrando cosas — Nombres, identificadores y direcciones, servicios de nombre, directorios, usos y mal usos.
  7. Sincronización y estados globales — Relojes, eventos y estados de procesos, sincronización, estado global y depuración distribuida
  8. Acuerdos y coordinación — Exclusión mutua, elecciones, consenso.
  9. Tolerancia a fallas — Replicación, servicios tolerantes a fallas.
  10. Privacidad y seguridad

Carga horaria

8 horas semanales, por 4 semanas (32hr); dos clases de tres horas y una practica de dos horas

Materias correlativas

  • Sistemas operativos

Canales de comunicación

Hay un numero de canales de comunicación disponibles:

  • Usamos el sitio de web del curso para publicar trabajos, artículos para leer, anuncios relacionados, etc. Visiten esto regularmente.
  • Usamos un Google Group (SDGE en UBA 2012) para discusiones y anuncios. Este canal esta dedicado a fomentar la discusion, particularmente entre ustedes. Si aun no tienen una subscripción, pueden pedir una: Email:
  • Finalmente, siempre esta la opción de email para preguntas que consideren inapropiadas para el grupo. Por favor incluyan "SDGE:Algún comentario descriptivo." en el sujeto del email para asegurarse que no se pierdan en mi inbox.

Bibliografía

Lista de artículos provista por el profesor.

Formas de evaluación

Reportes semanales, presentación y trabajos prácticos. La calificación en el curso será función de (i) la participación en las clases, (ii) la presentación de resúmenes escritos cortos (menos de una pagina de largo) de tres artículos de la bibliografía (iii) presentación oral de un articulo al resto de la clase y (iv) un trabajo practico.

Los tres primeros requerimientos sirven principalmente para asegurar la involucración plena del estudiante con el material discutido. Los resúmenes y la presentación de un articulo también buscan servir como ejercicios de refuerzo para algunos de los “meta-temas” discutidos en clase tal como la lectura y presentación de artículos de investigación.

El trabajo practico o de laboratorio busca introducir al estudiante a alguno de los retos de la investigación en el área. Dado el numero limitado de horas disponibles, el trabajo se centra en un proyecto conceptualmente simple (ej. analizar los traceroutes entre nodos en la Internet), desarrollado en un ambiente real como es PlanetLab.

Modelo general para cada clase

Presentación del tema de la clase 40'
Descanso 10'
2x Presentación y discusión de una articulo de investigación 40' c/u; 85'
Descanso 10'
Presentación de un meta-tema (ej. “Como leer artículos de investigación”) 35'
Total 180'

Plan detallado

Tema 1 — Junio 18

  • Introducción a sistemas distribuidos (Slides)
  • Leyendo artículos de investigación — reconociendo buenas ideas (Slides)

Tema 2 — Junio 25

  • Modelos de sistemas (Slides)
  • Escribiendo sumarios de artículos de investigación

Temas 3 y 4 — Junio 27

  • Comunicaciones y arquitectura de Internet (Slides)
  • Presentando artículos de investigación

Tema 5 — Julio 2

  • Mediciones y experimentación (Slides)
  • Generando buenas ideas de investigación

Tema 6— Julio 4

  • Nombrando y encontrando cosas (Slides)

Tema 7— Julio 6

  • Sincronización y estado global
  • Criticando ideas

Temas 8 y 9 — Julio 9?

  • Coordinación y tolerancia a fallas

Tema 10 — Julio 11

  • Privacidad, censura y seguridad
  • Maestrías, doctorados y post-doctorados en USA

Lista de artículos

Lo que sigue es la lista final de artículos a discutir. Para presentación los estudiantes pueden seleccionar, en orden de llegada, cualquiera de los artículos en la lista principal (no adicionales).

  1. Characterizing distributed systems

    1. Rethinking the Design of the Internet: The End-to-End Arguments vs. the Brave New World. M. Blumenthal and D. Clark. ACM Transactions on Internet Technology, 1(1):70-109, August 2001.
    2. Fallacies in Evaluating Decentralized Systems. A. Haeberlen, A. Mislove, A. Post and P. Druschel. In Proc. of IPTPS, 2006. (Slides)

    Additional reading

    1. Fallacies of Distributed Computing Explained. A. Rotem-Gal-Oz. Whitepaper.
    2. Distributed Computing Economics. J. Gray. Tech. Report, MSR-TR-2003-24, March 2003.
    3. Tussle in Cyberspace: Defining Tomorrow’s Internet. D. Clark et al. In Proc. of SIGCOMM, 2002.
    4. You and Your Research. R. Hamming. Transcriptions of the Bell Communications Research Colloquium Seminar, March 7, 1986.
  2. Systems models (client-server, p2p, hybrid, synchronous/asynchronous, …)

    1. Reliable Client Accounting for Hybrid Content-Distribution Networks. P. Aditya, M. Zhao, Y. Lin, A. Haeberlen, P. Druschel, B. Maggs and B. Wishon. In Proc. of NSDI 2012. (Slides)
    2. On Blind Mice and the Elephant - Understanding the Network Impact of a Large Distributed System. John S. Otto, Mario A. Sánchez, David R. Choffnes, Fabián E. Bustamante and Georgos Siganos. In Proc. of SIGCOMM 2011. (Slides)

    Additional reading

    1. The LOCKSS Peer-to-Peer Digital Preservation System. P. Maniatis, M. Roussopoulos, J Giuli, D. Rosenthal and M. Baker. ACM TOCS, 23(1), February 2005.

  3. Communication and coordination (rpc, rmi, pub/sub) and Internet architecture (perspective/directions, Internetworking, trends on Internetworking, new architectures)

    1. Internet Inter-Domain Traffic. C. Labovitz, S. Lekel-Johnson, D. McPherson, J. Oberheide and F. Jahanian. In Proc. of SIGCOMM, 2010. (Slides)
    2. RPC Chains: Efficient Client-Server Communication in Geodistributed Systems. Y. Song, M. Aguilera. R. Kotla and D. Malkhi. In Proc. of NSDI, 2009.

    Additional reading

    1. SAAR: A Shared Control Plane for Overlay Multicast. A. Nandi, A. Ganjam, P. Druschel, T.S. Eugene Ng, I. Soica, H. Zhang and B. Bhattacharjee. In Proc. of NSDI, 2007.
    2. Internet Indirection Infrastructure I. Stoica, D. Adkins, S. Zhuang, S. Shenker and S. Surana. IEEE/ACM TON, 12(2), April 2004.
    3. Consensus Routing: The Internet as a Distributed System. J. John, E. Katz-Bassett, A. Krishnamurthy, T. Anderson and A. Venkataramani. In Proc. of NSDI, 2008.
    4. Networking Named Content. V. Jacobson, D. Smetters, J. Thornton, M. Plass, N. Briggs and R. Braynard. In Proc. of CoNEXT, 2009.
  4. Measurements and experimentations

    1. Broadband Internet Performance: A View From the Gateway. S. Sundaresan, W. de Donato, N. Feamster, R. Teixeira, S. Crawford and A. Pescap. In Proc. of SIGCOMM, 2011.
    2. SatelliteLab: Adding Heterogeneity to Planetary-Scale Network Testbeds. Marcel Dischinger, Andreas Haeberlen, Ivan Beschastnikh, Krishna P. Gummadi and Stefan Saroiu. In Proc. of SIGCOMM, 2008.
    3. Web Content Cartography. B. Ager, W. Muhlbauer, G. Smaragdakis and S. Uhlig. In Proc. of IMC, 2011. (Best paper)

    Additional reading

    1. Netalyzr: Illuminating the Edge Network. C. Kreibich, N. Weaver, B. Nechaev and V. Paxson. In Proc. of IMC, 2010.
    2. Using PlanetLab for Network Research: Myths, Realities and Best Practices. N. Spring, L. Peterson, A. Bavier and V. Pai.
 ACM SIGOPS OSR, 40(1), January 2006.
    3. Reverse Traceroute. E. Katz-Bassett, H. Madhyastha, V. Adhikari, C. Scott, J. Sherry, P. van Wesep, T. Anderson and A. Kirshnamurthy. In Proc. of NSDI, 2010.
    4. Strategies For Sound Internet Measurements. 
S. Paxon. 
In Proc. of IMC, 2004.
  5. Naming and finding things

    1. The Design and Implementation of a Next Generation Name Service for the Internet. V. Ramasubramanian and E. Gun Sirer. In Proc. of SIGCOMM, 2004.
    2. A Layered Naming Architecture for the Internet. H. Balakrishnan, K. Lakshminarayanan, S. Ratnasamy, S. Shenker, I. Stoica and M. Walfish. In Proc. of SIGCOMM, 2004.

    Additional reading

    1. Comet: An active distributed key-value store. R. Geambasu, A. Levy, T. Kohno, A. Krishnamurthy and H. Levy, In Proc. of OSDI, 2010.
  6. Synchronization and global state

    1. D3S: Debugging Deployed Distributed Systems. X. Liu, Z. Guo, X. Wang, F. Chen, X. Lian, J. Tang, M. Wu, M. Frans Kaashoek and Z. Zhang. In Proc. of NSDI, 2008.
    2. CrystalBall: Predicting and Preventing Inconsistencies in Deployed Distributed Systems. M. Yabandeh, N. Knezevic, D. Kostic, and V. Kuncak. In Proc. of USENIX NSDI, 2009.

    Additional reading

    1. Improving Content Delivery Using Provider-Aided Distance Information. I. Poese, B. Frank, B. Ager, G. Smaragdakis and A. Feldmann. In Proc. of IMC, 2010.
  7. Agreement, coordination, and fault tolerance

    1. Scalable Consistency in Scatter. L. Glendenning, I. Beschastnikh, A. Krishnamurthy and T. Anderson. In Proc. of SOSP, 2011.
    2. Zookeeper: Wait-free Coordination for Internet-scale Systems. P. Hunt, M. Konar, F. Junqueira, and B. Reed. In Proc. of USENIX ATC, 2010.

    Additional reading

    1. Making Byzantine Fault-Tolerant Systems Tolerate Byzantine Faults. A. Clement, E. Wong, L. Alvisi, M. Dahlin, and M. Marchetti. In Proc. of NSDI, 2009.
    2. Depot: Cloud storage with minimal trust. P. Mahajan, S. Setty, A. Clement, L. Alvisi, M. Dahlin and M. Walfish. In Proc. of OSDI, 2010.
    3. FUSE: Lightweight Guaranteed Distributed Failure Notification. J. Dunagan, N. Harvey, M. Jones, D. Kostic, M. Theimer and A. Wolman. In Proc. of OSDI, 2004.
  8. Privacy and security

    1. I Know Where You Are and What You Are Sharing: Exploiting P2P Communications to Invade Users' Privacy. Stevens Le Blond, Chao Zhang, Arnaud Legout, Keith Ross, Walid Dabbous. In Proc. of IMC, 2011.
    2. Measuring Pay-per-Install: The Commoditization of Malware Distribution. J. Caballero, C. Grier, C. Kreibich, and V. Paxson. In Proc. of USENIX Security, 2011.

    Additional reading

    1. Telex: Anticensorship in the Network Infrastructure
. E. Wustrow, S. Wolchok, I. Goldberg, J. Alex Halderman. In Proc. of USENIX Security, 2011.
    2. Vanish: Increasing Data Privacy with Self-Destructing Data. R. Geambasu, T. Kohno, A. Levy and H. Levy. In Proc. of USENIX Security, 2009.
    3. Defeating Vanish with Low-Cost Sybil Attacks Against Large DHTs. S. Wolchok, O. Hofmann, N. Heninger, E. Felten, J. Halderman, C. Rossbach, B. Waters and E. Witchel. In Proc. of NDSS, 2010.

Labs

Proximamente.