Papers y bibliografía

La materia funciona como un club de lectura técnico: cada clase se apoya en una fuente primaria que se espera leída de antemano. Esta es la lista completa de lecturas del calendario, agrupada por eje temático, y al final lo que las clases mencionan sin asignarlo. La práctica 1 tiene su propia bibliografía.

Si es tu primera vez leyendo papers de sistemas, empezá por How to Read a Paper de Keshav. El método de las tres pasadas que propone ahorra muchísimo tiempo.

Ejes

• Fundamentos y método
• Compute
• Storage, replicación y consenso
• Stream processing y mensajería
• Consenso descentralizado
• Mencionados en clase

Fundamentos y método

• How to Read a Paper
  S. Keshav · se discute en la clase 1
  El método de las tres pasadas. Conviene leerlo antes que cualquier otro.
• Principles of Computer System Design: An Introduction · libro
  Jerome H. Saltzer y M. Frans Kaashoek · se discute en la clase 1
  Caps. 2.1, 4.1 y 4.2. De acá sale el marco de las tres abstracciones —memoria, intérpretes, enlaces— y la organización cliente-servicio.
• Linearizability: A Correctness Condition for Concurrent Objects
  Maurice Herlihy y Jeannette Wing · se discute en la clase 7
• Time, Clocks, and the Ordering of Events in a Distributed System
  Leslie Lamport · se discute en la clase 8
• Designing Data-Intensive Applications · libro
  Martin Kleppmann · se discute en las clases 3, 13 y 14
  Cap. 5, pp. 152–161, sobre replicación; cap. 11, pp. 439–451, sobre mensajería, y pp. 464–479, sobre procesamiento de streams.
• Distributed Systems: Concepts and Design (5.ª ed.) · libro
  George Coulouris, Jean Dollimore, Tim Kindberg y Gordon Blair · se discute en las clases 8 y 13
  Caps. 14.1 a 14.4, sobre tiempo y relojes; caps. 6.1, 6.3 y 6.4, sobre comunicación indirecta.

Compute

• MapReduce: Simplified Data Processing on Large Clusters
  Jeffrey Dean y Sanjay Ghemawat · se discute en la clase 2

Storage, replicación y consenso

• Chain Replication for Supporting High Throughput and Availability
  Robbert van Renesse y Fred B. Schneider · se discute en la clase 3
• The Google File System
  Sanjay Ghemawat, Howard Gobioff y Shun-Tak Leung · se discute en la clase 4
• In Search of an Understandable Consensus Algorithm (Raft)
  Diego Ongaro y John Ousterhout · se discute en las clases 5 y 6
  Se ve en dos clases: elección de líder primero, log y snapshots después.
• ZooKeeper: Wait-free coordination for Internet-scale systems
  Patrick Hunt et al. · se discute en la clase 7
• Dynamo: Amazon’s Highly Available Key-value Store
  Giuseppe DeCandia et al. · se discute en las clases 8 y 9
  SOSP 2007. Recibió el ACM SIGOPS Hall of Fame Award en 2017.
• Amazon DynamoDB: A Scalable, Predictably Performant, and Fully Managed NoSQL Database Service
  Mostafa Elhemali et al. · se discute en la clase 9
• Amazon DynamoDB Under the Hood: How We Built a Hyper-Scale Database · video
  AWS re:Invent 2018 (DAT321) · se discute en la clase 9
• Distributed Transactions at Scale in Amazon DynamoDB
  Joseph Idziorek et al. · se discute en la clase 10
• Spanner: Google’s Globally-Distributed Database
  James C. Corbett et al. · se discute en la clase 11
• Scaling Memcache at Facebook
  Rajesh Nishtala et al. · se discute en la clase 12

Stream processing y mensajería

• The Log: What every software engineer should know about real-time data’s unifying abstraction
  Jay Kreps · se discute en la clase 3
• Kafka: a Distributed Messaging System for Log Processing
  Jay Kreps, Neha Narkhede y Jun Rao · se discute en la clase 13
• Intra-cluster Replication in Apache Kafka · video
  Apache Software Foundation · se discute en la clase 13
• MillWheel: Fault-Tolerant Stream Processing at Internet Scale
  Tyler Akidau et al. · se discute en la clase 14

Consenso descentralizado

