CS-4513, Distributed Systems



6858000CS-4513, Distributed Systems,B-term 201000CS-4513, Distributed Systems,B-term 2010Distributed Computing Systems CS 4513B-Term 2010 This is a 4000-level undergraduate course during which you will study the concepts, design, and implementation of distributed computing systems. The course will:– Continue the study of computer operating systems begun in CS-3013, specifically the study of file systemsIntroduce the concepts of distributed computing and learn about protocols needed for their implementationReinforce the concepts of concurrency in computing environmentsright1905000During this course, students will work on team project to define, design, and implement a distributed application for Android phones. IndexGeneral OverviewSyllabus of TopicsDistributed Programming ProjectQuizzes and ExamsRecommended BackgroundCourse LogisticsOffice Hours and Schedule Grading PolicyAndroid Phones BS/MS CreditLecture Slides and NotesReference Materials Note: The main portion of this course web-site is password protected, including the Lecture Notes and Additional Project Notes. To access these, use user ID and password given in class must be supplied. General OverviewThis course will be a combination of lectures and class discussion, one major programming project, and quizzes and/or tests. Syllabus of TopicsThe following topics are typically included in CS-4513. It possible that some topics may be added or changed, depending upon the interests of the class and the needs of the programming project.File systemsRemote Procedure Call and Distribute File systemsNaming and Replication in Distributed SystemsAtomic Transactions and Distributed Atomic TransactionsMap-Reduce and Google-style distributed computation on a massive scaleAuthentication, including an introduction to encryption.The File Systems topic is a continuation of the Operating System course. You will be responsible for all of the material covered in Chapter 4 and in Section 5.4 of Modern Operating Systems, 3rd edition, by Andrew S. Tanenbaum. Students will be expected to be familiar with and to discuss the relevant sections of all reading material assigned during the term, whether mentioned in lectures or not.Distributed Programming ProjectThe practical component of this course will be a single, large, team programming project based on Android phones. Students will be divided into teams of about five people. Each team must propose and design a distributed application for the Android phone that is based on physical proximity to other users.The application may be anything you wish, but it must be distributed across at least three phones and scalable to several dozen phones. It must detect and recognize other copies of itself in the immediate vicinity and connect with those, so long as they stay near each other.Teams will be expected to propose their projects by the end of the second week, to report progress to the class by the end of the fourth week or the start of the fifth week, and give a final presentation on the last day of class.For additional information about Android phones, see below. For additional information about the project, see the following links:–Week1_AndroidProjectAssign.pptWeek1_AndroidProjectAssign.pdf Quizzes, Exams, and Class ParticipationIn lieu of a major exam for the course, there will be one quiz per week covering the recently introduced material. Quizzes will be held at 9:00 AM sharp and will last about 15-20 minutes. Up to two quizzes may be forgiven if arrangements are made with the professor in advance.Class participation is an essential part of the grade for the course. If you attend lectures but never say anything or engage in discussions, it would likely reduce your grade by one full letter or more. topRecommended BackgroundThe official course description on the WPI Computer Science web site says that this course “extends the study of the design and implementation of operating systems begun in CS 3013 to distributed and advanced computer systems. Topics include principles and theories of resource allocation, file systems, protection schemes, and performance evaluation as they relate to distributed and advanced computer systems.”You must have a solid background CS-3013 or an equivalent Operating Systems course. A full understanding of processes, threads, virtual memory, interrupts, and device handling is assumed.You will also need to know something about computer networks, protocols, and the 7-layer OSI stack. This is covered in CS-3516, Computer Networks. For those have not taken CS-3516 (or its predecessor, CS-4514), a brief tutorial will be offered at a time and place to be arranged in the first class. The following slides include the material of the tutorial. (.ppt, html). A tutorial on the use of sockets can be found here:– LogisticsCS-4513 meets for two 2-hour classes per week for a seven-week undergraduate term (28 hours). There will be no class on November 26 (Thanksgiving Day holiday).Time and Place: Tuesdays and Fridays, 9:00 — 10:50 AM, Salisbury Labs 305October 26 — December 14, 2010No class on Friday, November 26 (Thanksgiving Day holiday)Professor: Hugh C. LauerEmail: <professor’s last name>@cs.wpi.eduOffice hours: by appointment, or see chart belowOffice: Fuller Labs, room 235Teaching Assistant: Wei ZhangEmail: weizhang **at** cs.wpi.eduOffice hours: See chart belowOffice: Fuller Labs 317Textbooks:You need one of the following from an Operating System course:–Andrew S. Tanenbaum, Modern Operating Systems, 3rd edition, Prentice Hall, 2008.Silberschatz, Galvin, and Gagne, Operating Systems Concepts, John Wiley and Sons, 7th edition 2005 or 8th edition 2009. Class e-mail lists: The following two lists are in the domain cs.wpi.edu:–cs4513-all — to reach all students, the TA, and the professorcs4513-staff — to reach just the professor and the TA Course web site: Students needing to be absent from class should notify the professor by e-mail or in person as soon as possible, especially if a quiz is scheduled for the day of absence! HYPERLINK "" \l "_Index" topOffice Hours and ScheduleMondayTuesdayWednesdayThursdayFriday8:009:00ClassWZClass10:0011:00NoonHCL(if no CScolloquium)1:00HCL2:00WZHCL3:004:00topGrading PolicyFinal grades will be computed as follows: Quizzes: approx. 40% Team programming project: approx. 40% Class participation: approx. 20% Final grades will reflect the extent to which you have demonstrated understanding of the material, and completed the assigned projects. The base level grade will be a "B," which indicates that the basic objectives on assignments and exams have been met. A grade of "A" will indicate significant achievement beyond the basic objectives and a grade of "C" will indicate not all basic objectives were met, but work was satisfactory for credit. If there are any circumstances that limit or restrict your participation in the class or the completion of assignments, please contact the professor as soon as possible in order to work something out.Testing Weekly quizzes (see above) will be closed book and closed notes unless announced otherwise. There is no make-up for missed quizzes. If you have a planned absence during the term — for example, an interview, religious holidy, off-campus project activity, or other responsibility — please inform the professor in advance. Up to two quizzes may be forgiven.Skipping the final quiz is tantamount to taking an NR in this course.Academic Honesty Any violation of the WPI guidelines for academic honesty will result in no credit for the course and referral to the Student Affairs Office. More information can be found at individual assignments, you may consult with classmates, friends, colleagues, and others on the general idea of a problem, but you must then construct the final solution on your own and write it in your own words or your own coding style.Copying is not allowed. Borrowing algorithms from references, on-line sources, and other students is permitted provided that you cite your sources in your write-up and that you write out the solution in your own words or coding style!For team assignments, it is expected that all team members participate with roughly equal levels of effort. When you put your name on a team submission of an assignment, you are testifying not only that you have fully participated in that assignment, but also your teammates are also testifying that you have fully participated.Late Policy Unless you have arranged otherwise with the professor at least one day prior to the due date, late submissions will be penalized 10% of total assignment value per day or partial day (with the weekend counting as one day), and no assignments will be accepted after seven days beyond the due date. All assignments are due at the time specified on the assignment. Projects must be submitted as directed in class. Exceptions to these rules can be made only Android PhonesThe major project of this term is based on Android phones. The professor has received a grant of eighteen Motorola Droid phones from Google specifically for this course. In addition, students may use their own Android phones of any variety.Once a team has been established, the team may sign out one Droid phone for experimentation, plus several more when the project definition has been approved. All Android phones must be returned at the completion of the course. If a team member drops out or stops participating, any phones in the custody of that team member must be returned immediately and signed out by other team members.Failure to return signed out Android phones at the end of the course will be reported to the Campus Police as theft.To program Android phones, you will need access to the Android Software Development Kit, version 2.2 at the Android developer web site here:– . We have arranged for this to be installed in the public computer laboratories at WPI. In addition, there a numerous resources on the web about programming Android phones. Android phones are normally programmed in Java.Prior to starting the project, it is worthwhile to program the “Hello, World!” application on your phone. This can be found on the Android developer web site.The Droid phones as distributed by Google come with 30 days of “free” Verizon Wireless voice and data service (from the day of activation). You will not need this. Please don’t try to use it. You can connect via a WiFi network by the usual methods.When you first turn on one of these Droid phones, it wants you to go through the process of activating this account, along with an Android tutorial. The following web site explains how to skip the activation and tutorial step:– few of the phones already have been used and will not automatically start the BS/MS CreditStudents wishing to receive both BS and MS credit for this course must complete an additional research project. The project for this term is specified here (.doc, html). Note:If you wish to earn BS-MS credit, you must apply to the Professor at the start of the term and get a signature on the appropriate form. If you wait until after the course is completed, or after your BS-MS project is completed, you will not qualify for BS-MS Reference MaterialsThe following papers are relevant to the material presented in class:–Allman, Eric, “E-mail Authentication: what? Why? How?,” ACM Queue, November 2006, pp 30-34. (.pdf)Anderson, Thomas E., Dahlin, Michael D., Neefe, Jeanna M., Patterson, David A., Roselli, Drew S., and Wang, Randoph Y., “Serverless Network File Systems,” Proceedings of the 1995 Symposium on Operating System Principles, Copper Mountain, Colorado, December 1995. (.pdf)Birrell, Andrew D., Levin, Roy, Needham, Roger M., and Schroeder, Michael D., “Grapevine: An Exercise in Distributed Computing,” Communications of the ACM, vol 25, #4, April 1982, pp. 260-274. (.pdf)Birrell, Andrew D., and Nelson, Bruce Jay, “Implementing Remote Procedure Calls,” ACM Transactions on Computer Systems, vol. 2, #1, February 1984, pp 39-59. (.pdf)Dean, Jeffrey, and Ghemawat, Sanjay, “MapReduce: Simplified Data Processing on Large Clusters,” Communications of the ACM, vol 51, #1, January 2008, pp. 107-113. (.pdf)Dean, J. and Ghemawat, S. “MapReduce: Simplified data processing on large clusters,” In Proceedings of Operating Systems Design and Implementation (OSDI). San Francisco, CA, 2004. pp. 137-150. (.pdf). Note: This paper is an earlier version of the CACM paper above, but it contains some details not included in the CACM paper.Ghemawat, Sanjay, Gobioff, Howard, and Leung, Shun-Tak, “The Google File System,” Proceedings of the 2003 Symposium on Operating System Principles, Bolton Landing (Lake George), NY, October 2003. (.pdf)Gray, Jim, “Notes on Database Operating Systems,” in Operating Systems: an Advanced Course, vol 60 of Lecture Notes in Computer Science, Springer-Verlag, 1978, pp. 393-481 (.HYPERLINK ""pdf)Howard, John H., Kazar, Michael L., Menees, Sherri G., Nichols, David A., Satyanarayanan, M., Sidebotham, Robert N., and West, Michael J., “Scale and Performance in a Distributed File System,” ACM Transactions on Computer Systems, Vol 6, #1, Feb 1988, pp. 51-81. (.HYPERLINK ""pdf)L?mmel, Ralf, “Google’s MapReduce Programming Model — Revisited,” Microsoft Corp., Redmond, WA. (.HYPERLINK "'s%20MapReduce%20Programming%20Model%20Revisited.pdf"pdf)Lamport, Leslie, “Time, Clocks, and the Ordering of Events in a Distributed System,” Communications of the ACM, vol 21, #7, July 1978, pp558-565. (.HYPERLINK ""pdf)Lampson, B.W., and Sturgis, H. E., “Crash Recovery in a Distributed Data Storage System.”This widely referenced paper was not published anywhere. A copy of an original Xerox PARC report dated April 27, 1979 is here (.HYPERLINK "(earlier%20version).pdf"pdf). A later version dated June 1, 1979 appears here (.HYPERLINK ""pdf). This later version carries the following footnote:– “This paper was circulated in several drafts, but it was never published. Much of the material appeared in Distributed Systems—Architecture and Implementation, ed. Lampson, Paul, and Siegert, Lecture Notes in Computer Science 105, Springer, 1981, pp 246-265 and pp 357-370.McDougall, Richard, “Extreme Software Scaling,” ACM Queue, September 2005, pp 38-48.(.HYPERLINK ""pdf)Patterson, David A., “The Data Center is the Computer,” Communications of the ACM, vol 51, #1, January 2008, p. 105 (.HYPERLINK ""pdf). Note: This paper is technical perspective on the CACM paper by Dean and Ghemawat, listed above.Rosenblum, M, and Ousterhout, J. K., “The Design and Implementation of a Log-Structured File System,” Proceedings of 13th ACM Symposium on Operating Systems Principles, Pacific Grove, California, October 1991, pp. 1-15.(.HYPERLINK ""pdf)Schroeder, Michael D., Birrell, Andrew D., Needham, Roger M. “Experience with Grapevine: Growth of a Distributed System,” ACM Transactions on Computer Systems, Vol. 2, #1, February 1984, Pages 3-23. (.HYPERLINK ""pdf)Smed, J., Kaukoranta, T., and Hakonen, H. “Aspects of Networking in Multiplayer Computer Games,” The Electronic Library, vol. 20, #2, Pages 87-97, 2002. (.HYPERLINK ""pdf)Sutter, Herb, and Larus, James, “Software and the Concurrency Revolution,” ACM Queue, September 2005, pp 54-62. (.HYPERLINK ""pdf)Waldo, J., Wyant, G., Wollrath, A., Kendall, S., “A Note on Distributed Computing,” Sun Microsystems Laboratories, Inc., Technical Report SMLI-TR-94-29, November 1994. (.HYPERLINK ""pdf)top ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download