Michael A Bender
email: bender@cs.stonybrook.edu.

Jonathan W Berry
email: jberry@sandia.gov.

Rob Johnson

Thomas M Kroeger

Samuel Mccauley
email: smccauley@cs.stonybrook.edu.

Cynthia A Phillips

Bertrand Simon
email: bertrand.simon@ens-lyon.fr.

Shikha Singh
email: shiksingh@cs.stonybrook.edu.

David Zage
email: zage@cerias.net.

Anti-Persistence on Persistent Storage: History

Keywords:

come

INTRODUCTION

A data structure is history independent (HI) if its internal representation reveals nothing about the sequence of operations that led to its current state [START_REF] Micciancio | Oblivious data structures: applications to cryptography[END_REF][START_REF] Naor | Anti-persistence: history independent data structures[END_REF]. In this paper, we study history independence for persistent, disk-resident dictionary data structures.

We give two efficient history-independent alternatives to the B-tree, the primary indexing data structure used in databases. Specifically, we give an HI external-memory skip list and an HI cache-oblivious1 B-tree.

One of the main contributions of the paper is a data structure we build on the way: a history-independent packedmemory array (PMA). As we explain, the PMA [START_REF] Bender | Cache-oblivious B-trees[END_REF][START_REF] Bender | An adaptive packed-memory array[END_REF] is an unlikely candidate data structure to be made history independent, since traditional PMAs rely on history so fundamentally. The HI PMA is one of the primary building blocks in the HI cache-oblivious B-tree. However, it can also be bolted onto any dictionary data structure, using the PMA to hold the actual elements and deliver fast range queries.

Notions of History Independence

Informally, history independence partially protects a diskresident data structure when the disk is stolen by-or given to-a third party (the "observer"). This observer can access the data structure through the normal API but can also see its bit and pointer representation on disk. An HI data structure's bit representation never leaks any information to the observer that he could not learn through the API.

There are two notions of history independence, weak history independence (WHI) and strong history independence (SHI) [START_REF] Naor | Anti-persistence: history independent data structures[END_REF]. The notions are distinguished by how many times the observer can look at the data structure-that is by how many times an interloper can steal (or otherwise gain access to) the disk on which the data structure resides. A weakly history-independent data structure is history independent against an observer who can see the memory representation once. A strongly history-independent data structure is history independent against an observer who can see the memory representation multiple times.

In this paper, we focus on weak history independence. From a performance perspective, weak HI is a stronger notion because it allows provably stronger performance guarantees (see Section 2). Protecting against multiple observations reduces achievable performance.

Weak history independence is the appropriate notion of history independence in situations where only one observation is possible. For example, when the data is on a device that can be separated from the owner (say a portable or embedded device), the owner no longer interacts with the device. WHI provides the same level of protection in this case with significantly better performance compared to SHI.

History Independence and Data

History independence in a database can have major advantages, depending on the kind of data that is being stored and the security requirements.

HI data structures naturally support informationtheoretically-secure delete. In contrast, with more standard secure delete (where the file system overwrites deleted data with zeros), information about deleted data can leak from the memory representation. For example, it reveals how much data was deleted and where in the keyspace it might have been. In fact, a long history of failed redactions is one of the original motivations for history independence [START_REF] Hartline | Characterizing history independent data structures[END_REF]. History independence guarantees that the memory representation will leak no information about these previous (now secure) deletes. Encryption is not a panacea to protect history unconditionally, since determined attackers can recover the key used to encrypt on-disk data [START_REF] Halderman | Lest we remember: Cold-boot attacks on encryption keys[END_REF].

In a database, the source of the data can be more sensitive than the data itself. As a toy example, consider a database of known organized crime members maintained by the police. The police might want to share such a database with select individuals without revealing the order and times in which the data was added to the database. Revealing this order might leak information about how and when the data was collected, which could reveal sources that the police want to stay hidden. Journalists may desire the same property to ensure their sources' anonymity.

In such cases, we need to be particularly careful about avoiding information leaks by side channels. Since leakage can be subtle and hard to quantify, it is beneficial to have a guarantee that nothing extraneous is revealed, which is exactly what history independence guarantees. HI data structures naturally hide the order in which data was inserted.

History Independence in Persistent Storage

This paper focuses on history independence for externalmemory dictionaries. This area of history independence was initiated by Golovin [START_REF] Golovin | B-treaps: A uniquely represented alternative to B-trees[END_REF][START_REF] Golovin | The B-skip-list: A simpler uniquely represented alternative to B-trees[END_REF]; see Section 1.4 for details.

The ubiquitous (non-history-independent) externalmemory dictionary is the B-tree.

Our objective is to build history-independent, I/O efficient external-memory dictionaries.We support standard dictionary operations: insertions, deletions, searches, and range queries. Our two external-storage computational models (the external-memory model [START_REF] Aggarwal | The input/output complexity of sorting and related problems[END_REF] and the cache-oblivious model [START_REF] Frigo | Cache-oblivious algorithms[END_REF][START_REF] Frigo | Cache-oblivious algorithms[END_REF][START_REF] Prokop | Cache oblivious algorithms[END_REF]) apply to both rotating disks and SSDs.

We give weakly history-independent data structures for persistent storage; these are easy to implement and retain strong performance guarantees. We show that even rangequery data structures that seem to be inherently history dependent-in particular, packed-memory array or sparse tables [14, 16-18, 38, 41, 66]-can be made weakly history independent. Overall, our results demonstrate that it is possible to build efficient external-memory (and even cacheoblivious) history-independent data structures for indexing.

History Independence in Persistent Storage vs. RAM History independence has been vigorously explored in the context of data structures that reside in RAM [START_REF] Blelloch | Strongly history-independent hashing with applications[END_REF][START_REF] Blelloch | Uniquely represented data structures for computational geometry[END_REF][START_REF] Buchbinder | Lower and upper bounds on obtaining history independence[END_REF][START_REF] Hartline | Characterizing history independent data structures[END_REF][START_REF] Micciancio | Oblivious data structures: applications to cryptography[END_REF][START_REF] Naor | History-independent cuckoo hashing[END_REF][START_REF] Naor | Anti-persistence: history independent data structures[END_REF][START_REF] Tzouramanis | History-independence: a fresh look at the case of R-trees[END_REF] (see Section 1.4), but significantly less so in external memory. Although there is some theoretical work on history-independent on-disk data structures [START_REF] Golovin | Uniquely Represented Data Structures with Applications to Privacy[END_REF][START_REF] Golovin | B-treaps: A uniquely represented alternative to B-trees[END_REF][START_REF] Golovin | The B-skip-list: A simpler uniquely represented alternative to B-trees[END_REF] and experimental work on history-independent file systems [START_REF] Bajaj | The foundations of history independence[END_REF][START_REF] Bajaj | Ficklebase: Looking into the future to erase the past[END_REF][START_REF] Bajaj | HIFS: History independence for file systems[END_REF][START_REF] Roche | Oblivious secure deletion with bounded history independence[END_REF], the area is substantially less explored.

This lacuna may seem surprising, since many of the classical arguments in support of history independence especially apply to disks. Hard drives are more vulnerable than RAM because they are persistent and easier to steal, making it easier for an attacker to observe on-disk data.

I/O and Cache-Oblivious Models

We prove our results using the classic models for analyzing on-disk algorithms and data structures: the disk-access machine (DAM) model of Aggarwal and Vitter [START_REF] Aggarwal | The input/output complexity of sorting and related problems[END_REF] and the cache-oblivious model of Frigo et al. [START_REF] Frigo | Cache-oblivious algorithms[END_REF][START_REF] Frigo | Cache-oblivious algorithms[END_REF][START_REF] Prokop | Cache oblivious algorithms[END_REF]. The DAM has an internal memory (RAM) of size M and an arbitrarily large external memory (disk). Data is transferred between RAM and disk in blocks of size B < M . The performance measure is transfers (I/Os). Computation is free.

The cache-oblivious model extends the DAM model. Now parameters B and M are unknown to the algorithm designer or coder. They can only be used as parameters in analyses.

