CS254r: Programming Methodologies; Catalog Number: 2767

Dr. Robert L. Walton; Prof. Thomas E. Cheatham

Half course (spring term). W., 4-6. EXAM GROUP: 9

The Official Definition

Investigates program analysis, verification, and refinement; programming paradigms including those for parallel and distributed programming; program development and maintenance environments. This year, in a reversal of roles, instructors will present a world-wide programming environment they are designing (including a prototype implementation), and students will critique this system. Student critiques can be based on theoretical considerations, on comparison with other systems, on practical experience the students get when they try to build application systems on top of the prototype programming environment, or on other appropriate considerations.

Prerequisite: Computer Science 51 and 121 or equivalent.

More Details

The instructors have under development a replacement for HTML called WBW, the `World Beyond the Web'. This is a novel system, possibly even a bit radical, based on JAVA serialized objects. WBW permits anyone (not just owners of servers) to write brokers that actively accumulate information and make decisions. One goal is to make a replacement for an operating system shell that manages computations world wide. This world-wide shell would keep a history of computations done, permit the history to be posted on the internet, searched, and examined, and permit computations to be rerun by different people with different parameters.

The instructors are developing the design of the WBW storage system, and are developing a prototype of this system. By itself the storage system permits brokers to be written, but the storage system does not contain a shell, and does not even contain the detailed data structures that would be manipulated by a shell.

An initial version of the prototype WBW storage system should be available when the class starts. This prototype will undergo continuing development by the instructors during the course.

The main idea of the WBW storage system is that a `page' is a list of attribute name/value pairs. A piece of program code is associated with the page, as determined by one or more of the attribute values, e.g., the page type, and by the environment the code will run in. The code presents the data in the page to the user. The code may present data in several related pages to the user. The code may also permit any user to update the page. The code may be updated independently from the pages that use it, and anyone who can write a page can write or update the code used with that page.

Requirements

The following may be refined as the course progresses.

All students must do the following:

Find some other existing or proposed system that is somewhat similar to WBW, and briefly report on the nature of this system, and its differences from WBW.
Students are encouraged to work in pairs or in larger groups. Groups reporting on the same system should correlate verbal presentations to avoid duplication.
Write a simple WBW broker. An example would be a world wide lending library that permits anyone to make some of their books available for lending to others, permits anyone to search for a neighbor willing to lend a particular book, and permits people to negotiate a lending transaction once lender and borrower have been matched.
Simpler and fancier versions of brokers are possible. Students are encouraged to work in pairs, or in somewhat larger groups, with the larger groups implementing more features in their brokers.
Write a convincing informal proof that each of several particular distributed (3 process) algorithms proposed for the WBW system are correct, even if there are process failures and malicious processes (of course the algorithm goals are different if there are failures or maliciousness). The situation is not trivial, and a convincing informal proof may be a few pages. Also discuss the flaws in the various proposed algorithms, and try to create a flawless algorithm and prove it correct.
Students should work in pairs (but NOT larger groups), with each proof section written by one student and edited by the other, sharing fairly. There will be class discussion of the proofs before final submission, but discussions outside of class between students not paired should be very minimal.

The above will take about half the course. In the second half of the course students must construct critiques of the WBW system. Each critique may be based on one or more of the following:

Experience the students get implementing some system (e.g., broker), or key parts of a system, on top of the WBW system. Here the system the students implement should be larger than (and may be an extension of) the simple broker required above.
An example of a more ambitious project would be to try to define some of the data types for WBW JAVA objects that would underlie the eventual WBW shell.
Purely theoretical analysis.
Careful and detailed comparison with other existing or proposed systems.
Any other appropriate basis for criticism and evaluation, subject to instructor approval.

Students can produce a single critique based on a larger amount of work by one or more people, or several smaller critiques each based on a smaller amounts of work. In general, students can otherwise design their own activities in the second half of the course, and work in groups of any size, subject to instructor approval, as long as the result is a critique of the WBW system.

Course Information

