Peer-to-Peer Storage Systems: Exam Information

Spring 2004

Exam in Peer-to-Peer Storage Systems

Please send Henning (hniss@itu.dk) an email if you discover any inaccuracies or have comments on this page.

All significant changes to the contents of this page will also be announced by email on the official ITU course mailing list. (If you have received various announcements during the semester you are on the list.) Below you can also find a list of changes to the document.

Contents

dates | schedule | procedure | questions | preparation time | language | exam aids | curriculum | question/answer sessions | exam schedule

Dates

The exam will take place on Friday, June 18th, and Monday, June 21th. Students that have indicated that they prefer to be examined on June 18th will of course be examined on that day. Everybody has been signed-up for the exam.

A small plea: please, please let us know in advance if you don't intend to show up for the exam.

Schedule

The following table shows dates for important "events" in relation to the exam.

When What
May 28th
 Example exam questions posted (done).
June 1st
 Last chance to state date preference (within reason) (done).
June 2nd
 Exam schedule posted (done).
June 4th
 Real exam questions posted (done).
June 11th
(9:00-12:00)		 Question/answer session.
June 18th
(all day)		 Exam.
June 21th
(all day)		 Exam.

Procedure

You draw a question at random and immediately start presenting it. The presentation should take 10 minutes. It is followed by 15 minutes of questioning from the examiners. This may include questions in topics not covered by the question you have drawn, but it will be in material in the curriculum. Finally there are 5 minutes for evaluation and feedback.

Questions

We will announce example questions on May 28th. Two weeks prior to the exam (on June 4th) the "real" exam questions will be posted here.

Below are the real exam questions (also available on a separate page for easier printouts).

Below you will find eight questions/presentation topics each starting off from a concrete system, and each consisting of three to four subtopics. For each of the questions you should prepare, in advance, a presentation covering the subtopics listed for the question (and therefore, eight presentations in total). Each presentation should last no more than 10 minutes, and it is your responsibility to ensure this. You will therefore have to be brief when covering the subtopics listed below.

  1. Freenet
    • Describe the essentials of how Freenet stores and locates files.
    • Illustrate with an example how a file may move around in the network.
    • Describe the limitations of Freenet and contrast Freenet-style routing with other routing algorithms such as the ones used by Chord, Pastry, and SkipNet.
    • Give an overview of which kinds of anonymity Freenet provides and how it is achieved, and compare with FreeHaven.
  2. Chord
    • Describe the core functionality of a routing layer.
    • Describe and illustrate the use of finger tables in Chord.
    • Describe how stabilization works when a node is detected to be dead by a neighbour.
    • Compare the Chord routing algorithm to other routing algorithms such as the ones used by Freenet, Pastry, and SkipNet.
  3. Pastry
    • Describe the core functionality of a routing layer.
    • Describe the essentials of the Pastry routing algorithm (focus, for example, on core principles and network proximity).
    • Illustrate with an example how a message is routed from one peer to another.
    • Compare the Pastry routing algorithm to other routing algorithms such as the ones used by Freenet, Chord, and SkipNet.
  4. SkipNet
    • Describe the core functionality of a routing layer.
    • Describe the essentials of the SkipNet routing algorithm (focus, for example, on core principles of name based and numeric routing).
    • Illustrate with an example how a message is a routed from one peer to another.
    • Compare the SkipNet routing algorithm to other routing algorithms such as the ones used by Freenet, Chord, and Pastry.
  5. OceanStore
    • Illustrate with an example how a file is published and stored in OceanStore.
    • Describe how applications using OceanStore can update files and how OceanStore stores files.
    • Describe the tradeoff of consistency and efficiency in OceanStore and the difference between the primary and secondary replicas.
  6. Scribe
    • Describe the Scribe multicast tree data structure and how it is used to efficiently multicast messages to a group of recipients.
    • Describe how the tree structure is maintained when nodes join and leave multicast groups.
    • Illustrate with an example what happens when an interior node, in the multicast tree for a Scribe group, dies.
  7. SplitStream
    • Describe the essentials of the way SplitStream streaming works.
    • Describe and dicuss the invariant that SplitStream tries to maintain, and follow up with a discussion of how and why the invariant is allowed to be weakened.
    • Illustrate with an example how a new child wanting to listen on a stripe is adopted when the node it contacts has reached the outdegree limit.
  8. PIER
    • Describe the essentials of how tables are represented in the PIER system.
    • Illustrate with an example how a query is executed in PIER.
    • Describe the notion of query consistency offered by PIER and illustrate with an example how this may affect the result of a query,

