Comp 533: Distributed Systems

Course Overview

This course will provide a practical overview distributed systems. It will be driven by a series of implementation-based assignments, which will form a semester-wide project.

We will cover classical abstractions for sharing information among distributed processes. These sit between the network layer and application and include: distributed shared memory, byte and object communication, remote procedure call, and broadcast/multicast sessions. Some of the general issues we will address in the study of these abstractions are naming; synchronization; extensibilty; flexibility; programmability; and performance. Some of the specific abstractions we will cover are Unix pipes, sockets and signals; CSP and Ada guards; Ada Rendezvous; and Java NIO, Serialization and RMI.

We will also cover classical algorithms for ensuring that data kept by multiple sites is kept consistent even when message communication is unreliable and some sites go down. These include the Two Generals’ Problem, non-atomic and atomic broadcast, two-phase commit, and Paxos.

The assignments will involve experimentation, use, analysis, and/or implementation of some of the covered abstractions and algorithms. These assignments are layered to form a semester-wide project, allowing students to better understand the relationship among and motivation for the concepts implemented. Successive assignments required students to implement/use additional IPC abstractions and consistency/consensus algorithms. Later assignments implicitly test almost all aspects of previous assignments.

We will not cover topics that are the focus of other courses at UNC such as proofs of consensus algorithms (Comp 735), distributed file systems (Comp 790), “big data”, data centers, and other distributed applications (Comp 790s),  and parallelization/distribution of standard classical single-processor algorithms (Comp 633).consideration to things such as good class participation. You are encouraged to discuss the assignments with fellow students but required to write/code the solutions/programs individually. Also you cannot use solutions from previous offerings of the course. Not following these rules is a violation of the honor code policy.

Syllabus Handout in UNC Format

Instructor

Prasun Dewan

Office: FB 150

Email: dewan@cs.unc.edu

Office Hours:

Tue, Thu 3:15-4:15pm

Getting Help and Class Discussion

We will be using Piazza for class discussion and submitting videos and diaries. The system is highly catered to getting you help fast and efficiently from classmates and instructors. Rather than emailing technical questions, please post public questions to Piazza. Material containing private information should be posted as a private question on Piazza. If you do not get a response within a day or two on Piazza, please send email.

Before posing a question, please check if this question has been asked before. This will reduce post clutter and reduce our burden. Repeat questions will be ignored.

Piazza allows anyone to respond. So if you see a question that you think you can respond to, please do so, as that will reduce my burden and help you "teach" your fellow students. In fact, my responses will be delayed to give the fellow students a chance to respond first.

 Find our class page at:  http://piazza.com/unc/spring2019/comp533

 

Lectures

Room: SN 014

Time: TR 2-3:15pm

Exam Schedule

Midterm

Class time, Thu Mar 21 (in class)

Final

12pm on Monday May 6 (in class)

Old Exams

Exam 1

Midterm

Exam 2

Final

Downloads

Latest ObjectEditor (jar)

oeall22

OMP4 (jar)

omp4j-1.2.jar

 

Github Repositories

Beau’s Halloween Project and Coupled TrickOrTreat

Grader Basics

Comp533LocalChecks

 

Shared Google Drive Folder

 

Topics

 

Unit

Slides/Videos

Reference Material

Assignment

 

Course Overview

PPT PDF

YouTube

 

 

 

Device-CPU Communication

PPT PDF

YouTube

PPT Transcript

 

Hardware Aspects

 

 

 

Basic Computing Systems Concepts: Hardware, OS, Design Patterns

PPT PDF

YouTube

Mix

 

Scheduling and Context Switching

Basic Concepts + RMI --> Map-Reduce

 

Threads and Thread Coordination (for extra credit quizzes)

PPT PDF

YouTube-1

YouTube-2

YouTube-3

Mix-1

Mix-2

Mix-3

Commands Chapter

Process Coordination PDF  )

 

 

 

High-Performance Parallel and Distributed Computing

PPT PDF

 

 

 

Basic Concepts + RMI --> Map-Reduce

 

Java Byte IPC: From I/O to NIO

 

I/O

 

 

 

 

Blocking IPC

 

 

NIO and Select

 

 

NIOManager-Basics

 

NIO Manager-Command Objects

 

 

Summary

 

 

 

PPT PDF

YouTube

Mix

 

 

 

 

 

PPT PDF

YouTube

Mix

 

 

PPT PDF

YouTube

Mix

 

PPT PDF

YouTube

Mix

 

PPT PDF

YouTube

Mix

 

 

PPT PDF

YouTube

Mix

 

 

Interrupt Processing (See Synchronization of the Upper and Lower Halves and Rules for Interrupt Processing)

 

 

 

Sockets

OS Interface: Sockets

 

NIO Tutorial

 

 