• Bitcoin: A Peer-to-Peer Electronic Cash System
  Satoshi Nakamoto · se discute en la clase 15

Mencionados en clase

No son lectura asignada: son los trabajos que las clases citan al pasar o en las notas, como origen de una idea o para ir más lejos. Están ordenados por la clase en que aparecen por primera vez.

• A Note on Distributed Computing
  Jim Waldo, Geoff Wyant, Ann Wollrath y Sam Kendall · se menciona en las clases 1 y 2
  Sun Microsystems Laboratories, SMLI TR-94-29, 1994. Las cuatro características de la red que no se pueden esconder.
• Remote Procedure Call · tesis
  Bruce Jay Nelson · se menciona en la clase 1
  Carnegie Mellon, 1981; publicada también como Xerox PARC CSL-81-9. La primera taxonomía de semánticas de llamada.
• Performing Remote Operations Efficiently on a Local Computer Network
  Alfred Z. Spector · se menciona en la clase 1
• Implementing Remote Procedure Calls
  Andrew D. Birrell y Bruce Jay Nelson · se menciona en la clase 1
• The Datacenter as a Computer · libro
  Luiz André Barroso y Urs Hölzle · se menciona en la clase 1
• The Part-Time Parliament
  Leslie Lamport · se menciona en la clase 2
  Paxos. Circuló como reporte técnico en 1989 y se publicó en 1998.
• Paxos Made Live: An Engineering Perspective
  Tushar Chandra, Robert Griesemer y Joshua Redstone · se menciona en la clase 2
• Viewstamped Replication: A New Primary Copy Method to Support Highly-Available Distributed Systems
  Brian M. Oki y Barbara Liskov · se menciona en las clases 2 y 5
• Timestamps in Message-Passing Systems That Preserve the Partial Ordering
  Colin J. Fidge · se menciona en la clase 2
  1988. Relojes vectoriales, en paralelo con Mattern.
• Virtual Time and Global States of Distributed Systems
  Friedemann Mattern · se menciona en la clase 2
• Specifying Systems · libro
  Leslie Lamport · se menciona en la clase 2
  TLA+. Disponible gratis.
• Bigtable: A Distributed Storage System for Structured Data
  Fay Chang et al. · se menciona en las clases 2, 4 y 9
• Weighted Voting for Replicated Data
  David K. Gifford · se menciona en las clases 5 y 9
  El origen de los quórums: R + W > N.
• Session Guarantees for Weakly Consistent Replicated Data
  Douglas B. Terry et al. · se menciona en la clase 7
  Bayou. De acá salen read your writes y monotonic reads.
• The Chubby Lock Service for Loosely-Coupled Distributed Systems
  Mike Burrows · se menciona en las clases 7 y 9
• CAP Twelve Years Later: How the “Rules” Have Changed
  Eric Brewer · se menciona en la clase 8
• MapReduce: A Major Step Backwards
  David DeWitt y Michael Stonebraker · se menciona en la clase 8
  The Database Column, enero de 2008. El blog original ya no existe; el link es una copia.
• Managing Update Conflicts in Bayou, a Weakly Connected Replicated Storage System
  Douglas B. Terry et al. · se menciona en la clase 9
  Donde se acuña el término consistencia eventual.
• Epidemic Algorithms for Replicated Database Maintenance
  Alan Demers et al. · se menciona en la clase 9
  Gossip: la convergencia en orden logarítmico.
• The Notions of Consistency and Predicate Locks in a Database System
  K. P. Eswaran, J. N. Gray, R. A. Lorie e I. L. Traiger · se menciona en la clase 10
  Two-phase locking.
• Transaction Processing: Concepts and Techniques · libro
  Jim Gray y Andreas Reuter · se menciona en la clase 10
• A Majority Consensus Approach to Concurrency Control for Multiple Copy Databases
  Robert H. Thomas · se menciona en la clase 10
  La Thomas write rule.
• Concurrency Control in Distributed Database Systems
  Philip A. Bernstein y Nathan Goodman · se menciona en la clase 10
• Concurrency Control and Recovery in Database Systems · libro
  Philip A. Bernstein, Vassos Hadzilacos y Nathan Goodman · se menciona en la clase 10
• Principles of Transaction Processing · libro
  Philip A. Bernstein y Eric Newcomer · se menciona en la clase 10