Distributed Computing Seminar,  Semester א, תשס"ז  Winter 2005/2006

Professor Yehuda Afek

Sunday, 13:00 – 15:00 @  Kaploon 324

Date

title

presenter

material

October 22

 

 

 

October 29

 

 

 

Nov 5

 

 

 

Nov 12

 

 

 

Nov 19

 

 

 

Nov 26

 

 

 

Dec 3

 

 

 

Dec 10

 

 

 

Dec 17

 

 

 

Dec 24

 

 

 

Dec 31

 

 

 

Jan 7

 

 

 

Jan 14

 

 

 

Jan 21

 

 

 

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

Some Suggested Papers:

Title

Comments

Assigned

o                                Exploring Gafni's reduction land: from Ωk to wait-free adaptive (2p - [ p/k]) renaming via k-set agreement,
Achour Mostefaoui, Michel Raynal, Corentin Travers DISC 2005

Disc 2006

 

o                                Renaming in Message Passing Systems with Byzantine Failures,
Michael Okun, Amnon Barak

Disc 2006

 
    • Built-in Coloring for Highly-Concurrent Doubly-Linked Lists,
      Hagit Attiya, Eshcar Hillel

Disc 2006

 
    • A New Proof of the GHS Minimum-spanning Tree Algorithm,
      Yoram Moses, Benny Shimony

Disc 2006

 
    • Conflict Detection and Validation Strategies for Software Transactional Memory,
      Michael F. Spear, Virendra J. Marathe, William N. Scherer III, Michael L. Scott

Disc 2006

 
    • Subconsensus Tasks: Renaming is Weaker than Set Agreement,
      Eli Gafni, Sergio Rajsbaum, Maurice Herlihy

Disc 2006

 
  • Sketching Asynchronous Streams Over Sliding Windows              Srikanta Tirthapura, Bojian Xu, Costas Busch

Podc 2006 (Networking?)

 

BELOW ARE OLD SUGGESTIONS (SOME OF WHICH WE HAVE HEARD) FROM PREVIOUS SEMESTERS
  1.  
    1. 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.

Danny Hendler