אירועים והרצאות בפקולטה למדעי המחשב ע"ש הנרי ומרילין טאוב

A history-independent data structure does not reveal the history of operations applied to it, only its current logical state, even if its internal state is examined. While history independence has been extensively studied in sequential data structures, until very recently, it was not studied in a concurrent setting, where the data structure can be accessed by many threads at the same time.

In this talk I will discuss history-independent concurrent dictionaries, in particular, hash tables, and establish inherent bounds on their space requirements. We show that there is a lock-free history-independent concurrent hash table, in which each memory cell stores two elements and two bits, based on Robin Hood hashing. The expected amortized step complexity of the hash table is O(c), where c is an upper bound on the number of concurrent operations that access the same element, assuming the hash table is not overpopulated.