Distributed Computing Seminar,  Semester ב, תשס"ו  Winter 2005/2006

Professor Yehuda Afek

Sunday, 15:00 – 17:00 @  Kaploon 319

Date

title

presenter

material

30/4/2006

 

Ori Shalev

 

7/5/2006

Fully-Adaptive Long-Lived Renaming

Faith Ellen Fich, Univ. of Toronto (on sabbatical at the Technion)

Renaming allows processes to get distinct names from a small name space and release names they no longer need.

Adaptive renaming performs both these operations in time bounded above by a function of the number of processes, k, currently occupying, getting or releasing names.

In fully-adaptive renaming, the time is bounded above by a function of the number of processes, c, currently performing getting or releasing a name, but does not depend on the number of processes currently occupying names.

 

Two fault-tolerant implementations of fully-adaptive renaming are presented in which the name a process gets is bounded above by k. One algorithm is asynchronous, uses shared registers and LL/SC objects and has O(c) step complexity. The other algorithm is synchronous, uses registers and counters and has step complexity that is polylogarithmic in c.

26/3/2006

Queues and the FCFS property

Adam Morrison

 

 

19/3/2006

Topological proof that Renaming and set-consensus are different, OR something else

Eli Gafni

 

12/3/2006

Gafni Lamport “First Come First Served” paper

Adam Morrison

Relating Sequential Consistency, Linearizability and First-Come-First-Served Gafni and Lamport Manuscript 2002

5/3/2006
Introduction and administration

 

 
 

 

 

 

 

 

14/5/2006

Ori Shalev

 

 

21/5/2006

Eran Shalom

 

 

28/5/2006

Oren Poleg

 

 

4/6/2006

Hillel Avni

 

 

11/6/2006

 

 

 

 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, List of suggested papers below it:

Suggested Papers:

Title

Comments

Assigned
  1.  
    1. Obstruction-Free Algorithms can be Practically Wait-Free Faith Fich, Victor Luchangco, Mark Moir, and Nir Shavit Lecture Notes in Computer Science 3724, Springer Verlag, Pierre Fraignaud (Ed.), 19th International Symposium on Distributed Computing (DISC) 2005
    2. Computing with Reads and Writes in the Absence of Step Contention Hagit Attiya, Rachid Guerraoui, and Petr Kouznetsov

DISC05

 
  1.  
    1. Musical Benches Eli Gafni and Sergio Rasbaum Lecture Notes in Computer Science 3724, Springer Verlag, Pierre Fraignaud (Ed.), pp. 63-77: 19th International Symposium on Distributed Computing (DISC) 2005.
    2. The Committee Decision Problem and here

DISC05

 

3.       (Almost) All Objects are Universal in Message Passing Systems Carole Delporte, Hugues Fauconnier, and Rachid Guerraoui

DISC05

 

4.       Omega Meets Paxos: Leader Election and Stability without Eventual Timely Links Dahlia Malkhi, Florin Oprea, and Lidong Zhou

DISC05

 

5.       What can be implemented anonymously? Rachid Guerraoui, and Eric Ruppert

DISC05

 

6.       Adaptive Software Transactional Memory Virendra Marathe, William Scherer, and Michael Scott

DISC05

 

7.        

a.       General Compact Labeling Schemes for Dynamic Trees Amos Korman

b.      Proof Labeling Schemes  Amos Korman, Shay Kutten and David Peleg  PODC 05

DISC05

 

 

PODC 05

 

8.       The Dynamic And-Or Quorum System Uri Nadav, and Moni Naor

DISC05

 

9.       Non-Blocking Hash-tables with Open Addressing Chris Purcell, and Tim Harris

DISC05

 

OLD PAPERS BELOW (Last year seminar):

OLD PAPERS BELOW:

OLD PAPERS BELOW:

Byzantine Disk Paxos: Optimal Resilience with Byzantine Shared Memory.

New

 

Paxos Made Simple  Leslie Lamport

Together with above

 
  1. 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.

Adam
  1. The Concurrency Hierarchy, and Algorithms for Unbounded Concurrency, Gafni, Merritt, Taubenfeld PODC 01

Wait-free even if there is no bound to the number of processes that may arrive

Noa
  1. 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.

Adam (have not been presented)
  1. An Almost Non-blocking Stack Hans-J. Boehm, PODC-2004

Non-blocking until n approach

Dotan
  1. 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).

 
  1. 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

 
  1. 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.

 
  1. Split-Ordered Lists - Lock-Free Extensible Hash Tables <http://www.cs.tau.ac.il/%7Eorish/shalev-shavit.ps.gz>/ Shalev and Shavit PODC 2003.

 

Ori
  1. Concurrent Data Structure,  book chapter, Moir and Shavit,

 

 
  1. Obstruction-free Synchronization: Double-ended Queues as an Example Herlihy, V. Luchangco, and M. Moir ICDCS03

 

Eran
  1. The Repeat Offender Problem: A Mechanism for Supporting Dynamic-Sized, Lock-Free Data Structures Herlihy, V. Luchangco, and M. Moir, DISC02

 

Dotan (have not been presented)
  1. 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.

Danny Hendler

 

  1. Efficient Synchronous Snapshots Alex Brodsky and Faith Fich

Synchronous SnapShot in O(1)-update and O(m)-scan and variants

 
  1. Lower bounds for adaptive collect and related objects Hagit Attiya, Faith Fich, Yaniv Kaplan

F(k)-adaptive total contention implies       f^{-1}(n) multi writer registers.  + variants.

 

Lower bounds for distributed multi-valued objects

-------------------------------------------------

 

Unlike the well-studied distributed consensus problem, where processes need to agree on a single common value, operations applied to distributed mutli-valued objects, such as counters, stacks and queues, may return different values to different processes.

 

In this talk, I will present recent lower bounds and tradeoffs on the time and space requirements of implementations of distributed multi-valued objects. This is a general audience talk and prior knowledge of distributed systems will not be assumed.

 

Joint work with Faith Ellen Fich and Nir Shavit.

  1.  

Danny Hendler

 

 

 

  1.  

 

 
  1.