The following three questions are examples of the "real" exam questions. They are meant to be indicative of what you might encounter later (and they were in fact selected from the full list of questions).

Below you will find three example questions/presentation topics each starting off from a concrete system. For each of the questions you should prepare, in advance, a presentation covering the subtopics listed for the question (and therefore, three presentations in total). Each presentation should last no more than 10 minutes, and it is your responsibility to ensure this. You will therefore have to be brief when covering the subtopics listed below.

Preparation time

No time is offered for preparation (you will know the presentation topics in advance).

Language

The examination is performed in English or Danish at your choice. During a Danish examination, you are welcome to use the English technical terms.

Exam aids

For each question you are encouraged to bring slides for a 10 minutes presentation. Please bring hard-copies on foils rather than an electronic version. For the presentation you may at most use 3 slides with figures, keywords and short notes. No credit is given for saying what is on the slides, so it is recommended that they only include a disposition and possibly figures. The exam questions including the subtopics will be available for you on paper in the examination room.

Curriculum (pensum)

The following is a list of the curriculm for the exam.

Please note, that the paper announced via email for PIER was wrong. The correct one is listed below (namely, the one we used in class).

The curriculum list consists of the following papers, as well as slides and questions (here is a page with the complete list of questions) for lectures 2. to 10. mentioned on the main web page.

