The Setting
A recursive scheduling step must identify the high jobs in its child window, meaning the jobs whose priority is at least the chosen threshold, and retain their priority order. The step may keep the direction of the current list or switch direction before restricting the list to the child.
Let be a finite job set of size , with precedence relation and natural-number rank . A layout is a bijection from to the positions , read in consecutive triples.✦ For boundary slots and , the slot assignment of and its open window are given by (1). A full layout is a layout on jobs that respects precedence, meaning requires .✦ (1)
A boundary of a full layout on is a left endpoint, a right endpoint, or a triple of cardinality three.✦ Its time is respectively , , or a slot between and whose jobs are exactly .✦ For an actual boundary , the predecessor and successor cones and their weak versions are defined by (2). At the left endpoint, the predecessor cones are empty and the successor cones are ; at the right endpoint these conventions are reversed. (2)
A boundary at slot separates a window by a cutoff when the conditions in (3) hold. (3)✦
Lists and Structural Certificates
An atomic family on is an assignment of subsets of to atoms. A Boolean structural formula over an atomic family on is a signed atom or a conjunction or disjunction of formulas; its interpretation uses complement in , intersection, and union. The leaf count of a Boolean structural formula is one for a signed atom and adds across either binary operation.✦ A description with allowance of a subset is a Boolean structural formula with at most leaves whose interpretation is .✦ Atomic predicate expressiveness means that , the empty set, every rank upper tail, every boundary cone in (2), and every job triple each have a description with one leaf.✦ The rank upper tail is the set .✦
An indexed global set family consists of a finite set of natural-number indices and subsets .✦ Its membership indices, last membership index, global entry union, and numeric priority key at scale are given by (4), with maximum zero for an empty membership set. (4) The lexicographic list priority on is the relation in which means that precedes lexicographically.✦ The injection entries are disjoint in if distinct listed entries with indices at least two have disjoint intersections with .✦ A global upset of the job set is a subset of containing every successor of each of its jobs✦; a list has upward-closed entries if every listed entry is a global upset.✦
For an indexed global set family , rank , index , and rank threshold , the suffix is the indexed global set family obtained by discarding listed entries before , restricting the entry at to , and retaining later entries.✦ Appending a set places it at a new final index.✦ For subsets of , the two-set list is the indexed global set family with indices and entries .✦ Pruning retains exactly the indices whose entries meet , leaving their global entries unchanged.✦
For subsets of , a scale , and a threshold , let and be the unchanged-direction and switched lists in (5). Write for the unchanged-direction priority specified by , and for the direction-change priority specified by . The priority cut of a natural-number priority on at is the job set .✦ (5)
A rank-threshold run for on consists of bases , thresholds , and a distinguished second set . Every listed entry is . The base has allowance ; each listed nonzero base has allowance ; has allowance and . Coverage requires . If zero is listed, every job of requires index one to be listed and belongs to .
The exchange of jobs in a layout is the layout in which and trade positions and every other job keeps its position.✦
The past boundary invariant at requires every job in scheduled at or before to belong to .✦ The forbidden exchange invariant on at concerns every precedence-respecting layout that agrees with outside . If , places at slot , and , exchanging the positions of and in must violate precedence.✦
A reverse induction seed at for is a downward closed set with allowance that contains and whose jobs all have time strictly less than .✦ A node structural certificate for consists of a full layout, left and right boundaries at identifying , and a list with a rank-threshold run on . Its entries and second set are upward-closed, its injection entries are disjoint in , and it has at most five indices. Its confinement conditions are (6); it satisfies the past and forbidden exchange invariants at the left boundary, has allowance , and it has a reverse induction seed at the right boundary. Write for the collection of these certificates. (6)
An edge structural certificate for the full layout and parent consists of boundaries at , with actual and , together with cutoffs . The final cutoff has allowance ; separates by , and separate by . The cutoff satisfies . Its list has a rank-threshold run on , upward-closed entries and second set, disjoint injection entries in , and labels . It satisfies the past invariant at and the forbidden exchange invariant on the child at that boundary. A global cutoff of allowance and a downward-closed extension of allowance each agree with inside .
The Claim
Theorem 1. Let be an indexed global set family, let , and let the updated lists and side priorities be those of (5).
For unchanged-direction qualification, suppose , every rank is less than , , , and . The qualification identity is (7). (7)✦
Suppose every rank is less than and in the unchanged-direction case. For , the order agreement is (8). (8)✦
For switched qualification, suppose and . The qualification identity is (9). (9)✦
Assume every rank is less than in the switched-direction case. For all jobs , the order agreement is (10). (10)✦
For every indexed global set family and job set , pruning satisfies (11). (11)✦
Let be an edge structural certificate with child . Suppose precedence is transitive and has atomic predicate expressiveness for . The child construction, denoted , yields the certificate in (12). (12)✦
In the paper, the result reads: for either update, with its side priority cut and, in the switched case, an upset containing and containing no job at or before , the qualifier union on before pruning is exactly and its key order on these high jobs agrees with the side priority; after pruning it selects exactly and satisfies the child’s first invariant.
What Is Checked
The list claims concern indexed global set families and natural-number priorities; the child construction concerns edge structural certificates under transitive precedence and atomic predicate expressiveness. For , pruning a rank-threshold run on gives a rank-threshold run on with the same ranks and atomic family.✦