Handouts
- Jan 31: This web page; WBW Design Paper ( uncompressed).
- Feb 7: WBW User Manual ( uncompressed)
- Feb 11 (handout only on web): Binaries and Example Client. With these binaries you can write WBW clients and run your own WBW server or use our WBW server. Get this gzipped tar file and read the Read_Me file therein. Also, for older java runtimes, some newer java runtime classes are included in this jar file.
- Feb 14: Impossibility of Making Decisions in Partitionable Systems
- Mar 14: Impossibility of Making Decisions without the Aid of Clocks,
  WBW System Specification (early draft) ( uncompressed)
- Mar 18: Simple Broker Project Detailed Instructions
- Mar 21: WBW Theory Assignment
- Apr 11: WBW Theory Assignment Paper Outline
WBW Project home page.
WBW Resource List.
Room: Cruft 318 for the first 2 classes;
Maxwell-Dworkin 323 as of Feb 14.
Office Hours: Dr. Walton will be available (MD 121) most Mondays 1:15-5:15pm (except he may go to the 4pm CS colloquium usually in G125), and most Wednesdays 1:15-4:00pm (except if xeroxing is not done by 3pm it must take priority). It is best to email (walton@deas.harvard.edu) or call (495-7929) to agree on a time before you come, but this can be done rather at the last minute most days.
Course schedule as of May 2 (subject to revision):
- Jan 31: WBW Design Paper
- Feb 7: WBW User Manual
- Feb 14: Student Presentations: Briefly report on an existing or proposed system that is similar to WBW, and say what that system does (but do not compare with WBW).
- Feb 21: Student Presentations: Briefly report on the simple WBW broker you plan to implement and give some essentials of its design.
  Lecturer: Transversal Narrative of Update Operation.
- Feb 28: Beginning lecture on impossibility theorems.
- Mar 7: Student Presentations: Detailed verbal report on an existing or proposed system that is similar to WBW, and comparison of that system with WBW. Companion written report is due Monday Mar 12 in MD 121 or MD 133, 4pm.
  Lecture: More on on impossibility theorems.
- Mar 14: Student Presentations: Give a very brief oral review of your final project(s) and hand in a 1-2 page preliminary description.
- Mar 21: Student Presentations: Detailed verbal report on the design and user interface of the WBW broker you have implemented. User document and working code is due electronically by 4pm, Friday, March 23, before Spring Recess.
  Reports on existing system similar to WBW handed back for final revision.
  Mini-Lecture: WBW System Specification Paper
  Theory Assignment Handout: Assignment for algorithm correctness proofs and attempts to design flawless algorithm.
- Mar 28: Spring Recess
- Apr 4: Discussion of final projects.
  Final revisions of reports on existing systems similar to WBW are to be handed in. These will be Xeroxed during break and handed out to all the students.
  Lecture: Two-Server Algorithms and Theory Assignment
- Apr 11: Discussion of final projects. Written evidence of progress should be turned in by each student.
  Each student should bring an outline of the Theory Assignment document the class is to write cooperatively. In this outline redundancy may be reduced by saying for the 2nd and 3rd algorithm: `ditto as for the 1st algorithm except ...'.
  During break all these outlines will be Xeroxed. They will then be passed around and we will construct a common outline and assign the non-proof parts of the document to author/editor student pairs.
- Apr 18: Discussion of final projects. Students should hand in a final several page description of each project.
  Student presentation of Theory Assignment document non-proof parts. Hand in written drafts. Assignment of proofs to author/editor student pairs.
- Apr 25: Discussion of final projects. Written evidence of progress should be turned in by each student.
  Student presentation of Theory Assignment document proof parts. Hand in written drafts. Non-proof parts handed back for revision.
- May 2: Attend the CS144/244 class presentations in MD G115 from 4-5:30pm. Meet if necessary with Bob Walton at 5:30pm in the lobby outside G115.
  Students should submit by email as much of the theory assignment as they have done, for electronic markup with return by email. They should iterate this process over the next week or two until their part of the theory document is done. The theory document will be posted on the course web site (and maybe the wbw web site) when done.
  Students should request meetings with the instructor when the students determine there is a need.
- May 9: 15 min per person presentation of final project.
- May 18: Friday, 5pm. Final Project Submissions due. Theory assignments due if not previously finished (better to finish previously). Submit electronically and watch for confirmation. You can submit by email with a tar or ps file included, or can put in a public place and email the location. Don't `leave town' without confirmation.
- There are no exams.