Distributed OS: Winter 2014

Course Information

• Course Number: COMP 4000/5102
• Term: Winter 2014
• Title: Distributed Operating Systems
• Institution: Carleton University, School of Computer Science
• Instructor: Anil Somayaji (anilsomayaji at connect.carleton.ca): Wed. 3-4 and Thurs. 12-1 in HP 5137
• Teaching Assistant: Andrew Schoenrock (aschoenr at scs.carleton.ca)
• Lectures: Tuesday and Thursday 10:05-11:25 AM, ME 3356
• Course Website: http://homeostasis.scs.carleton.ca/wiki/index.php?title=Distributed_OS:_Winter_2014

Official Course Descriptions

COMP 4000: An advanced course emphasizing the principles of distributed operating systems including networking protocols, distributed file systems, remote IPC mechanisms, graphical user interfaces, load balancing, and process migration. Case studies include current "standards" as well as novel systems under development. Prerequisite(s): one of COMP 3203 or SYSC 4602, and one of COMP 3000, SYSC 3001, SYSC 4001.

COMP 5102: Design issues of advanced multiprocessor distributed operating systems: multiprocessor system architectures; process and object models; synchronization and message passing primitives; memory architectures and management; distributed file systems; protection and security; distributed concurrency control; deadlock; recovery; remote tasking; dynamic reconfiguration; performance measurement, modeling, and system tuning. Prerequisite(s): COMP 3000 and COMP 3203 or equivalent.

Communication

This wiki page is the canonical source of information on this course. Please refer to it for updates. When significant changes are made to this document it will be either announced in lecture and/or posted in the course discussion forum.

Online course discussions will be on cuLearn.

You should get an account on this wiki so you can edit content here. Email Prof. Somayaji to get one with your preferred username and email address to which a password should be sent.

Required Textbooks/Software

There are no required textbooks or software for this course. Instead we will be reading research papers which will be linked to from this webpage. While many of these papers will be available directly via web search, some will be behind paywalls. In this case there will be alternate links to those pages that go through the Carleton Library's proxy.

Grading

Students enrolled in COMP 4000 (undergraduates) have the following grading scheme:

• 15% Class Participation
• 15% Reading Responses
• 10% Lecture Notes/Wiki contributions
• 25% Midterm (Feb. 27th)
• 35% Final Exam

Students enrolled in COMP 5102 (mostly graduate students) instead have this grading scheme:

• 15% Class Participation
• 15% Reading Responses
• 10% Lecture Notes/Wiki contributions
• 10% Project Proposal (Feb. 13th - extended!)
• 15% Project Presentation (April 1st, 3rd)
• 35% Final Project

Optionally, students enrolled in COMP 4000 may choose to be graded on the COMP 5102 grading scheme.

Each of these elements are explained below.

Class Participation

You are expected to attend every class for this course. Moreover, you are expected to participate in each class. This participation part of your grade will be based in part upon attendance; however, it will also be based upon the degree to which you were an active participant. Students who attend every class but who do nothing while in class will get a worse participation grade than those who miss some classes but who fully participate in those they do attend.

Reading Responses

• Before the start of class on each Tuesday you should submit an all-text reading response on cuLearn that is approximately 500 words in length. Responses longer than 600 words may be marked off for verbosity. Your responses should say what you found interesting and what do you have questions about/were confused by. Where appropriate, they should also discuss the relationship between the papers of the week and other work that you know about (including those covered earlier in class).
• Do not summarize the readings. I've already read them! Instead you should be telling me what you got out of these papers, good and bad. Please also tell me what issues you'd like to learn more about, either in class or potentially through later readings.
• Responses will be graded on a scale of 0 to 4, with a 4 being given for a response that has clear evidence that you made an effort to read and understand all of the assigned readings.
• Please submit your responses in plain text or PDF format. (No MS Word files! Please convert to PDF or text before submitting.) You may want to consider writing your response as a text file formatted in Markdown and then convert the output to PDF using pandoc.
• Responses will be accepted until Thursday, 6 AM. Responses submitted after Tuesday morning, though, will have a maximum grade of 3, not 4.

Class Notes/Wiki contributions

Everyone will be expected to co-author the notes for at least one class and upload them to the class wiki. Class notes should capture the content of lectures and discussions in a way that will aid study for the midterm and final, especially for those who have missed that particular class. Draft class notes are due on the wiki a week after the class; however, it is recommended that preliminary notes be uploaded within 48 hours of class. Notes will need to be revised until they are acceptable; however, students other than the original authors may elect to make modifications and updates.

Wiki contribution grades will be determined based on the overall quality of wiki contributions over the course of the term.

Midterm and Final Exam

