WorksComputer Science
Quantifying the Advantage of Coarser DPOR
Abstract
Dynamic partial-order reduction (DPOR) has emerged as a promising approach to addressing interleaving explosion in bounded model checking of concurrent programs. Given an equivalence relation on interleavings, the model checker explores a program's executions while minimizing repeated visits to the same class; optimal model checkers avoid such repetition altogether. A coarser equivalence promises faster exploration by reducing the number of classes. This has motivated alternatives to Mazurkiewicz's trace equivalence such as reads-from and reads-value-from equivalence. This promise, however, does not always materialize in practice: while a coarser equivalence can yield exponentially fewer classes on some families of programs, it may offer little or no reduction for the program at hand. We show how to quantify the advantage of coarser equivalences for individual programs. We focus on the problem of counting the reads-from (RF) equivalence classes induced by a given program, as well as the problem of computing the ratio of RF to Mazurkiewicz class counts under sequential consistency. We show that both problems are -hard and that the reduction ratio remains hard to approximate accurately under standard complexity assumptions. Guided by these limits, we present CoEst, a sampling-based algorithm for estimating both the RF count and its ratio to the Mazurkiewicz count. For a fixed number of threads, each trial runs in polynomial time and yields unbiased count estimates. As the number of independent trials grows, the count and ratio estimates converge almost surely to their true values. Our algorithm can provide statistical evidence for deciding whether Mazurkiewicz or RF model checking is likely to be faster for a given program. In experiments across 34 benchmark configurations, our method selects the faster checker in 99.4% of runs using a one-minute estimation budget.
Introduction
When writing concurrent programs, developers must reason about all possible interleavings of operations from different threads. This makes concurrent software especially difficult to get right. Subtle concurrency errors routinely find their way into deployed software such as libraries that implement concurrent data structures and synchronization mechanisms. Worse still, these errors are often difficult to reproduce and debug. Automated tools like (bounded) model checkers offer a first line of defense against concurrency errors by systematically exploring program executions, say upto a bounded length, to find violations of correctness properties.
The number of possible interleavings of a program can unfortunately grow exponentially with program size, making exhaustive exploration prohibitively expensive. In response, modern model checkers employ dynamic partial-order reduction (DPOR) [14]. In essence, DPOR-based model checkers group executions into equivalence classes and explore representative executions from each class. This reduces the state space by avoiding redundant exploration. Model checkers such as Nidhugg [1] and GenMC [24] (using TruSt [22]) additionally support optimal exploration, visiting exactly one representative per equivalence class.
The choice of equivalence relation determines how much DPOR can reduce exploration. Classical DPOR uses Mazurkiewicz equivalence, which groups executions that differ only in the order of independent operations. To reduce exploration further, researchers have developed coarser equivalences that merge more executions into each class. Reads-from (RF) equivalence, for example,
Authors’ contact information: Minjian Zhang, [email protected]; Rupak Majumdar, [email protected]; Umang Mathur, [email protected]; C.-H. Luke Ong, [email protected]. groups executions with the same events and read sources, even when they order conflicting writes differently. Under sequential consistency, this can leave exponentially fewer classes to explore [1, 7]. More broadly, researchers have proposed coarser equivalences that can yield exponentially fewer classes than earlier approaches [2, 3, 8, 11]. But does this theoretical advantage translate into faster model checking? This is the central question we seek to answer in this paper, while focusing on Mazurkiewicz and RF equivalence, under the sequential consistency memory model.
The answer is not straightforward. First, the exponential advantage may not show up in all programs. Consider, for example, the two programs and in Figure 1. has one RF class but Mazurkiewicz classes. , on the other hand, has classes under both equivalences. Second, even for programs for which coarsening offers an advantage in terms of the number of classes, a model checker may still perform more work when generating representatives of the coarser classes and, in turn, may spend overall more time despite actually exploring fewer classes. In this paper, we take a quantitative view of this tradeoff and ask if we can estimate the advantage of a coarser equivalence for a given program before completing its exploration. Such estimates would help us choose which model checker to run. For a given program, suppose exploring an RF class costs, on average, times as much as exploring a Mazurkiewicz class. Let denote the ratio of the number of RF classes to the number of Mazurkiewicz classes. The total exploration time for RF is then approximately times that for Mazurkiewicz, so RF is expected to be faster when . We therefore ask: can we estimate without completing the exploration?

Figure 1. Each thread executes the shown code once. (a) Unobserved writes: Mazurkiewicz classes, one RF class. (b) List insertion: classes under both equivalences. Nodes are distinct and preallocated; the mutex is abstract and blocking. Counts include only the displayed data accesses.
The counting complexity landscape. We first study the problem from a complexity-theoretic perspective. We begin with some background on the complexity of counting equivalence classes. Counting Mazurkiewicz classes was recently shown to be complete for the class #P [5].1 In this work, we study two concrete problems:
Problem 1 (Counting RF classes.) Given a bounded SC program , compute , the number of RF-equivalence classes of its maximal executions.
Problem 2 (Computing the reduction ratio). Given such a program , compute
where counts its Mazurkiewicz classes.
We show that both problems above are harder than the problem of counting Mazurkiewicz classes, and thus also #P-hard. When the number of threads is part of the input, we further show that RF counting does not belong to #P unless NP SPP.2 Under the assumption that this inclusion does not hold, coarsening can therefore move counting outside #P, despite leaving fewer classes.
Given this evidence of intractability of exact computation, we next consider a natural question: can we efficiently approximate or to a prescribed relative error, with high probability? We first remark that, even for Mazurkiewicz counting, such a guarantee is impossible in polynomial time (unless NP = RP)2 [5]. Motivated by this limitation, in [5], Balasubramanian et al. pursued a weaker goal: constructing a polynomial-time unbiased estimator for .3 Their result raises the question: can we obtain the same guarantee for RF counting, or estimate the reduction ratio directly? Unfortunately, we show that neither quantity admits a polynomial-time unbiased estimator when the number of threads is part of the input, assuming .2 We also show that admits no fully polynomial randomized approximation scheme (FPRAS) unless NP = RP, even for loop-free programs with two threads and Boolean shared variables.2 On a positive note, we show that when we fix the number of threads (i.e., treat it as a constant), then RF counting belongs to #P and therefore admits an unbiased estimator with polynomial time per trial.
A practical estimation algorithm. Despite these worst-case barriers, we propose a practical algorithm, CoEst (for “Coarsening Estimator”), for estimating and . CoEst is a randomized algorithm, and each trial produces unbiased estimates of and . It guarantees that (1) each trial runs in polynomial time when the number of threads is fixed, and (2) it is a strongly consistent estimator of , i.e., the ratio of the average RF and Mazurkiewicz count estimates converges almost surely to as the number of independent trials grows. For any finite number of trials, we also bound the probability that the relative error exceeds a given tolerance, in terms of the true counts and variances.
At a high level, borrowing insights from prior work on Mazurkiewicz counting [5] central to making estimation practical, CoEst also works atop the optimal model checker TruST (with Mazurkiewicz equivalence based DPOR) and uses Knuth’s estimator [20] to sample leaves from its exploration tree. To adapt this approach to RF counting, we need to avoid overcounting; several Mazurkiewicz classes may belong to the same RF class. We do this by fixing, a priori, exactly one canonical Mazurkiewicz representative per RF class. We develop a procedure, IsCanonical, that checks whether a given execution graph is this representative. When sampling, we assign a leaf weight of one if it represents a canonical maximal execution, and zero otherwise. Using these modified weights in Knuth’s estimator gives an unbiased RF-count estimate. Alongside, we also maintain the original Mazurkiewicz contributions and use the two accumulated estimates to compute the reduction ratio.
Finally, we show how we can use CoEst’s samples to help choose between RF and Mazurkiewicz model checkers. Recall that RF exploration is expected to be faster when . We use a statistical test to assess whether the samples provide sufficient evidence that lies below or above this threshold. The test uses a normal approximation, with an asymptotic significance guarantee. When the evidence is insufficient, it reports an inconclusive result.
Empirical Evaluation. We implement CoEst in GenMC and evaluate whether short estimation runs help select the faster checker and whether the savings outweigh the cost of making this choice. Our benchmarks include concurrent data structures, synchronization algorithms, a simplified device-driver model, and synthetic programs.
We use off-the-shelf model checkers implementing Mazurkiewicz-based and RF-based DPOR. We run each checker for up to one minute to measure its exploration rate, obtaining an estimate of the relative per-class cost that we combine with CoEst’s estimate of . With a one-minute estimation budget, population budget , and ten seeds per configuration, we choose the faster checker in 338 of 340 decisions (99.4%) across 34 configurations. On the 25 configurations where neither pilot finishes, the reconstructed total cost, including both pilots and estimation, is 43.9% lower than ideal round robin and only 12.2% above an oracle that selects the faster checker at no selection cost.
We also evaluate the numerical accuracy of the ratio estimates on 29 configurations with exact reference ratios. After one minute of sampling with , the mean q-error across 27 configurations is 1.08, where a q-error of one indicates an exact estimate and two indicates a factor-of-two error. The remaining two configurations yield zero estimates in all or most runs because these runs sample no canonical representative. Although these ratios are underestimated in most runs, the estimates still lead to the faster checker in every run.
Organization. The rest of the paper is organized as follows. § 2 presents the preliminaries. § 3 motivates the reduction ratio and its use in checker selection. § 4 presents our complexity results. § 5 describes CoEst, its accuracy guarantees, and the statistical test for checker selection. § 6 presents our implementation and evaluation, and § 7 discusses related work. Additional proofs and variance analysis appear in the appendices.
Preliminaries
Concurrent Programs
We consider a bounded concurrent program whose threads communicate through reads and writes to shared locations, starting from a fixed initial state. Each thread’s local computation and control flow are deterministic once its read results are fixed. Under sequential consistency (SC), an execution interleaves the threads’ operations in program order, and each read observes the last preceding write to its location. We assume a finite upper bound on execution length.
Let and be the finite sets of threads and shared locations, and let be the value domain. A shared-memory event is a tuple , where is its thread, is its occurrence index within that thread, and is a label or , with and , recording the operation, location, and value. We write , , , , , and for these attributes. Each location has an initialization write that records its initial value; let .
We write for the set of executions of , represented by their shared-memory events. An execution is maximal if it cannot be extended by another program step, and denotes the set of maximal executions. Boundedness and determinism imply that these sets are finite.
Execution Graphs and Equivalences
We describe program semantics using execution graphs [22, 24]: the executions allowed under SC are represented by graphs that respect the threads’ code and satisfy the SC consistency condition.
Execution graphs. A full execution graph consists of:
a finite set of labeled events containing the initialization writes . No two thread events have the same thread identifier and occurrence index, and each thread’s events are indexed consecutively in program order, starting from 1. Let and denote the reads and writes in , respectively, with , and let denote the writes to location ;
a reads-from relation . Every read has exactly one source with , satisfying and ;
a coherence order , where each is a strict total order on with as its least element.
Here, full refers to the inclusion of both and ; a full graph may also represent an execution prefix. We write , , and for its components.
The program-order relation orders each thread’s events by their indices and places all initialization writes before all thread events:
The from-read relation
relates each read to every write to the same location that follows its source in coherence order, where denotes relational composition from left to right. A graph is compatible with ’s per-thread semantics if each thread’s labeled event sequence follows its code when its reads return the recorded values. Such a graph is SC-consistent if and only if
The reads-from (RF) graph of retains its labeled events and read sources while forgetting coherence:
Program order remains determined by the thread identifiers and occurrence indices in the event tuples. For an execution , let be the full graph it induces: reads-from records each read’s source, and coherence records the order of writes to each location in . The full graphs induced by maximal executions form the set
Equivalence and realizability. Two executions are Mazurkiewicz equivalent exactly when their full graphs coincide [5], and RF-equivalent exactly when their RF projections coincide [1, 7]. Thus, Mazurkiewicz equivalence refines RF equivalence: each RF class contains one or more Mazurkiewicz classes.
A candidate full or RF graph is realizable in , written , if some execution of induces it. For an RF graph compatible with the threads’ code, this amounts to asking whether it admits a coherence order satisfying (1). This RF consistency-checking problem is NP-complete in general [17].
Example 3 (Mazurkiewicz and RF equivalence). In Figure 2, the executions and have different coherence orders but the same read source. Their full graphs therefore represent different Mazurkiewicz classes with the same RF projection, as illustrated on the right. The program has three Mazurkiewicz classes and two RF classes.