Freenet
Ian Clarke, Oskar Sandberg, Brandon Wiley, and Theodore W. Hong, "Freenet: A Distributed Anonymous Information Storage and Retrieval System", in Hannes Federrath (ed), "Designing Privacy Enhancing Technologies: International Workshop on Design Issues in Anonymity and Unobservability", LNCS 2009, Springer, 2001.
http://www.doc.ic.ac.uk/~twh1/academic/papers/icsi-revised.pdf
Chord
Ion Stoica, Robert Morris, David Liben-Nowell, David R. Karger, M. Frans Kaashoek, Frank Dabek, Hari Balakrishnan, "Chord: A Scalable Peer-to-peer Lookup Protocol for Internet Applications". To Appear in IEEE/ACM Transactions on Networking.
http://www.pdos.lcs.mit.edu/chord/papers/paper-ton.pdf
OceanStore
John Kubiatowicz, David Bindel, Yan Chen, Steven Czerwinski, Patrick Eaton, Dennis Geels, Ramakrishna Gummadi, Sean Rhea, Hakim Weatherspoon, Westley Weimer, Chris Wells, and Ben Zhao, "OceanStore: An Architecture for Global-Scale Persistent Storage", appears in Proceedings of the Ninth international Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS 2000), November 2000.
http://oceanstore.cs.berkeley.edu/publications/papers/pdf/asplos00.pdf
Pastry
Antony Rowstron and Peter Druschel, "Pastry: Scalable, distributed object location and routing for large-scale peer-to-peer systems". IFIP/ACM International Conference on Distributed Systems Platforms (Middleware), Heidelberg, Germany, pages 329-350, November, 2001.
http://research.microsoft.com/~antr/PAST/pastry.pdf
Scribe
Miguel Castro, Peter Druschel, Anne-Marie Kermarrec and Antony Rowstron, "SCRIBE: A large-scale and decentralised application-level multicast infrastructure", IEEE Journal on Selected Areas in Communications (JSAC) (Special issue on Network Support for Multicast Communications). 2002, to appear.
http://research.microsoft.com/~antr/PAST/jsac.pdf
SkipNet
Nicholas J.A. Harvey, Michael B. Jones, Stefan Saroiu, Marvin Theimer, and Alec Wolman, "SkipNet: A Scalable Overlay Network with Practical Locality Properties", in Proceedings of the Fourth USENIX Symposium on Internet Technologies and Systems (USITS '03), Seattle, WA, March 2003.
http://www.research.microsoft.com/sn/Herald/papers/USITS/SkipNet-Usits.pdf
FreeHaven
Roger Dingledine, Michael J. Freedman, David Molnar, "The Free Haven Project: Distributed Anonymous Storage Service", in Proceedings of the Workshop on Design Issues in Anonymity and Unobservability, July 2000 (LNCS 2009).
http://www.freehaven.net/doc/berk/freehaven-berk.ps
PIER
Ryan Huebsch, Joseph M. Hellerstein, Nick Lanham, Boon Thau Loo, Scott Shenker, Ion Stoica, "Querying the Internet with PIER.". In VLDB, 2003.
http://db.cs.berkeley.edu/papers/vldb03-pier.pdf
SplitStream
M. Castro, P. Druschel, A-M. Kermarrec, A. Nandi, A. Rowstron and A. Singh, "SplitStream: High-bandwidth multicast in a cooperative environment", SOSP'03, Lake Bolton, New York, October, 2003.
http://research.microsoft.com/~antr/PAST/SplitStream-sosp.pdf

Question/answer session

There will be a question/answer session (spørgetime) on Friday, June 11th from 9:00 to 12:00. If you know some of your questions in advance, please send them them by email to Henning (hniss@itu.dk).

Exam schedule

The actual scheduling of each student will follow later on June 2nd. Everybody that indicated that they wished to be examined on June 18th, will of course be examined on that day. If you have a preference for one of the two days, but have not already said so, please do that by email to Henning (hniss@itu.dk) no later than June 1th.

The final schedule will be announced by email and posted here on June 2nd. Please check this page for changes to the schedule on June 17th. All changes will also be announced by email as soon as possible.

Since some people may not show up, you must be at ITU at least half an hour before the scheduled time (unless you are first in the morning or at 13:00).

Here is the exam schedule (everybody should have had their wishes satisfied).

Friday, June 18th

09:00-09:30Nicolai Ritz* 13:30-14:00Håvard Semundset*
09:30-10:00Morten Franck* 14:00-14:30Christian Theil Have
10:00-10:30Matthew Paul Travaille* 14:30-15:00Morten Bjerre
10:30-11:00Paul Frederick d'Souza 15:00-15:30Orri Gautur Palsson
11:00-11:30Eirik Todal Laberg* 15:30-16:00Troels Krogh*
11:30-12:00Chr. Schmidt-Madsen* 16:00-16:30
12:00-12:30Peter Gath Hansen* 16:30-17:00
12:30-13:30Lunch break

Monday, June 21th

09:00-09:30Peter Tiedemann** 12:00-13:00Lunch break
09:30-10:00Niels Teglsbo 13:00-13:30Jesper Munk**
10:00-10:30Mikkel Blanne** 13:30-14:00Erik Matthias Verdoner**
10:30-11:00Erik Aarslew-Jensen** 14:00-14:30Philip Skov Knudsen
11:00-11:30Mads Lundemann 14:30-15:00Sravan Kumar Anathula**
11:30-12:00Mads Danquah 15:00-15:30

A brief note about the schedule generation: Everybody was registered as either don't care about exam day (no marker above), prefers June 18th (a * marker above), or prefers June 21th (a ** marker above). Then a random schedule was generated for each of the two days, where the "don't care" students were randomly distributed to those days. Finally, as Nicolai Ritz and Peter Tiedemann had both wished to be examined early during the day, Peter was moved to the front of the second day's schedule (Nicolai, by chance, already was at the front).

Updates: Morten Franck moved to early on the first day. Mikkel Blanne moved to early on the second day. A few cancellations registered. Troels Krogh moved up one slot.

Last updated: June 4, 2004 (hniss) With inspiration from the Distributed Systems exam page.

Changes to the document

When What
2004/06/17 Minor exam schedule changes (twice).
2004/06/15 Minor exam schedule changes.
2004/06/07 Tried to clarify the number of questions posted.
2004/06/04 Real exam questions posted.
2004/06/03 HTML'ified exam schedule.
2004/06/02 Exam schedule posted.
2004/05/28 Example questions posted.
2004/05/21 First version of the page.