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: 12:30 - 1:45 pm
Wednesdays: 11:00-11:59 am
[CSB-130]

Graduate Teaching Assistants

Gabriele Maurina

Videep Venkatesha

Jackson Volesky
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.

This module introduces the core ideas of threads, thread safety, and concurrent programming. It begins with a comparison of threads and processes, followed by an exploration of the thread lifecycle: how stacks and heaps are used, and how threads are created and managed. The focus then shifts to the challenges of concurrency. Topics include data synchronization, race conditions, intrinsic locks, and reentrancy. Compound actions, object sharing and confinement, and the preservation of multivariable invariants are examined as essential ingredients of thread safety. Building on these foundations we then turn to techniques for writing correct and reliable concurrent code. This includes making classes thread-safe, extending thread-safe classes with new functionality, and working with synchronized and concurrent collections. Different locking strategies are also analyzed, highlighting their advantages and trade-offs.
Ultimately, the goal of this module is to provide a clear framework for understanding both the mechanics and the principles that govern programs running many tasks at the same time.

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
4. Implement basic synchronization mechanisms (e.g., locks, synchronized collections) to manage shared resources.
5. Diagnose concurrency bugs by tracing execution and identifying violations of invariants.
6. Compare and critique different locking and synchronization strategies in terms of scalability, fairness, and performance.
7. Develop novel concurrency solutions that balance safety, performance, and maintainability in complex systems.
   

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.
3. Describe how architectural styles (layered, object-based, data-centric, event-driven) influence system design.
4. Compare and critique scaling strategies while highlighting trade-offs between performance, fault tolerance, and complexity.
   
   

This module examines the fascinating world of peer-to-peer (P2P) systems where every machine is a peer that can act both as a client and a server. We will begin by laying out the core characteristics of P2P systems and tracing their evolution across generations. We will identify the middleware and requirements that make such systems possible. Next, we will then compare/contrast structured and unstructured approaches. Structured systems (like Chord, Pastry, and Tapestry) use carefully designed algorithms to organize peers and guarantee efficient lookups. Unstructured systems (like Napster and Gnutella) rely on looser, more ad hoc connections. BitTorrent, with its swarming downloads, shows how these ideas can power real-world applications at scale. We will explore the time and space complexity of P2P algorithms, understanding the trade-offs that emerge when scaling to millions of peers. Another way to think of these exemplar systems is not just as case studies, but as landmarks in the evolution of distributed thinking.

Objectives:

1. Explain structured and unstructured P2P systems
2. Explain bounded routing in structured P2P systems
3. Analyze the trade-offs between structured and unstructured P2P systems in terms of scalability, fault tolerance, and lookup efficiency.
4. Evaluate exemplar P2P systems (e.g., Chord, Pastry, BitTorrent) and justify design choices in terms of routing complexity and performance.
5. Build systems based on structured P2P concepts
   
   

Objectives:

1. Explain the differences between MapReduce and other paradigms (RDBMS, HPC, Grid, volunteer computing).
   
2. Express computations using the Map and Reduce functions.
   
3. Apply partitioning, combiner, and refinement functions to improve performance.
   
4. Analyze the trade-offs of pushing computation to the data versus moving data to the computation.
   
5. Design systems that leverage the MapReduce framework to scale gracefully with growing datasets.

Objectives:

1. Express programs using MapReduce.
2. Design systems that push computations to the data to preserve data locality.
   
3. Design programs that leverage the Hadoop framework to scale.
4. Understand the architecture and design principles of the Hadoop Distributed File System (HDFS).
   
5. Analyze how job configuration, task splitting, and combiners affect performance.
   
6. Evaluate the role of YARN in managing resources and scheduling jobs.

Objectives:

1. Understand memory residency and its implications for performance.
   
2. Express processing functionality concisely using lambda expressions.
   
3. Differentiate between transformations and actions in Spark.
   
4. Analyze narrow versus wide transformations and their overall impact on program execution.
   
5. Design Spark programs that leverage RDDs and partitioning to scale efficiently.
   

Objectives:

1. Explain the differences between traditional batch-style computations and streaming.
   
