2012 Nov 21 at 13:30
DC 1304
Faith Ellen, University of Toronto
A Fetch-and-Increment object stores a non-negative integer and supports a single operation, FI, that returns the value of the object and increments it. Such objects are used in asynchronous shared memory algorithms for many distributed computing problems, such as renaming, mutual exclusion, and barrier synchronization. This talk will present an efficient implementation of a wait-free Fetch-and-Increment object from read-write registers and load-linked/store conditional (LL/SC) objects, based on a new data structure. In a system with p processes, every FI operation finishes in O(log^2 p) steps, and only a polynomial number of registers (large enough to hold a value) and O(log p)-bit LL/SC objects are needed.
This work is joint with Philipp Woelfel and Vijaya Ramachandran and appeared at DISC 2012.