Thus, an optimal cache-oblivious data structure is not parameterized by any block, cache or RAM size, or memoryor disk-access times. Remarkably, many problems have optimal (and practical) cache-oblivious solutions, including Btrees [START_REF] Bender | Cache-oblivious B-trees[END_REF][START_REF] Bender | A locality-preserving cache-oblivious dynamic dictionary[END_REF][START_REF] Brodal | Cache oblivious search trees via binary trees of small height[END_REF]. Informally, a cache-oblivious B-tree has approximately optimal memory or I/O performance at every level of an unknown multilevel memory hierarchy.

Packed-Memory Arrays and External-Memory Dictionaries

In this paper, we give a history-independent PMA and two external-memory dictionaries: a history-independent external skip list and a history-independent cache-oblivious Btree. This subsection puts our results in context. We first define a PMA. Then we describe the technical issues involved in making a history-independent PMA. We (this paper's authors) were surprised when we first suspected that a history-independent PMA could indeed exist. Here, we try to articulate why the PMA might seem to be an unlikely candidate data structure to make history independent, but why it is nonetheless possible.

We next explain why a history independent PMA leads, almost directly, to an HI cache-oblivious B-tree, the first nontrivial history-independent cache-oblivious data structure.

Finally, we discuss the history-independent externalmemory skip list. This HI data structure still offers highprobability guarantees, analogous to in-memory skip lists. See Section 2 for the definition of with high probability, which we also write as "whp".

Although the idea of a B-skip list, which promotes elements with probability 1/B rather than probability 1/2 is folklore and has appeared in the literature repeatedly [START_REF] Abraham | Skip B-trees[END_REF][START_REF] Callahan | Topology B-trees and their applications[END_REF][START_REF] Ciriani | Static optimality theorem for external memory string access[END_REF][START_REF] Golovin | The B-skip-list: A simpler uniquely represented alternative to B-trees[END_REF], we prove that its high-probability I/O guarantees are asymptotically no better than those of an in-memory skip list run in external memory.

Packed-Memory Arrays

One of the classic data-structural problems is called sequential file maintenance: maintain a dynamic set of elements in sorted order in a linear-sized array. If there are N elements, then the array has Θ(N ) empty array positions or gaps interspersed among the elements to accommodate future insertions. The gaps allow some elements to shift left or right to open slots for new elements-like shifting books on a bookshelf to make room for new books.

Remarkably, there are data structures for these problems that are efficient even for adversarial inserts and deletes. Indeed, the number of element moves per update is only O(log2 N ) both amortized [START_REF] Itai | A sparse table implementation of priority queues[END_REF][START_REF] Willard | Inserting and deleting records in blocked sequential files[END_REF] and in the worst case [START_REF] Willard | Maintaining dense sequential files in a dynamic environment[END_REF][START_REF] Willard | Good worst-case algorithms for inserting and deleting records in dense sequential files[END_REF][START_REF] Willard | A density control algorithm for doing insertions and deletions in a sequentially ordered file in a good worst-case time[END_REF], which is optimal [START_REF] Bulánek | Tight lower bounds for the online labeling problem[END_REF].

In external memory, this data structure is called a packedmemory array [START_REF] Bender | Cache-oblivious B-trees[END_REF][START_REF] Bender | An adaptive packed-memory array[END_REF]. It supports inserts, deletes, and range queries. Given the location where we want to insert or delete (which can be found using a separate indexing structure, e.g., [START_REF] Bender | A locality-preserving cache-oblivious dynamic dictionary[END_REF][START_REF] Brodal | Cache oblivious search trees via binary trees of small height[END_REF]), it takes only O(1 + (log 2 N )/B) amortized I/Os to shift the elements. Given the starting point, a range query returning k elements costs Θ(1 + k/B) I/Os. 2 Prior PMAs operate as follows. To insert a new element after an existing element or to delete an element, find an enclosing subarray or range, and rebalance. This spreads out the elements (and gaps) within that range. The rebalance range is chosen based upon the density within the range, where ranges have minimum and maximum allowed densities. These thresholds depend upon the size of the range: small ranges have high thresholds for the maximum density and low thresholds for the minimum density. The larger a range is, the less variability is allowed in its density. The algorithmic subtlety has to do with choosing the right rebalance ranges and the right minimum and maximum density thresholds for each range size.

However, range densities are very history dependent. For example, if you repeatedly insert towards the front of an array or if you repeatedly delete from the back of the array, then the front of the array will be denser than the back. How could we possibly make a version of this data structure, that is history independent-that is, where newly inserted (or deleted) elements do not seem to increase (or decrease) some local density? We answer this question in this paper.

To use a more evocative image, picture a long trough where you are pouring sand in one location (corresponding to inserts) and letting out sand in another location (corresponding to deletes). As the sand piles up, the pile gradually flattens (corresponding to local rebalances). Although rebalances may flatten out the pile, we may still expect a bump for newly arrived sand, and a depression for recently departed sand. Perhaps surprisingly, we can avoid bumps and depressions with mostly local rebalances.

Cache-Oblivious B-Trees

A B-tree is a dictionary supporting search, insert, delete, and range query operations. There are cache-oblivious versions [START_REF] Bender | Exponential structures for efficient cache-oblivious algorithms[END_REF][START_REF] Bender | A locality-preserving cache-oblivious dynamic dictionary[END_REF][START_REF] Brodal | Cache oblivious search trees via binary trees of small height[END_REF][START_REF] Kasheff | Cache-oblivious dynamic search trees[END_REF][START_REF] Rahman | Optimised predecessor data structures for internal memory[END_REF].

A history-independent PMA can immediately yield a history-independent cache-oblivious B-tree. The idea is to take a PMA and "glue" it to a static cache-oblivious Btree [START_REF] Prokop | Cache oblivious algorithms[END_REF]. For details, see [START_REF] Bender | A locality-preserving cache-oblivious dynamic dictionary[END_REF][START_REF] Brodal | Cache oblivious search trees via binary trees of small height[END_REF]. We use a similar method to construct our history-independent cache-oblivious B-tree in Section 3.

External-Memory Skip Lists

The skip list is an elegant search-tree alternative introduced by Pugh [START_REF] Pugh | Skip lists: a probabilistic alternative to balanced trees[END_REF]. Skip lists are randomized data structures having a weakly history independent pointer structure [START_REF] Golovin | Uniquely Represented Data Structures with Applications to Privacy[END_REF][START_REF] Pugh | Skip lists: a probabilistic alternative to balanced trees[END_REF].

Skip lists with N elements support searches, inserts, and deletes in O(log N ) operations whp and range queries returning k elements in O(log N + k) operations whp [START_REF] Devroye | A limit theory for random skip lists[END_REF][START_REF] Kirschenhofer | The path length of random skip lists[END_REF][START_REF] Papadakis | Analysis of the expected search cost in skip lists[END_REF]. They are heavily used in internal-memory algorithms [START_REF] Anagnostopoulos | Persistent authenticated dictionaries and their applications[END_REF][START_REF] Arge | Skip-webs: efficient distributed data structures for multi-dimensional data sets[END_REF][START_REF] Aspnes | Skip graphs[END_REF][START_REF] Fomitchev | Lock-free linked lists and skip lists[END_REF][START_REF] Goodrich | Efficient authenticated dictionaries with skip lists and commutative hashing[END_REF][START_REF] Herlihy | A simple optimistic skiplist algorithm[END_REF][START_REF] Jacob | A distributed polylogarithmic time algorithm for self-stabilizing skip graphs[END_REF][START_REF] Oshman | The SkipTrie: low-depth concurrent search without rebalancing[END_REF][START_REF] Shavit | Skiplist-based concurrent priority queues[END_REF].

This paper gives a simple and provably good externalmemory history-independent skip list, which has high probability guarantees. Specifically, our skip list supports insert, deletes, and searches with O(log B N ) I/Os whp, and range queries returning k elements with O(log B N + k/B) whpwhich is just the search plus scan cost. Thus, our history independent, external memory skip list has high-probability bounds matching those of a B-tree.

Our challenge is to tweak the folklore B-skip list [START_REF] Abraham | Skip B-trees[END_REF][START_REF] Callahan | Topology B-trees and their applications[END_REF][START_REF] Ciriani | Static optimality theorem for external memory string access[END_REF][START_REF] Golovin | The B-skip-list: A simpler uniquely represented alternative to B-trees[END_REF] as little as possible (and in a history-independent way) so that we can achieve high-probability bounds for searches and inserts while maintaining optimal range queries.

Results

We begin by giving an efficient, history-independent packed memory array. THEOREM 1. There exists a weakly history-independent packed-memory array on N elements which can perform inserts and deletes in O(log 2 N ) amortized element moves with high probability. This PMA requires O(N ) space, can perform inserts and deletes in amortized O log Theorem 1 directly yields a history-independent cacheoblivious B-tree with these performance bounds: THEOREM 2. There exists a weakly history-independent, cache-oblivious B-tree on N elements which can perform inserts and deletes in O log 2 N B + log B N amortized I/Os with high probability. This cache-oblivious B-tree requires O(N ) space and can answer a range query for k elements in O(log B N +k/B) I/Os, i.e., the search plus the scan cost.

We give a simple and provably good external-memory history-independent skip list, which has high probability guarantees analogous to in-memory skip lists. THEOREM 3. There exists a weakly history-independent, external-memory skip list on N elements which can perform look-ups in O(log B N ) I/Os with high probability. For a parameter ε > 0, the skip-list requires O(log B N ) amortized I/Os for inserts and deletes, with a worst case of O(B ε log N ) I/Os, all with high probability. This skip-list requires O(N ) space and can answer a range query for k elements in O( 1 ε log B N + k/B) I/Os with high probability.

The parameter ε indicates a small trade-off between the worst-case rebuild cost after an update and the cost of medium-size range queries (see Section 6).

We contrast our data structure with the B-skip list, which promotes elements from one level to the next with probability 1/B. We prove that with high probability, there exist at least Ω( √ N B) elements where the cost to search for any one of them is O(log N B ). Thus, the high-probability I/O bounds for searching in a B-skip list are not asymptotically better than for searching in a regular (internal-memory) skip list that is implemented in external memory.

Related Work

History of History Independence

The history of history independence spans nearly four decades. The central notions of history independence predate its formalism.

One of the key ideas of history independence is unique representation, which was studied as far back as 1977 by Snyder [START_REF] Snyder | On uniquely represented data strauctures[END_REF]. Many uniquely represented data structures were published before the conception of history independence [4, 6, 7, 52-54, 59, 60]. Similar to unique representation, the idea of randomized structures that are uniformly represented, that is, have representations drawn from a distribution irrespective of the past history, emerged with Pugh's skip list [START_REF] Pugh | Incremental computation and the incremental evaluation of functional programs[END_REF][START_REF] Pugh | Skip lists: a probabilistic alternative to balanced trees[END_REF] and Aragon and Seidel's treap [START_REF] Aragon | Randomized search trees[END_REF].

Nearly a decade later, Micciancio [START_REF] Micciancio | Oblivious data structures: applications to cryptography[END_REF] defined oblivious data structures as those whose topology does not reveal the sequence of operations that led to the current state. In 2001, Naor and Teague [START_REF] Naor | Anti-persistence: history independent data structures[END_REF] strengthened obliviousness to history independence ("anti-persistence"), generalizing it to include the entire bit representation of the structure, including memory addresses.

Hartline et al. [START_REF] Hartline | Characterizing history independent data structures[END_REF] proved that a reversible data structure (i.e. one whose state graph is strongly connected) is SHI if and only if it fixes a canonical representation for each state depending only on initial (possibly random) choices made before any operations are performed.

Buchbinder and Petrank [START_REF] Buchbinder | Lower and upper bounds on obtaining history independence[END_REF] further explored strong versus weak history independence, proving a separation between the two notions for heaps and queues in a comparisonbased model.

History-independent data structures are well-studied when the objective is to minimize RAM computations. Examples include SHI hashing [START_REF] Blelloch | Strongly history-independent hashing with applications[END_REF][START_REF] Naor | History-independent cuckoo hashing[END_REF][START_REF] Naor | Anti-persistence: history independent data structures[END_REF], dictionaries and ordermaintenance [START_REF] Blelloch | Strongly history-independent hashing with applications[END_REF], and history-independent data structures for computational geometry [START_REF] Blelloch | Uniquely represented data structures for computational geometry[END_REF][START_REF] Tzouramanis | History-independence: a fresh look at the case of R-trees[END_REF].

Golovin [START_REF] Golovin | B-treaps: A uniquely represented alternative to B-trees[END_REF][START_REF] Golovin | The B-skip-list: A simpler uniquely represented alternative to B-trees[END_REF] began an algorithmic study of historyindependent data structures in external-memory. First, Golovin proposed the B-treap [START_REF] Golovin | B-treaps: A uniquely represented alternative to B-trees[END_REF], a strongly history-independent external-memory B-tree variant based on treaps [START_REF] Aragon | Randomized search trees[END_REF].

Golovin notes that while the B-treap is a uniquerepresentation data structure supporting B-tree operations with low overhead, from a practical point of view, it is complicated and difficult to implement [START_REF] Golovin | The B-skip-list: A simpler uniquely represented alternative to B-trees[END_REF]. Golovin thus proposes a strongly history-independent B-skip list [START_REF] Golovin | The B-skip-list: A simpler uniquely represented alternative to B-trees[END_REF] as a simpler alternative to the B-treap. This data structure achieves O(log B N ) I/Os in expectation for searches and updates and O(k/B + log B N ) I/Os in expectation for range queries returning k elements.

Golovin's B-skip list builds upon the folklore extension of skip lists (see e.g., [START_REF] Abraham | Skip B-trees[END_REF][START_REF] Callahan | Topology B-trees and their applications[END_REF][START_REF] Ciriani | Static optimality theorem for external memory string access[END_REF][START_REF] Golovin | The B-skip-list: A simpler uniquely represented alternative to B-trees[END_REF]): promote an element from one level to the next with probability 1/B, rather than 1/2. The folklore B-skip list's I/O bounds are only in expectation, and do not extend to good high probability bounds (see Lemma 15).

Other Applications of History Independence

The theoretical work on history independence in external memory complements the security and experimental work on history-independent data structures for persistent storage, such as file systems, cloud storage, voting systems and databases [10-12, 19, 44, 45, 56].

History independence has many applications in security and privacy. For example, history-independent data structures help to guarantee privacy in incremental signature schemes [START_REF] Micciancio | Oblivious data structures: applications to cryptography[END_REF] and vote-storage mechanisms [START_REF] Bethencourt | Cryptographic methods for storing ballots on a voting machine[END_REF][START_REF] Molnar | Tamper-evident, history-independent, subliminal-free data structures on prom storage-or-how to store ballots on a voting machine[END_REF][START_REF] Moran | Deterministic history-independent strategies for storing information on write-once memories[END_REF].

History-independent data structures often have nice properties. For example, skip lists [START_REF] Pugh | Skip lists: a probabilistic alternative to balanced trees[END_REF] have weakly historyindependent topologies, and are weight balanced [START_REF] Nievergelt | Binary search trees of bounded balance[END_REF] in a randomized sense. Canonical representations [START_REF] Hartline | Characterizing history independent data structures[END_REF] find applications in other areas besides security, e.g. concurrent data structures [START_REF] Shun | Phase-concurrent hash tables for determinism[END_REF], equality testing [START_REF] Sundar | Unique binary search tree representations and equality-testing of sets and sequences[END_REF] and dynamic and incremental algorithms [START_REF] Acar | Dynamizing static algorithms, with applications to dynamic trees and history independence[END_REF][START_REF] Pugh | Incremental computation and the incremental evaluation of functional programs[END_REF].

PRELIMINARIES

An event E n on a problem of size n occurs with high probability (whp) if Pr [E n ] ≥ 1-1/n c for some constant c. Often the event E n is parametrized by some constant d, in particular, because the event is defined using Big Oh notation. (See, e.g., Theorem 11.) In this case, we can say more strongly that for every c, there is a d so that Pr [E n ] ≥ 1 -1/n c . We use high probability guarantees to bound a data structure's performance more tightly than can be done using expectation alone. Even if a data structure performs well in expectation, it may have a large number of poorly-performing operations (see, for example, Lemma 15).

Two instances I 1 and I 2 of a data structure are in the same state if they cannot be distinguished via any sequence of operations on the data structure. The memory representation of an instance I of a data structure is the bit representation of I, including data, pointers, unused buffer space, and all auxiliary parts of the structure, along with the physical addresses at which they are stored.

DEFINITION 4 (WEAK HISTORY INDEPENDENCE).

A data structure is weakly history independent (WHI) if, for any two sequences of operations X and Y that take the data structure from initialization to the same state, the distribution over memory representations after X is performed is identical to the distribution after Y .

Building Blocks for History Independence

We use history-independent allocation [START_REF] Naor | Anti-persistence: history independent data structures[END_REF] as a black box. We also use the weak history-independent dynamic arrays [START_REF] Hartline | Characterizing history independent data structures[END_REF], rather than strongly independent dynamic arrays [START_REF] Hartline | Characterizing history independent data structures[END_REF][START_REF] Naor | Anti-persistence: history independent data structures[END_REF]. 3Weakly history-independent dynamic arrays take constant amortized time per update with high probability. The idea is to maintain the following invariants. For array A storing n elements: (1) the size |A| is uniformly and randomly chosen from {n, . . . , 2n -1}, and, (2) after each insert or delete resize with probability Θ(1/|A|).

Performance Advantages of WHI over SHI

We focus on weak history independence because of its performance benefits. In particular, weak history independence allows us to have high-probability guarantees in our data structures.

Strong history independence for reversible data structures requires a canonical representation [START_REF] Hartline | Characterizing history independent data structures[END_REF]. 4 While canonical representations are useful to have, maintaining them imposes strict limitations on the design and efficiency of the data structure, as argued by several authors [START_REF] Buchbinder | Lower and upper bounds on obtaining history independence[END_REF][START_REF] Hartline | Characterizing history independent data structures[END_REF]. Moreover, amortization, strong history independence, and highprobability guarantees are largely incompatible.

In particular, SHI dynamic arrays cannot achieve the same with high probability guarantees as WHI dynamic arrays. OBSERVATION 1. No strongly-history-independent dynamic array can achieve o(N ) amortized resize cost per insert or delete with high probability.

PROOF. Consider a strongly-history-independent dynamic array that needs to be strictly greater than 50% full. (The proof generalizes to arbitrary capacity constraints.) For integer k, the adversary chooses a random ∈ {k, k + 1, . . . , 2k}. Then the adversary inserts up to elements into the array, and then alternates between adding and removing an element from the array, so that the array alternates between having and + 1 elements.

Given the capacity constraints on the array, there must be at least two different canonical representations for the arrays of sizes k, k + 1, . . . , 2k. Thus, there is a probability of at least 1/k that the adversary forces an array resize (with cost Ω(N )) on every insert and delete in the alternation phase.

Observe that k can be arbitrarily large. No matter how long the data structure runs, it cannot avoid an Ω(N ) resize with probability greater than 1 -1/k. Most importantly, this observation applies to PMAs as well. A PMA with N elements at a given time is required to have size Θ(N ), so it generalizes the dynamic array. That is, Observation 1 lets us conclude the following: REMARK 1. A strongly history-independent PMA cannot give any o(N ) amortized with high probability operation bounds. In contrast, our weakly history-independent PMA has a O(log 2 N ) bound (Theorem 1).

Observation 1 similarly generalizes to other amortized data structures with large worst-case costs. Thus, while strong history independence provides stronger security guarantees, it can come at a high performance cost.

Oblivious Adversary and Oblivious Observer

Our performance analyses assume an oblivious adversary, which determines the sequence of operations presented to the data structure. The oblivious adversary cannot see the outcomes of the data structure's coin flips nor the current state of memory. Said differently, the adversary is required to choose the entire sequence of operations before the data structure even starts running. The oblivious adversary is used for analyzing randomized structures such as skip lists [START_REF] Pugh | Skip lists: a probabilistic alternative to balanced trees[END_REF] or treaps [START_REF] Aragon | Randomized search trees[END_REF]. Our (weak) history-independence analyses assume an oblivious observer. The observer cannot control the input sequence and does not see the data structure's coin flips. The observer gets to observe the data structure's memory representation once. We prove history independence by showing that for every state of the data structure, the distribution of memory representations is the same, regardless of how the data structure got to that state.

HISTORY-INDEPENDENT PACKED MEMORY ARRAY

This section gives a history-independent packed memory array (PMA). A PMA is an Θ(N )-sized array that stores a sequence of elements in a user-specified order. There are up to O(1) gaps between consecutive elements to support efficient insertions and deletions.

A PMA with N elements supports the following:

• Query(i, j)-return the ith through jth elements of the PMA, inclusive, where 0 ≤ i ≤ j < N . • Insert(i, x)-insert x as the ith element of the PMA, where 0 ≤ i ≤ N . Elements with rank i through N -1 before the insert become the elements with i + 1 though N after the insert. • Delete(i)-delete the ith element of the PMA, where 0 ≤ i < N .

The PMA's performance is given in Theorem 1.

High-Level Structure of HI PMA

Packed-memory arrays and sparse tables in the literature [14, 16-18, 38, 41, 66] are not history independent; the size of the array, densities of the subarrays, and rebalances depend strongly on the history. We guarantee history independence for our PMA as follows. First, we ensure the size of the PMA is history independent. We resize using the HI dynamic array allocation strategy [START_REF] Hartline | Characterizing history independent data structures[END_REF], as summarized in Section 2.1.

Next, we ensure that the N elements in the array of size N S = Θ(N ) are spread throughout the array according to a distribution (given below) that is independent of past operations.

We maintain this history-independent layout recursively. At the topmost level of recursion, we (implicitly) maintain a set of size Θ(N S / log N S ), which we call the candidate set. The candidate set consists of elements that have rank N/2 ± Θ(N S / log N S ). We pick a random element from the candidate set, which we call the balance element. If the balance element has rank r, then we recursively store the first r -1 elements in the first half of the array and the remaining N -r -1 elements in the second half of the array.

In general, when we are spreading elements out within a subarray A of the PMA, the candidate set has size Θ(|A|/ log N S ), and as before, the balance element is randomly chosen from this set. The base case is when |A| = Θ(log N S ), at which point the elements are spread evenly throughout A.

Thus, how the elements are spread throughout the PMA depends only on the size N S (which is randomly chosen as described in Section 2.1), the number of elements in the PMA N , and the random choices of all the balance elements.

We maintain the balance elements in each candidate set using a simple generalization of reservoir sampling [START_REF] Vitter | Random sampling with a reservoir[END_REF] in which there are deletes, described below. In this particular instance of reservoir sampling, the size of a candidate set at any given level of recursion stays the same, unless the size of the entire PMA changes.

See Figure 1 for an illustration of our PMA. The top part represents how each level of recursion partions the elements into ranges. We show repeated elements across levels to aid visualization; they are only stored once in the data structure (at the bottom level). The division of elements into ranges at each level helps in maintaining the balance elements, which are stored in a separate structure.

Reservoir Sampling with Deletes

We first review a small tweak on standard reservoir sampling [START_REF] Vitter | Random sampling with a reservoir[END_REF], reservoir sampling with deletes, which we use to help build the PMA.

Game: We have a dynamic set of elements. The objective is to maintain a uniformly and randomly chosen leader of the set, where each element in the set has equal probability of being selected as leader. In other words, we are interested in reservoir sampling with a reservoir of size 1.

Since the set is dynamic, at each step t, an element may be added to or deleted from the set. The adversary is oblivious, which means that the input sequence cannot depend on the particular element chosen as leader.

We can maintain the leader using the following technique. Let n t denote the number of elements in the set at time t (including any newly-arrived element). Initially, if the set is nonempty, we choose the leader uniformly at random. When a new element y arrives, y becomes the leader with probability 1/n t ; otherwise the old leader remains. When an element is deleted, there are two cases. If that element was the leader, then we choose a new leader uniformly at random from the remaining elements in the set. If the deleted element was not the leader, the old leader remains. LEMMA 5 ([62]). At any time step t, if there are n t elements in the pool, then each element has a probability 1/n t to be the leader.

Detailed Structure of the HI PMA

The size N S of our history-independent PMA is a random variable that depends on the number of elements N stored in the PMA (similar to dynamic arrays in Section 2.1). We select parameter N randomly from {N, . . . , 2N -1}, and N S is a function of N (as described below).

We view the PMA as a complete binary tree of ranges, where a range is a contiguous sequence of array slots. This tree has height h = log N -log log N . The root is the entire PMA and has depth 0. The leaves in the binary tree are ranges comprising C L log N slots, and C L is a constant to be determined later. Thus, the PMA has a total of N S = 2 h C L log N ≤ (2C L + 1) N = Θ(N ) slots.

Consider a range R in the binary tree with left child R 1 and right child R 2 . Recall from Section 3.1 that the balance element b R of R is the first element of R 2 ; all the elements in R of smaller rank than b R are stored in R 1 . The values of b R for each range/node are stored in a separate tree.

For each non-leaf range R at depth d, define the candidate set M R to be the c 1 N 2 -d / log N middle elements of R. More precisely, if R holds elements, then we fix the size of M R and set the first element of M R to be the 1 + /2 -|M R |/2 th element of R. Our PMA is parameterized by a constant 0 < c 1 < 1-6/ log N . 5 A larger c 1 reduces the amortized update time and increases the space. We require C L ≥ 1+c 1 +6/ log N . The value of C L and c 1 need not change as N changesvalues such as c 1 = 1/2 and C L = 2 will work for sufficiently large N (over 4096 in this case).

Dynamically Maintaining Balance Elements

As elements are inserted into or deleted from the PMA, the candidate set M R for some range R could change. This change might be caused by a newly inserted or deleted element that belongs to M R or just because insertions at one end of R cause the median element of R to change.

As the candidate set M R changes, we maintain the invariant that the balance element b R is selected uniformly and randomly from M R . (In particular, this means that b R is selected history-independently.) We use reservoir sampling with deletes as the basis for maintaining this invariant. INVARIANT 6. After each operation, for each range R, balance element b R is uniformly distributed over the candidate set M R .

Whenever one element leaves their candidate set, another one joins, since the candidate set size of each range is fixed between rebuilds of the entire PMA. Thus, we describe how to maintain the candidate set when exactly one element is added, and one leaves.

If the balance element is the element leaving the candidate set, we select the new balance element uniformly at random. Otherwise, when a new element enters the candidate set, it has a 1/|M R | chance of becoming the new balance element (as in reservoir sampling).

When the balance element of a range changes, we rebuild the entire range and all of its subranges. Rebuilding a range of |R| slots can be done in Θ(|R|) time; see Lemma 10.

Detecting Changes to the Candidate Set

In order to determine how inserts and deletes affect the candidate set of a range R, we need to know the rank of the element being inserted or deleted, the current candidate set of R, and the rank of the current balance element of R.

The rank of the element being inserted and deleted is specified as part of the insert or delete operation.

To compute the other information, our PMA maintains an auxiliary data structure containing the number of elements R in each range R. During an insert or delete, as we descend the tree of ranges, we keep track of the ranks of the first and last element in each range as follows. Suppose we are at range R whose first element has rank x. If we descend to R 1 , then we know the rank of the first element of R 1 is also x. If we descend to R 2 , then the rank of its first element is x + R1 . Given the rank of the first element of a range and the number of elements in that range, it is easy to compute its candidate set. Note also that the rank of the balance element of a range R whose first element has rank x is x + R1 .

We need to store R for each range so that it can be accessed efficiently, both in terms of operations and I/Os. Since the ranges form a complete binary tree, we store the numbers R in a binary tree organized in a Van Emde Boas layout (see [START_REF] Bender | Cache-oblivious B-trees[END_REF][START_REF] Prokop | Cache oblivious algorithms[END_REF]). We call this auxiliary data structure the rank tree.

The Van Emde Boas layout is a deterministic, static, cache-oblivious-and hence history-independent-layout of a complete binary tree. It supports traversing a root-to-leaf path in O(log N ) operations and O(log B N ) I/Os. Thus, the rank tree is history independent.

Whenever the size of a range changes due to an insert or delete, we update the corresponding entry in the rank tree. Whenever we rebuild a range R in the PMA, we update all entries of the rank tree corresponding to descendants of R. Whenever we rebuild the entire PMA, we rebuild the entire rank tree.

CORRECTNESS AND PERFORMANCE

Balance-Element Structural Lemmas

First, we show correctness-the data structure always finds a slot for any element it needs to store. LEMMA 7. At all times, the size of a range is larger than the number of elements it contains.

PROOF. Consider a range at depth d. This range has

N S /2 d = 2 h-d C L log N ≥ C L N /2 d
slots. We will show that the maximum number of elements it can contain is smaller than this number of slots.

The number of elements in the range is at most half of the elements in its parents range, plus half of the size of the parent's candidate set (rounding up). In other words, if S(d) is the maximum number of elements in a range at depth d, S(0) ≤ N and

S(d) ≤ S(d -1)/2 + M R /2 ≤ S(d -1)/2 + 1 2 c 1 N 2 d-1 log N + 1 2 ≤ S(d -1) 2 + c 1 N 2 d log N + 3 2 .
By induction,

S(d) ≤ N 2 d + c 1 d N 2 d log N + 3.
Since d ≤ log N , and

N /2 d ≥ N /2 h ≥ (log N )/2, S(d) ≤ N 2 d (1 + c 1 ) + 3 ≤ N 2 d 1 + c 1 + 6 log N . Since we choose C L ≥ 1+c 1 +6/ log N , we have S(d) ≤ C L N /2 d .
As Lemma 7 establishes, each leaf range in the PMA (which has Θ(log N ) slots) never fills up completely. Using a similar argument, it can be shown that each leaf also contains Ω(log N ) elements if c 1 < 1 -6/ log N . Because the elements are spread out evenly in the leaves, this implies there are O(1) gaps between two consecutive elements. LEMMA 8. If c 1 < 1 -6/ log N , the leaves are always constant-factor full. There is O(1) space between two consecutive elements in the array.

Next, we prove weak history independence. As mentioned in Section 3.1, when we are spreading elements out within a subarray A of the PMA, the balance element is randomly chosen from the candidate set. The elements of A are recursively split between its children according to this balance element. The base case is when |A| = Θ(log N ), at which point the elements are spread evenly throughout A.

Thus, how the elements are spread throughout the PMA depends only on N (and the related N S ), the number of elements in the PMA N , and the random choices of all the balance elements. This immediately gives weak historyindependence, as formalized in the following lemma. LEMMA 9. This PMA is weakly history independent.

PROOF. We show that the memory representation of the PMA is based only on N and some randomness (in particular, the random choices made during balance element selection and the random choice of N ).

Let the PMA contain a set of elements S of size N , with a set of balance elements P . Then P partitions the elements of S into leaf ranges.

Since the elements are evenly spaced in each leaf range, the position of each element within the leaf is determined by the number of elements in that leaf. Since S is partitioned into leaf ranges by P , P determines the position of each element in the PMA. Thus P , N , and N determine the memory representation of the data structure. By Invariant 6, P is selected from a distribution based only on N and N .

Thus, any two sequences of operations X and Y that insert S into the PMA result in the same distribution on P , and the same distribution on memory representations.

Proving the Performance Bounds

We begin by bounding the cost of a rebalance. Then we bound the total number of rebalances. Our goal is to bound the cost of our PMA operations. Specifically, we want to show Theorem 11. THEOREM 11. Consider k (not necessarily consecutive) operations on a PMA during which its maximum size is N M , its minimum size is Ω(N M ), and k = Ω(N M ). The amortized cost of these operations is O(log 2 N M ) with high probability with respect to k: in other words, these k operations require O(k log 2 N M ) total RAM operations with high probability.

Before proving this theorem, we need some supporting lemmas and definitions. DEFINITION 12. A rebuild that is not charged to a range R is called a free rebuild. Free rebuilds come from two sources: (1) they are rebuilds of an ancestor range (whose cost is charged to the ancestor), or (2) they are triggered by the interstitial operations between the nonconsecutive operations of Theorem 11.

We further categorize non-free rebuilds by their causes. An out-of-bounds rebuild is a rebuild caused by the pivot leaving the candidate set. A lottery rebuild is a rebuild caused by deleting the pivot or by inserting into the candidate set an element that becomes a new pivot.

Gearing up to Lemma 13, we concentrate on the cost of all rebalances at a single depth d. Let M d be the size of the candidate set at depth d.

We give a lower bound on the probability that two outof-bounds rebuilds happen in quick succession. This lemma holds regardless of the number of free and lottery rebuilds that happen in between. LEMMA 13. After any rebuild of a range R at depth d, consider a sequence of t operations on R, for any t ∈ {1, . . . , M d /2 }, with arbitrary free and lottery rebuilds occurring during these operations. The probability p(t) that no out-of-bounds rebuild happens during these t operations is at least 1 -2t/M d .

PROOF. Let p i (t) be the probability that no out-of-bounds rebuild happens in the first t time steps, given that exactly i free and lottery rebuilds happen during the first t time steps. We prove the lemma by induction on i.

Define the guard number as the number of elements between the pivot and the closest endpoint of the candidate set.

First, the base case: for any t, p 0 (t) is at least the probability that the guard number after a rebuild is larger than t. Indeed, the balance element cannot be moved closer to an endpoint of the candidate set by more than one element per operation. As the pivot is sampled uniformly after any type of rebuild, we have

p 0 (t) ≥ Pr [guard number > t] ≥ 1 -2t/M d .
Now, assume by induction that p i (t) ≥ 1 -2t/M d and we want to show p i+1 (t) ≥ 1 -t/M d . Let t be the last time step before the (i + 1)st non-out-of-bounds rebuild.

The following conditions ensure that there are no out-ofbounds rebuilds in the first t operations:

1. there is no out-of-bounds rebuild in the first t operations, and 2. there is no out-of-bounds rebuild in the subsequent tt operations. These two events are independent since there is a fixed (free or lottery) rebuild between them. The first occurs with probability p i (t ) and the second with probability p 0 (t -t ). Thus, we have

p i+1 (t) ≥ p i (t ) p 0 (t -t ) ≥ (1 -2t /M d ) (1 -2(t -t )/M d ) ≥ 1 -2t/M d ,
and the induction is complete. DEFINITION 14. Consider an out-of-bounds rebuild of a range R at depth d.

We call this rebuild a good out-of-bounds rebuild if R has only free and lottery rebuilds for the next M d /4 operations.

By Lemma 13, an out-of-bounds rebuild is good with probability at least 1/2.

We are now ready to prove Theorem 11. PROOF OF THEOREM 11. Consider the sequence of rebuilds of ranges at a given depth d. We analyze lottery rebuilds and out-of-bounds rebuilds separately. Since variations in N slightly change the candidate set size, let M denote the smallest candidate-set size at depth d over the k operations. However, since N = Θ(N M ) at all times,

M = Θ(|M d |).
We give a (weak) bound on k/M which helps show that the high-probability bounds hold with respect to k.

In particular,

k/M ≥ k log N M N M ≥ k log k log N M N M log k = Ω(log k), since k/ log k = Ω(N M / log N M ) if k = Ω(N M ).
Each operation has probability at most 1/M of causing a lottery rebuild. Thus, there are k/M lottery rebuilds in expectation. Then using Chernoff bounds, the probability that we have more than (1 + δ)k/M rebuilds is less than e -δk/3M . Recall that k/M = Ω(log k). Substituting, there are O(k/M ) lottery rebuilds with high probability. Now, we bound the out-of-bounds rebuilds. By the pigeonhole principle, there cannot be more than k/(M/4) + 2 d = O(k/M ) good out-of-bounds rebuilds (the second term comes from the number of ranges at depth d).

We bound how many bad out-of-bounds rebuilds can happen before reaching this limit on good out-of-bounds rebuilds. Any out-of-bounds rebuild is good with probability at least 1/2. Then after k/M = Ω(log k) out-of-bounds rebuilds, we obtain Θ(k/M ) good out-of-bounds rebuilds with high probability, again by Chernoff bounds. As we can only get O(k/M ) good rebuilds, we have O(k/M ) out-of-bounds rebuilds in total.

Therefore, every k operations, there are O(k/M ) out-ofbounds and lottery rebuilds of ranges at depth d with high probability. Each rebuild costs O(M log N M ) RAM operations by Lemma 10 (because that is the number of slots in a range at depth d). Thus, the total rebuild cost for depth

d is O(k log N M ).
Having determined the cost of rebalancing at each depth, we account for the total cost. The amortized rebalance cost, summing over all

h = O(log N M ) levels, is O(log 2 N M ).
Each resize costs O(N M ) and occurs with probability O(1/N M ) after every insertion. Using Chernoff bounds, there are O((k log N M )/N M ) = Ω(log k) resizes after k operations with high probability, leading to an additional amortized cost of O(log N M ).

Finally, each insert or delete requires extra bookkeeping: we must find the appropriate leaf range to insert the element by traversing the rank tree. This traversal takes O(log N M ) RAM operations, and rebuilding the leaf so that the elements are still evenly spaced takes O(log N M ) RAM operations.

This gives a total of O(k log 2 N M ) total RAM operations with high probability.

Using similar analysis, we can also bound the I/O performance. Recall that rebalancing a range of size R takes O(R/B + 1) I/Os, and traversing a tree in the Van Emde Boas layout requires O(log B N M ) I/Os. Carrying these terms through the above proof gives the desired bounds.

To complete the proof of Theorem 1, we need to extend this analysis to handle the PMA changing size significantly. PROOF OF THEOREM 1. We partition the k = Ω(N ) operations on the PMA into types based on the size of the PMA. In particular, let Nt be the value of N during the tth operation. Then operation t is of type

0 if N ≥ Nt > N/2, type 1 if N/2 ≥ Nt > N/4, and type i if N/2 i ≥ Nt > N/2 i+1 for 0 ≤ i ≤ log N .
We analyze each type of operations as a whole, and bound its total cost, summing to O(k log 2 N ) RAM operations in total. Each type is analyzed using two cases.

First, consider a type i which has at least √ N total opera-tions. Then by Theorem 11, these operations take amortized O(log 2 N ) RAM operations with high probability. Second, consider a type i which has less than √ N operations. We call the operations of these types small-type operations. We show that the total cost of all small-type operations is a lower-order term.

Since the PMA begins as empty, and each operation can only insert one element, there are at least N/2 i+1 operations of type i. Thus, each small-type operation t has Nt ≤ √ N . Then overall, a type which has less than

√

N operations must operate on a PMA of size ≤ √ N . Thus, each type has total cost O(N ). Summing over the O(log N ) such types, we get a worst-case total cost of O(N log N ) for small-type operations; amortizing gives a cost of O(log N ) RAM operations.

Thus the total amortized cost is O(log 2 N ) with high probability with respect to N . The I/O cost to rebuild range R is |R|/B by Lemma 10; carrying this term through the above analysis, we obtain the desired I/O bounds.

Experimental Results

We implemented a normal PMA and our historyindependent PMA. We found that while there was approximately a factor of 7 overhead in the run time, the asymptotic performance matched our analysis.

We also examined the number of element moves required during an insert. Figure 2 shows the number of moves required divided by N log 2 N vs. the number of elements inserted. The linear nature of this data supports our theoretical analysis.

These tests were run on a Dell server with an Intel Xeon processor (E5-2450 @ 2.10GHz). In these tests, inserting 100 million random numbers took approximately 23 minutes. Additionally the space overhead ranged from 1.8 to 5 times the number of elements. The history-independence of our PMA depends on the balance elements being uniformly distributed across the candidate set; see Lemma 5. To test this, we inserted values of 1-100,000 sequentially into a history-independent PMA and recorded the position of the balance for each range within this PMA where the candidate set size was eight or greater. We did this test 10,000 times and used the χ 2 goodness-offit test to compare these balance elements with a uniform distribution. To ensure enough samples we only looked at ranges where the expected count for each bucket was ten or greater. This resulted in 148 p-values. If our null hypothesis, that these balances are uniformly distributed, holds, these pvalues themselves should be uniformly distributed. Running the χ 2 goodness-of-fit test across these p-values showed a result consistent with data coming from a uniform distribution (p=0. 47, n=148). As a result we can say there is no statistically significant evidence of that our balance elements have a deviation from a uniform distribution.

HISTORY-INDEPENDENT CACHE-OBLIVIOUS B-TREE

In this section we prove Theorem 2, which establishes the performance of our history-independent cache-oblivious Btree. This N -element data structure, must, without knowledge of the block size B, The requirements above are similar to those achieved by our PMA. The key difference is that PMA items are searched by rank (before being inserted, deleted, or completing a range search) rather than value.

•
By slightly augmenting our PMA, we obtain a cacheoblivious B-tree achieving the above bounds. We call our data structure the augmented PMA.

The augmented PMA has an additional, static-topology tree associated with it. Recall that our PMA has the sizes of each range stored in a complete binary tree, in a Van Emde Boas layout. We store an additional tree storing the values of each balance element. The two trees are identically structured, and identically maintained. Thus, this leads to only a constant factor increase in both space and running time. To search (by value) in the augmented PMA, we traverse a path in the new tree of balance-element values. This costs O(log B N ) I/Os and O(log N ) operations. Once we have found the element, we can determine its rank by traversing the rank tree, summing the sizes of any left children each time we go to a right child.

Once the rank of the element is known, we insert, delete, or perform range queries as in the normal PMA, establishing the desired bounds.

HISTORY-INDEPENDENT EXTERNAL-MEMORY SKIP LIST

In this section we prove Theorem 3. We give a historyindependent external-memory skip list.

In-memory skip lists support updates and queries in O(log N ) time whp. The natural extension to external memory [START_REF] Abraham | Skip B-trees[END_REF][START_REF] Callahan | Topology B-trees and their applications[END_REF][START_REF] Ciriani | Static optimality theorem for external memory string access[END_REF][START_REF] Golovin | The B-skip-list: A simpler uniquely represented alternative to B-trees[END_REF] promotes elements with probability 1/B rather than probability 1/2. We prove that for this extension, the high-probability I/O bounds are asymptotically no better than those of an in-memory skip list run in external memory ( Lemma 15).

We build an external-memory skip list with good (i.e., Btree-like) high-probability bounds for searches, updates, and range queries, while retaining the structure of the folklore B-skip list as much as possible.

High-Level Structure of the HI External-Memory Skip List

First, we describe why the folklore B-skip list fails to achieve high-probability I/O bounds. Then, we present the approach used in our skip list.

Golovin and others [START_REF] Abraham | Skip B-trees[END_REF][START_REF] Callahan | Topology B-trees and their applications[END_REF][START_REF] Ciriani | Static optimality theorem for external memory string access[END_REF][START_REF] Golovin | The B-skip-list: A simpler uniquely represented alternative to B-trees[END_REF] promote elements with probability 1/B (rather than 1/2, as in the in-memory skip list). Consider an array, a sequence of contiguous elements at any level that have not been promoted to the next level (i.e., lie between two promoted elements). These arrays can have size O(B log N ) whp, which is O(log N ) times larger than the expected length. When this list is embedded in an array (analogous to the nodes in a B-tree), then a scan to search for these elements costs O(log N ) I/Os whp.

We change the promotion probability to 1/B γ , where 1/2 < γ < 1 -log log B/ log B. Now, all arrays have size O(B γ log N ) whp, so searches and updates take O(B γ log N/B) = O(log B N ) I/Os whp.

While a promotion probability of 1/B γ results in fast searches and updates, it slows down range queries. If we pack arrays at the leaf level (the leaf arrays) of the skip list into disk blocks [START_REF] Golovin | The B-skip-list: A simpler uniquely represented alternative to B-trees[END_REF], then most disk blocks will be underutilized, containing only B γ elements on average. Thus, a range query returning k elements may require O(log B N + k/B γ ) I/Os, which is worse than the target of O(log B N + k/B) I/Os.

For efficient range queries, we pack multiple arrays into disk blocks at the leaf level as follows. Contiguous arrays, delimited by elements promoted twice, are packed together into a leaf node. A leaf node is stored consecutively on disk; see Figure 3.

The packing strategy described above permits some leaf nodes to get too large, achieving size Θ(B 2γ log N ). If we pack elements as densely as possible, then every new insert would require rewriting the entire node at a cost of O(B 2γ-1 log N ) I/Os, which is worse than Θ(log B N ) I/Os.

Similar to PMAs and HI dynamic arrays [START_REF] Hartline | Characterizing history independent data structures[END_REF], we leave empty spaces between the elements in the leaves to support efficient inserts. We do so in a way that maintains history independence; see Invariant 16.

Detailed Structure of the HI External-Memory Skip List

A skip list S is a series of linked lists {S 0 , S 1 , . . . , S h }, where S 0 ⊇ S 1 ⊇ . . . ⊇ S h . Let H = {0, 1, . . . , h} be the levels of the skip list, and h the height of the skip list. The base list S 0 contains all the elements in the skip list; we call level 0 the leaf level. Each S i , for 0 < i ≤ h, stores a sorted subset of the elements from S i-1 , along with the special element front to mark the beginning of the list; see Figure 3. The function level : S 0 → H determines the highest list that contains an element x, that is, if level (x) = i then x ∈ S j for all j ≤ i and x / ∈ S k for i < k ≤ h. The height of each element is determined randomly, according to promotion probability p. Specifically, for i ∈ H -{0}, if an element is in S i-1 , it is also in S i with probability p. Thus, level (x) of an element x is the number of coin flips before we see a tail, when using a biased coin with probability p of flipping a head.

Next, we show that the folklore B-skip list, which has a Front promotion probability of 1/B, performs poorly for some elements with high probability.

LEMMA 15. In a B-skip list with promotion probability p = 1/B, there exist Ω( √ N B) elements with search cost Ω(log(N/B)) with high probability with respect to N/B.

For our history-independent external-memory skip list, we choose promotion probability p = 1/B γ , where 1/2 < γ ≤ 1 -log log B/ log B is a constant. Let 1/p = B γ be integral to simplify analysis. We parameterize our running times by ε > 0, with γ = (ε + 1)/2.

The parameter γ can be tuned-there is a trade-off between the cost of a range query and the worst-case cost of insertion. Specifically, a range query returning k elements has a cost of O( 1 ε log B N + k/B), while the worst-case insert cost is O(B ε log N ) I/Os. The expected insert cost remains O(log B N ) I/Os for all allowed values of γ.

We now describe how to partition the elements into arrays at nonleaf levels. We also describe how to pack the leaf arrays into leaf nodes.

Partitioning Non-Leaf Levels. We partition the list S i at each level i for 1 ≤ i ≤ h into arrays. The array at level i starts with a promoted element, i.e., element x with level (x) ≥ i + 1. It contains all elements up to (and not including) the next promoted element. The size of an array is the number of elements stored in it plus any empty slots. We maintain these sorted arrays history independently [START_REF] Hartline | Characterizing history independent data structures[END_REF].

Partitioning the Leaf Level. We store the leaf level compactly to support I/O-efficient range queries. The leaf arrays at the leaf level are packed into a leaf node. Formally, a leaf node B is a set of contiguous leaf arrays starting at some element x that has been promoted twice, that is, level (x) ≥ 2.

We store the leaf arrays history independently (see Section 2.1), with the following modification: even when a leaf array has n elements with n ≤ B γ elements, we maintain its size n s ≥ B γ . We call the extra n s -n array slots gaps. This modification retains history independence. INVARIANT 16. Let n be the number of elements in a leaf array of total size n s then:

• If n ≤ B γ , then n s is uniform in [B γ , 2B γ -1]. • If n ≥ B γ , then n s is uniform in [n, 2n -1].
Searches, Insertions, and Deletions. Search is implemented exactly as in a standard skip list: for an element y, start at the top list S h , and scan right till a value x > y is reached, in which case, descend a level down and continue till y is found or shown not to exist.

To insert or delete an element y, search for the leaf array where y belongs and insert or delete it. This involves shifting elements in the leaf array and causes an array resize with probability O(1/B γ ) by Invariant 16. If a resize occurs, rebuild the entire leaf node containing the array.

When inserting y, determine level (y) = by tossing a biased coin with probability of heads p. At levels 1 ≤ i < , y starts an array, splitting the existing array into two. If ≥ 2, y starts a leaf node, splitting the existing leaf node into two.

When deleting y, at levels 1 ≤ i < , merge the leaf array that y started with its predecessor. If ≥ 2 then merge the leaf node that y started with its predecessor.

History Independence of External-Memory Skip List

The history independence of our external-memory skip list follows immediately from the following facts:

• level (x) for each element x is generated randomly,

• the elements within an array appear in sorted order,

• the size of each array is chosen history-independently (by Invariant 16 for leaf arrays and [START_REF] Hartline | Characterizing history independent data structures[END_REF] for non-leaf arrays), • within a leaf node, the leaf arrays are packed contiguously in sorted order, and, • each array is allocated in blocks of size Θ(B) historyindependently [START_REF] Naor | Anti-persistence: history independent data structures[END_REF].

Performance Analysis

We bound the height of the external-memory skip list. The proof is similar to standard skip lists.

LEMMA 17. An external-memory skip list with promotion probability p has height h = O(log 1/p N ) whp.

PROOF. For any element x, the probability that its level is more than O(log 1/p N ) is given by: Pr[level (x) ≥ c log 1/p N ] ≤ p c log 1/p N = 1/N c .

Applying the union bound we get, Pr[∀x, level (x) ≥ c log 1/p N ] ≤ N (1/N c ) = 1/N c-1 .

Thus, the height of our external-memory skip list with p = 1/B γ is O(log B N ).

Search. To analyze searches, we bound the size of the arrays and leaf nodes.

An array contains elements between two consecutive promoted elements. Thus, the size of an array is bounded by the length of the longest sequence of tails, when flipping a biased coin with Pr[head] = 1/B γ , which is O(B γ log N ).

LEMMA 18. The number of I/Os required to perform a search is O(log B N ) with high probability.

PROOF. Similar to the backward analysis in standard skip lists [START_REF] Pugh | Skip lists: a probabilistic alternative to balanced trees[END_REF], examine the search path from bottom up starting at the leaf level. Each element visited by the path was either promoted and the search path came from the top, or was not promoted and the search path came from the left. The number of down moves is bounded by the height h = c log B N (Lemma 17). At each level, the search path traverses at most two arrays.

The total length of the arrays touched by the search path is bounded by the number of coin flips required to obtain c log B N heads, where Pr

CONCLUSION

We show that adding history independence to some externalmemory data structures can come at low cost. We focus on history-independent indexing structures, alternatives to the traditional B-tree, the primary indexing structure used in databases. We give HI PMAs and cache-oblivious B-trees with the same asymptotic time and space bounds as their non-HI counterparts. We give a HI skip list that performs even better than the non-HI B-skip list because the bounds are given with high probability rather than in expectation.

  I/Os with high probability, and can perform a range query for k elements in O(1 + k/B) I/Os. When B = Ω(log N log log N ) (reasonable on today's systems), then log 2 N B = O(log B N ), so inserts and deletes in our PMA have the same I/O complexity as in a B-tree.

Figure 1 :

 1 Figure1: Illustration of our PMA showing the subdivisions of elements into ranges. In each range, the balance element is framed and the candidate set is hatched. The actual array is represented in the bottom, where occupied slots are shaded. The candidate-set size at any given level does not depend on the range. The rank of each balance element is stored in a separate tree.

LEMMA 10 .

 10 Rebuilding a range R containing |R| slots takes O(|R|) RAM operations and O(|R|/B + 1) I/Os. PROOF. The algorithm first recursively chooses the balance elements for all ranges contained in this range R and updates them in the rank tree; this takes O(|R|) time and O(|R|/B + log B |R| + 1) = O(|R|/B + 1) I/Os. Then, all elements in R are gathered, and inserted into the appropriate leaf range using a sequence of linear scans.

Figure 2 :

 2 Figure 2: Experimental results of runtime for random inserts on normal and history-independent PMAs.

  insert or delete items with O((log 2 N )/B + log B N ) amortized I/Os with high probability, • use O(N ) space, and • answer range queries containing k elements in O(log B N + k/B) I/Os. When B = Ω(log N log log N ), which is reasonable on today's systems, log 2 N B + log B N = O(log B N ), so that our history-independent cache-oblivious B-tree matches the I/O complexity of a standard B-tree.

Figure 3 :

 3 Figure 3: Illustration of a search path for element key 18 in the external skip list (B = 3 and p = 1/2).

  [head] = 1/B γ . We need O(B γ log N ) coin flips whp.Thus, the number of I/Os during the search at nonleaf levels is O(log N/B 1-γ + log B N ) = O(log B N ) whp, since γ ≤ 1 -log log B/ log B. At the leaf level, the search scans one leaf array, which costsO(B γ log N/B) = O(log B N ).Insert. To bound the insert cost, we bound the cost of rebuilding a leaf node. The size of a leaf node is the number of elements stored in it plus the number of gaps.The number of elements in a leaf node is bounded by the length of the longest sequence of tails in N coin flips with Pr[head] = p 2 = 1/B 2γ , which is O(B 2γ log N ) whp.The number of gaps between any k consecutive leaf elements can be shown by a Chernoff bound argument to be O(k + B γ log N ). Thus, the size of a leaf node is O(B 2γ log N ) whp. Rebuilding it costs O(B 2γ log N/B) = O(B ε log N ) I/Os. LEMMA 19. The cost of performing an insert or delete operation is amortized O(log B N ) I/Os whp, with a worst case cost of O(B ε log N ) I/Os whp. PROOF. When an element y is inserted or deleted, the splits and merges at levels 1 ≤ i < level (y) are dominated by the search cost of O(log B N ). The cost of inserting in a leaf array is dominated by the cost of rebuilding the leaf node: O(B ε log N ) I/Os whp. The rebuild occurs with probability O(1/B γ ). The amortized I/O cost is then O(B 2γ-1 log N/B γ ) = O(log N/B 1-γ ) = O(log B N ) in expectation and whp with respect to the number of operations, since γ ≤ 1 -log log B/ log B. Range Query. To analyze a range query on a range of size k, we bound the number of leaf nodes across which the k elements are spread. That is, we bound the number of heads obtained on k biased coin flips with Pr[head] = 1/B 2γ . LEMMA 20. The number of leaf nodes across which k consecutive leaf elements are stored is O( 1 ε log B N + k/B) with high probability. LEMMA 21. A range query returning k elements costs O( 1 ε log B N + k/B) I/Os with high probability. PROOF. We break the analysis into several cases depending on the source of the cost. • If the k consecutive elements fit in a single leaf node and there are no gaps, then the size of each such leaf array is O(B γ log N ) whp. Thus, O(B γ log N/B + k/B) = O(log B N + k/B) I/Os suffice. • If the k consecutive elements span across arrays with gaps. The sum of sizes of the gaps between these elements is O(k + B γ log N ). Thus, a range query takes O(k/B + B γ log N/B) = O(log B N + k/B) I/Os. • If the k consecutive elements span several leaf nodes, by Lemma 20 they span O(k/B + 1 ε log B N ) leaf nodes. Every time the range query scan crosses a leaf node boundary, we incur an I/O to bring in the next leaf node, which requires O(k/B + 1 ε log B N ) I/Os. Thus, overall a range query scanning k consecutive elements takes O( 1 ε log B N + k/B). Space. Finally, we bound the space used. LEMMA 22. The external skip list on N elements requires Θ(N ) space with high probability. PROOF. The non leaf levels of the external skip list store Θ(N ) elements with only constant factor space. At the leaf level, the number of gaps between N elements is O(N + B γ log N ) = Θ(N ) whp. Lemmas 18, 19, 21, and 22 prove Theorem 3.

A cache-oblivious[START_REF] Frigo | Cache-oblivious algorithms[END_REF][START_REF] Frigo | Cache-oblivious algorithms[END_REF][START_REF] Prokop | Cache oblivious algorithms[END_REF] algorithm or data structure is memory-hierarchy universal, in that it has no memory-hierarchyspecific parameterization (see Section 1.1).

This scanning bound is a further requirement on how the elements are distributed. Beyond the O(N ) overall space limitation, only O(1) gaps can separate two consecutive elements.

Here it is assumed the contents of the dynamic array are stored (internally) in a history independent manner-thus the size of the array should not depend on the history of inserts and deletes.

A data structure is reversible if the state-transition graph is strongly connected[START_REF] Hartline | Characterizing history independent data structures[END_REF], which is true of all structures in this paper and most structures that support deletes.

When N ≤

[START_REF] Willard | Maintaining dense sequential files in a dynamic environment[END_REF], no such c1 exists. For such small N , we use a dynamic array instead.

Acknowledgments

This research was supported in part by NSF grants CCF 1114809, CCF 1217708, IIS 1247726, IIS 1251137, CNS 1408695, and CCF 1439084, and by the Laboratory Directed Research and Development program at Sandia National Laboratories, a multi-program laboratory managed and operated by Sandia Corporation, a wholly owned subsidiary of Lockheed Martin Corporation, for the U.S. Department of Energy's National Nuclear Security Administration under contract DE-AC04-94AL85000.