2. Explain the role of micro-batching in Spark Streaming.
   
3. Design programs that support incremental computation of results.
   
4. Analyze the trade-offs between stateful and stateless transformations.
   
5. Evaluate performance considerations in streaming applications.
   

In distributed systems few aspects are more fundamental (or more slippery!) than time. On a single machine we take it for granted that events can be ordered by the system "clock". But spread those events across thousands of machines, each with its own imperfect sense of time, and the problem becomes much trickier. Synchronizing clocks turns out to be one of the core challenges of modern distributed computing. In this module, we will explore how time is kept and shared in distributed environments. We will start with the most concrete anchors: global positioning systems (GPS) and their role in providing precise time signals. Next we will move into time synchronization algorithms such as the Berkeley and Cristian algorithms along with methods tailored for wireless settings where communication is much less reliable.

But physical time can only take us so far. To capture the order of events without relying on perfectly synchronized clocks, distributed systems introduced the idea of logical clocks. We will be looking at Lamport clocks, vector clocks, and even matrix clocks. Each of these offers a richer picture of causality in distributed computations. To summarize distributed systems measure time in two ways: (1) the imperfect but practical signals of the physical world and (2) the elegant constructs of logical clocks that let us reason about order even when the real clocks disagree.

Objectives:

1. Explain the importance of time synchronization in distributed systems.
   
2. Describe the role of physical time sources (such as GPS) in providing synchronization.
   
3. Explain how synchronization algorithms like Berkeley’s and Cristian’s operate including their assumptions and limitations.
   
4. Contrast the capabilities of different logical clocks: scalar, vector, and matrix.
   
5. Analyze the trade-offs between physical and logical time in terms of accuracy, scalability, and system complexity.
   
6. Given a set of choices evaluate which clock model or synchronization approach is appropriate for a given distributed application.
   

Objectives:

1. Explain the motivation for replication and the challenges it introduces.
   
2. Differentiate between data-centric and client-centric consistency models.
   
3. Describe guarantees such as sequential consistency, causal consistency, monotonic reads/writes, read-your-writes, and writes-follow-reads.
   
4. Analyze the performance and correctness implications of different consistency protocols.
   
5. Evaluate strategies for replica placement in terms of fault tolerance, latency, and scalability.
   
6. Design systems that respect the constraints of the CAP theorem making informed trade-offs between consistency, availability, and partition tolerance.
   
   

At small scales, building a storage system feels straightforward: put data on a disk, add redundancy, and manage access. But at the scale of Amazon and Google these simple solutions break down. The need to store petabytes of information across thousands of machines forces a rethinking of the very foundations of storage design. In this module, we will examine two landmark systems that transformed the field of extreme-scale storage. Amazon’s Dynamo was designed for high availability and resilience under failure. We will look at its assumptions and requirements, its partitioning and replication strategies, its use of versioning, and the architectural choices that made it robust in practice. You will also be very pleasantly surprised as to how Dynamo weaves together so many of the concepts that we have covered so far.

We will then turn to the Google File System (GFS) which took a very different path. Built to support massive data-processing frameworks GFS introduced new abstractions: (1) files chunked into large blocks, (2) centralized metadata management, and (3) novel operations such as atomic appends and snapshots. We will also explore how it handles replication, consistency, and garbage collection. Together, both Dynamo and GFS highlight not only the diversity of approaches to scaling storage but also the trade-offs between availability, consistency, simplicity, and performance. By comparing Dynamo and GFS side by side, you will see how design decisions reflect both the technical constraints and the unique needs of the applications they serve.

Objectives:

1. Explain the motivations behind extreme-scale storage systems.
   
2. Describe the key design decisions in Amazon Dynamo and Google File System.
   
3. Analyze how assumptions and requirements shape system architectures.
   
4. Contrast different approaches to scaling as exemplified by Dynamo and GFS.
   
5. Evaluate trade-offs in partitioning, replication, and consistency strategies.
   
6. Design informed strategies for storage in distributed environments applying lessons from Dynamo and GFS.
   

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 in late October.

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