Abstract: I will give a survey of our recent results on distributed queues, stacks, and heaps that are based on overlay networks and that are highly scalable in a sense that they can process requests massively in parallel while keeping the sequential semantics of the data structures. That is, the way the system executes the requests either satisfies sequential consistency or at least linearizability. Furthermore, any set of requests can be served in just O(log n) time (given that the available bandwidth at the processes is ~O(max. number of requests per process)), and the data in the data structures is distributed in a fair way among the processes. This is achieved via a combination of techniques including, e.g., distributed hashing, distributed aggregation, and distributed k-selection.
