Abstract: The talk will focus on two solutions to the problem of storing a dynamic ordered dictionary over a distributed set of machines. Both of these data structures can support efficient search operations as well as range queries. This second part of the talk focuses on family trees and 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