Undergraduates by default will be required to complete an in-class midterm exam and a formally scheduled final exam. These will be essay tests based on the material covered in class. Sample questions will be made available during study sessions prior to the exams.

Project

The project may be a literature review of a specialized area of computer science related to distributed operating systems, or it may be a research proposal on a problem related to distributed operating systems. A research proposal should be thought of as an abbreviated literature review paper combined with a description of potential future work that would fill a gap in the covered literature.

You may choose to follow up on your proposal and actually implement what you propose; given the implementation complexity of most research problems in distributed operating systems, though, such an implementation is strictly optional (but may be advisable if you wish to make your project publishable).

Your project outline should consist of an abstract, an argument outline, and at least ten references that you plan to cite in your final project.

You should run ideas for your project by Prof. Somayaji before writing your proposal before you spent time making your outline.

Collaboration

Collaboration on all work is allowed except for the midterm and final exams. Collaboration, however, should be clearly acknowledged. Specifically, co-authored works should be marked as such. When co-authored, all authors of reading responses and projects will get the same grade, unless there is reason to believe that some co-authors did not in fact contribute significantly to the submitted work. Co-authored contributions may get different grades depending upon the relative contribution of the different authors; however, the default here will also be to give all authors the same grade.

It is essential that outside references be cited appropriately. Proper citation format should be followed except where more relaxed forms are specifically allowed.

Plagiarism or intellectual dishonesty of any kind is strictly forbidden. In other words, it should always be clear what is your work and what is the work of others. If anything you submit is, in part or whole, very similar in content or structure to that of work produced by someone else, you are plagiarizing. This includes figures.

Think of plagiarism as a kind of unauthorized collaboration. Don't do it. Plagiarism and other instructional offenses will be reported to the Dean of Science for disciplinary action, as per university guidelines.

Topics

The Early Internet (Jan. 14)

• Robert E. Kahn, "Resource-Sharing Computer Communications Networks" (1972) (DOI)
• Computer Networks: The Heralds of Resource Sharing (1972) - video

The Alto (Jan. 16)

• Thacker et al., "Alto: A Personal computer" (1979) (archive.org)

The Mother of all Demos (Jan. 21)

If you can, watch the whole demo. The Stanford version with annotated clips is good if you are short for time.

• Doug Engelbart Institute, "Doug's 1968 Demo"
• Wikipedia's page on "The Mother of all Demos"

The Early Web (Jan. 23)

• Berners-Lee et al., "World-Wide Web: The Information Universe" (1992), pp. 52-58
• Alex Wright, "The Web That Wasn't" (2007), Google Tech Talk

UNIX and Plan 9 (Jan. 28)

• Dennis M. Ritchie and Ken Thompson, "The UNIX Time-Sharing System" (1974)
• Presotto et. al, Plan 9, A Distributed System (1991)
• Pike et al., Plan 9 from Bell Labs (1995)

NFS and AFS (Jan 30)

• Russel Sandberg et al., "Design and Implementation of the Sun Network Filesystem" (1985)
• John H. Howard et al., "Scale and Performance in a Distributed File System" (1988)

GFS and Ceph (Feb. 4)

• Sanjay Ghemawat et al., "The Google File System" (SOSP 2003)
• Weil et al., Ceph: A Scalable, High-Performance Distributed File System (OSDI 2006).

Chubby (Feb. 13)

Note: no response this week, as proposals are due on this day.

• Burrows, The Chubby Lock Service for Loosely-Coupled Distributed Systems (OSDI 2006)

Oceanstore (Mar. 4)

• John Kubiatowicz et al., "OceanStore: An Architecture for Global-Scale Persistent Storage" (2000)
• Sean Rhea et al., "Pond: the OceanStore Prototype" (2003)

Farsite (Mar. 6)

• Atul Adya et al.,"FARSITE: Federated, Available, and Reliable Storage for an Incompletely Trusted Environment" (2002)
• William J. Bolosky et al., "The Farsite Project: A Retrospective" (2007)

Public Resource Computing (March 11)

• Anderson et al., "SETI@home: An Experiment in Public-Resource Computing" (CACM 2002) (DOI) (Proxy)
• Anderson, "BOINC: A System for Public-Resource Computing and Storage" (Grid Computing 2004) (DOI) (Proxy)

Project Help Session (March 13)

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

Distributed Hash Tables (March 18)

• Wikipedia's article on Distributed Hash Tables
• Zhao et al, "Tapestry: A Resilient Global-Scale Overlay for Service Deployment" (JSAC 2003)

Structured Data 1 (March 20)

• Chang et al., "BigTable: A Distributed Storage System for Structured Data" (OSDI 2006)
• DeCandia et al., "Dynamo: Amazon’s Highly Available Key-value Store" (SOSP 2007)

Structured Data 2 (March 25)

