CS254 SYLLABUS Feb 25, 2000 Instructors: Dr. Robert Walton and Prof. Thomas Cheatham walton@deas.harvard.edu Web: www.deas.harvard.edu/courses/cs254r/2000/ Text: The Grid: Blueprint for a New Computing Infrastructure Ed. by Ian Foster and Carl Kesselman Morgan Kaufmann 1999 ISBN 1-55860-475-8 There will be 60-90 minutes of lecture and 30-60 minutes of discussion per meeting. The lecturing will be broken into 2 or more parts each followed by discussion. The following is subject to change; but The Grid text will be the subject of the first lectures. Meeting Date Lecture Reading. 2/2 Introduction. Computational Grids. The Grid, ch 1 & 2 2/9 Applications: Distributed Supercomputing The Grid, ch 3 Distributed Real-Time The Grid, ch 4 Data-Intensive Computing The Grid, ch 5 Teleimmersion The Grid, ch 6 2/16 Programming Tools: Application Specific Tools The Grid, ch 7 Languages and Libraries The Grid, ch 8 Object-Based Approaches The Grid, ch 9 Commodity Supercomputing The Grid, ch 10 2/23 Services I: Globus The Grid, ch 11 Schedulers The Grid, ch 12 Resource Management The Grid, ch 13 3/1 Services II: Security The Grid, ch 16 Infrastructure I: Computing Platforms The Grid, ch 17 Network Protocols The Grid, ch 18 3/8 NO CLASS 3/15 Infrastructure II: Network Quality of Service The Grid, ch 19 Operating Systems The Grid, ch 20 Network Infrastructure The Grid, ch 21 3/22 Finish up The Grid book questions Theory Introduction 3/29 Spring Recess 4/5 Theory I: Impossibility with Partitioning Impossibility of Making Decisions with Partitioning 2-Phase Commit 3-Phase Commit 4/12 Theory II: Impossibility without Clocks Impossibility of Making Decisions with Failures and without Clocks Information Flooding Algorithms 4/19 Limited Batch Operating System (LBOS) World Beyond the Web (WBW) 4/26 World Beyond the Web (WBW) Hospital Computing Grid (HCG) 5/3 Listen to CS244 Project Reports 5/10 Security Mathematics of Cryptography Java Permission/Policy Based Security 5/17 Security TLS (son of SSL) Kerberos SSH JINI `The Grid' Book Assignments Each week when we discuss particular chapters of the book, you are NOT REQUIRED to have read the chapters in advance. The lecture during class will introduce the material in the chapters, often briefly. There will be a set of questions whose possible answers will be discussed somewhat during the class. New questions may also be posed. Many of these ques- tions will then be assigned during class as home- work. After the class, each student is then to read the chapters and compose answers to any 2 of the assigned questions. The student may freely choose which 2 questions to answer in any week. The exact assignment agreed upon during a class will be posted on the web site by the morning after the class, so there is no confusion. This posting is the final definition of the assignment. No printed version of these assignments will be handed out, but printed versions of some questions may be handed out. The answers are to be submitted by e-mailing them to cs254-grader@deas.harvard.edu by 1pm on the Tuesday before the next class including the phrase `question #' in the e-mail `Subject', where # is the question number that uniquely identifies the question in the course (e.g., `question 1.1', `question 2.5') PLEASE e-mail each question separately; they will be automatically sorted by question # and then the answers are to be resubmitted as hardcopy at the next class (the day after you e-mail the answers) PLEASE BE SURE to include your name and the question number on the hardcopy The hardcopy will be graded. The e-mailed answers will be made available only to class members via the internet soon after the class when the hardcopy is submitted. It is likely that the e-mailed answers will also be made available during the class at which the assignment is due, and discussed during class. There is an almost zero-tolerance lateness policy for these `The Grid' question assignments. The only lateness tolerated is that the e-mail submission may occur between 1pm Tuesday and the start of class at 4pm Wednesday, at the loss of 1 point (out of 10, see below). In computing the course grade for a student, only the highest 2/3'rds, roughly, of the student's question scores will be counted. This allows for occasional differences in view between grader and student about what is a good answer, and for some illness. Additional excuse for `The Grid' question assignments may only be obtained with a note from a doctor or appropriate officer of the university. If a student chooses, she or he may answer only one question, instead of two, in a given week, and the exclusion of the lowest 1/3'rd question scores can be applied to the other question. An answer to a question should not be longer than a printed page (e.g. 60 lines of 80 columns), and may be as short as one half page if well written. It is not necessary to give a complete answer to questions that would require long answers; in these cases it will suffice to answer some part of the question, or to give details of some part of the whole answer. IN ANY CASE the answer should contain one or more clear, coherent, and interesting ideas. Student's may need to visit and read web sites in order to answer a question. Students MAY NOT DISCUSS questions they are answer- ing with other students who are answering the SAME question. Students may discuss questions they are answering with other students who are answering DIFFERENT questions. We really do not want to see two students submitting highly similar answers, and may deduct points precipitously if we see a recurring pattern of this. However, two students may talk with each other if they are answering different parts of the same question, or if they are taking different sides of a debatable issue that is the answer. As long as students are not trying to answer the same thing, they can talk or show each other their answers. Each `The Grid' question answer will be graded on a scale of 1 to 10. We currently anticipate that each student will be asked to submit answers to 12 questions, of which 8 will count in the grade, and these will count for 25% of the total class grade. These numbers may change during the course. [The Grid questions will count for 50% of the course grade. Students will be given a score based on their highest 8 question scores, out of a total of 12 questions asked.] This assignment scheme will probably not be changed during the course, but we reserve the right to do so. Theory Assignments Much of the theory in this course involves defining a non-deterministic automaton that models some real world system very abstractly, and then proving theorems about that automaton. Students will be given handouts that state the definitions, theorems, and proofs to be covered. Most of the lemmas and theorems in these handouts will not have formal proofs given, though mostly there will be an informal discussion of the proofs somewhere in the handouts. The assignments will be to provide some of the proofs that are missing in the handouts. Usually these will be formal proofs. The other unassigned proofs will be designated as `practice proofs'. Students MAY NOT collaborate, either in writing or verbally, on any assigned proof. Instructors will NOT discuss assigned proofs with students, other than to give short hints. Students may collaborate, both in writing and verbally, on PRACTICE PROOFS. Students may ask instructors for detailed discussions of practice proofs. All FORMAL proofs submitted by students MUST be done in the numbered assertion style of the essay Proofs in Computer Science by Robert L. Walton in order to clearly show the nested structure of the proof. Informal proofs can be submitted in natural language style. Proofs must be formal unless indicated otherwise in the assignment. Each proof will be graded on a scale of 0 to 10. The grading is very strict. If a student does badly on a proof, the student may rewrite the proof and resubmit it. Then final grade will be the grade on the resubmission times 70%. The assigned proofs are due in writing in class. If a student gets less than 7 on a proof, the instructor will contact the student by email, and leave the graded homework of the student with the instructor's secretary in MD 133 by noon Friday after class (earlier if possible). The resubmission is due at the next class. Because of the resubmission policy, two students should NOT discuss assigned proofs until after they are BOTH sure they will not be resubmitting. This is the hardest part of the course. The total grade on these proofs will count for no more than 15% of the final grade. Readings for Theory Assignments All of the following are essays by BW. Introduction to the Formal Description of Computer Systems The following cover background material you should mostly already know, and therefore you can mostly skim these. With the exceptions noted below, this material will NOT be covered in class. Sets and Relations Proofs in Computer Science Labeled Graphs and Trees Automata In the last 4 essays, the following topics may be new to you, and will be covered in class: Partial Functions Labeling on Graphs Non-Language Automata In the last 4 essays, the following topics may be new to you, but will NOT be needed in the theory part of the course, and will be ignored: Closures of Relations Hypergraphs and Deductions Entity Relation Models The real reading of the theory part of this class is the following two essays: On the Impossibility of Making Decisions in Partitionable Systems On the Impossibility of Making Decisions without the Aid of Clocks Final Projects It was decided to have a final project worth 35% of the grade. Details are in the assignments file. Final Grading Three separate scores will be computed for each student: one for The Grid questions, one for theory, one for project. The last may not be numerical. The students will be ranked separately for each of the three kinds of scores. In all cases instructors examine the rank orderings and may make occasional minor adjustments, say for students who seemed to be going uphill during the course. Because of the heavy tutoring done on the theory problems, there may be some rank adjustments to be sure the tutoring does not unreasonably affect rank ordering. The base grade for each student will be assigned using The Grid question score and the project score, but treating the theory score as if it did not exist. Then this base grade will be adjusted by the theory score by up to + or - 1/6'th letter grade, so the total range of theory adjustment will be 1/3'rd letter grade. [Note we consider the difference between B+ and A- to be 1/3'rd letter grade: sorry.]