💻 computer science

A Unifying Approach to Probabilistic Testing Equivalences

This paper proposes a unifying framework for probabilistic testing equivalences in concurrent systems by introducing a new distribution-based semantics and a predicate-based testing approach, which yields internal and external characterizations that generalize classical equivalences, are proven to be congruences, and are comprehensively compared with probabilistic bisimilarities.

Original authors: Weijun Chen, Yuxi Fu, Huan Long, Hao Wu

Published 2026-04-08

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Weijun Chen, Yuxi Fu, Huan Long, Hao Wu

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a quality control inspector for a fleet of autonomous delivery robots. These robots don't just move; they make decisions based on chance (like a coin flip) and sometimes get stuck in loops (divergence). Your job is to figure out: Are two different robots "the same" in how they behave?

This paper proposes a new, unified way to answer that question. It's like creating a universal "compatibility test" that works for any robot, regardless of how complex its internal wiring is.

Here is the breakdown of their approach using simple analogies:

1. The Problem: The "Black Box" Dilemma

In the past, scientists tried to test these probabilistic systems in two main ways:

The "External" Test (The Observer): You send a robot out into the world with a specific mission (a "test"). You watch if it succeeds, fails, or gets stuck. If two robots pass the same tests, they are considered equivalent.
- Analogy: You hire two drivers. You tell them, "Drive to the beach." If both get there, you call them "equivalent drivers."
The "Internal" Test (The Blueprint): You look inside the robot's code to see if the logic matches.
- Analogy: You compare the blueprints of the two cars to see if the engines are built the same way.

The problem is that for complex systems involving randomness, these two methods often didn't agree, or they were too specific to one type of robot.

2. The New Solution: The "Probability Cloud"

The authors introduce a new way of looking at the robots. Instead of looking at a single robot at a single moment, they look at a "Probability Cloud" (a distribution).

The Old Way: "Robot A is at the intersection."
The New Way: "There is a 50% chance Robot A is at the intersection, a 30% chance it's at the park, and a 20% chance it's lost."

They call this Distribution-Based Semantics. Imagine a cloud of dust where each speck represents a possible state of the robot, and the size of the speck represents the probability of being there. This allows them to track the entire cloud as it evolves, rather than just following one path.

3. The Two Main Tests: "May" vs. "Fair"

The paper focuses on two specific ways to judge if two robots are equivalent:

