CSx55: Distributed Systems

Shrideep Pallickara
Office: Room 364, CS Building
Office Hours:
1:00-2:00 pm Friday
[in-person and via Zoom]

E-mail: compsci_csx55 {aT} colostate.edu
(with the obvious change)
Tel: 970.492.4209

TTh: 9:30 - 10:45 am
Fridays: 4:00-5:00 pm
[CSB-130]

Graduate Teaching Assistants

Gabriele Maurina

Daniel Rehberg

Ethan Seefried

E-mail: compsci_csx55 {aT} colostate.edu
(with the obvious change)

Objectives:
[1] Clarify logistics
[2] Clarify expectations for the CS455 and CS555 variants of the course.

Threads vs processes, thread lifecycle, stacks and heaps, creation and management of threads, data synchronization, race conditions, intrinsic locks and reentracy. Compound actions, sharing objects and confinement, multivariable invariants and thread-safety, making a class thread-safe, multivariable invariants, adding functionality to a thread-safe class, synchronized & concurrent collections, and locking strategies.

1. Design thread safe programs that scale and leverage concurrency
2. Reason about program correctness in multi-threaded settings
   
3. Design scalable server-side programs
   

1. Explain the role topologies play in scaling and failure recovery.
2. Identify differences between topologies based on random graphs, regular graphs, power law, and small-world networks.
   
   

Peer to Peer (P2P) Systems: characteristics, P2P generations, P2P middleware and requirements.
Structured and Unstructured P2P Systems.  Time & Space complexity of P2P algorithms. Exemplar Systems: Pastry, Chord, Tapestry, Napster, Gnutella, and BitTorrent.

Objectives:

1. Explain structured and unstructured P2P systems
2. Explain bounded routing in structured P2P systems
3. Build systems based on structured P2P concepts
   

Objectives:

1. Express programs using MapReduce.
2. Design systems that push computations to the data to preserve data locality.
   
3. Design programs that leverage frameworks to scale.

Objectives:

1. Express programs using MapReduce.
2. Design systems that push computations to the data to preserve data locality.
   
3. Design programs that leverage frameworks to scale.
4. Understand the design of the Hadoop Distributed File System

Software stack, interactive shells in Spark, core Spark concepts, Resilient Distributed Datasets (RDDs), lazy evaluations, Operations:transformations & actions, Pair RDDs, dependencies and transformations, and partitioning schemes. Narrow and wide transformations.

Objectives:

1. Understand memory residency and its implications
2. Express functionality using lambda expressions
   
   

Objectives:

1. Explain differences between traditional batch-style computations and streaming.
2. Explain microbatching in streaming computations.
3. Design programs that facilitate incrementatl computation of results.
   

Objectives:

1. Explain the importance of time synchronization in distributed systems.
2. Contrast capabilties across different types of logical clocks: scalar, vector, and matrix.
   

Replication, Consistency and Coherence [CS555]

Performance and correctness implications of replication and consistency.
(a) Data and client centric consistency, consistent ordering of operations: sequential consistency and causal consistency. Monotonic read, Monotonic write, Read-your-writes, and Writes-follow-read.
(b) Consistency Protocols
(c) Replica placements
(d) Brewer's CAP theorem and design implications

Objectives:

1. Design systems based on the CAP theorem
   

In this module, we will cover two of the most powerful extreme scale storage systems and the design considerations that underpin them. These frameworks substantially advanced the design of storage systems that scale and they have completely different approaches to the scaling problem.

Amazon Dynamo: Assumptions & requirements, design choices, systems architecture, partitioning algorithm, replication, versioning, and experiences.


Google File System: Demand pulls, file system interface, chunking, managing file system metadata, records and atomic appends, creating snapshots, replication, consistency, deletion and garbage collection.

Objectives:

1. Contrast different approaches to scaling in distributed systems.
   

Distributed coordination, conditions requirements for distributed mutual exclusion, token-based and permission-based approaches, Central-Server algorithm, Ricarat and Agarwala's algorithm, Maekawa's algorithm and voting sets..

Objectives:

1. Analyze distributed mutual exclusion algorithms.
2. Design systems that can enforce mutual exclusion in distributed settings.
   

Election Algorithms: Requirements, performance of algorithms, ring-based algorithm, failure detectors, Garcia-Molina Bully Algorithm, and elections in wireless environments.

1. Analyze distributed election algorithms.
2. Explain key differences between different types of failure detectors.
   

Each group will present their term projects to the entire class. The format of these term project presentations will be prescriptive so that the core achievements can be highlighted. The term project presentation guidelines will be posted right after Spring Break.

Objectives:

1. Present research work coherently and objectively to a peer audience.
2. Highlight and assess key contributions of a work. In particular, identify which works are innovative and what makes these works so compelling.
3. Frame questions effectively during research presentations.
   
   

Term Project Presentation Guidelines

Schedule A

Schedule B