|
|
|
Distributed Computing Seminar, Semester Alef, Fall 2004
Professor Yehuda Afek
Sundays, ??? @ Schreiber ???
This seminar is intended for graduate students interested to pursue
research in Asynchronous Distributed Computing. (Following on the distributed computing
class I taught last year (Spring 2004)).
Every week we will review a specific topic, usually covered by one
recent paper from a conference or a journal (see below). The student leading the discussion in a
given week should read the paper(s) carefully and prepare a presentation
discussion on the paper to be held in the meeting.
Participants are required to:
- present a research
paper(s), and lead a discussion on the topic;
- Write a 1-2 page
report which critically evaluates the papers (flaws in the model, not
exciting when compared to related work, mistakes, etc.), give a vague or
specific idea how to improve the paper, and propose what else can be
done with this topic;
- attend the talks of
the seminar and actively participate in the discussions.
Your presentation should cover the motivation for the problem as well as
some technical parts of the paper in detail. Assume that the other
participants know nothing about the subject. You are encouraged to deviate from the
logical structure of the paper and present it in the most lucid (clear)
presentation of the topic.
Schedule of Presentations
|
|
|
|
date
|
title
|
presenter
|
material
|
|
|
2004/10/17
|
Introduction
|
Yehuda Afek
|
|
|
|
2004/10/24
|
|
|
|
|
|
2004/10/31
|
|
|
|
|
|
2004/11/7
|
|
|
|
|
|
|
2004/11/14
|
|
|
|
|
|
|
2004/11/21
|
|
|
|
|
|
|
2004/11/28
|
|
|
|
|
|
|
2004/12/5
|
|
|
|
|
|
|
2004/12/12
|
|
|
|
|
|
|
2004/12/19
|
|
|
|
|
|
|
2004/12/26
|
|
|
|
|
|
|
2005/1/2
|
|
|
|
|
|
|
2005/1/9
|
|
|
|
|
|
|
2005/1/16
|
|
|
|
|
|
|
|
|
|
|
|
Suggested Papers
|
|
|
Title
|
Comments
|
Assigned
|
- High
performance dynamic lock-free hash tables and list-based sets
Maged Michael, SPAA 2002, pg 73-82
|
Using CAS to implement efficiently hash
function, for OS operations.
|
|
- The Concurrency
Hierarchy, and Algorithms for Unbounded Concurrency, Gafni,
Merritt, Taubenfeld PODC 01
|
Wait-Free even if there
is no bound on the number of processes that may arrive
|
|
- Implementing
Shared Memory Overwriting Objects Hanan Weisman, Master Thesis,
Tel-Aviv 1996 Relating
Sequential Consistency, Linearizability and First-Come-First-Served
Gafni and Lamport Manuscript 2002
|
Imlementing swap from other consensus-2
objects.
|
|
- An Almost
Non-blocking Stack Hans-J. Boehm, PODC-2004
|
Non-blocking until n
approach
|
|
- Bringing Practical
Lock-Free Synchronization to 64-bit Applications Simon Doherty, Maurice Herlihy,
Victor Luchangco and Mark Moir Practical
Lock-free and Wait-Free LL/SC/VL Implementations using 64bit CAS
Maged Michael, IBM DISC 2004
|
Implementing in single 64 bit word what was implemented in a split 64
(into two 32).
|
|
- A
round-by-round failure detector - unifying synchrony and asynchrony, Eli Gafni PODC-98 pg 143-152
|
Model a
system by its round-by-round failure detector, and then relating the diff
models
|
|
- A Simple Algorithmically
Reasoned Characterization of Wait-free Computations Elizabeth
Borowsky and Eli Gafni, PODC-97
|
Iterated simulation with immediate snapshots. New model and reduction technique.
|
|
- Split-Ordered
Lists - Lock-Free Extensible Hash Tables <http://www.cs.tau.ac.il/%7Eorish/shalev-shavit.ps.gz>/
Shalev and Shavit PODC 2003.
|
|
|
- Concurrent
Data Structure, book
chapter, Moir and Shavit,
|
|
|
- Obstruction-free
Synchronization: Double-ended Queues as an Example Herlihy, V. Luchangco, and M. Moir ICDCS03
|
|
|
- The
Repeat Offender Problem: A Mechanism for Supporting Dynamic-Sized,
Lock-Free Data Structures Herlihy, V. Luchangco, and M. Moir, DISC02
|
|
|
- On the
Inherent Weakness of Conditional Synchronization Primitives Faith
Fich, Danny Handler, Nir Shavit Operation
Valency and the Cost of Coordination Danny Handler and Nir Shavit
|
Sqrt(n) lowerbounds when large valence.
|
|
|