|COOKIES: By using this website you agree that we can place Google Analytics Cookies on your device for performance monitoring.|
Towards Practical Randomization in Concurrent Data Structures
If you have a question about this talk, please contact Microsoft Research Cambridge Talks Admins.
This event may be recorded and made available internally or externally via http://research.microsoft.com. Microsoft will own the copyright of any recordings made. If you do not wish to have your image/voice recorded please consider this before attending
Given the widespread adoption of multi-core processor architectures, one of the biggest challenges in distributed computing is designing 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 names from a namespace of limited size.
Our 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 sorting networks, renaming, and the mutual exclusion problem. Importantly, this result can be extended to yield new linear lower bounds on deterministic implementations of practical objects such as stacks, queues, and fetch-and-increment counters, showing that implementing these data structures deterministically is also inherently expensive. On 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 logarithmic time, with high probability, ensuring a namespace of optimal size. Our algorithm is asymptotically time-optimal, and can be extended to obtain counters and fetch-and-increment registers in polylogarithmic time.
Together, these results suggest that, while obtaining fast deterministic implementations of these data structures may be impossible, randomization can be a very powerful tool when designing concurrent data structures, whose potential is yet to be exploited in full.
This talk is part of the Microsoft Research Cambridge, public talks series.
This talk is included in these lists:
Note that ex-directory lists are not shown.
Other listsTheory Workshop Research Office Linked Events Institution of Civil Engineers (Cambridge Branch)
Other talksObserving Quasars that Switch Off. And back On again: What we are learning, and still don't understand, about the active central engines. Molecular characterization of the Flagellar Pocket Collar cytoskeletal of the protozoan parasite Trypanosoma brucei Cambridge - Corporate Finance Theory Symposium September 2017 - Day 2 DataSHIELD: taking the analysis to the data not the data to the analysis tba Workshop: 'The development and facilitation of an emotion and memory group programme for the treatment of complex PTSD'