Skip to content (access key 's')
Logo of Technion
Logo of CS Department

The Taub Faculty of Computer Science Events and Talks

Theory Seminar: Random Binary Search Trees with Concurrent Insertions
event speaker icon
George Giakkoupis (IRISA/INRIA Rennes)
event date icon
Wednesday, 31.10.2018, 12:30
event location icon
Taub 201
We consider the following simple random experiment to determine the impact of concurrency on the performance of binary search trees: n randomly permuted keys arrive one at a time. When a new key arrives, it is first placed into a buffer of size c. Whenever the buffer is full, or when all keys have arrived, an adversary chooses one key from the buffer and inserts it into the binary search tree. The ability of the adversary to choose the next key to insert among c buffered keys, models a distributed system, where up to c processes try to insert keys concurrently. We show that the expected average depth of nodes in the resulting tree is 2ln n + O(c), for any adversarial strategy of choosing the next buffered key to be inserted into the tree. This result is tight, and answers an open question by Aspnes and Ruppert (DISC 2016).