See Background Concepts and Details in Atomic Broadcast using NIO

Atomic Broadcast using NIO

 

Issues in Serialization (for Extra Credit quiz and assignment)

PPT PDF

YouTube-1

YouTube-2

YouTube-3

YouTube-4

Mix-1

Mix-2

Mix-3

Mix-4

 

Serialization Demo

Extensible Serialization (Extra Credit)

 

 

Java Remote Method Invocation

PPT (2013) PDF (2013)

PPT-1 (2015)

PPT-2 (2015)

PPT-3 (2015)

YouTube-1 (2013)

YouTube-2 (2013)

YouTube-3 (2015)

Mix-1

Mix-2

Mix3

 

RMI Demo

RMI

Sun RPC

Transparent RPC

Centralized Asynchronous Consensus Using RMI and NIO

 

 

Byte Communication

PPT PDF

YouTube-1

YouTube-2

YouTube-3

Mix-1

Mix 2

Mix-3

Interprocess Communication (PDF)

 

 

 

Distributed Synchronous Consensus Using GIPC, RMI and NIO

 

 

 

 

 

 

 

 

 

 

 

 

Atmosphere Tutorial

PPT PDF

YouTube

Mix

 

 

 

 

RPC Implementation: Basic Steps

PPT

PDF

YouTube

Mix

 

Explicit Receive and RPC

 

 

IPC Design Space

PPT PDF

YouTube-1

YouTube-2

Mix

 

Interprocess Communication (PDF)

 

 

Distributed Consensus-Part 5: Paxos Algorithm

PPT PDF

YouTube

Mix

 

Paxos Paper

 

 

Distributed Consensus-Part 6: Paxos Implementation (Optional)

PPT PDF

YouTube

Mix

 

 

Consensus Techniques

Rubric (Word, PDF)

(Optional)

 

Mystery of the 20G Byte File

PPT PDF

YouTube

 

 

 

 

 

 

 

 

 

Rows below are under construction

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Introduction to Distributed Systems

PPT PDF

YouTube

Mix

 

 

 

 

 

Threads and Thread Coordination 

PPT PDF

YouTube-1

YouTube-2

YouTube-3

Mix-1

Mix-2

Mix-3

Commands Chapter

Process Coordination PDF  )

 

 

 

Byte Communication

PPT PDF

YouTube-1

YouTube-2

YouTube-3

Mix-1

Mix 2

Mix-3

 

NIO Tutorial

NIO Demo-Part 1

NIO Demo-Part 2

Interprocess Communication (PDF)

 

 

 

Replication Using Non-Blocking I/O

Rubric (Word, PDF)

 

Java Remote Method Invocation

PPT PDF

YouTube-1

YouTube-2

YouTube-3

Mix-1

Mix-2

Mix3

 

RMI Demo

Interprocess Communication (PDF)

Replication Using RMI

Rubric (Word, PDF)

Replication and Consensus Using GIPC

Rubric (Word, PDF)

 

 

IPC Design Space

PPT PDF

YouTube-1

YouTube-2

Mix

 

Interprocess Communication (PDF)

 

 

RPC Implementation: Basic Steps

PPT

PDF

YouTube

Mix

 

Explicit Receive and RPC

Rubric (Word, PDF)

 

RPC Architecture

PPT

PDF

YouTube

Mix

 

 

 

RPC and Factory Patterns

PPT

PDF

YouTube

Mix

 

 

 

Java Object Communication

PPT PDF

YouTube

Mix

 

 

 

 

Issues in Serialization

PPT PDF

YouTube-1

YouTube-2

YouTube-3

YouTube-4

Mix-1

Mix-2

Mix-3

Mix-4

 

Serialization Demo

Extensible Serialization

Rubric (Word, PDF)

 

Distributed Consensus-Part 1: Context

PPT PDF

YouTube

Mix

 

 

Consensus Techniques

Rubric (Word, PDF)

 

 

Distributed Consensus-Part 2: Replicated Objects and Asynchronous Learners

PPT PDF

YouTube

Mix

 

 

 

 

 

Distributed Consensus-Part 3: (Semi) Synchronous Replication

PPT PDF

YouTube

Mix

 

 

 

 

 

Distributed Consensus-Part 4: Centralization

PPT PDF

YouTube

Mix

 

 

 

 

 

Distributed Consensus-Part 5: Paxos Algorithm

PPT PDF

YouTube

Mix

 

 

 

 

 

Distributed Consensus-Part 6: Paxos Implementation

PPT PDF

YouTube

Mix

 

 

 

 

 

Group Communication

PPT PDF

YouTube

Mix

 

 

 

 

GIPC Overview

PPT PDF

YouTube

 

 

 

 

GIPC Extensibility

PPT PDF

YouTube