Figure 2. A program (left) and two full execution graphs with a common RF projection (right). records the read value; transitive po and co edges are omitted.
Counting Problems
For , let denote the corresponding equivalence on executions. We write
for the number of classes of maximal executions of . Thus, counts distinct full execution graphs, while counts their distinct RF projections. With this notation, we restate the two problems introduced in § 1.
Problem 1 (Counting RF classes). Given a bounded SC program , compute , the number of RF-equivalence classes of its maximal executions.
Problem 2 (Computing the reduction ratio). Given such a program , compute
where counts its Mazurkiewicz classes.
Model Checking and Partial-Order Reduction
We focus on execution-based model checkers, which explore program behaviors by executing or interpreting the program and check properties such as the absence of local assertion violations. Dynamic partial-order reduction (DPOR) reduces this exploration by grouping equivalent executions and exploring representatives. Classical DPOR uses Mazurkiewicz equivalence to avoid redundant interleavings of independent operations. Under sequential consistency, RF-based DPOR uses the coarser reads-from equivalence, so one representative can cover several Mazurkiewicz classes [1, 7].
An exploration algorithm is optimal for a chosen equivalence if complete exploration visits exactly one representative of each class of maximal executions. TruSt, implemented in GenMC, provides optimal DPOR exploration for Mazurkiewicz equivalence under SC [22]. Nidhugg also supports optimal Mazurkiewicz exploration using a different algorithm from TruSt, while its RF-SC mode provides optimal exploration for RF equivalence [1].
GenMC and Nidhugg are stateless model checking tools: they avoid maintaining a global set of visited program states. Statelessness does not, however, imply a polynomial bound on exploration bookkeeping. TruSt additionally guarantees exploration space polynomial in the maximum execution length [22].
The chosen equivalence also affects the work needed to generate each representative. For a full execution graph with a fixed coherence order, SC consistency can be checked in polynomial time using the acyclicity condition in (1). For an RF graph, the coherence order is unspecified, and consistency requires finding a coherence completion satisfying that condition, an NP-complete problem in general [1, 17]. A coarser equivalence can therefore reduce the number of representatives while increasing the cost of generating them.
When is Coarser DPOR Better?
RF equivalence has motivated optimal model checkers that can explore substantially fewer executions than checkers based on Mazurkiewicz equivalence [1, 7]. Since RF equivalence is coarser, one RF class can contain many Mazurkiewicz classes. On some programs, this reduces the number of executions to explore by an exponential factor and leads to substantial performance improvements.
But does exploring fewer classes always make an RF checker faster? The answer is unfortunately no: RF checkers are not always the fastest choice. RF exploration repeatedly invokes consistency checks to determine whether candidate RF graphs can be realized under SC. This problem is NP-complete in general when the number of threads may grow [17]. Specialized procedures can nevertheless handle these checks efficiently in practice. For example, Abdulla et al. [1] report that the first two polynomial-time phases of their consistency procedure resolved every query in their evaluation, without invoking the expensive complete procedure.
RF exploration can nevertheless incur a higher cost per class. For example, on fib-bench(6), Abdulla et al. [1] report that Nidhugg/rfsc (based on RF DPOR) takes about 1.64 times as long as Nidhugg/optimal (based on Mazurkiewicz DPOR), although both explore the same number of executions. Our experiments also show substantial differences in verification time in both directions. On Treiber static (L3), the Mazurkiewicz checker is about 7.8 times as fast as the RF checker, whereas on Eratosthenes SC (N14, U16), the RF checker is about 16.4 times as fast (§ 6).
Whether this cost is worthwhile depends on how much RF equivalence reduces the execution space. Figure 1 illustrates two extremes. In Figure 1(a), each of threads writes to the same shared location, and no thread reads it. The write orders induce distinct Mazurkiewicz classes, but all have the same RF projection. RF exploration therefore replaces classes with one. In Figure 1(b), each thread inserts a node into a mutex-protected list. Each read of head identifies the preceding insertion, so the read sources determine the entire insertion order. Both equivalences have classes. Here, RF exploration obtains no reduction to compensate for any additional cost per class.
These examples raise the question that motivates our work: given a program, is the reduction offered by RF equivalence worth the cost of exploring it? Existing evaluations show programs on which RF exploration is beneficial, but we would like to answer this question before committing to a complete exploration. Doing so requires understanding two quantities: the relative cost of exploring a class, and the reduction in the number of classes to explore.
A general formal characterization of this overhead is difficult. Model checkers differ in their exploration algorithms and implementations. For example, both GenMC [24] and Nidhugg [1] support optimal exploration, but they use different exploration algorithms and can incur different costs per explored class. Moreover, SC consistency checking is NP-complete in general, and the cost of a consistency query can depend strongly on the input. In practice, however, we can summarize the relative exploration cost of the two model checkers on a given program by an average factor : exploring an RF class costs approximately times as much as exploring a Mazurkiewicz class.
This factor may be supplied by the user based on experience, or estimated from short pilot runs. Our experiments show that short pilots provide reasonably accurate estimates of this relative cost on the evaluated benchmarks (§ 6).
Knowing this cost alone does not tell us which checker will finish first. A short run tells us how fast a checker is exploring, but not how much it has to explore. An RF checker may visit fewer classes during the pilot because it spends more time on each class, yet finish earlier because its total number of classes is much smaller. We therefore also need to estimate the reduction offered by RF equivalence.
The second quantity, namely the reduction ratio, measures how much RF equivalence reduces the Mazurkiewicz execution space. It depends only on the program and the two equivalences, regardless of how the checkers are implemented. Computing this ratio is itself a natural mathematical problem, which we study by counting execution classes under the two equivalences. § 2.3 defines these counts formally in (2) and states the RF-counting and reduction-ratio problems (Problems 1 and 2). When , RF equivalence eliminates no classes; a small ratio indicates substantial reduction.
If exploring an RF class costs times as much as exploring a Mazurkiewicz class on average, then RF exploration takes approximately times as long as Mazurkiewicz exploration. We therefore predict RF exploration to be faster when
For example, if an RF class costs five times as much to explore, RF exploration must visit fewer than one fifth as many classes to compensate.
But how can we obtain this ratio without completing the exploration? We first study the complexity of computing and estimating it in § 4. These results guide the design of our estimation algorithms in § 5. We then evaluate these algorithms in § 6 and show how their ratio estimates, together with overhead estimates from short pilot runs, help us choose between RF and Mazurkiewicz checkers.
From Mazurkiewicz to RF Counting
A direct way to compute the reduction ratio is to count RF and Mazurkiewicz classes separately. For Mazurkiewicz counting, Balasubramanian et al. [5] show that exact counting of bounded concurrent programs4 is #P-complete and that the problem admits no fully polynomial randomized approximation scheme (FPRAS) unless RP = NP. Nevertheless, they obtain an unbiased estimator by sampling Mazurkiewicz traces: each trial runs in polynomial time and returns a value whose expectation equals the number of Mazurkiewicz classes.
We ask whether analogous guarantees are possible for RF equivalence. Although RF equivalence merges Mazurkiewicz classes and therefore leaves fewer classes to count, does this make the counting problem easier or harder? Can we construct an unbiased estimator with polynomial time per trial for the RF count, or estimate the reduction ratio directly with the same guarantee? If we allow a relative error and probability of failure, are there FPRAS for the ratio?
In this section, we answer these questions from a complexity-theoretic perspective. When the number of threads is part of the input, we show that, under the assumptions stated below, RF counting lies outside #P. The separation extends to unbiased estimation: unlike the Mazurkiewicz count, neither the RF count nor the reduction ratio admits an oracle-free unbiased estimator with polynomial time per trial. Thus, coarsening the equivalence can make counting computationally harder despite reducing the number of execution classes.
We begin with a brief review of some complexity classes.
The classes SPP and PP. Throughout this section, hardness and completeness for counting problems use polynomial-time Turing reductions: a reduction may query an oracle for the target problem and process its answers in polynomial time.
Our lower bounds also use two decision classes. A language belongs to SPP if there exist such that
The class PP consists of languages for which a polynomial-time probabilistic machine accepts with probability greater than exactly on inputs in the language.
The class SPP is low for PP: giving a PP machine an SPP oracle does not increase its computational power, so [13]. Consequently,
For our lower bounds on unbiased estimation, we assume . Whether this equality holds remains open at the time when this paper is written; see Fortnow and Grochow [15] for a discussion.
Exact counting. We first study the complexity of counting RF classes and computing the reduction ratio exactly. We show that both problems are -hard.
Theorem 4 (Appendix A). For bounded deterministic SC read/write programs with polynomially bounded execution length, value size, and per-operation simulation cost, counting RF-equivalence classes of maximal executions is -hard under polynomial-time Turing reductions. The numbers of threads, shared locations, and values may grow with the input.
Exact computation of the reduction ratio. Given that RF counting is hard, we now query if we can compute the reduction ratio efficiently without counting the two spaces separately? We show that exact computation of the ratio is also -hard, even for loop-free programs.
Proposition 5 (Appendix B). Exact computation of
is -hard under polynomial-time Turing reductions, even for loop-free deterministic SC read/write programs.
Separation from Mazurkiewicz counting. The results so far show that counting RF classes and computing the reduction ratio are at least as hard as Mazurkiewicz counting. We now take a further step and show that RF counting is likely harder by separating it from .
Theorem 6 (Appendix C). Counting RF-equivalence classes of maximal executions of bounded deterministic SC read/write programs does not belong to unless .
Unbiased estimation. For choosing a checker, however, exact values may not be necessary: perhaps approximation or estimation would suffice. Although exact RF counting is hard, can we construct an unbiased estimator whose per-trial running time is polynomial, as we can for Mazurkiewicz counting?
Recall that Mazurkiewicz counting admits an unbiased estimator with polynomial time per trial despite being -complete. Unfortunately, we show that RF counting admits no such estimator when the number of threads is part of the input, unless . The same impossibility holds for estimating the reduction ratio directly.
Formally, an unbiased estimator for a function is a probabilistic algorithm satisfying
for every input . We use the standard bit model: algorithms use fair random bits and output rational numbers whose signed numerators and positive denominators are explicitly represented in binary. An estimator is polynomial-time if every trial terminates within a fixed polynomial in the input size, regardless of its random choices. This representation permits exponentially large sampling weights with polynomially many bits; unbiasedness imposes no bound on their variance.
Theorem 7 (Appendix D). Assume that . Counting RF-equivalence classes of maximal executions of bounded deterministic SC read/write programs admits no oracle-free polynomial-time unbiased estimator.
A direct consequence is that estimating the reduction ratio directly cannot avoid the same barrier.
Corollary 8 (Appendix § 15). Assume that . The reduction ratio
admits no oracle-free polynomial-time unbiased estimator.
Given that polynomial-time unbiased estimation is out of reach, one may ask whether allowing relative error and a small probability of failure would help. We show that the ratio admits no FPRAS either, unless , even with only two threads.
Proposition 9 (Appendix § 19). Unless , there is no FPRAS for the reduction ratio , even for loop-free deterministic SC read/write programs with two threads and Boolean shared variables.
Canonical Sampling and Statistical Test
The previous section shows that RF counting and computing the reduction ratio are difficult and unlikely to admit even an unbiased estimator with polynomial time per trial when the number of threads is part of the input. But what if we are willing to accept a higher computational cost in ? A program may have only a few threads even when it has many shared locations and a large execution bound, making this a useful tradeoff to consider. Theoretically, we can indeed show that, for every fixed , RF counting belongs to . Since every function admits a polynomial-time unbiased estimator, we can recover the same per-trial guarantee as for Mazurkiewicz counting when is fixed.
Fixing the number of threads does not, however, make exact counting or approximation easy. Even with only two threads, RF and Mazurkiewicz counting remain -complete, and computing the reduction ratio remains -hard. None of these problems admits an FPRAS unless . Thus, unbiased estimation remains a useful target, just as it is for Mazurkiewicz counting.
In this section, we first establish membership by constructing a canonicity checker that recognizes exactly one Mazurkiewicz representative of each RF class in polynomial time for fixed . Note that when is not fixed, this is a solver.
We then use this checker to construct our unbiased RF-count estimator. Each trial performs polynomial-time computation apart from one call to a witness-producing SC consistency checker, whose cost can grow rapidly with . Combining the RF and Mazurkiewicz estimates gives a strongly consistent estimator of the reduction ratio. Finally, we present a statistical test based on this ratio estimator to support checker selection by testing whether the ratio lies below or above a given threshold.
A canonical representation function. The key insight behind our algorithm is that SC consistency checking can be used to select a canonical representative for each RF class. The SC consistency procedure of Abdulla et al. [1] searches for an execution realizing a given RF graph. The write orders in this execution determine a compatible coherence order. By fixing a deterministic search policy that depends only on the RF graph, we can use the first completion found as its canonical representative.
Proposition 10 (Canonical completion: Appendix § 16). For every fixed number of threads , there is a deterministic polynomial-time function that, given an RF graph on at most threads, returns an SC-consistent full graph satisfying
or returns if no such completion exists.
With this function, we can count RF classes by guessing their RF graphs and checking whether they have a completion.
Proposition 11 (RF counting with a fixed thread bound: Appendix § 17). For every fixed , the RF-counting problem of § 4, restricted to programs with at most threads, belongs to #P. It therefore admits an unbiased estimator with polynomial time per trial.
Estimating the RF count and reduction ratio. The result above shows that, for every fixed , an unbiased RF-count estimator with polynomial time per trial must exist. This theoretical insight guides our algorithm design, but such an algorithm may still have such high variance that it fails to produce useful estimates within a reasonable time budget.
How should we sample to obtain useful estimates in practice? Balasubramanian et al. [5] address this question for Mazurkiewicz counting. Their approach is to use TruSt’s exploration tree as the sampling space. This tree is organized by the program’s semantics: its successful paths generate maximal execution graphs, with exactly one path for each Mazurkiewicz class. The branching choices along a sampled path determine its sampling probability, allowing the estimator to compute the corresponding weight during sampling.
Our idea is to build on this design. With a small modification using our canonicality checker, we can reuse these weighted execution samples to obtain an unbiased RF-count estimator. Let us now refer to the Mazurkiewicz estimator of Balasubramanian et al. [5] as T. Each trial of T samples a path through TruSt’s exploration tree in polynomial time.5 If the path reaches a maximal execution graph G, T returns , where and is the probability of sampling G. Otherwise, it returns . With this weighting, each Mazurkiewicz class contributes one in expectation.
A natural idea is to collect maximal execution samples from T, check which are canonical, and use the fraction of canonical samples to estimate . If the samples were uniform over maximal Mazurkiewicz classes, this would give an unbiased estimate: exactly one class per RF class passes the canonicality check. However, T does not sample uniformly, so the canonical-hit rate can differ from the reduction ratio.
Example 12. Consider again the program in Figure 2, which has three maximal Mazurkiewicz classes and two RF classes. The graphs and shown in the figure belong to the same RF class. The third graph, denoted by , has reading from and belongs to the other RF class. Suppose that the canonicality checker selects and as representatives, and that T samples , , and with probabilities , , and , respectively. The expected canonical-hit rate is then , whereas the reduction ratio is . Increasing the number of samples does not remove this bias.
Nor can we simply replace T with an efficient uniform sampler. The construction used to prove Proposition 15 also rules out polynomial-time uniform sampling of maximal Mazurkiewicz classes unless , even for two-thread programs.
However, we can account for the unequal sampling probabilities using the weights already returned by T. With these weights, each Mazurkiewicz class contributes one in expectation. For RF counting, we keep the weight only when the sampled graph is canonical. Exactly one Mazurkiewicz class then contributes to each RF class, giving an unbiased RF-count estimate.
As shown in Algorithm 1, our procedure PairedEstimation takes the sampled execution graph and its weight , and runs the canonicality checker on . It keeps the original weight as the Mazurkiewicz estimate , and sets the RF estimate to if is canonical and otherwise. Note, however, that we cannot take the ratio for each pair and then average these ratios. For , is simply one if the sample is canonical and zero otherwise, so this would give the same canonical-hit estimator discussed in the example above.
This procedure is implemented by CoEst (Coarsening Estimator) in Algorithm 1. It runs PairedEstimation independently times and returns the ratio of the accumulated RF and Mazurkiewicz contributions:
Proposition 13. For every program , the pair returned by PairedEstimation satisfies
Using independent trials, CoEst gives a strongly consistent estimate of the reduction ratio:
Example 14. Consider the same program and sampling probabilities as in Example 12. When is sampled, CoEst records . When is sampled, it records , since this graph is not canonical. When is sampled, it records . Thus,
Both count estimates are unbiased, and the ratio of their accumulated contributions converges almost surely to the true ratio .
A statistical test for checker selection. As discussed in § 3, let denote the average cost of exploring an RF class relative to a Mazurkiewicz class. We predict RF exploration to be faster when , and Mazurkiewicz exploration to be faster when .
We therefore ask whether our samples provide sufficient evidence for either conclusion. We use a standard -score test to assess whether the estimated ratio is sufficiently far from the
Algorithm 1 CoEst: canonical-rejection estimation
1: procedure PairedEstimation($P$)
2: \quad $(G,w) \leftarrow T(P)$
3: \quad if IsCanonical($G$) then
4: \qquad return $(w,w)$
5: \quad end if
6: \quad return $(w,0)$
7: end procedure
8: procedure CoEst($P,N$)
9: \quad $S_{\mathrm{Maz}} \leftarrow 0; S_{\mathrm{RF}} \leftarrow 0$
10: \quad for $i \leftarrow 1$ to $N$ do
11: \qquad $(X,Y) \leftarrow$ PairedEstimation($P$)
12: \qquad $S_{\mathrm{Maz}} \leftarrow S_{\mathrm{Maz}}+X; S_{\mathrm{RF}} \leftarrow S_{\mathrm{RF}}+Y$
13: \quad end for
14: \quad return $S_{\mathrm{RF}}/S_{\mathrm{Maz}}$
15: end procedure
threshold relative to its sampling uncertainty. If the evidence is insufficient, we report the result as inconclusive.
Fix before collecting the estimation samples. We collect a predetermined number of independent paired estimates and define
Then
Thus, testing whether is below or above amounts to testing whether the mean of is negative or positive.
Let and be the sample mean and sample standard deviation of these differences. We use two one-sided normal tests, each with asymptotic significance level 0.05. The test reports the RF direction when
and the Mazurkiewicz direction when
Otherwise, the result is inconclusive.
We also study finite-sample accuracy in Appendix § 20. Our bound accounts for two sources of error: substantial underestimation of the Mazurkiewicz count, and errors in the two count estimates that do not cancel when we take their ratio. Even inaccurate count estimates can give an accurate ratio when they err by similar proportions.
An alternative RF estimator. We end this section with a natural question: can we sample RF classes directly, instead of sampling Mazurkiewicz classes and rejecting non-canonical graphs? In principle, an RF exploration tree could support the same estimation approach: each sampled maximal RF graph would contribute its inverse sampling probability if the tree is also branch independent. TruSt/wb [22] offers a possible route to such an estimator. The original paper describes an RF variant of TruSt and sketches its adaptation to SC, but does not provide a corresponding correctness proof for the SC adaptation. Developing this adaptation into an estimator would require establishing its correctness and the properties needed for efficient sampling and out of the scope of this work.
Nidhugg/rfsc [1] also explores RF classes under SC, but its pending exploration choices are updated using information obtained from other branches. Unlike TruSt, it therefore does not directly support sampling a single path independently of the rest of the exploration. How to obtain an efficient estimator from this algorithm remains unclear.
Experimental Evaluation
In this section, we gauge CoEst to choose between RF and Mazurkiewicz checkers and ask whether this choice saves enough verification time to pay for the estimation and checker pilots. Each estimation run has a one-minute budget. We combine its ratio estimate with the exploration rates measured during the pilots. We first examine the accuracy of the estimates and the choices they produce. We then compare the total cost with two alternatives: (a) always using one checker and (b) running both in round robin. To understand the role of sampling weights and population size, we compare 3 population budgets with a baseline that uses the same samples without their weights.
Experimental Setup and Benchmarks
Implementation and platform. We used OpenAI’s Codex (GPT 6 Astra) and Anthropic’s Claude Code (Fable 5.2) to implement CoEst in GenMC 0.19.0. We compare GenMC in Mazurkiewicz mode with Nidhugg in RF-SC mode at revision 845a1463. The implementation is built with GCC 14.2.0 and LLVM 19.1.7 in RelWithDebInfo mode with -O2 optimization. Each measurement runs in its own aarch64 Linux Docker container with one CPU and 16 GiB of memory, on a shared Apple M3 Max host with 14 CPU cores and 36 GiB of memory.
Benchmarks. Our suite contains 34 configurations of bounded programs from 24 families, covering concurrent data structures, synchronization algorithms, a simplified device-driver model, and synthetic workloads. We draw or adapt programs from the GenMC and Nidhugg suites [16, 26], and include the optimistic-list algorithm of Herlihy et al. [19] and synthetic benchmarks. Table 1 lists the configurations, which vary thread counts, operation counts, data-structure sizes, and loop bounds.
Thirteen configurations have , each from a different family. We also include one configuration each of Write-only and Control-flow, with RF counts 1 and 531, respectively. For the remaining nine families, the reduction can change with instance size, so we include several sizes where possible. For example, the values are 0.020 and 0.011 on two sizes of Sigma, and 0.26 and 0.21 on two sizes of QU. We include three sizes each of Eratosthenes and Sigma, and two each of ApproxDS, Scull, RW-SC, Opt-lock, QU, and Race-parametric. We use only one size of Lamport: the next smaller instance has just 16 executions, while neither checker completes the next larger one within three hours.
Canonicality checking. We implement IsCanonical using GenMC’s consistency validator with deterministic backtracking over coherence orders and constraint propagation inspired by Abdullah et al. [1]. The search depends only on the input RF graph. We also implemented their polynomial-time procedure for fixed . Although it has a better worst-case bound, backtracking was slightly faster in our preliminary experiments, so we use it here.
Sampling protocol. Similar to Tèstor [5] CoEst uses the stochastic-enumeration [31] to reduce variance. The population budget limits the number of sampled paths advanced together within a trial. We evaluate ; with , each trial follows a single random path. We repeat trials for one minute, allowing the active trial to finish when the budget expires. Warmup made little difference in our preliminary runs, so we omit it from the reported experiments. Each completed trial returns paired contributions . After trials, we compute
For each configuration and population budget, we repeat the experiment with ten random seeds. Each run receives the full sampling budget and produces its own estimates and choice of checker. Across the 34 configurations, the median run completes about 60,000 trials with , 1,800 with , and 640 with .
Baseline: Canonical hit. We implement the generally biased estimator discussed in Example 12 as a baseline, which we call Canonical hit (CH). It uses exactly the same single-path samples as CoEst with , and returns the fraction of sampled normally terminating executions that are canonical. We compare CoEst with CH to see whether this bias hurts estimation accuracy in practice.
Blocked executions. A checker may encounter a failed assume during exploration, including one introduced by a spinloop transformation. Checkers such as GenMC and Nidhugg report these runs as blocked executions and exclude them from their normal-execution counts. Which blocked executions are explored depends on the checker’s program transformations, treatment of bounds, and exploration algorithm. For example, Awamoche [23] can avoid many blocked executions arising from await and confirmation-CAS loops. We count classes of normally terminating executions under the chosen equivalence. Blocked samples contribute zero to both the RF and Mazurkiewicz estimates.
Choosing Between RF and Mazurkiewicz Checkers
As discussed in § 3, the reduction in execution classes must offset the additional cost of exploring each RF class. We use two maintained, state-of-the-art DPOR model checkers: GenMC in Mazurkiewicz mode (Maz) and Nidhugg in RF-SC mode (RF). Choosing tools with different exploration algorithms and implementations lets us test whether our estimates of the reduction between equivalence relations can help select the faster checker across different DPOR implementations.
Predicting which checker will finish sooner. A short pilot tells us how quickly each checker explores; the ratio estimate tells us how much exploration RF can avoid. We run each checker for up to one minute to obtain rates and . We compute each pilot rate by dividing the checker’s reported normal-execution count by its running time.
These rates estimate the relative per-class cost as . The corresponding threshold is . We predict RF checker to be faster when and Mazurkiewicz otherwise.
Full checker runs and exact counts. We use the estimators to select the largest workload for which we expect at least one checker to finish within three hours. We then run each checker with a three-hour timeout to measure its verification time and determine which checker is faster.
To evaluate estimation accuracy, we obtain both exact counts using GenMC, so they follow the same bounded-program semantics as our estimator. We count canonical representatives rather than using Nidhugg’s RF count because the two tools can transform bounded programs differently. In particular, an execution that reaches a bound before terminating may be counted as complete by one tool and blocked by the other. Nidhugg’s reported RF count agrees with GenMC’s canonical
| Configuration | (s) | (s) | Canonical hit q-err. | Canonical hit correct | CoEst, q-err. | CoEst, correct | CoEst, q-err. | CoEst, correct | CoEst, q-err. | CoEst, correct | ||
| ApproxDS (N6, M4) | 0.0202 | 0.0961 | 476.72 | 93.95 | 4.86 | 0/10 | 1.45 | 10/10 | 1.23 | 10/10 | 1.10 | 10/10 |
| Barrier (L2) | 1 | 0.295 | 553.65 | 1322.15 | 1 | 10/10 | 1 | 10/10 | 1 | 10/10 | 1 | 10/10 |
| DQ (L3) | 1 | 0.423 | 827.05 | 1960.58 | 1 | 10/10 | 1 | 10/10 | 1 | 10/10 | 1 | 10/10 |
| Eratosthenes SC (N14, U16) | 0.00757 | 0.127 | 435.98 | 26.60 | 61.3 | 0/10 | 3.30 | 9/10 | 1.21 | 10/10 | 1.11 | 10/10 |
| Lamport (N3, U16) | 0.428 | 0.271 | 1.01 | 1.70 | 1.18 | 10/10 | 1.43 | 9/10 | 1.01 | 10/10 | 1.01 | 10/10 |
| MCS (N4, U8) | 1 | 0.245 | 3080.46 | (OOM) | 1 | 10/10 | 1 | 10/10 | 1 | 10/10 | 1 | 10/10 |
| MS queue (W3, RW1) | 1 | 0.470 | 6350.25 | 1 | 10/10 | 1 | 10/10 | 1 | 10/10 | 1 | 10/10 | |
| Mutex Musl (L1) | 1 | 0.471 | 149.23 | 249.23 | 1 | 10/10 | 1 | 10/10 | 1 | 10/10 | 1 | 10/10 |
| Optimistic list (L2) | 1 | 0.193 | 125.52 | 719.98 | 1 | 10/10 | 1 | 10/10 | 1 | 10/10 | 1 | 10/10 |
| QU (4,3,3) | 0.209 | 0.178 | 1596.26 | 1910.45 | 4.25 | 10/10 | 2.54 | 4/10 | 1.14 | 9/10 | 1.10 | 9/10 |
| RW-SC (N7) | 0.0103 | 0.178 | 680.81 | 41.81 | 2.57 | 10/10 | 2.27 | 10/10 | 1.65 | 10/10 | 1.47 | 10/10 |
| Scull (R3, W2) | 0.187 | 0.143 | 2090.16 | 2992.09 | 2.85 | 10/10 | 1.92 | 5/10 | 1.62 | 6/10 | 1.16 | 10/10 |
| Spinlock (N4, U6) | 1 | 0.316 | 3194.93 | 9332.99 | 1 | 10/10 | 1 | 10/10 | 1 | 10/10 | 1 | 10/10 |
| STC (P5, 2/2/2/2, U16) | 1 | 0.208 | 764.46 | 3705.85 | 1 | 10/10 | 1 | 10/10 | 1 | 10/10 | 1 | 10/10 |
| Ticketlock (L1) | 1 | 0.384 | 2734.27 | 7636.23 | 1 | 10/10 | 1 | 10/10 | 1 | 10/10 | 1 | 10/10 |
| Treiber dynamic (W4, RW1) | 1 | 0.480 | 2946.04 | 8215.90 | 1 | 10/10 | 1 | 10/10 | 1 | 10/10 | 1 | 10/10 |
| Treiber static (L3) | 1 | 0.147 | 353.01 | 2749.56 | 1 | 10/10 | 1 | 10/10 | 1 | 10/10 | 1 | 10/10 |
| TTAS | 1 | 0.351 | 64.80 | 170.55 | 1 | 10/10 | 1 | 10/10 | 1 | 10/10 | 1 | 10/10 |
| Write-only (N11) | 0.00233 | 1572.75 | 0.0102 | 10/10 | 10/10 | 10/10 | 10/10 | |||||
| TWA (N4, A4, U16) | 1 | 0.528 | 9883.11 | 1 | 10/10 | 1 | 10/10 | 1 | 10/10 | 1 | 10/10 | |
| ApproxDS (N7, M5) | – | 0.0890 | 2637.40 | – | 10/10 | – | 10/10 | – | 10/10 | – | 10/10 | |
| Eratosthenes SC (N13, U16) | 0.0148 | 0.134 | 124.76 | 14.24 | 30.1 | 0/10 | 1.71 | 10/10 | 1.07 | 10/10 | 1.10 | 10/10 |
| Scull (R2, W2) | 0.208 | 0.135 | 152.63 | 230.64 | 2.65 | 10/10 | 1.32 | 9/10 | 3.23 | 8/10 | 1.31 | 9/10 |
| RW-SC (N8) | – | 0.160 | 1026.85 | – | 10/10 | – | 10/10 | – | 10/10 | – | 10/10 | |
| Sigma (N9) | 0.0105 | 0.155 | 1422.42 | 97.57 | 4.65 | 10/10 | 1.05 | 10/10 | 1.04 | 10/10 | 1.04 | 10/10 |
| Opt-lock (N13) | 0.113 | 86.35 | 0.0766 | 7570 | 0/10 | 5.94 | 10/10 | 1.64 | 10/10 | 1.49 | 10/10 | |
| Control-flow (N9) | 0.160 | 8856.33 | 0.2057 | 10/10 | 10/10 | 10/10 | 10/10 | |||||
| Race-parametric (N7) | 0.153 | 0.0563 | 403.64 | 729.21 | 3.74 | 10/10 | 2.09 | 9/10 | 1.12 | 10/10 | 1.05 | 10/10 |
| QU (3,3,3) | 0.264 | 0.185 | 110.41 | 155.00 | 3.45 | 10/10 | 1.75 | 8/10 | 1.06 | 10/10 | 1.05 | 10/10 |
| Sigma (N8) | 0.0199 | 0.158 | 73.92 | 9.69 | 3.74 | 10/10 | 1.03 | 10/10 | 1.03 | 10/10 | 1.03 | 10/10 |
| Race-parametric (N6) | 0.198 | 0.0826 | 36.58 | 84.60 | 3.01 | 10/10 | 1.45 | 9/10 | 1.05 | 10/10 | 1.04 | 10/10 |
| Sigma (N10) | – | 0.151 | 1097.66 | – | 10/10 | – | 10/10 | – | 10/10 | – | 10/10 | |
| Opt-lock (N512) | – | 0.190 | 181.86 | – | 0/10 | – | 10/10 | – | 10/10 | – | 10/10 | |
| Eratosthenes SC (N17, U32) | – | 0.115 | 241.55 | – | 0/10 | – | 10/10 | – | 10/10 | – | 10/10 |
| Mean q-error (27 configurations) | 286 | 1.56 | 1.19 | 1.08 | ||||||||
| Mean q-error, (14 configurations) | 550 | 2.09 | 1.36 | 1.15 | ||||||||
| Correct choices | 280/340 | 322/340 | 333/340 | 338/340 |
tbl:1. Ratio estimates and checker choices with a one-minute sampling budget. : exact RF/Maz count ratio; : RF/Maz pilot rate ratio; , : Maz and RF verification times. For each method, q-err. gives the mean q-error over ten seeds, and correct counts choices of the faster checker. Mean q-errors at the bottom exclude Write-only and Control-flow, whose zero estimates give infinite q-error. Missing exact ratios are marked –; denotes a timeout, and (OOM) denotes memory exhaustion. A single trial exceeds the sampling budget; the run ends when that trial completes.
count on 22 of the 26 configurations on which both checkers complete. On the remaining four, Nidhugg reports approximately 8% to 21% fewer executions.
For each configuration on which GenMC completes its Mazurkiewicz exploration, the number of explored classes gives , and the number passing the canonicity check gives . This yields the exact ratio for 29 configurations. The remaining five are those on which Maz times out for which we don’t have a ground truth of .
Results
How accurate are the estimates? We measure ratio accuracy using q-error,
A q-error of one is exact, and two means that the estimate differs from the reference by a factor of two in either direction. tbl:1 reports the arithmetic mean of the ten seeds’ q-errors for each configuration. A zero estimate against a positive reference has infinite q-error. This occurs on Write-only and Control-flow, where canonical executions are rarely sampled. Their mean q-errors are therefore infinite. We examine these two cases below and compute the mean q-error across the other 27 configurations with reference ratios.
On these 27 configurations, CoEst has a mean q-error of 1.56 with , 1.19 with , and 1.08 with . The ratio estimate is exact for every seed and population budget on the 13 configurations with . Every Mazurkiewicz class is then canonical, so the RF and Mazurkiewicz contributions agree on every trial. On the remaining 14 configurations, the mean q-errors are 2.09, 1.36, and 1.15, respectively. A larger population lets each trial cover more of the tree at the cost of completing fewer trials. Here, the additional work within each trial pays off in lower mean q-error.
CH has a mean q-error of 286 over the same 27 configurations, and 550 over the 14 with . It overestimates on 13 of these 14 configurations, by factors between 2.6 and 7,570, and underestimates it only on Lamport. The weights correct for these unequal probabilities. Applying them to the same samples (CoEst with ) reduces the mean q-error over the 27 configurations from 286 to 1.56.
On Write-only and Control-flow, the real values are extremely small, and most runs sample no canonical representative, yielding zero estimates and infinite q-error. Every estimate nevertheless falls below the pilot threshold, so all runs correctly choose RF.
How often do we choose the faster checker? RF finishes sooner on 14 of the 34 configurations, and Maz on the other 20. Always choosing Maz is therefore correct in 200 of 340 runs (58.8%), and always choosing RF in 140 (41.2%). Using CoEst’s estimates and the pilot rates, we choose the faster checker in 322 runs (94.7%) with , 333 (97.9%) with , and 338 (99.4%) with . With , all ten seeds choose correctly on 32 of the 34 configurations. The two incorrect choices are one seed each on QU (4,3,3) and Scull (R2, W2). CH chooses correctly in 280 runs (82.4%).
Choosing solely by the pilot exploration rates would select Maz on every configuration, since for every configuration. This is equivalent to Always Maz, which misses the fourteen configurations on which RF finishes sooner. Therefore the ratio estimate helps identify when RF’s smaller exploration space makes up for its lower exploration rate.
Does the time saved pay for the choice? A correct choice is useful only if it saves more time than we spend making it. We compare CH and CoEst at the three population budgets with Always Maz, Always RF, and Ideal round robin. We exclude nine configurations on which at least one checker finishes during its pilot, since no subsequent choice is needed. This leaves 25 configurations and, with ten seeds each, 250 choices for each sampling setting. RF is faster on seven of these configurations.
Ideal round robin gives both checkers equal processor shares and stops when either finishes. With independent memory limits and no switching overhead, its cost is
We reconstruct the cost of our procedure from the recorded runs, charging two one-minute pilots, the measured estimation time , and a fresh run of the selected checker :
The measured estimation time includes finishing any trial still in progress when the budget expires. We reuse the selected checker’s recorded runtime across the ten seeds. We also report its slowdown, , which measures the cost of the choice without the preliminary work. Timeouts and memory exhaustion give lower bounds on slowdown and total cost.
Table 2 shows that CoEst with chooses the faster checker in 248 of 250 decisions, with a geometric mean slowdown of 1.002 and a worst slowdown of 1.51. Its reconstructed total cost is 127.05 hours, 43.9% below ideal round robin’s 226.43 hours, at least 49.9% below the Always Maz bound of 253.55 hours, and at least 41.6% below the Always RF bound of 217.65 hours. The other population budgets give similar total costs, despite making more incorrect choices: 127.21 hours with 243 correct decisions for , and 127.64 hours with 235 correct decisions for .
| Strategy | Correct choices | Mean slowdown | Worst slowdown | Total cost (h) |
| Canonical hit | 220/250 | |||
| CoEst, | 235/250 | 1.018 | 1.81 | 127.64 |
| CoEst, | 243/250 | 1.010 | 1.51 | 127.21 |
| CoEst, | 248/250 | 1.002 | 1.51 | 127.05 |
| Always Maz | 180/250 | |||
| Always RF | 70/250 | |||
| Ideal round robin | – | 2.000 | 2.00 | 226.43 |
Table 2. Checker selection on 25 configurations where neither checker finishes during its one-minute pilot, with ten decisions per configuration. Slowdown is relative to the faster checker; we report the geometric mean and maximum. Costs for CH and CoEst include both pilots, estimation, and a fresh checker run. denotes a lower bound due to timeout or memory exhaustion.
CH chooses correctly in 220 of the 250 decisions. Its 30 incorrect choices occur on ApproxDS (N6, M4), Opt-lock (N512), and Eratosthenes SC (N17, U32). It chooses Maz on these programs, although RF verifies them much faster. Its total cost is at least 185.61 hours. We note that both methods benefit from the 13 configurations with , on which every seed correctly chooses Maz. On the remaining 12 configurations (120 decisions), CoEst with costs 34.36 hours, 36.4% less than ideal round robin’s 54.06 hours, whereas CH costs at least 92.92 hours.
In all but twenty runs of CoEst, every estimation trial is fast and the last trial extends the one-minute budget by less than a second. The exception is Opt-lock (N512), where a single trial can cost more than verifying the program with RF. With and , the first trial is still running when the minute expires and finishes after about 190 and 500 seconds respectively. The resulting total costs are about 490 and 800 seconds, compared with 364 seconds for ideal round robin. Nidhugg verifies this program in 182 seconds by exploring 6,139 executions, while a single trial with expands about 30,000 nodes of the Mazurkiewicz tree. The smaller population avoids this expensive trial: with , a one-minute run completes about 507,000 trials, and the total cost is 363 seconds. This illustrates the limitation of CoEst with large budgets: Here, RF reduces the exploration space so substantially that advancing many Mazurkiewicz paths within a single trial costs more than completing RF verification. The larger population is unnecessary for this choice: with , CoEst already selects RF correctly in all ten runs, at a much lower estimation cost.
When is the choice difficult? When is close to the pilot threshold , a small estimation error can change the choice. Table 3 lists the seven configurations on which Maz is faster and CoEst makes at least one incorrect choice across the tested seeds and population budgets.
| Configuration | |||||||
| QU (4,3,3) | 0.209 | 0.178 | 1.18 | 1.20 | 6 | 1 | 1 |
| Scull (R3, W2) | 0.187 | 0.143 | 1.31 | 1.43 | 5 | 4 | 0 |
| QU (3,3,3) | 0.264 | 0.185 | 1.43 | 1.40 | 2 | 0 | 0 |
| Scull (R2, W2) | 0.208 | 0.135 | 1.54 | 1.51 | 1 | 2 | 1 |
| Lamport (N3, U16) | 0.428 | 0.271 | 1.58 | 1.69 | 1 | 0 | 0 |
| Race-parametric (N6) | 0.198 | 0.0826 | 2.40 | 2.31 | 1 | 0 | 0 |
| Race-parametric (N7) | 0.153 | 0.0563 | 2.72 | 1.81 | 1 | 0 | 0 |
Table 3. The configurations with on CoEst failed to predict with 100%, ordered by .
The closer is to one, the smaller the underestimate needed to select RF incorrectly. All incorrect choices with occur in this group.
Among the configurations requiring a choice after the pilots, these mistakes incur only modest overhead. As Table 2 shows, even with , CoEst has a geometric mean slowdown of 1.018 and a worst slowdown of 1.81. CH’s worst slowdown exceeds 59.4, because its bias can hide a substantial advantage of RF.
Do short pilots capture relative exploration costs? We compare the RF/Maz cost per reported execution during the pilots and over the complete runs:
where and are the respective normal-execution counts from the complete runs. A value above one means that RF spends more time per reported execution.
To measure how well a pilot predicts work beyond the observed prefix, we consider the 17 configurations where neither checker finishes during its pilot and both complete in the reference runs. Table 4 reports the comparison. The median relative difference is 6.62%, and the mean is 11.55%. The pilot estimate is within 10% of the full-run value on eleven configurations and within 20% on thirteen. The largest differences, about 42% and 50%, occur on Barrier and Race-parametric.
| Configuration | Relative difference | ||
| ApproxDS (N6, M4) | 10.401 | 9.755 | 6.62% |
| Barrier (L2) | 3.386 | 2.388 | 41.81% |
| DQ (L3) | 2.365 | 2.371 | 0.23% |
| Mutex Musl (L1) | 2.124 | 2.126 | 0.08% |
| Optimistic list (L2) | 5.189 | 5.736 | 9.53% |
| QU (4,3,3) | 5.630 | 5.727 | 1.69% |
| QU (3,3,3) | 5.407 | 5.326 | 1.51% |
| Scull (R3, W2) | 6.993 | 7.665 | 8.76% |
| Spinlock (N4, U6) | 3.169 | 3.549 | 10.71% |
| STC (P5, 2/2/2/2, U16) | 4.817 | 4.848 | 0.63% |
| Ticketlock (L1) | 2.607 | 3.382 | 22.92% |
| Treiber dynamic (W4, RW1) | 2.084 | 2.789 | 25.29% |
| Treiber static (L3) | 6.796 | 7.789 | 12.75% |
| TTAS | 2.847 | 2.859 | 0.42% |
| Scull (R2, W2) | 7.404 | 7.279 | 1.72% |
| Sigma (N9) | 6.432 | 6.514 | 1.26% |
| Race-parametric (N7) | 17.761 | 11.807 | 50.44% |
| Median relative difference | 6.62% | ||
| Mean relative difference | 11.55% |
Table 4. RF/Maz cost per reported normal execution, measured by pilots and complete checker runs. and ; the relative difference is . Both checkers remain unfinished after their one-minute pilots and complete in the reference runs on all 17 configurations. Each row compares one recorded pilot pair with one full-run pair, using actual observation times.
How often do the samples support the choice? We use the test from Section 5 to assess the evidence for our choices, at a nominal significance level of 5% per one-sided test. With and , the test is conclusive in 298 and 308 of 340 runs, respectively; every conclusion agrees with the observed faster checker. The remaining 42 and 32 runs include all seven and two incorrect choices, respectively. Ten runs in each group complete only one trial on Opt-lock (N512), so the test cannot estimate the variance. With , all 18 incorrect choices likewise occur among the 94 inconclusive runs.
Related Work
In this paper, we study the size of the execution space under RF reduction and its ratio to the space under Mazurkiewicz reduction.
The counting class SpanP. The class SpanP [21], equivalently #·NP[18], consists of functions that count polynomial-size strings satisfying an NP predicate. RF counting belongs to this class: a nondeterministic polynomial-time procedure can guess a maximal execution and output its RF graph, counting distinct outputs. Toda and Watanabe [30] show that every SpanP function can be computed in polynomial time with access to a #P oracle. Consequently, every #P-hard function in SpanP is SpanP-complete under polynomial-time Turing reductions. Our hardness result therefore makes RF counting SpanP-complete under these reductions. However, Mazurkiewicz counting is also SpanP-complete under the same reductions, so this classification does not establish that RF counting is harder. Our conditional separation of RF counting from #P in § 4 provides this distinction.
Model counting. RF counting can be formulated as projected model counting [4]: projection variables describe an RF graph, while auxiliary variables encode an execution witnessing its realizability. The formula can be handled by exact projected counters or hashing-based approximate counters such as ApproxMC [6, 28], following Stockmeyer’s approach [29].
We pursue an execution-based approach for two reasons. First, building a monolithic program encoding for estimation would reintroduce a cost that execution-based checkers avoid by evaluating local computations directly. Second, hashing-based counters obtain their polynomial-time guarantees relative to a SAT oracle. Fixing the thread count does not bound the encoding’s variable count independently of program size or provide a polynomial-time procedure for the resulting SAT queries. These guarantees therefore do not recover our polynomial-time-per-trial bound for fixed .
Related algorithms count words and Mazurkiewicz traces from explicit automata [10, 25]; we estimate RF classes directly from bounded programs.
Coarser execution equivalences. RF equivalence is itself part of a broader effort to reduce the execution space beyond Mazurkiewicz equivalence. Data-centric DPOR and optimal RF exploration exploit read sources to merge otherwise distinct classes [1, 7]. Value-based abstractions can merge executions further by identifying reads that obtain the same value from different writes. In particular, Agarwal et al. [2] introduce reads-value-from (RVF) equivalence, which preserves read values and the causal ordering among reads, and develop the RVF-SMC model checker. These approaches develop and explore coarser partitions; our work asks how to quantify the reduction before committing to a complete exploration. Our concrete estimator and evaluation focus on RF reduction relative to Mazurkiewicz reduction. Extending checker selection to RVF would additionally require estimating its partition and accounting for the cost of its exploration procedure.
Conclusion
In this work, we studied how to quantify the advantage of RF equivalence for individual programs without completing their exploration. We showed that counting RF classes is #P-hard and that even polynomial-time unbiased estimation is likely impossible for an unbounded number of threads. For a fixed number of threads, however, our algorithm CoEst produces unbiased estimates of the RF and Mazurkiewicz class counts in polynomial time per trial. The resulting ratio estimator is strongly consistent.
Our experiments show that these estimates can help choose between RF and Mazurkiewicz model checkers. Combining the estimated reduction ratio with the exploration rates measured during short runs of the two checkers reduces total verification time on our benchmarks, even after including the time spent making the choice. Our comparison with canonical-hit sampling shows that weighting improves both estimation accuracy and checker selection.
AI Use. We used OpenAI’s GPT models to polish the paper, assist with proofs, and support algorithmic discussions and development. We also used OpenAI’s Codex and Anthropic’s Claude Code to assist with the implementation used in our experiments.
Data-Availability Statement
The code and data underlying this study include the implementation of CoEst in GenMC, benchmark programs and configurations, experimental logs, and scripts for running the experiments and generating the reported tables. We plan to make these materials publicly available.
References
Proof of Theorem 4
Proof idea. We reuse the reduction establishing #P-hardness of Mazurkiewicz counting in Balasubramanian et al. [5]. The constructed programs satisfy , so the same reduction establishes #P-hardness of RF counting.
Proof of Proposition 5
Proof idea. Given a Boolean formula over variables, construct a program with shared locations , initially zero. For each , a separate thread writes . A main thread reads each into a local bit , evaluates , and writes if the formula holds. One additional thread writes . No thread reads .
The reads can realize every Boolean assignment, and each assignment determines exactly one RF class. An unsatisfying assignment contributes one Mazurkiewicz class. A satisfying assignment contributes two, distinguished by the order of the two writes to . Hence,
The exact ratio therefore determines the model count:
This establishes #P-hardness with a single oracle query.
Proof of Theorem 6
Proof. We prove that implies . The key is a polynomial-time construction that maps a Boolean formula to two loop-free deterministic SC read/write programs and satisfying
All counts range over maximal executions.
Our construction combines Papadimitriou’s SAT reduction for polygraph acyclicity [27 Section 3, Theorem 1] with the serialization gadget used by Gibbons and Korach for SC verification with a fixed read-mapping [17 Section 4.1, Theorem 4.1]. We implement the prescribed read sources using guarded reads and add an auxiliary read to turn realizability into a difference of class counts.
The source formula. A clause is mixed if it contains both positive and negative literals. A formula is noncircular if at most one occurrence of each variable belongs to a mixed clause. By Papadimitriou’s normalization [27 Lemma 3], we can transform in polynomial time into an equisatisfiable noncircular CNF formula with two or three literals per clause. We use the variable and clause gadgets of that reduction below.
Blocks and prescribed read sources. The reduction encodes Boolean choices and clause constraints through the relative order of blocks. To implement these constraints using ordinary SC reads and writes, we ensure that block bodies do not interleave in any execution where all success checks pass. Each block is implemented by a separate thread with a distinct owner identifier . All shared locations are initially zero. Let be a common marker and let be a fresh shared flag written only by . The block executes
ok_T ← true;
write(A, id(T));
body(T);
a ← read(A);
if ok_T ∧ a = id(T) then
write(finish_T, 1);
The local flag records whether all prescribed reads in the body succeeded. A failed check sets it to false, but does not stop the block or skip subsequent body operations.
If every block writes its finish flag, every marker read must read its own block’s marker write. The intervals from these writes to their corresponding reads are pairwise disjoint: if two overlapped, the later marker write would prevent the earlier block’s read from reading its own write. Successful blocks therefore have a strict total order, denoted by
We use two operations to construct the block bodies. The operation RequireRF introduces a fresh location : block writes id to , and block reads and checks that it obtains this value. An accompanying operation AddCompetingWrite adds write to a third block . Each call to RequireRF uses a fresh location; the accompanying operation refers to that same location. Within each block, fix a deterministic order for all added operations.
Without the competing write, a successful prescribed read requires . With the competing write, it requires precisely
The second condition prevents from overwriting the designated source between and . Conversely, executing the blocks serially in any total order satisfying these constraints makes every prescribed read succeed.
Variable and literal gadgets. For each variable of , create three blocks , , and add
Their two possible successful orders encode the truth value of :
For each literal occurrence , create fresh blocks , . For a positive occurrence , add
For a negative occurrence , add
These constraints force whenever evaluates to false. If is false, then and hence . This rules out in (4), forcing . If is false, then and hence . This rules out , again forcing .
Clause gadgets and soundness. For a clause with occurrences , where , add
If every literal in the clause were false, the successful block order would contain the cycle
which is impossible. Thus, any execution in which every block writes its finish flag determines a satisfying assignment of .
Completeness. Conversely, fix a satisfying assignment of . For each false literal choose in its ordering disjunction. For a true positive literal choose ; for a true negative literal choose . Choose the variable orders according to the assignment.
These are exactly the variable- and clause-gadget edge choices in Papadimitriou’s SAT-to-polygraph construction. Its completeness argument shows that, for a noncircular formula, the resulting directed graph is acyclic [27 proof of Theorem 1]. A topological order therefore gives a total block order satisfying all constraints in (4). Executing complete blocks in this order makes every marker and prescribed body read succeed, so every finish flag is written.
The two programs. Program consists of the block threads and one checker thread. The checker reads every once in a fixed order, without short-circuiting. If all these reads return 1, it performs one additional read of a fresh location , initially 0. It discards that read’s value and terminates. Call an execution successful when this auxiliary read occurs.
Program is identical, except for one additional thread whose only operation is . All threads are loop-free and nonblocking, so every maximal execution completes every thread.
By soundness, a successful execution yields a satisfying assignment of . By completeness, a satisfying assignment gives a successful execution by running all blocks in the constructed order and then running the checker. Consequently, a successful execution exists exactly when is satisfiable.
One successful RF class. Existence alone is not enough for (3): we also need all successful executions of to induce the same RF graph. In every such execution, all body events and finish writes occur. Each body read has its prescribed source; each marker read reads its own block’s marker write; each checker read of a finish flag reads its unique noninitialization write; and the auxiliary read reads initialization. Thus, the event set, event labels, and all read sources are fixed. Different satisfying assignments and block orders only change information discarded by RF projection. Hence the number of successful RF classes of is exactly one if is satisfiable and zero otherwise.
Cancellation of the other classes. Map each RF graph of to one of by deleting the extra auxiliary write. If the auxiliary read reads from that write, redirect it to initialization and change its returned value to 0. Deleting the write from an SC execution witnesses realizability of the resulting graph: no other operation accesses this fresh location, and the read’s value has no effect on subsequent behavior.
Every unsuccessful RF graph of has exactly one preimage: there is no auxiliary read, so the additional write introduces no read-source choice. This preimage is realizable by scheduling the write after all other events.
Every successful RF graph has exactly two preimages, according to whether the auxiliary read reads initialization or the added write. The former is realized by placing the write last; the latter by placing it immediately before the auxiliary read. These are the only possible sources, and all other graph components are unchanged. Therefore,
which proves (3).
Size of the construction. The number of blocks, locations, and instructions is polynomial in . Block identifiers require only logarithmically many bits, and local computation consists of comparisons and Boolean operations. Thus, both programs, including their execution-length bounds, are constructible in polynomial time.
Consequence for #P membership. Suppose . Since and are constructible in polynomial time, both functions
belong to . Their difference therefore belongs to GapP. By (3), this difference is the characteristic function of SAT: it equals 1 on satisfiable formulas and 0 on unsatisfiable formulas. The characterization of SPP by 0–1-valued GapP functions [13] then gives SAT SPP. Since SAT is NP-complete and SPP is closed under polynomial-time many-one reductions, we obtain NP SPP. Thus, RF counting does not belong to unless NP SPP.
D Proof of Theorem 7
Proof. Suppose, for contradiction, that an estimator satisfying the conditions of the theorem exists. We show that 3-SAT is low for PP, contradicting the assumption . The weighted-counting argument below is an explicit specialization of the arguments underlying Theorems 4, 8, and 17 of de Campos et al. [9], combined with Fenner’s PP-lowness criterion [12 Theorem 1.1].
Recall that GapP consists of differences of two functions. Fenner’s criterion states that a language is low for PP if there exist a function and a polynomial such that, for every input ,
Here, lowness means . We construct such a function for 3-SAT using the assumed unbiased estimator.
All constructions below are specified for valid 3-CNF encodings and extended by zero to malformed inputs. These extensions can be implemented by polynomial-time validity checks and preserve the counting-class membership claims below.
Let be a 3-CNF formula. By the construction establishing (3), there are polynomial-time constructible programs and such that
where is 1 if is satisfiable and 0 otherwise.
Both programs have size polynomial in . The worst-case polynomial running-time bound on therefore gives a polynomial bounding the number of random bits used by either invocation. Padding with unused random bits, we represent both runs using a common uniformly distributed string and define
Each invocation has the correct marginal distribution. Thus, unbiasedness and linearity of expectation give
To obtain an integer-valued function, define
Because outputs explicit binary rational numbers within polynomial time, is computable in polynomial time and has polynomial bit length. Moreover,
Taking expectations yields
Now define
We claim that . Write
Choose a polynomial such that for every . Each sum belongs to #P: a machine guesses and an -bit nonnegative integer , and accepts exactly when . Their difference is , proving the claim.
Since is uniform,
Consequently,
To place these intervals within those required by Fenner’s criterion, define
The added term is a #P function: a machine guesses bits and accepts on every path. Thus , and
These intervals lie in and , respectively. Taking , Fenner’s criterion therefore gives
Since 3-SAT is NP-complete under polynomial-time many-one reductions, it follows that , contradicting the assumption of the theorem. □
Proof of Corollary 8
Proof. Suppose such an estimator exists. Independently generate a polynomial-time unbiased Mazurkiewicz estimate . Their product satisfies
contradicting Theorem 7. □
Proof of Proposition 10
Proof sketch. The SC consistency procedure of Abdulla et al. [1] searches for an execution realizing , whose write orders determine a compatible coherence order. For every fixed , this search takes polynomial time. We fix a deterministic search order that depends only on . If the search succeeds, is the full graph obtained by adding the returned coherence order to ; otherwise, . Since all search choices depend only on , the procedure always selects the same full graph for the same RF graph. □
Proof of Proposition 11
Proof sketch. A nondeterministic machine guesses an RF graph using a unique encoding and computes . It rejects if . Otherwise, it accepts if and only if is a valid maximal execution of under SC. For fixed , these checks take polynomial time, and the accepting computations correspond one-to-one with RF classes. Thus, RF counting belongs to #P.
An unbiased estimator follows by randomly simulating this machine and returning the inverse sampling probability if the computation accepts, or zero otherwise. Each accepting computation contributes one in expectation, and each trial takes polynomial time. □
Proof of Proposition 13
Proof. Recall that TruSt constructs execution graphs incrementally through forward extensions and backward revisits, while exploring each maximal Mazurkiewicz class exactly once [22]. With a fixed scheduler, its exploration induces the transition system described by Balasubramanian et al. [5]. The states include the execution graph and the exploration metadata required by TruSt. Crucially, the exploration is branch-independent: the successors of a state do not depend on which other branches have previously been explored. Thus, defines a fixed rooted exploration tree that can be sampled without constructing it in full.
Let denote its leaves and those representing maximal executions of . Optimality gives a bijection between and the maximal Mazurkiewicz classes. Other exploration leaves contribute zero, including blocked leaves that do not represent maximal executions. We refer to [5] for the transition rules and the polynomial bounds on path length and successor generation.
Recall that Knuth’s method gives an unbiased estimate of the total leaf weight of a rooted tree [20]. It samples a root-to-leaf path using known positive child-selection probabilities and returns the sampled leaf’s weight divided by the product of these probabilities. At a node with children, each choice can be implemented using fair random bits: interpret the bits as a nonnegative integer and select child .
TeStor uses stochastic enumeration, an extension of Knuth’s method that samples multiple paths while preserving unbiasedness [5]. This extension does not affect the argument below: both methods are unbiased for any fixed assignment of leaf weights.
Our algorithm changes only these weights. For Mazurkiewicz counting, each leaf representing a maximal execution has weight one, and all other leaves have weight zero. For RF counting, we additionally set the weights of noncanonical leaves to zero. The canonicity checker selects exactly one full graph for each RF class, and optimality ensures that this graph appears at exactly one leaf. The modified tree therefore has total leaf weight . Applying the same sampling procedure to the original and modified weights yields
The canonicity procedure selects one valid full graph for each realizable RF projection, independently of the sampled graph and previous trials. Since every such full graph occurs exactly once in , exactly one leaf contributes for each maximal RF class. Consequently,
The procedure PairedEstimation applies these two cost functions to the same sampled leaf, returning
Thus,
Equivalently, the RF estimate retains the original Mazurkiewicz weight on canonical leaves and replaces it by zero on all other leaves. The stochastic-enumeration extension of TeStor is likewise unbiased for any fixed leaf-cost function [5]. Applying it to and therefore preserves both conclusions.
Finally, let be independent repetitions of the paired trial. The strong law of large numbers gives
Since , the denominator is almost surely positive for all sufficiently large , and
Any fixed convention used when the denominator is zero does not affect this limit. □
Inapproximability of the Reduction Ratio
Proposition 15. Unless NP = RP, there is no fully polynomial randomized approximation scheme
even for loop-free deterministic SC read/write programs with two threads and Boolean shared variables. Both counts range over classes of maximal executions.
Proof. We adapt the assignment-and-amplification construction used for Mazurkiewicz counting in [5].
Let be a CNF formula over Boolean variables, and let be its number of satisfying assignments. Set
Construct a program with shared variables , all initially zero, and the following two threads. The variables are local to .
| Thread | Thread |
| <br><br><br>if then<br><br> | <br><br><br><br> |
Encoding assignments. For each , let denote the read of in and its unique noninitial write in . The value of is one exactly when precedes . Every assignment is realizable: process the indices in increasing order, scheduling when and when . This respects both threads’ program orders. After these pairs have completed, both threads have finished their accesses to . For a fixed assignment, the reads-from sources of all reads are fixed, as is the set of executed events. There are no reads of . Consequently, all executions producing that assignment belong to the same RF class. Different assignments have different reads-from relations, so
Counting Mazurkiewicz classes. If an assignment does not satisfy , only executes a write suffix. Its stores have a fixed program order, so this assignment contributes exactly one Mazurkiewicz class.
If an assignment satisfies , both threads execute stores to . Their program orders permit exactly
merges of the two store sequences. Different merges order some pair of conflicting stores differently and therefore belong to different Mazurkiewicz classes. Every merge is realizable by first completing the assignment pairs as above and then scheduling the two suffixes according to that merge. There are no further cross-thread dependencies, so this assignment contributes exactly Mazurkiewicz classes.
It follows that
and hence
Separating satisfiable and unsatisfiable formulas. The amplification satisfies
If is unsatisfiable, then and . If is satisfiable, then , so
Thus, the polynomial-time construction gives the gap
Suppose that an FPRAS for exists. Run it on with relative-error parameter . With probability at least , its output satisfies
On this event, an unsatisfiable formula yields , whereas a satisfiable formula yields . Comparing the output with therefore gives a polynomial-time randomized SAT decision procedure with bounded error.
To obtain the one-sided error required for RP, apply the standard SAT witness self-reduction. For an input formula with variables, amplify the decision procedure so that each call has error probability at most . Maintain a partial assignment and, for each next variable, test whether setting it to zero leaves a satisfiable formula. Choose zero if the test answers yes and one otherwise. Use fresh randomness for each call, and finally verify the resulting complete assignment against the original formula. Constant formulas can be evaluated directly.
If the original formula is unsatisfiable, verification always rejects. If it is satisfiable and every decision call is correct, the procedure preserves satisfiability at every step and returns a satisfying assignment. There are at most calls; their conditional error bounds and a union bound give success probability at least . Amplification and all reduced program constructions take polynomial time. Thus , which implies .
Finite-Sample Accuracy
Strong consistency guarantees convergence as the number of trials grows, but does not specify the accuracy after a given number of trials. We study this question by bounding the probability of a large relative error after trials.
Fix a program and write
Let be independent repetitions of the paired estimator. The contributions are nonnegative and have finite second moments, with
Write
The ratio estimator is when , and zero otherwise.
Our analysis considers the two count estimates together. If both estimates are 20% too large, for example, their ratio is still correct. More generally, their errors cancel when they overestimate or underestimate the counts by similar proportions. We measure the error that remains through .
Proposition 16 (Finite-sample accuracy). Write
For every and ,
The first term bounds the probability that the estimated Mazurkiewicz count is less than half its true value. Dividing by a small estimate can amplify the error in the ratio. The second term accounts for the cancellation between the two count estimates. Indeed,
This is exactly the difference between the two relative errors. Its expectation is zero, and measures how much it varies. When the relative errors tend to stay close, this variance is small, and fewer trials suffice to control this part of the error.
The bound gives a sufficient sample budget for a desired relative accuracy and failure probability when the true counts and variances are known. These quantities are generally unknown; substituting sample estimates for them does not by itself preserve the guarantee.
Proof. Write
Since , we have . Independence between trials gives
On the event , the denominator is positive and
Thus, a relative error of at least requires either or . Consequently,
where the second inequality follows from Chebyshev’s inequality. Zero-denominator outcomes are included in the first event. Taking the minimum with one proves the proposition. □
References
- [1]Parosh Aziz Abdulla, Mohamed Faouzi Atig, Bengt Jonsson, Magnus Lång, Tuan Phong Ngo, and Konstantinos Sagonas. 2019. Optimal Stateless Model Checking for Reads-From Equivalence under Sequential Consistency. Proceedings of the ACM on Programming Languages 3, OOPSLA, Article 150 (Oct. 2019), 29 pages. doi:10.1145/3360576DOI
- [2]Pratyush Agrawal, Krishnendu Chatterjee, Shreya Pathak, Andreas Pavlogiannis, and Viktor Toman. 2021. Stateless Model Checking Under a Reads-Value-From Equivalence. In Computer Aided Verification: 33rd International Conference, CAV 2021, Virtual Event, July 20–23, 2021, Proceedings, Part I. Springer-Verlag, Berlin, Heidelberg, 341–366. ISBN 978-3-030-81684-1. doi:10.1007/978-3-030-81685-8_16
- [3]Stavros Aronis, Bengt Jonsson, Magnus Lång, and Konstantinos Sagonas. 2018. Optimal Dynamic Partial Order Reduction with Observers. In Tools and Algorithms for the Construction and Analysis of Systems, Dirk Beyer and Marieke Huisman (Eds.). Springer International Publishing, Cham, 229–248. ISBN 978-3-319-89963-3.DOI
- [4]Rehan Abdul Aziz, Geoffrey Chu, Christian Muise, and Peter Stuckey. 2015. #3SAT: Projected Model Counting. In Theory and Applications of Satisfiability Testing—SAT 2015 (Lecture Notes in Computer Science, Vol. 9340). Springer, Cham, 121–137. doi:10.1007/978-3-319-24318-4_10
- [5]A. R. Balasubramanian, Mohammad Hossein Khosheshi Jorshari, Rupak Majumdar, Umang Mathur, and Minjian Zhang. 2026. State Space Estimation for DPOR-Based Model Checkers. Proceedings of the ACM on Programming Languages 10, PLDI, Article 213 (June 2026), 25 pages. doi:10.1145/3808291DOI
- [6]Supratik Chakraborty, Kuldeep S. Meel, and Moshe Y. Vardi. 2013. A Scalable Approximate Model Counter. In Principles and Practice of Constraint Programming. Springer, Berlin, Heidelberg, 200–216. doi:10.1007/978-3-642-40627-0_18DOI
- [7]Marek Chalupa, Krishnendu Chatterjee, Andreas Pavlogiannis, Nishant Sinha, and Kapil Vaidya. 2018. Data-Centric Dynamic Partial Order Reduction. Proceedings of the ACM on Programming Languages 2, POPL, Article 31 (Jan. 2018), 31 pages. doi:10.1145/3158119DOI
- [8]Krishnendu Chatterjee, Andreas Pavlogiannis, and Viktor Toman. 2019. Value-centric dynamic partial order reduction. Proc. ACM Program. Lang. 3, OOPSLA, Article 124 (Oct. 2019), 29 pages. doi:10.1145/3360550DOI
- [9]Casio P. de Campos, Georgios Stamoulis, and Dennis Weyland. 2020. A structured view on weighted counting with relations to counting, quantum computation and applications. Information and Computation 275 (2020), 104627. doi:10.1016/j.ic.2020.104627DOI
- [10]Alexis del Noet, Kuldeep S. Meel, and Umang Mathur. 2026. Counting and Sampling Traces in Regular Languages. Proceedings of the ACM on Programming Languages 10, POPL, Article 81 (Jan. 2026), 28 pages. doi:10.1145/3776723
- [11]Azadeh Farzan and Umang Mathur. 2024. Coarser Equivalences for Causal Concurrency. Proceedings of the ACM on Programming Languages 8, POPL, Article 31 (2024), 31 pages. doi:10.1145/3632873DOI
- [12]Stephen A. Fenner. 2003. PP-Lowness and a Simple Definition of AWPP. Theory of Computing Systems 36, 2 (2003), 199–212. doi:10.1007/s00224-002-1089-8DOI
- [13]Stephen A. Fenner, Lance J. Fortnow, and Stuart A. Kurtz. 1994. Gap-Definable Counting Classes. J. Comput. System Sci. 48, 1 (1994), 116–148. doi:10.1016/S0022-0000(05)80024-8DOI
- [14]Cormac Flanagan and Patrice Godefroid. 2005. Dynamic partial-order reduction for model checking software. In Proceedings of the 32nd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (Long Beach, California, USA) (POPL ’05). Association for Computing Machinery, New York, NY, USA, 110–121. ISBN 158113830X. doi:10.1145/1040305.1040315
- [15]Lance Fortnow and Joshua A. Grochow. 2011. Complexity Classes of Equivalence Problems Revisited. Information and Computation 209, 4 (2011), 748–763. doi:10.1016/j.ic.2011.01.006DOI
- [16]GenMC developers. 2022. GenMC v0.7 Regression Benchmarks. https://github.com/MPI-SWS/genmc/tree/v0.7/tests/correct/data-structures Release commit 0f94ce362c9d91e269f9dcd66791792b8bb8eb2c; accessed 22 September 2026.
- [17]Philip B. Gibbons and Ephraim Korach. 1997. Testing Shared Memories. SIAM J. Comput. 26, 4 (1997), 1208–1244. doi:10.1137/S0097539794279614DOI
- [18]Lane A. Hemaspaandra and Heribert Vollmer. 1995. The Satic Notations: Counting Classes beyond #P and Other Definitional Adventures. ACM SIGACT News 26, 1 (1995), 2–13. doi:10.1145/203610.203611
- [19]Maurice Herlihy, Nir Shavit, Victor Luchangco, and Michael Spear. 2020. The Art of Multiprocessor Programming (2 ed.). Morgan Kaufmann. doi:10.1016/C2011-0-06993-4DOI
- [20]Donald E. Knuth. 1975. Estimating the Efficiency of Backtrack Programs. Math. Comp. 29, 129 (1975), 121–136. doi:10.2307/2005469DOI
- [21]Johannes Köbler, Uwe Schöning, and Jacobo Torán. 1989. On Counting and Approximation. Acta Informatica 26, 4 (1989), 363–379. doi:10.1007/BF00276023DOI
- [22]Michalis Kokologiannakis, Iason Marmanis, Vladimir Gladstein, and Viktor Vafeiadis. 2022. Truly Stateless, Optimal Dynamic Partial Order Reduction. Proceedings of the ACM on Programming Languages 6, POPL, Article 49 (Jan. 2022), 28 pages. doi:10.1145/3498711DOI
- [23]Michalis Kokologiannakis, Iason Marmanis, and Viktor Vafeiadis. 2023. Unblocking Dynamic Partial Order Reduction. In Computer Aided Verification, Constantin Enea and Akash Lal (Eds.). Springer Nature Switzerland, Cham, 230–250. ISBN 978-3-031-37706-8.DOI
- [24]Michalis Kokologiannakis and Viktor Vafeiadis. 2021. GenMC: A Model Checker for Weak Memory Models. In Computer Aided Verification (Lecture Notes in Computer Science, Vol. 12759). Springer, 427–440. doi:10.1007/978-3-030-81685-8_20DOI
- [25]Kuldeep S. Meel, Sourav Chakraborty, and Umang Mathur. 2024. A Faster FPRAS for #NFA. Proceedings of the ACM on Management of Data 2, 2, Article 112 (2024), 22 pages. doi:10.1145/3651613DOI
- [26]Nidhugg Developers. [n. d.]. Nidhugg Benchmark Suite. https://github.com/nidhugg/nidhugg/tree/master/benchmarks approxds_append.c and the RFSC/DC-DPOR Parker benchmark; accessed 22 September 2026.
- [27]Christos H. Papadimitriou. 1979. The Serializability of Concurrent Database Updates. J. ACM 26, 4 (1979), 631–653. doi:10.1145/322154.322158DOI
- [28]Mate Soos and Kuldeep S. Meel. 2019. BIRD: Engineering an Efficient CNF-XOR SAT Solver and Its Applications to Approximate Model Counting. Proceedings of the AAAI Conference on Artificial Intelligence 33, 1 (2019), 1592–1599. doi:10.1609/aaai.v33i01.33011592DOI
- [29]Larry Stockmeyer. 1983. The Complexity of Approximate Counting. In Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing. Association for Computing Machinery, 118–126. doi:10.1145/800061.808740DOI
- [30]Seinosuke Toda and Osamu Watanabe. 1992. Polynomial-Time 1-Turing Reductions from #PH to #P. Theoretical Computer Science 100, 1 (1992), 205–221. doi:10.1016/0304-3975(92)90369-QDOI
- [31]Radislav Vaisman and Dirk P. Kroese. 2017. Stochastic Enumeration Method for Counting Trees. Methodology and Computing in Applied Probability 19, 1 (2017), 31–73. doi:10.1007/s11009-015-9457-4