📄 http:^^www.cs.utexas.edu^users^joshi^cs380d-main.html
字号:
MIME-Version: 1.0
Server: CERN/3.0
Date: Monday, 06-Jan-97 21:45:24 GMT
Content-Type: text/html
Content-Length: 8021
Last-Modified: Thursday, 11-Apr-96 15:24:04 GMT
<HTML><HEAD><TITLE>CS 380D : Distributed Computing I</TITLE><!-- Changed by: Rajeev Joshi, 10-Apr-1996 --></HEAD><basefont size=4><center><H1>CS 380D : Distributed Computing I</H1><H2>Spring 1996</H2></center><HR><H3>Instructor : <b>Lorenzo Alvisi</b></H3><H3>Teaching Assistant : <b>Rajeev Joshi</b></H3><HR><br><center><b>Contents</b></center> <UL> <LI> <a href="#Staff">Office Hours & Locations</a> <LI> <a href="#Mechanics">Mechanics</a> <LI> <a href="#Textbook">Required Textbook</a> <LI> <a href="#Content">Course Content</a> <LI> <a href="#Grading">Grading</a> <LI> <a href="#Assignments">Problem Sets</a> <LI> <a href="#Final">Information pertaining to the final exam</a> <LI> <a href="midterm-solutions.ps">Suggested Solutions to the Midterm Exam</a> <LI> <a href="news:utexas.class.cs380d">Newsgroup <I>(utexas.class.cs380d)</I></a> </UL><HR><center><H2><A NAME=Staff>Instructional Staff</A></H2></center><b>Lorenzo Alvisi</b>, Taylor Hall 4.122, Phone: 471-9792 <BR>Office Hours: Tuesdays, 10:00-12:00<BR> <BR><b>Rajeev Joshi</b>, UA-9 #4.108D , Phone: 471-9756<BR>Office Hours: Mondays and Thursdays, 2:00-4:00 pm.<BR><P>Other meetings with Lorenzo and Rajeev can be arranged by appointment.<P><HR><center><H2><A NAME=Mechanics>Mechanics</A></H2></center><P>I expect that 2/3 of the classes will cover material from the requiredtextbook; the remainder will come from other sources (i.e. papers,other textbooks). References to such sources will be given in classat the appropriate time.<P>Lectures: 9:00-10:30 Monday and Wednesday, in Robert Lee Moore Hall5.124.<BR>The newsgroup for the class is<a href="news:utexas.class.cs380d">utexas.class.cs380d</a>.<P><HR><center><H2><A NAME=Textbook>Required Textbook</A></H2></center><P><em> Distributed Systems</em>, Second Edition, S. Mullender (editor), ACMPress, Addison-Wesley Publishing Company, Reading MA, 1994.<P><HR><center><H2><A NAME=Content>Course Content</A></H2></center><P>CS380 covers abstractions that have proved useful or are expected tobe useful for designing and building tomorrow's distributedsystems. These include:<UL><LI> global states (cuts, logical and vector clocks, causal messagedelivery, global property detection)<LI> message logging and checkpointing<LI> replication management (state machine approach, primary backupapproach)<LI> agreement protocols (Byzantine agreement, ordered multicast)<LI> group programming (techniques and applications)<LI> distributed file systems (caching, disconnected operations)<LI> time services (Byzantine clock synchronization, NTP)<LI> security (encryption, authentication, security in group programming)</UL><P>We will integrate the discussion of the general principles with thepresentation of case studies that exemplify how such principleshave been used to design and implement real systems.Other topics, depending on time and interest, will be presented by meor by some of you (the size of the class does not allow all of you to give apresentation). Such topics may include:<UL><LI> distributed shared memory<LI> distributed objects<LI> kernel support for distributed systems<LI> weak consistency for replica management<LI> protocols for electronic commerce<LI> protocols for wide-area networks</UL><HR><center><H2><A NAME=Grading>Grading</A></H2></center><P>There will be 4 or 5 written homework assignment. Solutions will begraded F, B, or A. Any solution that demonstrates a credible effort onbehalf of its authors (whether the solution is right or wrong) willreceive a B or better.<P>Collaboration on homework assignment by up to three students ispermitted and encouraged, but not required. When there is such acollaboration, a single solution should be submitted forgrading, with the names of the collaborators. Other collaborationswill be considered violations of Academic Integrity.<P>There will be a written, take-home midterm examination, for which nocollaboration will be allowed.<P>There will be no final exam. Each student however will be required towrite a final paper (about 20 pages) that surveys one of the issuesthat we have discussed in class. A list of suggested topics will bedistributed in class on Monday 4/8. The paper is due at the start ofthe last class, Wednesday 5/1: hence, you will have 4 weeks tocomplete the paper.<P>You can also team up with a colleague and prepare one or twolectures on a topic not previously covered in class. If you choosethis option, you and your colleague will only be required to write asingle survey paper of about 20 pages. I warmly encourage you toconsider volunteering for a presentation: it will give you an excellentopportunity to improve your communication skills.<P><HR><center><H2><A NAME=Assignments>Problem Sets</A></H2></center><P>In this and all subsequent problem sets, you shouldconform to the following general guidelines:<UL><LI> ``Prove'' and ``show'' are synonymous. A precise proof isrequired when you are asked to ``prove'' or ``show'' something.<LI> To show that something is impossible, you have to give a proof thatmakes it clear that the problem cannot be solved, no matter what the algorithmis. It is insufficient to show that a particular algorithm does not work.<LI> Any algorithm that you develop must be accompanied by a proof ofcorrectness, unless you explicitly told otherwise.</UL><P><HR><img src="images/hpoint-right.gif"> <b>Due: Mon, 5 Feb 1996</b><br><DL ><DT>Problem 1<DD> The snapshot protocols discussed in class and in thetextbook assume that communication channels are FIFO. Derive asnapshot protocol for an asynchronous system that does not depend onthe FIFO assumption, and prove it correct (i.e. prove that theprotocol produces a consistent global state). You may assume that atmost one snapshot is being computed at any point during a run. <BR><b> Note</b>: The book contains a reference to a paper by Mattern thatcontains a solution to the problem. I urge you to resist thetemptation to solve the problem by visiting the library...<P><DT>Problem 2<DD> Taking the snapshot of a distributed computation is ageneral technique for computing stable global predicates. Moreefficient protocols can be derived for computing specific predicates,that are often conceptually simpler and more efficient (in terms ofthe number of messages they exchange) than a snapshot-based solution.<P>In this problem you are required to derive such a ``specialized''protocol for detecting a deadlock in an asynchronous distributedsystem. Ideally, your protocol would not need a centralized monitorprocess, and would have a message cost of <em>O(n)</em>, where <em>n</em>is the number of processes in the distributed system (a monitor-basedsnapshot protocol for detecting deadlock has a cost of <em>O(n*n)</em>).</DL>The suggested solutions to these problems are nowonline. <a href="solutions.ps">This link points to the postscript file.</a><HR><img src="images/hpoint-right.gif"> <b>Due: Wed, 28 Feb 1996, 0900</b><br><a href="ProblemSet2.ps">This link points to the postscript file</a>describing the second homework assignment.<HR><center><H2><A NAME=Final>The final exam</A></H2></center>The assignment constituting the final exam is due <b>by 5 p.m., FridayMay 3, 1996. </b><br><a href="final.ps">This link</a> points to thePostscript file describing the assignment.<HR><img src="images/mail.gif" align=top border=0>If you have questions, feel freeto send email to <a href="mailto:lorenzo@cs.utexas.edu"> Lorenzo</a> or to<a href="mailto:joshi@cs.utexas.edu"> Rajeev</a> .<HR></BODY><basefont size=3><ADDRESS><br><b>If you have ideas on improving this page, please send yoursuggestions to<br></b><a href="mailto:joshi@cs.utexas.edu"><img src="images/mail.gif" align=top border=0><tt> joshi@cs.utexas.edu</tt><br><br></a>Rajeev Joshi, last updated 11 Apr 1996<br><br></ADDRESS></HTML>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -