| Classic theoretical models and pies for data structures, such as the cell-probe model, the unit, cost word-RAM model, or hashing, assume an ideal architecture in which the data structure is stored in a reliable memory which is randomly accessed by a single processor.;However, in many realistic applications, a data structure is implemented by a system whose architecture is not well captured by this ideal model, e.g., by a cluster of servers, in a computer with multiple processing cores, or over the Internet.;This thesis bridges this gap between the theory and the practice of data structures. We consider three new issues for data structures, namely, locality, contention, and churn, and study the effects of these new issues on the power of data structures. We make several contributions to the theory of data structures. (1) In order to address the notion of verification in data structures, we study nondeterministic computation in data structures. We introduce a new tool, called cell-probe proofs, with which we prove several nondeterministic lower bounds for data structure problems. (2) We introduce the concept of locally checkable data structures, which captures the notion of local verification in data structures. We show that for several well-motivated data structure problems the answers to queries cannot be verified locally. (3) We introduce a measure of memory contention to the cell-probe model, the classic model for data structures. We establish the first lower bound for the tradeoff between the time cost and the memory contention of data structures. We also introduce a general technique to transform any data structure to a low-contention data structure. (4) We study the impact of churn on the load balance performance of hash functions. We study ranged hash functions, a generalized model for consistent hashing introduced by Karger et al. Several upper and lower bounds for ranged hash functions are introduced. |