• Lakshman & Malik, "Cassandra - A Decentralized Structured Storage System" (LADIS 2009)
• Geambasu et al., "Comet: An active distributed key-value store" (OSDI 2010)

Computational Models (March 27)

• Dean & Ghemawat, "MapReduce: Simplified Data Processing on Large Clusters" (OSDI 2004)
• Murray et al., "Naiad: a timely dataflow system" (SOSP 2013)

Presentations 1 (April 1)

• Gehana
• Keerthi
• Simon & Peter
• Adam
• Bo

Presentations 2 (April 3)

• Mojgan
• Mohammed
• Sijo
• Sandarbh
• Ronak Chaudhari

The Future (April 8)

• Berkeley CS Dept., "A view of the parallel computing landscape" (CACM 2009)
• Berkeley CS Dept., "The Landscape of Parallel Computing Research: A View from Berkeley" (2006 Tech Report) Note Section 6.2, "Deconstructing operating system support".

Grid Computing (Optional)

• Foster et al., "The Anatomy of the Grid: Enabling Scalable Virtual Organizations" (IJHPCA 2001) (DOI) (Library Proxy)
• Foster et al., "Cloud Computing and Grid Computing 360-Degree Compared" (GCE 2008) (DOI) (arXiv.org)

Schedule

Date	Topic
Jan. 7	Lecture 1
Jan. 9	Lecture 2
Jan. 14	Lecture 3
Jan. 16	Lecture 4
Jan. 21	Lecture 5
Jan. 23	Lecture 6
Jan. 28	Lecture 7
Jan. 30	Lecture 8
Feb. 4	Lecture 9
Feb. 6	Lecture 10
Feb. 11	Lecture 11
Feb. 13	Lecture 12 Project Proposals Due
Feb. 25	Midterm Review
Feb. 27	Midterm Exam
Mar. 4	Lecture 14
Mar. 6	Lecture 15
Mar. 11	Lecture 16
Mar. 13	Lecture 17
Mar. 18	Lecture 18
Mar. 20	Lecture 19
Mar. 25	Lecture 20
Mar. 27	Lecture 21
Apr. 1	Lecture 22
Apr. 3	Lecture 23
Apr. 8	Lecture 24
April 24, 2 PM	Final Exam

University Policies

Student Academic Integrity Policy

Every student should be familiar with the Carleton University student academic integrity policy. A student found in violation of academic integrity standards may be awarded penalties which range from a reprimand to receiving a grade of F in the course or even being expelled from the program or University. Some examples of offences are: plagiarism and unauthorized co-operation or collaboration. Information on this policy may be found in the Undergraduate Calendar.

Plagiarism

As defined by Senate, "plagiarism is presenting, whether intentional or not, the ideas, expression of ideas or work of others as one's own". Such reported offences will be reviewed by the office of the Dean of Science.

Unauthorized Co-operation or Collaboration

Senate policy states that "to ensure fairness and equity in assessment of term work, students shall not co-operate or collaborate in the completion of an academic assignment, in whole or in part, when the instructor has indicated that the assignment is to be completed on an individual basis".

Please see above for the specific collaboration policy for this course.

Academic Accommodations for Students with Disabilities

The Paul Menton Centre for Students with Disabilities (PMC) provides services to students with Learning Disabilities (LD), psychiatric/mental health disabilities, Attention Deficit Hyperactivity Disorder (ADHD), Autism Spectrum Disorders (ASD), chronic medical conditions, and impairments in mobility, hearing, and vision. If you have a disability requiring academic accommodations in this course, please contact PMC at 613-520-6608 or pmc@carleton.ca for a formal evaluation. If you are already registered with the PMC, contact your PMC coordinator to send me your Letter of Accommodation at the beginning of the term, and no later than two weeks before the first in-class scheduled test or exam requiring accommodation (if applicable). After requesting accommodation from PMC, meet with me to ensure accommodation arrangements are made. Please consult the PMC website for the deadline to request accommodations for the formally-scheduled exam (if applicable) at http://www2.carleton.ca/pmc/new-and-current-students/dates-and-deadlines

Religious Obligation

Write to the instructor with any requests for academic accommodation during the first two weeks of class, or as soon as possible after the need for accommodation is known to exist. For more details visit the Equity Services website: http://www2.carleton.ca/equity/

Pregnancy Obligation

Write to the instructor with any requests for academic accommodation during the first two weeks of class, or as soon as possible after the need for accommodation is known to exist. For more details visit the Equity Services website: http://www2.carleton.ca/equity/

Medical Certificate

The following is a link to the official medical certificate accepted by Carleton University for the deferral of final examinations or assignments in undergraduate courses. To access the form, please go to http://www.carleton.ca/registrar/forms