Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
Algorithms and Complexity Group Wednesday, November 21, 2012: Efficient Fetch-and-Increment
0 views
Skip to first unread message
wlr...@uwaterloo.ca
Nov 14, 2012, 3:30:09 PM11/14/12
to
A new Algorithms and Complexity Group event has been scheduled:
Efficient Fetch-and-Increment
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.
Date: Wednesday, November 21, 2012
Time: 13:30
Please look on WebCalendar to view this appointment.
http://www.cs.uwaterloo.ca/odyssey/event/1625
Efficient Fetch-and-Increment
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.
Date: Wednesday, November 21, 2012
Time: 13:30
Please look on WebCalendar to view this appointment.
http://www.cs.uwaterloo.ca/odyssey/event/1625
0 new messages