{'fraction_non_alphanumeric': 0.04004025210529103, 'fraction_numerical': 0.001800752078809385, 'mean_word_length': 4.211703008556445, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Available Stabilizing Heaps

This paper describes a heap construction that supports insert and delete operations in arbitrary (possibly illegitimate) states. After any sequence of at most O(m) heap operations, the heap state is guarantee to be legitimate, where m is the initial number of items in the heap. The response from each operation is consistent with its effect on the data structure, even for illegitimate states. The time complexity of each operation is O(lg K) where K is the capacity of the data structure; when the heap's state is legitimate the time complexity is O(lg n) for n equal to the number items in the heap.


Introduction
Increased visibility of systems emphasizes the theme of system availability. When availability is not important, systems may handle failures by stopping normal system activity and restoring damaged data from a recent backup copy. But stopping and restoring from a backup interferes with system availability, and in many instances it is preferable to let system services continue, even if the behavior of the services show temporary inconsistencies. Bookkeeping is intrinsic to system implementation, so data structures are found at the core of system programs. The objective of system availability motivates research of data structures with availability properties.
(Self-) stabilization is the paradigm usually associated with recovery from transient faults of unlimited scope [3]. Stabilization is traditionally associated with a distributed system, where each process can perpetually check and repair its variables. Our work departs from this traditional setting: we investigate a sequential, non-distributed data structure, supposing that the data structure is managed only by standard methods. We further suppose that each method invocation starts cleanly (with no transient damage to internal or control variables of that invocation), which resembles other work on fault tolerance [4,7,5]. The heap proposed here also constrains operation behavior during the period of convergence to a legitimate state -an issue not usually addressed by stabilization research (papers [2,8,6] are the exception).

Stabilizing Heap Construction
The data structure presented below is a variant of the standard binary heap [1] with a maximum capacity of K items. Two operations are defined for the heap, insert(p), which inserts value p into the heap, and deleteMin( ), which returns and removes an item of least value from the heap. We say that an insert(p) succeeds if it inserts item p into the heap and fails otherwise. The response to an insert(p) invocation indicates success or failure by returning "ack" for success and "heap full" for failure. Similarly, a deleteMin( ) succeeds if it returns an item and fails by returning a "heap empty" indication.
The heap construction described here is based on a binary, balanced tree of K nodes, rooted at a node named root, and denoted by A. Each node x in tree A has two associated constants x.left and x.right, which refer respectively to the left and right child of x in A. The symbol λ denotes the absence a child: x.left = λ (x.right = λ) indicates that x has no left (right) child in A. We suppose that x.left and x.right cannot be corrupted by a transient fault. (A conventional heap implementation by an array [1] satisfies this assumption, since there is a static mapping between parent and child.) Each node x has three variable fields, x.val, x.height, and x.nextslot used for storage and management of heap items in the tree.
The field x.val may contain a heap item for node x. We use the symbol ∞, which is a value outside the domain of possible heap items, to indicate the absence of a heap item at a particular node. For convenience, let λ.val = ∞ and let y.val ≤ ∞ hold by definition for all y ∈ A. We define tree T A to be a truncation of tree A that includes only nodes in a path of non-∞ values. Formally, for any node x, let x ∈ T A iff x.val = ∞ and either x is root or the child, with respect to A, of some y satisfying y ∈ T A (the definition is The expression T A denotes the bag (multiset) given by {x.val | x ∈ T A }, and |T A | is the number of nodes in tree T A .
Implementation of a binary heap should satisfy the balance property and the heap property.
The balance property is that any heap of m items is contained in a tree T A with height O(lg m). The heap property holds at x ∈ T A iff x.val ≤ y.val for any y child of x. The data structure satisfies the heap property iff the heap property holds at every x, x ∈ T A .
Legitimate State. The fields of A's nodes determine whether or not the tree is in a legitimate state. The state of A is legitimate iff (i) for every x ∈ T A , the heap property holds; (ii) the balance property holds; (iii) for every x ∈ T A , x.height is the height of the subtree (in T A ) rooted at x; and (iv ) for every x ∈ T A , x.nextslot equals the minimum distance from x to a descendant y ∈ T A such that y has fewer children in T A than A, and if no such descendant Let findSlot(root) be a recursive procedure locating a minimum-depth node y in A such that y ∈ T A : if x has one child y in A such that y ∈ T A , then findSlot(x) returns y; if x has two children in A such that neither is in T A , then findSlot(x) returns an arbitrary child of x; and if x has two children in T A , findSlot(x) compares the nextslot fields of x's children and returns findSlot(y) for the child y that has a smaller nextslot field (if both children have equal nextslot fields, then y can be any child of x.) An invocation of findSlot(root) may fail to return an element y, and instead will return symbol λ, if no y ∈ T A can be located.
The implementation of insert(p) consists of assigning y := findSlot(root), and if y = λ, then insert(p) responds with a "heap full" indication; otherwise, the following sequence executes. First, the operation assigns y.val, y.height, y.nextslot := p, 0, t where t = 0 if y has a child in A and otherwise t = K. Second, z.val := ∞ is assigned for every child z of y in A. Third, the operation calls upHeapify(y). The upHeapify routine swaps values of items on a path from y to root, until each parent has a value at most that of its child in the path. As upHeapify traverses the path from leaf to root, it also enforces, for each item y on the path, y.height := 1 + max((y.left).height, (y.right).height) and y.nextslot := 1+min((y.left).nextslot, (y.right).nextslot) (with appropriate adjustments to these expressions for cases of single or no children).
The implementation of deleteMin( ) consists of y := deepLeaf(root), and if y = λ, saving root.val for the response, then assigning root.val := y.val and y.val := ∞, and then calling downHeapify(root). Along the path from y to root, the height and nextslot fields are also recomputed owing to the deletion of y. The downHeapify routine swaps values as needed, along some path from root to a leaf, so that the heap property is restored to T A .
Active Tree. If A is not in a legitimate state, it is still possible to consider the maximum fragment of A that enjoys the heap property. The active tree S A is defined recursively by: if root.val = ∞ then S A is empty, otherwise root ∈ S A ; and if x ∈ S A and y is a child of x (with respect to A) such that y.val = ∞ and y.val ≥ x.val, then y ∈ S A .
Operation Modifications for Stabilization. The definition of a legitimate state implies, for every x ∈ S A and y ∈ S A where y is a child of x in A, that the val field of y is ∞. In an illegitimate state, this condition need not hold, though S A is defined even for illegitimate states. Our first modification of operations (including internal routines such as deepLeaf and findSlot) is the following: whenever an item x ∈ S A is encountered, it is first examined to verify that every child y satisfies y.val ≥ x.val, and if this is not the case, then y.val := ∞ is immediately assigned. (The only exception to this modification are the heapify routines, which are expected to encounter value reversals along a particular path.) The result of this modification is that operations consider children and leaves with respect to S A rather than T A . Observe that if a sequence of heap operations could somehow encounter all the nodes of T A , then T A = S A would hold as a result. A second modification introduced below does this, enforcing a scan of sufficiently many nodes of T A over any sequence of heap operations so that T A = S A will hold. We call this modification "truncation" since it removes nodes from T A to enforce the heap property. The truncation modification is a convenience for our presentation -another possibility would be to treat y.val as equivalent to ∞ whenever y.val < x.val for x the parent of y, and adjusting the definition of legitimate state (and T A ) accordingly.
The following lemma considers an operation applied to A in an arbitrary (possibly illegitimate) state; for this lemma, T denotes S A prior to the operation and T ′ denotes S A after the operation. Proof: Although findSlot(root) does not guarantee to find an available position for an insert(p) operation for illegitimate A, if findSlot(root) does return r = λ, then from the logic of findSlot, r is a child of some node of T , and thus T ′ will contain p as a result of insert(p). For a deleteMin operation, deepLeaf(root) returns some leaf of T (not necessarily at greatest depth in T ) provided T is nonempty, so deleteMin returns root.val of T . The O(lg K) time bound is satisfied because any path from root to leaf in T has length at most lg K.

Lemma 1 An operation applied to
The accuracy of height and nextslot fields is critical for maintaining the balance condition and locating an available node for heap insertion. In an illegitimate state, these fields have arbitrary values. Although heap operations recompute height and nextslot fields, such recomputation is limited to paths selected by the operations. The second change we make to operations is to add calls to a new routine verify. Each application of verify works on three objectives: (1 ) to apply truncation along one path P from root to a leaf of S A , (2 ) to assign height and nextslot fields from leaf to root in P , and (3 ) to modify fields so that the next invocation of verify will select a path different from P . To support objective (3 ), we add a new binary field toggle, with domain {ℓ, r}, to every node. The path P chosen by verify is obtained by following toggle directions from root until a leaf of S A is reached. Our intent is that O(|S A |) successive invocations of verify will visit all nodes of the active tree. The first few lines of verify in Figure 1 assign x.toggle for the case of x having fewer than two children: in case x has only a single child, then x.toggle should be r or ℓ according to the location of its only child. In case x has no children, x.toggle is assigned ℓ. The setup for a new path occurs by call to nextPath(x), which only occurs when x is a leaf of the active tree.
The idea of nextPath(x) is to locate an ancestor w of x with w.toggle = ℓ and change w.toggle to r, thereby setting up the "next path" for verify to examine. The routine leftFringe ensures that whenever such a change of w.toggle from ℓ to r takes place, the toggle fields are such that the leftmost path of the subtree rooted at w.right will be selected for this "next path" of verify. All lines but the last of leftFringe consider degenerate cases (single or no children). Not shown in the figure is the swAncestor procedure: swAncestor(x) returns the nearest ancestor w of x such that w has two children in S A and w.toggle = ℓ; if no such ancestor w exists, then swAncestor(x) returns λ. Observe that if swAncestor does return λ, then nextPath(x) sets up the "next path" to be the leftmost path starting from root in S A . Proof: Let P denote the path of nodes examined via recursion for a given invocation of verify(root). Observe that leftFringe(root) is called within this invocation of verify iff P is the rightmost path within S A (otherwise swAncestor would return a non-λ value). By construction, leftFringe(x) for x = root sets up the leftmost path in S A to the right of P .
Let T x be a subtree of S A , rooted at x, with m leaves. If m successive verify invocations examine the leaves of T x , then (i), (iii) and (iv ) hold for the nodes of T x afterwards (this can be shown by induction on subtree height). Let S be a preorder listing of the leaves of S A ; S has at most ⌊(|S A | + 1)/2⌋ items since any binary tree of n items has at most (n + 1)/2 leaves. It is straightforward to show that any |S| successive invocations of verify(root) visit the leaves of S A in an order corresponding to some rotation of sequence S.
The remaining modification to standard heap operations consists of having each insert and deleteMin operation begin with "verify(root) ; balance(root)". A balance(root) invocation consists of deleting a leaf r found by deepLeaf(root) from the heap and then reinserting r into the heap. When all height and nextslot fields in the active tree have legitimate values, the effect of balance(root) is to move an item from a position of maximum depth to a position of minimum depth. Since these fields could be illegitimate, care must be taken in the implementation of balance so that deleted leaf r is, in any case, reinserted into the heap (perhaps by reversing the delete of r if reinsertion fails). To see why the balance(root) call is needed, consider an initial active tree with height k that has only one leaf. Without the balance(root) call, if only insert operations are applied to the heap, then O(2 k ) operations would be required to bring the tree into balance.  In the rest of this proof, we assume that properties (i), (iii) and (iv ) hold. For the sake of generality we suppose that A is only loosely balanced: assume there exist constants a and b so that for any t, 0 < t ≤ K, the minimum height h t taken over all subtrees of A with t nodes that contain node root satisfies h t ≤ a + b lg t. From this assumption, it follows that any subtree T of A rooted at root with height exceeding h t is nonoptimal; furthermore, it follows that there is some node w ∈ A not contained in T , that is a child of some node of T , so that w has depth at most h t .
We define gap(α) for any state α to be a variant function.
It is straightforward to show that once gap is zero, any subsequent operation application results in zero gap, and that zero gap implies balance. If the initial gap is some value g > 0, any new item inserted into the heap is placed at minimum depth, any deleteMin removes a node at maximum depth, so gap does not increase by the insert or delete operations.
Moreover, every operation invokes balance(root), which decreases positive gap by at least one, so within g = O(m) operations, property (ii) is established.

Availability and Stabilization
The previous section presents a heap construction that is stabilizing (Lemma 4) and also satisfies certain properties expected of operations even when the data structure's state is illegitimate (Lemma 1). Lemmas 1 and 4 depend on the definition of S A . Is there a characterization of availability and stabilization independent of implementation specifics such as S A ? Such a characterization could be adapted to specify availability and stabilization for general types and implementations of data structures.
Let H be an infinite history of operations on a heap, that is, H is a sequence of insert and deleteMin invocations and corresponding responses. We characterize a heap implementation in terms of properties of all possible operation histories, first for the case of an initially empty heap. Let t denote a point either before any operation or between operations in H. If t is before any operation, define C t = ∅, otherwise let C t = I t \ D t , where I t is the bag of items successfully inserted prior to point t, and D t is the bag of items returned by deleteMin operations prior to point t (recall that success or failure of an operation is judged by the response it returns). We call C t the heap content at point t. Heap operations satisfy the following constraints: (a) a deleteMin operation immediately following any point t fails iff C t = ∅, and otherwise returns min(C t ); (b) an insert operation immediately following any point t fails iff |C t | = K, and otherwise returns "ack"; (c) the running time of any operation immediately following t is O(lg |C t |). From (a)-(c) one can show the usual heap properties, for instance, no deleteMin returns an item not previously inserted.
The above characterization of heap behavior by history depends on C t = ∅ for the initial point t. Availability is a relaxation of this characterization to allow arbitrary initial heap content.
Let P denote a history fragment starting from an initially empty heap, that consists of at (but is allowed to fail even if |C t | = K). The construction of Section 2 satisfies availability, as shown by Lemma 1, by choosing P to be a sequence of insert operations for the items of the active tree at the initial state. The simplest heap implementation satisfying availability is one that returns a failing response to every operation (P is empty and the heap content is continuously empty in this case).
Stabilization is also a weakening of (a)-(c). Let H t denote the suffix of history H following point t. A heap implementation is stabilizing if, for each history H of operations, there exists P (a history fragment of successful insert operations) and a point t such that (a)-(c) hold for P •H t . We call the history prefix C satisfying H = C •H t the convergence period of H. The construction of Section 2 is stabilizing by choosing P to contain insert operations for the active tree at some point t that exists by Lemma 4. The definition of stabilization permits operations to arbitrarily succeed or fail during the convergence period, and a deleteMin operation could return a value unrelated to heap content within the convergence period. A plausible stabilizing heap implementation is one that resets the heap content to be empty whenever some inconsistency is detected during the processing of an operation (resetting the heap amounts to establishing a legitimate "initial" state for subsequent operations).

Discussion
The heap construction presented here satisfies desired availability properties: success or failure in an operation response is a reliable indication of the operation's result on the data structure. We have not addressed the issue of relating heap damage to the extent of a fault -if a fault somehow sets root.val = ∞ then the entire heap contents are lost by our construction. Our intent is to separate concerns by first developing a stabilizing heap, and then later adding logic for limited cases of corrupted items. This is a topic for future work.