CS254r ASSIGNMENTS Feb 10, 2000 For `The Grid' assignments, rules are in the syllabus, and the questions are in `Questions for The Grid Book Assignments'. Assignment due 2/8 1pm e-mail, 2/9 in class hardcopy: Do a `The Grid' assignment choosing any two questions from among: 1.1, 1.2, 1.3, 1.4, 2.1, 2.2, 2.3, 2.4, 2.5, 2.6. NOTICE: The due date for the above assignment has been extended to 1pm Fri 2/10 for e-mail and 5pm Fri 2/10 in room 133 for hardcopy. However, students taking advantage of this cannot do question 1.3 or 2.2. This extension is due to students arriving late in the course. Assignment due 2/15 1pm e-mail, 2/16 in class hardcopy: Do a `The Grid' assignment choosing any two questions from among: 3.1, 3.2, 4.1, 4.2, 4.3, 4.4, 5.1, 5.2, 5.3, 5.4, 6.1, 6.2, 6.3 One of the answers you give MUST involve doing some research using the web. Questions 4.1, 4.2, 4.3, 4.4, and 5.4 clearly qualify. Many of the other questions would also qualify if you find a way of answering them that uses information from the web. For example, you might find examples of tera- and penta-byte databases on the web. Also, it is preferred, but not absolutely required, that your two questions be from DIFFERENT chapters. Assignment due 2/22 1pm e-mail, 2/23 in class hardcopy: Do a `The Grid' assignment choosing any two questions from among: 7.1, 7.2, 8.1, 8.2, 8.3, 9.1, 9.2, 9.3, 9.4, 9.5, 10.1, 10.2 One of the answers you give MUST involve doing some research using the web. Also, it is preferred, but not absolutely required, that your two questions be from DIFFERENT chapters. Assignment due 2/29 1pm e-mail, 3/1 in class hardcopy: Do a `The Grid' assignment choosing any two questions from among: 11.1, 11.2, 11.3, 11.4, 11.5, 12.1, 12.2, 13.1, 13.2 One of the answers you give MUST involve doing some research using the web. Also, it is preferred, but not absolutely required, that your two questions be from DIFFERENT chapters. Assignment due 3/14 1pm e-mail, 3/15 in class hardcopy: Do a `The Grid' assignment choosing any two questions from among: 16.1, 16.2, 17.1, 17.2, 17.3, 17.4, 17.5, 18.1, 18.2, 18.3 One of the answers you give MUST involve doing some research using the web. Also, it is preferred, but not absolutely required, that your two questions be from DIFFERENT chapters. Assignment due 3/21 1pm e-mail, 3/22 in class hardcopy: Note: there will be NO lateness penalty for submitting e-mail up to 24 hours late on this assignment. Do a `The Grid' assignment choosing any two questions from among: 19.1, 19.2, 19.3, 20.1, 20.2, 20.3 21.1, 21.2, 21.3 Problems from the Impossibility of Making Decisions in Partitionable Systems Proofs of Lemma's 7, 10, and 11 are PRACTICE Problems. Proofs of Lemma's 9 and 12, proof of Theorem 13, and definition of the algorithm left to the reader near the bottom of page 2, are ASSIGNED problems; do NOT discuss with other students. UNGRADED Assignment due 4/5 in class hardcopy: You should do the following practice problems and bring your solution to class. Solutions will be passed out and gone over in class. You can grade your own solutions, they will NOT be collected. 1. Prove Lemma 7. 2. Prove Lemma 10. 3. Prove Lemma 11. Assignment due 4/12 in class hardcopy: These problems are to be graded. Do NOT discuss with other students. 1. Prove Lemma 9. 2. Prove Lemma 12. 3. Prove Theorem 13. 4. Describe INFORMALLY a very simple algorithm that makes decisions in a partitionable system where the sender is reliably informed whether a sent message is received, and all messages take less than 1 second to deliver. See the bottom half of page 2. Problems from the Impossibility of Making Decisions without the Aid of Clocks Proofs of Lemma's 2, 5, 10, 13, 17, 18, 21, and Corollary 6 are PRACTICE Problems. The solutions to SOME of these will be handed out in class. Proofs of Lemma's 14, 15, 19, and 20 are ASSIGNED problems; do NOT discuss with other students. Proof of Lemma 22 and the Lemmas and Theorems following are reserved for students who decide they would like to do more work on proofs instead of doing some other final project; so please do NOT discuss these with other students. Assignment due 4/19 in class hardcopy: These problems are to be graded. Do NOT discuss with other students. 1. Prove Lemma 14. 2. Prove Lemma 15. 3. Prove Lemma 19. 4. Prove Lemma 20. It is OK to run up to 1.5 days late with problems 1 and 2 (turn in by Friday 1pm); and up to one week late with problems 3 and 4; BUT, you are not excused from doing the subsequent assignment while you are working on late proofs. The next assignment is a project. If you want, you can do more proofs, Lemma 22 and following, instead of a project. [As has been announced in class, late theory assignments and resubmits have been accepted without time limit or penalty as long as students worked by themselves on the problems in an orderly manner. This is because for about half the class the proofs are a very hard assignment and the pedagogical situation is such that extensive tutoring is the only viable approach. Students may submit/resubmit up till 5/25, but should submit a little at a time and get feedback, and should not submit very much at the last minute.] Projects You can choose any of the following as a final project for the course. You are expected to put in about 30 person hours over about 4 weeks. You may work in a team with other students in the course, but as the time is short, be careful you do not have to interact too much to make progress, and be sure you are clear on who is graded on what (if a document has two equal authors both get the same grade and the document should have 60 hours work). As usual, you may discuss your project with anyone who is not supposed to be doing the same thing independently. The project is due 5/17. It is the last assignment [Note, the due date was changed to 5/25 on 5/10] in the course (after the theory assignments). It is your opportunity to focus on what interests you most in this rather large subject. The possible projects are: 1. Write a formal description of one or more exist- ing systems apropos to this course, using the method of `A Survey of Distributed Directories'. [Note this last document never got written during the course. A VERY early draft was given to students who asked for it.] 2. Write a customer specification, user manual, or design document for a system intended to help grid something (the world, a hospital, your home). Examples for WBW, LBOS, and and HCG will be handed out in class. 3. Write a critique of several related systems. See `Design of a New World-Wide Information Storage System' for an indication of the types of issues that may need to be raised. For each system, identify the critical choices that determine the nature of the system. 4. Benchmark a system apropos to this course, e.g. Globus. You may have to help install the system on the class computers (method1 and method2). Benchmarking can be broadly interpreted to mean give prototype programs that show that the system works, without timing. Its conceivable that you may have to write a report on how the system could not be installed, but it should be a close call with interesting details. The instructors may help install systems if they have time. Examples are globus, condor, beowulf. 5. Continue your study of proofs by proving Lemma 22 and beyond in the Clocks paper. NOT A TEAM PROJECT. 6. Write a somewhat formal description of a main theoretical result in distributed computing, such as results from Larry Raab's thesis to the affect that cacheing writable data in a distributed transaction system may not help availability much, or results on virtual synchrony. 7. You may suggest your own idea for a project subject to approval. Project Submission Instructions: The reports for your project should be placed in the basket specially prepared to receive them. This basket has a piece of cardboard labeled CS254r FINAL PROJECTS on top of the reports in the basket, and a place to check off your names on the cardboard when you place your report in the basket (and under the cardboard). The basket, most unfortunately, is going to move around a bit. It will be in MD 121 till latish Wed afternoon However, there may be NO one to open the MD 121 door for you on Tuesday or until 1:30pm Wed. If you come Wed afternoon, look around in MD 121 or 141 or the second floor printer for BW. If you are coming after 4pm Wed, email walton@deas earlier. in MD 247 from latish Wed afternoon till Friday early afternoon This is Ronda Scott's office. Ronda leaves at 5pm sharp, so don't be late. Ronda may not be in on Friday. in MD 121 OR MD 141 on Friday from the early afternoon (1-1:30pm) There you will find TEC and BW grading the projects. The reports are officially due Thur by 5pm sharp (don't be late). But we will not notice if you somehow get them in the basket before we start grading Friday at 1pm or later. Note there will be NO one in our MD 133 secretary's office on Wed, Thur, or Fri. Sorry for the complexity this causes. If you are planning on handing in the report sometime other than Wed afternoon before 4pm or Thur afternoon before 5pm, please tell walton@deas by email or in person. The instructors would also like you to email walton@deas one copy of each report for posting on the class PRIVATE web page. Consider this an assignment unless you really object to having the report posted, in which case we will let you out of this.