Abstract: The talk will focus on two solutions to the problem of storing a dynamic ordered dictionary over a distributed set of nodes. Both of these data structures can support efficient search operations as well as range queries. The talk will include definitions of the two data structures, an outline of their fundamental routines, and a discussion of their theoretical performance.
The content of the talk is taken from the following two papers:
"Skip Graphs" by James Aspnes and Gauri Shah, appeared in SODA 2003
"Family Trees" by Kevin C. Zatloukal and Nicholas J. A. Harvey, appeared
in SODA 2004