BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Towards Practical Randomization in Concurrent Data Structures - Da
 n Alistarh\, EPFL
DTSTART:20120315T090000Z
DTEND:20120315T100000Z
UID:TALK36934@talks.cam.ac.uk
CONTACT:Microsoft Research Cambridge Talks Admins
DESCRIPTION:Given the widespread adoption of multi-core processor architec
 tures\, one of the biggest challenges in distributed computing is designin
 g fast\, highly concurrent implementations of common data structures such 
 as counters\, stacks\, pools\, or queues. In this talk\, we examine these 
 data structures through the lens of a classical distributed problem called
  renaming\, in which a set of concurrent processes need to pick unique nam
 es from a namespace of limited size. \n\nOur first result is that renaming
  deterministically is expensive\, as it requires linear shared-access time
  in the worst case. The lower bound exploits a new connection between sort
 ing networks\, renaming\, and the mutual exclusion problem. Importantly\, 
 this result can be extended to yield new linear lower bounds on determinis
 tic implementations of practical objects such as stacks\, queues\, and fet
 ch-and-increment counters\, showing that implementing these data structure
 s deterministically is also inherently expensive. \nOn the other hand\, we
  prove that this worst-case cost can be circumvented using randomization. 
 We present a new randomized renaming algorithm that assigns names in logar
 ithmic time\, with high probability\, ensuring a namespace of optimal size
 . Our algorithm is asymptotically time-optimal\, and can be extended to ob
 tain counters and fetch-and-increment registers in polylogarithmic time.\n
 \nTogether\, these results suggest that\, while obtaining fast determinist
 ic implementations of these data structures may be impossible\, randomizat
 ion can be a very powerful tool when designing concurrent data structures\
 , whose potential is yet to be exploited in full.
LOCATION:Small lecture theatre\, Microsoft Research Ltd\, 7 J J Thomson Av
 enue (Off Madingley Road)\, Cambridge
END:VEVENT
END:VCALENDAR