A. The "May" Equivalence (The Optimist's View)

Question: "Is it possible for this robot to succeed?"
Analogy: If you flip a coin, and heads means "success," does the robot have any chance of flipping heads? Even if it's a 1% chance, the answer is "Yes, it may succeed."
The Result: Two robots are "May Equivalent" if they both have a non-zero chance of passing the test.

B. The "Fair" Equivalence (The Realist's View)

Question: "Is the robot guaranteed to eventually succeed, no matter how unlucky it gets?"
Analogy: Imagine a robot that gets stuck in a loop 99% of the time but has a tiny 1% chance of escaping. The "May" test says it's fine. But the "Fair" test says, "No! If it gets stuck in that loop, it never succeeds. It's not reliable."
The Result: "Fair" equivalence is stricter. It demands that the robot doesn't have a "trap" that it can't escape from.

4. The "Unifying" Magic

The authors' biggest breakthrough is showing that these two ways of testing (looking at the cloud internally vs. testing it externally) actually lead to the same conclusion.

The Metaphor: Imagine you want to know if two different types of fruit (an apple and a pear) are "sweet."
- External Test: You taste them.
- Internal Test: You measure their sugar content.
- The Discovery: The authors prove that for these probabilistic robots, the "sugar content" (internal math) perfectly predicts the "taste" (external test). You don't need to do both; one implies the other.

5. Why This Matters (The "Congruence" Property)

In computer science, a "congruence" means that if you have two equivalent parts, you can swap them into a bigger machine, and the whole machine still works the same.

Analogy: If you have two identical batteries, you can swap one for the other in a flashlight, and the flashlight works.
The Paper's Claim: Their new testing method is robust. If Robot A is equivalent to Robot B, you can put them inside a giant robot army, and the army will still behave the same way. This is crucial for building complex, reliable software systems.

6. The "Spectrum" of Equivalence

The paper draws a map (Figure 1 in the text) showing how these tests relate to each other:

Probabilistic Bisimulation (The Strictest): This is like checking if two robots are identical down to every single gear and probability. It's very hard to pass.
Fair Testing (The Middle Ground): This checks if they are reliable enough for real-world use.
May Testing (The Loosest): This just checks if they can work.

The authors show that Bisimulation is stricter than Fair Testing, which is stricter than May Testing.

Summary

This paper is like inventing a new, universal ruler for measuring the reliability of chaotic, random systems.

It stops us from getting lost in complex "trees" of possibilities.
It uses "clouds" of probability to keep things simple.
It proves that looking at the math inside the system gives the exact same answer as testing the system in the real world.
It ensures that if two parts are "equivalent," they can be swapped in any complex machine without breaking it.

This is a foundational step toward building safer, more predictable AI and autonomous systems that operate in a world full of uncertainty.

1. Problem Statement

Probabilistic concurrent systems are fundamental to modern mobile computing, yet defining behavioral equivalences for them remains challenging. Existing approaches to probabilistic testing equivalences often suffer from:

Model Dependency: Theories are frequently tied to specific underlying models (e.g., Markov Decision Processes, Probabilistic Automata, or specific process calculi like pCSP), lacking a unifying framework.
Handling of Nondeterminism: There is a tension between how nondeterminism and randomness interact. Some approaches resolve all nondeterminism via schedulers, while others struggle to distinguish between "innocent" divergence (probability 0) and "pathological" divergence.
Complexity of Semantics: Traditional semantics often rely on complex constructions like infinite unfolding trees or scheduler-based resolutions, making proofs and comparisons difficult.
Gap in Characterization: While classical testing equivalences (May, Must, Fair) are well-understood for non-probabilistic systems (CCS), their probabilistic extensions often lack a unified internal characterization that aligns with external observer-based definitions.

The paper aims to propose a unifying approach that is model-independent, handles the interplay of nondeterminism and probability naturally, and provides both internal and external characterizations for probabilistic testing equivalences.

2. Methodology

The authors develop a novel framework centered on distribution-based semantics and process predicates.

A. Distribution-Based Semantics (RCCS Model)

Instead of using tree-based semantics or scheduler-based approaches, the authors define a new semantics for the Randomized CCS (RCCS) model:

States as Distributions: Transitions occur between distributions of processes ( $\mu \to \nu$ ) rather than single processes.
Linear Evolution: The semantics treats probabilistic transitions as linear operations on convex combinations of distributions. A key property (Lemma 2) is that if $\mu_1 \to \nu_1$ and $\mu_2 \to \nu_2$ , then a convex combination $p\mu_1 + (1-p)\mu_2$ transitions to $p\nu_1 + (1-p)\nu_2$ .
Handling Divergence: This approach naturally distinguishes between processes that diverge with probability 0 (innocent) and those with positive probability, without requiring explicit scheduler definitions.

B. Predicate-Based Testing Framework

The authors generalize the classical testing framework (De Nicola & Hennessy) by replacing the special success action $\omega$ with process predicates ( $\phi \subseteq \text{Process}$ ).

Satisfaction Probability: For a distribution $\mu$ and predicate $\phi$ , the satisfaction probability is $\mu(\phi) = \sum_{P \in \phi} \mu(P)$ .
Testing Outcomes: The set of outcomes $O^\mu_\phi$ is the collection of satisfaction probabilities reachable via internal transitions. Crucially, these sets are convex (intervals).
Characteristics: Two key metrics are defined:
- May Characteristic ( $\chi^{may}_\phi$ ): The supremum of satisfaction probabilities (best-case scenario).
- Fair Characteristic ( $\chi^{fair}_\phi$ ): The infimum of the supremum over all reachable states (worst-case scenario, ensuring success is possible from any reachable state).

C. Unifying Characterizations

The paper introduces two types of equivalences:

Internal Characterizations: Based on the properties of the distributions themselves.
- Diamond Equivalence ( $=^\mathcal{D}_\diamond$ ): Based on "probabilistic equipollence" (matching $\chi^{may}$ ).
- Box Equivalence ( $=^\mathcal{D}_\square$ ): Based on "probabilistic strong equipollence" (matching $\chi^{fair}$ ).
- These are defined relative to a testing context $\mathcal{D}$ and require extensionality (closed under parallel composition, localization, and renaming).
External Characterizations: Based on interaction with observer processes.
- Probabilistic May/Fair Equivalences ( $=^\mathcal{D}_{may}, =^\mathcal{D}_{fair}$ ): Defined by matching testing outcomes against all observers in the context.

3. Key Contributions

New Semantics: Introduced a distribution-based semantics for probabilistic processes that avoids schedulers and infinite trees, offering a simpler, linear, and semantically well-founded approach.
Unifying Framework: Established a framework where internal (predicate-based) and external (observer-based) characterizations coincide.
- Theorem 17 proves that $=^\mathcal{D}_\diamond \equiv =^\mathcal{D}_{may}$ and $=^\mathcal{D}_\square \equiv =^\mathcal{D}_{fair}$ .
Congruence Results: Proved that all proposed testing equivalences are congruences (Theorem 19), meaning they are preserved under all standard process operators (parallel composition, restriction, recursion, etc.). This is a significant advancement over previous works where equivalences often failed to be congruences for recursive or parallel systems.
Spectrum of Equivalences: Mapped the relationships between various probabilistic equivalences (Figure 1):
- Strict Hierarchy: $\approx_p$ (Probabilistic Weak Bisimilarity) $\subsetneq =^\mathcal{D}_\square$ (Box/Fair) $\subsetneq =^\mathcal{D}_\diamond$ (Diamond/May).
- Conservative Generalization: The probabilistic equivalences restricted to classical CCS processes are conservative generalizations of classical testing equivalences.
Model Independence (Case Study): Successfully applied the framework to the pCSP model. The results matched existing definitions (Deng et al.) and demonstrated that the framework is adaptable to different process algebras without redefining core semantics.

4. Key Results

Theorem 12: The Box equivalence is strictly finer than the Diamond equivalence ( $=^\mathcal{D}_\square \subsetneq =^\mathcal{D}_\diamond$ ).
Theorem 17: The internal characterizations (Diamond/Box) are identical to the external characterizations (May/Fair) for any testing context.
Theorem 30 & 34: Established the strict inclusion chain:
$\approx_p \subsetneq =^\mathcal{D}_\square \subsetneq =^\mathcal{D}_\diamond$
This shows that probabilistic weak bisimulation is the most discriminating, followed by the "Fair" (Box) equivalence, and then the "May" (Diamond) equivalence.
Handling Divergence: The framework successfully distinguishes between processes with different divergence probabilities (e.g., a process that diverges with probability 0.5 vs. one that diverges with probability 1), a nuance often lost in classical "Must" testing.

5. Significance

Theoretical Unification: The paper provides a cohesive theory that bridges the gap between internal structural properties and external testing behaviors in probabilistic systems. It generalizes classical results (May/Fair/Box/Diamond) to the probabilistic domain.
Practical Applicability: By proving congruence, the equivalences can be used for modular verification and compositional reasoning in complex probabilistic systems.
Flexibility: The distribution-based approach is shown to be easily transferable to other models (demonstrated via pCSP), suggesting it could serve as a standard foundation for future probabilistic process calculi.
Future Directions: The authors identify promising avenues for future work, including:
- Developing decision algorithms for these equivalences (likely PSPACE-hard or harder due to probabilistic branching).
- Investigating metric-based testing equivalences to handle approximate behaviors (epsilon-equivalence).
- Extending the framework to Probabilistic Must equivalence and divergence-sensitive variants.

In summary, this paper offers a robust, mathematically elegant, and unifying solution to the problem of defining and comparing probabilistic concurrent systems, moving beyond model-specific ad-hoc definitions to a general theory grounded in distribution-based semantics.