6.891 Multiprocess Synchronization

Handouts | Mail | Scribe Help | Class Member | Reference

This course deals with theoretical and practical algorithmic aspects of synchronization and coordination. We will analyze the design and behavior of state of the art concurrent data structures and algorithms in the context of real multiprocessor architectures.

This is a graduate level course open to undergraduates with instructor approval.

Topics covered in the course include:

This course is offered by Professor Nir Shavit for Fall 1995. Class meets every Wednesday 10AM-1PM in Room 36-372.

Last update on December 12, 1995 by Yang-hua Chu.
This page has been accessed times since created.

Lecture Notes

Lecture 1, 9/13/95: Introduction, Administrative remarks.

 Lecture 2, 9/20/95: Mutual exclusion problem, Fairness, and Bakery algorithm.

Lecture 3, 9/27/95: FIFO queue data struction, Linearizability.

Lecture 4, 10/11/95: More on linearizability, Granularity, Wait free synchronization

Lecture 5, 10/18/95: Registers types and constructions, Atmoic snapshot of shared memory, Unbounded snapshot algorithm, Single-scanner algorithm.

Lecture 6, 10/21/95: Concurrent Time Stamp System

Lecture 7, 10/25/95: Unbounded and bounded concurrent time stamp system.

Lecture 8, 11/1/95: Consensus number, Queue and compare & swap primitive, Universality results.

Lecture 9, 11/8/95: Spin lock, Queue lock, Tree lock.

Lecture 10, 11/15/95: Combining tree, Balancing network, Counting network.

Lecture 11, 11/22/95: Diffracting tree, Message passing.

Lecture 12, 11/29/95: Pools, Elimination Trees, Barriers

Scribe Help

LaTeX Quick Help: Click on this link to get some quick tips about writing a latex document.

LaTeX Document: Click on this link to get some documentation on how to get started with LaTeX to write class notes.

Send E-mail:

Please be remineded to fill out your e-mail address below. The person cannot reply you unless you provides this information.

For comments about this web page, please send e-mail to Yang-hua Chu.

Your E-mail address:

Mail to:

Subject:

Information About the Class Members for Fall 1995:

Name E-mail Phone (617) Address Year Duty...
Prof. Nir Shavit shanir@theory.lcs.mit.edu 253-5905 NE43-367 DWTK teach
Michael Bender bender@das.harvard.edu 493-4879 Aiken Computation Lab, Harvard G scribe 11/8
Yang-hua Chu yhchu@mit.edu 225-7623 New House 5, RM 311 4 web page
Sandeep Gupta skgupta@amsterdam.lcs.mit.edu 253-7436 NE43-520 G scribe 11/1
Patricia Liu pjliu@mit.edu 876-1521 518 Putman Ave Apt 6 G ps solutions
Daniel Risacher magnus@mit.edu 577-5739, 253-2612 60 Wadsworth St Apt 21h RM, NE43-409 G scribe 12/13
Sheryl Risacher saeor@im.lcs.mit.edu 577-5739, 253-3517 60 Wadsworth St # 21m G scribe 11/15
Eva Tsai eytsai@mit.edu 225-6173 East Campus, Bem RM 113 4 scribe 11/22
Ely Wilson terkaar@mit.edu 225-9539 Random Hall RM 434 4 scribe 12/6
Emmett Witchel witchel@amsterdam.lcs.mit.edu 536-7615, 253-7328 20 Commonwealth Ave Basement G scribe 11/29

Links and Reference

SYNClib : Scalable Distributed Synchronization Project in Germany.