| Date |
Topic |
Readings |
Handouts |
Notes |
| 09.05.02 |
Shared memory algorithms Mutual Exclusion: Nancy Lynch |
Lamport-fast-mutex Friedberg and Peterson |
H1Course
description H2Readinglist H3 Schedule |
Lecture1 (.tex)
(.ps) |
| 09.10.02 |
Renaming:
Nancy Lynch |
Moir-Anderson-fast-ll-ren Attiya-Fouren-adapt-agmt-ren |
Lecture2 (.tex)
(.ps) |
|
| 09.12.02 |
Computing
with unknown set of participants. Computing with faulty objects:
Nancy Lynch |
Meritt-Taub-infinite-procs |
H4
Schedule version2 |
Lecture3
(.tex) (.ps) |
| 09.17.02 |
Client-server computing Byzantine quorum systems: Rodrigo Rodrigues |
Dahlia
Malkhi and Michael Reiter. Byzantine quorum systems. Distributed
Computing,1998. .ps Lorenzo Alvisi et al. Dynamic Byzantine quorum systems. In International Conference on Dependable Systems and Networks, 2000. .ps |
Lecture4 (.ps) |
|
| 09.19.02 |
Shared
memory algorithms(cont.) Computing with Unknown set of Processes: Nancy Lynch |
Meritt-Taub-infinite-procs(cont.) Gaf-Merit-Taub-conc-hierar Yehuda Afek, David Greenberg, Michael Merritt, and Gadi Taubenfeld. Computing with faulty shared objects. Journal of the ACM, 42(6):1231--1274, November 1995. .ps jayanti-chdra-toueg(shorter version .pdf) |
Lecture5 (.tex) (.ps) |
|
| 09.24.02 |
Client-server computingConsensus:Toh Ne Win, Rui Fan |
Eli Gafni and Leslie Lamport. Disk Paxos. To appear in
Distributed Computing. Also appeared as SRC Research
Report 163 (July, 2000). .ps
G. Chockler and D. Malkhi. Active Disk Paxos with infinitely many processes. In Proceedings of the Twenty-First ACM Symposium on Principles of Distributed Computing (PODC 2002), Monterey, CA, July 2002. .ps |
Lecture6 (.tex) (.ps) |
|
| 09.26.02 |
Networks
with known participants Logical time. Clock synchronization: Nancy Lynch |
Hagit Attiya
and Jennifer Welch. Distributed computing: Chapters 6 and 13. |
Lecture7 (.tex) (.ps) |
|
| 10.01.02 |
Data replication: Rodrigo Rodrigues |
Miguel Castro and Barbara Liskov.
Practical Byzantine fault tolerance. In Proceedings of the
Third Symposium on Operating Systems Design and Implementation,
.ps
Rodrigues, Castro, Liskov. BASE: Using abstraction to improve fault tolerance. In Proceedings of the 18th ACM Symposium on Operating Systems Principles (SOSP), .ps |
Lecture8 (.ppt) |
|
| 10.03.02 |
Failure detectors: Tina Nolte |
Chandra, Toueg. Unreliable
failure detectors for reliable distributed systems. Journal
of the ACM, 1996. .ps Aguilera, Chen, Toueg. Using the heartbeat failure detector for quiescent reliable communication and consensus in partitionable networks. .ps Gupta, Chandra, Goldszmidt. On scalable and efficient distributed failure detectors. .pdf |
H4.2 Revised Schedule (.ps) |
Lecture9 (.tex) (.ps) |
| 10.08.02 |
Fault tolerant broadcasts: Vida Ha |
V. Hadzilacos and S. Toueg. A
modular approach to the specification and implementation of fault-tolerant
broadcasts. May 1994..ps
Kenneth Birman, et al. Bimodal multicast. May 1999. .pdf |
Lecture10 (.tex) (.ps) |
|
| 10.10.02 |
Consensus (part I): Nancy Lynch |
L. Lamport. The part-time parliament. ACM Transactions on Computer Systems, 1989. .psRoberto DePrisco, Nancy Lynch, Alex Shvartsman, Nicole Immorlica, and Toh Ne Win. A Formal Treatment of Lamport's Paxos Algorithm. In progress, 2002. .ps |
Lecture11 (.tex) (.ps) |
|
| 10.17.02 |
Consensus (part II): Nancy Lynch |
Marcos Kawazoe Aguilera and Sam Toueg. A simple bivalency proof t resilient consensus requires t+1 rounds. Information Processing Letters, 1999. .ps Achour Mostefaoui, Sergio Rajsbaum, Michel Raynal, and Matthieu Roy. A hierarchy of conditions for consensus solvability. 2001. .pdf |
Lecture12 (.tex) (.ps) |
|
| 10.22.02 |
Consensus (part III): Nancy Lynch |
Idit Keidar and Sergio Rajsbaum.
On the cost of fault-tolerant consensus when there are no faults
-a tutorial. 2001. .ps
and PODC
Tutorial Slides
Eli Gafni. A round-by-round failure detector - unifying synchrony and asynchrony. In Proceedings of the 17th Annual ACM Symposium on Principles of Distributed Computing, pages 143--152, Puerto Vallarta, Mexico, June 1998. .pdf |
Lecture13 |
|
| 10.24.02 |
Performing work in distributed systems: Alex Shvartsman |
G. G. Malewicz, A. Russell, and A.
A. Shvartsman. Distributed cooperation in the absence of communication.
In Proceedings of the 14th International Conference on Distributed
Computing, DISC, 2000. .ps
C. Georgiou, A. Russell, and A.A. Shvartsman. The complexity of synchronous iterative do-all with crashes. Distributed algorithms (DISC 2001). .ps |
Lecture14 (.tex) (.ps) |
|
| 10.29.02 |
Self-stabilization (part I): Boaz Patt-Shamir |
Edsger W. Dijkstra. Self-stabilizing
systems in spite of distributed control. Communication of the
ACM, 1974. .pdf George Varghese. Self-stabilization by counter flushing. SIAM Journal on Computing, .ps Adam M. Costello and George Varghese. Self-stabilization by window washing.PODC '96, .ps |
Lecture15 (.tex) (.ps) |
|
| 10.31.02 |
Self-stabilization (part II): Boaz Patt-Shamir Indraneel Charaborty |
Shmuel Katz, Kenneth J. Perry: Self-Stabilizing
Extensions for Message-Passing Systems. Distributed Computing 7(1):
17-26 (1993). Conference version, PODC, 1990 .pdf Baruch Awerbuch, Boaz Patt-Shamir, George Varghese, and Shlomi Dolev. Self-stabilization by local checking and network reset. Proceedings of the 8th International Workshop on Distributed Algorithms, WDAG'94, 1994. .ps Baruch Awerbuch, Boaz Patt-Shamir, and George Varghese. Self-stabilization by local checking and correction.Based on FOCS 91 paper and Ph.D. thesis. .ps |
Lecture16
|
|
| 11.5.02 |
Networks with
unknown participants End to end communication, routing: Boris Paskalev Building communication structures: Sayan Mitra, Seth Gilbert |
Y. Afek, B. Awerbuch, E. Gafni, Y. Mansour, A. Rosen, and N. Shavit.
Slide: The key to polynomial end-to-end communication. Journal
of Algorithms, 22:158--186, 1997. .pdf B. Awerbuch and D. Peleg. Sparse partitions. In In 31st
Annual IEEE Symposium on Foundations of Computer Science, pages
503--513, 1990.
.pdf B. Awerbuch and D. Peleg. Online tracking of mobile users. Journal of the ACM, 42(5):1021--1058, 1995. .pdf |
Lecture17 |
|
| 11.7.02 |
Group Communication (part I): Rui Fan |
Flaviu Cristian and Frank Schmuck.
Agreeing on processor group membership in asynchronous distributed
systems. Technical Report CSE95-428, University of California-San
Diego, La Jolla, CA 92093-0114, 1995. .ps
Gregory Chockler, Idit Keidar, and Roman Vitenberg. Group communication specifications: A comprehensive study. ACM Computing Surveys, 33(4):1--43, December 2001. .ps I. Keidar, J. Sussman, K. Marzullo, and D. Dolev. A client-server oriented algorithm for virtually synchronous group membership in WANs. In 20th International Conference on Distributed Computing Systems (ICDCS), pages 356--365, Taipei, Taiwan, April 2000. .ps Full version: MIT Technical Memorandum MIT-LCS-TM-593. .ps |
Lecture18 (.tex) (.ps) |
|
| 11.12.02 |
Group Communication (part II): Nancy Lynch |
Idit Keidar and Danny Dolev. Totally
ordered broadcast in the face of network partitions. In D. Avresky,
editor, Chapter 3 of Dependable Network Computing, pages
51-75, Kluwer Academic, 2000. .ps
Alan Fekete, Nancy Lynch, and Alex Shvartsman. Specifying and using a partitionable group communication service. ACM Transactions on Computer Systems, 19(2):171--216, May 2001. .ps |
Lecture19 (.tex) (.ps) |
|
| 11.14.02 |
Location services (part I): Ching Law, Andrew Lau |
Ion Stoica, Robert Morris, David Karger,
M. Frans Kaashoek, and Hari Balakrishnan. Chord: A scalable peer-to-peer
lookup service for internet applications. Proceedings of the
ACM SIGCOMM '01 Conference, San Diego, California, August 2001.
.ps Kirsten Hildrum, John Kubiatowicz, Satish Rao, and Ben Y. Zhao. Distributed object location in a dynamic network. In Proceedings of the Fourteenth ACM Symposium on Parallel Algorithms and Architectures (SPAA 2002), Winnipeg, Manitoba, Canada, August 2002. .ps Silvia Ratnasamy, Paul Francis, Mark Handley, Richard Karp, and Scott Shenker. A scalable content-addressable network. In Proceedings of the ACM SIGCOMM' 01 Conference, San Diego, CA, pages 161-172, August 2001. .pdf |
Lecture20 (text) |
|
| 11.19.02 |
Location services (part II): Ching Law, Andrew Lau |
Frank Dabek, M. Frans Kaashoek, David Karger, Robert Morris,
and Ion Stoica. Wide-area cooperative storage with CFS In Proceedings
of the 18th ACM Symposium on Operating Systems Principles (SOSP '01),
Chateau Lake Louise, Banff, Canada. October 2001. .ps
A. Rowstron and P. Druschel. Storage Management and Caching in PAST, A Large-scale, Persistent Peer-to-peer Storage Utility, ACM SOSP, October 2001. .ps N. Lynch, D. Malkhi, and D. Ratajczak. Atomic Data Access in Content Addressable Networks: A Position Paper. First International Workshop on Peer-to-Peer Computing (IPTPS 2002), Cambridge, MA, March 2002. .pdf |
Lecture21 (text) |
|
| 11.21.02 |
Reconfigurable atomic memory: Nancy Lynch |
Nancy Lynch and Alex Shvartsman. RAMBO: A Reconfigurable Atomic Memory Service for Dynamic Networks. Technical Report MIT Laboratory for Computer Science, MIT-LCS-TR-856, 2002. .ps Nancy Lynch and Alex Shvartsman. RAMBO: A Reconfigurable Atomic Memory Service for Dynamic Networks. In Distributed Computing (DISC) October 2002, Toulouse, France, volume 2508 of Lecture Notes in Computer Science, pages 173-190, 2002. Springer-Verlag. .pdfH. Attiya and J. L. Welch. Sequential consistency versus linearizability. ACM Transactions on Computer Systems, 12(1):91--122, May 1994. An earlier version appeared in Proc. 3rd ACM Symposium on Parallel Algorithms and Architectures, pages 304-315, Hilton Head, South Carolina, July 1991. .ps |
Lecture22 (.ps) (.ppt) |
|
| 11.26.02 |
Mobile computing
Topology control: Vahab Mirrokni and Mohammad Hajiaghayi |
L. Li, J. Halpern, V.
Bahl, Y. M. Wang, and R. Wattenhofer. Analysis of a cone-based distributed
topology control algorithm for wireless multi-hop networks. In Twentieth
ACM Symposium on Principles of Distributed Computing (PODC 2001),
Newport, RI, August 2001. .pdf
M. T. Hajiaghayi, M. Bahramgiri, and V. S. Mirrokni. Fault-tolerant and 3-Dimensional distributed topology control algorithms in wireless multi-hop networks. Proceedings of the 11th IEEE International Conference on Computer Communications and Networks (IC3N), pages 392-398, October 14-16, 2002, Miami, Floria. .ps |
Lecture23 slides (.ps) |
|
| 12.03.02 |
Routing and end-to-end communication: Indraneel Charaborty and Boris Paskalev |
David B. Johnson and David A. Maltz. Dynamic
source routing in ad hoc wireless networks. In chapter 5 of Tomasz Imielinski
and Hank Korth, editors, Mobile Computing, Kluwer Academic Publishers,
1996. .ps E.M. Gafni and D.P. Bertsekas. Distributed algorithms for generating loop-free routes in networks with frequently changing topology. IEEE Transactions on Communications, 29(1):11--18, January 1981. Charles E. Perkins and Elizabeth M. Royer. Ad hoc on-demand distance vector routing. In Proceedings of the 2nd IEEE Workshop on Mobile Computing Systems and Applications, New Orleans, LA, pages 90-100, February 1999. .ps Young-Bae Ko and Nitin H. Vaidya. Location-aided routing (LAR) in mobile ad hoc networks. ACM/Baltzer Wireless Networks (WINET), Vol.6-4, 2000. .pdf Young-Bae Ko and Nitin H. Vaidya. Geocasting in mobile ad-hoc netowrks: location-based multicast algorithms. In Proceedings of the 2nd IEEE Workshop on Mobile Computer Systems and Applications, (WMCSA), New Orleans, LA, February 1999. .pdf |
Lecture24 |
|
| 12.05.02 |
Leader election, mutual exclusion and other
problems: Nancy Lynch |
N. Malpani, Vaidya N., and J. L. Welch.
Distributed token circulation in mobile ad hoc networks. In Proceedings
of the 9th International Conference on Network Protocols (ICNP),
Riverside, CA, November 2001. .pdf Jennifer Walter, Jennifer L. Welch, and Nitin Vaidya. A mutual exclusion algorithm for ad hoc mobile networks. Wireless Networks, 9(6):585-600, 2001. .pdf |
Lecture25 (.tex) (.ps) |
|
| 12.06.02 |
Coordinated robots: Sayan Mitra |
Ichiro Suzuki, Masafumi Yamashita. Distributed
Anonymous Mobile Robots: Formation of Geometric Patterns. SIAM Journal
on Computing, Volume 28, Number 4 pp. 1347-1363 1999 Society
for Industrial and Applied Mathematics .ps
J. Walter, J. Welch, and N. Amato. Distributed reconfiguration of metamorphic robot chains. In Proceedings of the Nineteenth Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC 2000), Portland, Oregon, pages 171-180, 2000. .ps |
H5
Schedule (Final version) |
Lecture26 (.tex) (.ps) |