Distributed OS: Fall 2021

Course Outline

Here is the course outline.

Experiences

• Experience 1, due November 2, 2021
• Experience 2, due November 30, 2021

Using Openstack

The experiences (and potentially your project) will involve using the SCS Openstack cluster:

• How to use Openstack (for COMP 4000/5102)
• SCS Openstack web console (only available from the Carleton network)

Classes

More information will be posted here by the first class.

Note: If you don't have access to the course information on brightspace, please email Prof. Somayaji, you may need to be manually added. (If you're at UofO or you recently added COMP 5102, you probably need to be added manually.) On Brightspace the course should show up as COMP 4000 no matter whether you enrolled in it or COMP 5102.

Project Help

To develop a literature review or research proposal, start with a single research paper that you find interesting and that is related to distributed operating systems in some way.

To begin selecting a paper, I suggest that you:

• search on Google Scholar using keywords relating to your interests, and/or
• browse the proceedings of major conferences that publish work related to distributed operating systems.

The main operating system conferences are OSDI and ACM SOSP (sosp.org,ACM DL). Note that not all the work here is on distributed operating systems! Also, many other conferences publish some work related to distributed operating systems, e.g. NSDI.

To help you write a literature review or the background of a research paper, read the following:

• Harvey, "What Is a Literature Review?" (DOC) (PPT)
• Taylor, "The Literature Review: A Few Tips On Conducting It"

Implementation experiences will depend upon your technical background and personal interests. If you have an idea, please discuss with Anil or William as soon as you can.

Readings & Classes

September 9, 2021

Introduction

September 14, 2021

UNIX

• The UNIX System: Making Computers More Productive (1982), video
• Dennis M. Ritchie and Ken Thompson, "The UNIX Time-Sharing System" (1974)

Note that the video covers the main points of the paper.

September 16, 2021

LOCUS

• Bruce Walker et al., "The LOCUS Distributed Operating System." (1983)

September 21, 2021

NFS

• Russel Sandberg et al., "Design and Implementation of the Sun Network Filesystem" (1985)

September 23, 2021

Distributed Shared Memory

• Jelica Protic et al., "Distributed Shared Memory: Concepts and Systems" (1996)

September 28, 2021

Plan 9

• Presotto et. al, Plan 9, A Distributed System (1991)
• Pike et al., Plan 9 from Bell Labs (1995)

September 30, 2021

Solaris Zones

• Price & Tucker, "Solaris Zones: Operating System Support for Consolidating Commercial Workloads" (LISA 2004)
• Galvin, "Solaris 10 Containers" (;LOGIN 2005)

October 5, 2021

NASD & GFS

• Garth A. Gibson et al., "A Cost-Effective, High-Bandwidth Storage Architecture" (1998)
• Sanjay Ghemawat et al., "The Google File System" (SOSP 2003)

October 7, 2021

Chubby & ZooKeeper

• Burrows, The Chubby Lock Service for Loosely-Coupled Distributed Systems (OSDI 2006)
• Hunt et al., "ZooKeeper: Wait-free coordination for Internet-scale systems" (USENIX ATC 2010) (video)

October 12, 2021

BigTable & MapReduce

• Chang et al., "BigTable: A Distributed Storage System for Structured Data" (OSDI 2006)
• Dean & Ghemawat, "MapReduce: Simplified Data Processing on Large Clusters" (OSDI 2004) (be sure to read paper)

October 14, 2021

Omega & Borg

• Schwarzkopf et al., "Omega: flexible, scalable schedulers for large compute clusters" (EuroSys 2013)
• Verma et al., "Large-scale cluster management at Google with Borg" (EuroSys 2015)

October 19, 2021

Midterm Review

October 21, 2021

Midterm

November 2, 2021

Cassandra & Dynamo

• Lakshman & Malik, "Cassandra - A Decentralized Structured Storage System" (LADIS 2009)
• DeCandia et al., "Dynamo: Amazon’s Highly Available Key-value Store" (SOSP 2007)

November 04, 2021

Haystack & F4

• Beaver et al., "Finding a needle in Haystack: Facebook’s photo storage" (OSDI 2010)
• Muralidhar et al., "f4: Facebook's Warm BLOB Storage System" (OSDI 2014)

November 09, 2021

Proposal due by 11:59 PM

Spanner & Tensorflow

• Corbett et al., "Spanner: Google’s Globally-Distributed Database" (OSDI 2012)
• Martin Abadi et al., "TensorFlow: A System for Large-Scale Machine Learning" (OSDI 2016)

November 11, 2021

Ceph

• Weil et al., Ceph: A Scalable, High-Performance Distributed File System (OSDI 2006).
• Weil et al., CRUSH: Controlled, Scalable, Decentralized Placement of Replicated Data (SC 2006)

November 16, 2021

OceanStore & BOINC

• John Kubiatowicz et al., "OceanStore: An Architecture for Global-Scale Persistent Storage" (SIGPLAN 2000)
• Sean Rhea et al., "Pond: the OceanStore Prototype" (FAST 2003)
• Anderson, "BOINC: A System for Public-Resource Computing and Storage" (Grid Computing 2004)

November 18, 2021

Tapestry & Delos

• Zhao et al, "Tapestry: A Resilient Global-Scale Overlay for Service Deployment" (JSAC 2003)
• Balakrishnan et al., "Virtual Consensus in Delos" (OSDI 2020)

Background (optional but helpful):

• Wikipedia's article on Distributed Hash Tables

November 23, 2021

Cryptocurrency origins

• Lamport et al., "The Byzantine Generals Problem" (TOPLAS 1982)
• Nakamoto, "Bitcoin: A Peer-to-Peer Electronic Cash System" (2008)
• Nakamoto, "Re: Bitcoin P2P e-cash paper" (2008)
• Lemieux, "Who is Satoshi Nakamoto?" (Regulation, Fall 2013)

December 7, 2021

Project Presentations (Informal)

December 9, 2021

Class wrap up & Exam review

December 19, 2021

Final Exam (Online, 2-5 PM)