Stochastic Connectivity as the Foundation of a Runtime Model for Microservice Availability Analysis Anatoly A. Krasnovsky
Anna Maslovskaya
Innopolis University Innopolis, Russia MB3R Lab Innopolis, Russia
Innopolis University Innopolis, Russia
arXiv:2607.00740v1 [cs.SE] 1 Jul 2026
Abstract Microservice availability is commonly assessed by fault injection and chaos experiments, but such experiments are costly, operationally risky, and difficult to repeat for every architectural change. Distributed tracing and deployment metadata provide cheaper evidence, yet they usually remain descriptive: they show which services interacted, not what endpoint-level availability property follows. This paper proposes a formal runtime availability model based on stochastic connectivity for resilience-oriented analysis of microservice endpoints. It treats endpoint availability under explicit fault scenarios as a measurable facet of microservice resilience, combining a typed service-dependency graph, a replication map, a probability measure over node and edge states, and request-specific success predicates. Its semantics separates computational failures of service replicas from communication failures of logical dependencies, showing that replication cannot compensate for bottleneck dependencies. The model can be reconstructed from traces and deployment artifacts, parameterized for architectural what-if analysis, and analyzed by Monte Carlo simulation before or alongside fault injection. We define the model, its trace-to-model construction, elementary semantic properties, and a synthetic adequacy study. The study matches closed-form oracle cases within sampling error and exposes boundaries caused by edge bottlenecks, correlated failures, missing traces, and time-dependent failures.
Keywords runtime models, stochastic models, edge reliability, availability, resilience analysis, distributed tracing, model discovery, microservices, chaos engineering
1
Introduction
Microservice systems are routinely described as graphs of services, queues, databases, gateways, and APIs. This graph intuition is operationally useful, but it is too informal for availability reasoning. A dependency map obtained from tracing or a service mesh can show that service 𝑎 called service 𝑏, yet it does not define whether the dependency was blocking, whether at least one replica of 𝑏 is sufficient, whether the call matters for a particular endpoint, or which network and routing failures are included in the probability space. As a result, teams often fall back to fault injection and chaos engineering to learn availability behavior empirically [3, 15]. Such experiments are valuable, but they are costly, disruptive, and hard to repeat for every dependency or replication change. Model-driven engineering offers a different path: make the abstraction explicit, give it semantics, and analyze the model before
executing failures in the system. This is especially natural for runtime models, which abstract monitored system state and operational context for analysis and adaptation [6, 13]. Microservice platforms already generate the raw material for such models through distributed traces, deployment manifests, service-mesh telemetry, and observability metadata. The missing step is a compact formal model that explains which availability question the reconstructed graph answers. From a resilience perspective, endpoint availability under explicit fault scenarios is the measurable quantity: given a fault model over replicas and communication dependencies, the model asks whether an endpoint still satisfies its success predicate. The route taken here is synthetic: we adapt probabilistic connectivity reasoning from graph reliability to the runtime-model setting of trace-observed microservice systems, and combine it with deployment-level replication and endpoint-specific success predicates. This paper proposes a runtime availability model based on stochastic connectivity. A microservice system is represented as M = ⟨𝐺, 𝑅, 𝑃, Φ⟩,
𝐺 = (𝑉 , 𝐸, 𝜏),
(1)
where 𝐺 is a typed service-dependency graph, 𝑅 maps service types to replica counts, 𝑃 is a probability measure over node and edge states, and Φ is a family of request-specific success predicates. The central idea is that endpoint availability is not a global property of the whole graph. It is the probability that a particular success predicate holds under a sampled state of service replicas and communication dependencies. Prior work provides the empirical starting point. Model discovery and graph simulation showed that trace-derived service graphs and replica counts can approximate endpoint availability under independent fail-stop faults on DeathStarBench [19]. A subsequent OpenTelemetry Demo case study showed that endpoint predicates matter: broker-mediated asynchronous work can be irrelevant for an immediate HTTP response while remaining relevant for eventual workflow completion [18]. Those studies used empirical graphsimulation estimators and left the general runtime-model semantics implicit. This paper formalizes that semantics by defining the tuple syntax, node-and-edge state space, probability measure, request predicates, and adequacy boundaries of stochastic connectivity. It also generalizes the earlier node-oriented estimators by making logical dependency failures first-class state variables. The paper makes four contributions: (i) a formal runtime model for resilience-oriented endpoint availability analysis under node and edge failures; (ii) a trace-to-model construction that maps distributed traces and deployment metadata to the model components; (iii) elementary semantic properties, including estimator unbiasedness, monotonicity, path reliability with edge states, replication
,
Krasnovsky, Maslovskaya
limits under edge bottlenecks, and invariance of immediate HTTP success under non-blocking asynchronous edges; and (iv) a synthetic adequacy study with compact oracle families, large-family sanity checks, and boundary cases for correlation, timing, and partial observability.
which service dependencies can be reconstructed; the OpenTelemetry Demo is a representative instrumented application [21], and industrial surveys confirm the role of tracing in microservice analysis [20]. The gap addressed here is semantic: observability data describes what happened, while stochastic connectivity defines what availability claim can be analyzed from it.
2
3
Related Work
Runtime and quality models. [email protected] research treats models as causally connected abstractions of executing systems, used for monitoring, analysis, adaptation, and assurance [5, 6, 13]. This places stochastic connectivity in the runtime-model tradition: traces, deployment metadata, and telemetry provide the runtime evidence, while the model supplies the semantics needed for analysis. Architecture-based self-adaptation systems such as Rainbow show that explicit architectural models can guide runtime decisions when monitored conditions change [12]; broader self-adaptation roadmaps make assurance and uncertainty central concerns [8]. Architecture-level quality prediction is represented by approaches such as the Palladio Component Model [4] and architecture-based reliability prediction [7, 14]. Availability itself belongs to the broader dependability vocabulary, where service delivery, faults, errors, and failures must be distinguished explicitly [2]. Stochastic connectivity targets a smaller object: endpoint availability under explicit node, edge, and predicate semantics, reconstructed from runtime evidence. Network and architecture reliability. Classical network reliability studies probabilistic connectivity of graphs under node or edge failures [9]. Exact reliability computation is computationally difficult in general [27], motivating randomized approximation schemes and Monte Carlo estimators [17]. Software-architecture research similarly studies reliability and availability prediction from architectural structure, component reliabilities, usage profiles, and deployment assumptions [7, 14, 16]. Stochastic connectivity combines these perspectives for trace-observed microservice systems. A microservice dependency graph is not only a communication graph: vertices denote service types with replicas, edges denote typed execution dependencies, and the property of interest is request-specific success rather than all-terminal connectivity. This is why the model includes 𝑅 and Φ, not only 𝐺 and edge probabilities. Microservice resilience and observability. Microservices introduce independently deployable components, decentralized ownership, and dense cross-service interactions [10, 24, 28]. Practitioneroriented and grey-literature studies report both the benefits of this style and recurring operational costs around monitoring, testing, deployment, and failure handling [26]. Fault-injection systems such as Gremlin demonstrate the practical need for resilience testing at the message-exchange and network layer [15]; chaos engineering generalizes this practice to controlled experiments on production-like systems [3]. Older studies of Internet service outages already showed that failures are not limited to crashed components; configuration, front-end, and operational failures are often central to service unavailability [23]. Benchmarks such as DeathStarBench provide realistic microservice applications for studying these effects [11]. At the same time, distributed tracing systems such as Dapper [25], OpenTelemetry semantic conventions [22], and OpenTelemetry-based tooling produce execution evidence from
Motivating Example
Consider an endpoint 𝑢 served by a frontend 𝑓 . The request synchronously calls a catalog service 𝑐 and a payment service 𝑝, while the payment service asynchronously publishes an event to a broker 𝑘 for later processing by an email service 𝑚. A monitoring tool can reconstruct the edges (𝑓 , 𝑐), (𝑓 , 𝑝), (𝑝, 𝑘), and (𝑘, 𝑚) from traces, but availability depends on the success criterion. For an immediate HTTP response, the event publication may be non-blocking: the request can succeed if 𝑓 , 𝑐, and 𝑝 are live and reachable through live synchronous dependencies. For eventual workflow completion, the broker and the email consumer may become mandatory. Now add a second ambiguity: even if 𝑝 has many replicas, the logical dependency (𝑓 , 𝑝) can fail because of a load balancer, service discovery, service-mesh route, DNS problem, or network partition. A node-only state space treats the dependency as perfectly reliable whenever both endpoints have at least one live replica. This can systematically overestimate endpoint availability. The model must therefore represent both computational failures of replicas and communication failures of logical edges. This example illustrates why a plain dependency graph is underspecified. The same graph supports multiple availability questions, and the same replicated service can be protected against node failures while remaining exposed to edge failures. A model must therefore represent dependency types, request-specific predicates, and edge reliability, not only service adjacency.
4
Formal Stochastic Connectivity Model
Let 𝑉 be a finite set of service types. Let 𝐸 be a finite set of directed logical dependencies, each with a source and target in 𝑉 ; when the dependency key is immaterial, write 𝑒 = (𝑣, 𝑤) for a dependency from 𝑣 to 𝑤. The typing function 𝜏 : 𝐸 → {sync, async}
(2)
classifies dependencies as blocking or non-blocking for the success semantics currently under analysis. The classification is semantic rather than purely technological: a message-broker edge can be non-blocking for immediate HTTP success but relevant for an eventual-completion predicate. The replication map 𝑅 : 𝑉 → N>0 gives the number of runtime replicas for each service type. Let 𝐼𝑅 = {(𝑣, 𝑖) | 𝑣 ∈ 𝑉 , 1 ≤ 𝑖 ≤ 𝑅(𝑣)}
(3)
enumerate replicas. The system state space includes replica states and logical edge states: Ω = Ω𝑉 × Ω𝐸 = {0, 1}𝐼𝑅 × {0, 1}𝐸 .
(4)
For 𝜔 = (𝑥, 𝜖) ∈ Ω, 𝑥 𝑣,𝑖 = 1 means that replica 𝑖 of service 𝑣 is operational, while 𝜖𝑒 = 1 means that logical dependency 𝑒 is operational. A service type is live if at least one of its replicas is
Stochastic Connectivity as the Foundation of a Runtime Model for Microservice Availability Analysis
Table 1: Model components and their intended runtime interpretation.
live: 𝐿𝑣 (𝜔) = 1
"𝑅 (𝑣) ∑︁
# 𝑥 𝑣,𝑖 ≥ 1 .
,
(5)
𝑖=1
Equation (5) is the default stateless 1-out-of-𝑅(𝑣) semantics; stateful or quorum-backed service groups replace it by 𝐿𝑘𝑣 𝑣 (𝜔) = Í𝑅 (𝑣) 1[ 𝑖=1 𝑥 𝑣,𝑖 ≥ 𝑘 𝑣 ], with 𝑘 𝑣 = 1 in the synthetic replicated-bottleneck families below. The probability measure 𝑃 over Ω defines the fault model. In the most general formulation, 𝑃 is arbitrary: it may encode independent failures, correlated failure domains, shared load balancers, zone failures, or empirically observed dependencies. The baseline instantiation used for architectural what-if analysis factors node and edge failures: 𝑃 (𝜔) = 𝑃node (𝑥) · 𝑃edge (𝜖),
(6)
where Ö
𝑃node (𝑥) =
𝑥
𝜃 𝑣,𝑖𝑣,𝑖 (1 − 𝜃 𝑣,𝑖 ) 1−𝑥 𝑣,𝑖 ,
(7)
𝜌𝑒𝜖𝑒 (1 − 𝜌𝑒 ) 1−𝜖𝑒 .
(8)
(𝑣,𝑖 ) ∈𝐼𝑅
𝑃edge (𝜖) =
Ö 𝑒 ∈𝐸
Here 𝜃 𝑣,𝑖 is the live probability of replica (𝑣, 𝑖), and 𝜌𝑒 is the live probability of dependency 𝑒. The product form is a baseline parameterization; dependent failures are represented by replacing 𝑃, without changing the syntax of 𝐺, 𝑅, or Φ. For a state 𝜔 and edge-mode set 𝐵 ⊆ {sync, async}, define the live 𝐵-subgraph 𝐺𝜔𝐵 = (𝑉𝜔 , 𝐸𝜔𝐵 ), (9) where 𝑉𝜔 = {𝑣 ∈ 𝑉 | 𝐿𝑣 (𝜔) = 1}, (10) 𝐸𝜔𝐵 = {𝑒 = (𝑣, 𝑤) ∈ 𝐸 | 𝜏 (𝑒) ∈ 𝐵, 𝐿𝑣 (𝜔) = 1, (11) 𝐿𝑤 (𝜔) = 1, 𝜖𝑒 = 1}. sync
{sync}
We write 𝐺𝜔 for 𝐺𝜔 . Thus, a usable dependency requires live source and target services and a live logical edge, explicitly separating replica redundancy from communication reliability. A request class 𝑢 is modeled by an entry service 𝑠𝑢 ∈ 𝑉 , a mandatory target set 𝑇𝑢 ⊆ 𝑉 , and a success predicate Φ𝑢 ∈ Φ. The canonical immediate-response predicate is h i Φ𝑢imm (𝜔) = 1 ∀𝑡 ∈ 𝑇𝑢 : reach𝐺𝜔sync (𝑠𝑢 , 𝑡) . (12) For eventual-completion semantics, let 𝑇𝑢evt ⊆ 𝑉 be the mandatory completion targets and 𝐵𝑢evt ⊆ {sync, async} the dependency modes relevant to completion. The corresponding predicate is evt evt Φ𝑢 (𝜔) = 1 ∀𝑡 ∈ 𝑇𝑢 : reach 𝐵𝑢evt (𝑠𝑢 , 𝑡) . (13) 𝐺𝜔
The endpoint availability is 𝐴𝑢 = 𝑃 (Φ𝑢 (𝜔) = 1) = E𝜔∼𝑃 [Φ𝑢 (𝜔)].
(14)
When exact enumeration is too expensive, availability is estimated by Monte Carlo sampling: 𝑁 ∑︁ b𝑢(𝑁 ) = 1 𝐴 Φ𝑢 (𝜔 ( 𝑗 ) ), 𝑁 𝑗=1
𝜔 (𝑗) ∼ 𝑃.
(15)
Equation (15) is deliberately simple. Reachability itself is inexpensive; the modeling question is whether the state space, probability
Component
Runtime source
Semantic role
𝐺 = (𝑉 , 𝐸, 𝜏 )
Traces, service mesh, protocol tags
𝑅
Deployment manifests, instance IDs Health checks, restarts, fault scenarios Network errors, routing, mesh telemetry What-if parameters or empirical estimates Endpoint semantics, analyst specification
Service dependencies and blocking/non-blocking edge meaning Redundancy of service types through runtime replicas Computational availability of service replicas Availability of logical communication dependencies Fault model over nodes, edges, and correlations Request-specific definition of success
Ω𝑉 Ω𝐸 𝑃 Φ𝑢
measure, typed edge semantics, and request predicate faithfully capture the availability property being asked. Table 1 summarizes the modeling roles of the tuple components. The tuple is intentionally minimal. Removing 𝑅 collapses service types and runtime replicas, making redundancy invisible. Removing edge states silently assumes perfect communication. Removing 𝜏 conflates blocking calls with non-blocking side effects. Removing Φ turns availability into an underspecified graph-global property rather than an endpoint-level property. The model therefore exposes the smallest set of semantic choices that must be fixed before a trace-derived graph can support availability reasoning.
5
Trace-to-Model Construction and Parameterization
Let T = {𝑡 (1) , . . . , 𝑡 (𝑚) } be a set of distributed traces, where each trace is parsed as a tree or DAG of spans. Parent-child relations between spans are projected to logical dependencies keyed by source service, target service, operation/protocol, and span kind. Repeated observations with the same key are aggregated into 𝐸; if the same service pair appears in both blocking and non-blocking modes, the modes remain distinct logical dependencies. Service names, span attributes, peer service attributes, RPC system tags, messaging system tags, and deployment metadata provide candidate labels for vertices and edges. OpenTelemetry semantic conventions provide a common vocabulary for trace attributes, span names, and operation kinds [22]. The function 𝜏 is inferred from protocol and span semantics: HTTP and RPC interactions are treated as synchronous unless the endpoint semantics says otherwise; messaging interactions, including broker-mediated interactions, are treated as asynchronous for immediate-response predicates. The replication map 𝑅 can be obtained from deployment manifests, orchestrator APIs, or distinct runtime instance identifiers observed in telemetry. The edge variables 𝜖𝑒 do not require tracing to observe every individual packet. They abstract the operational success of a logical dependency: service discovery, routing, mesh policy, load balancer behavior, network reachability, and protocollevel availability. This makes edge reliability a first-class part of the model rather than an implicit perfect-network assumption. The measure 𝑃 can be used in two modes. In architectural whatif analysis, the researcher or engineer chooses 𝜃 𝑣,𝑖 and 𝜌𝑒 as free parameters to explore sensitivity of an endpoint to node and edge reliability. This is the mode used in the synthetic tests. In empirical baseline estimation, 𝜃 𝑣,𝑖 can be estimated from container
,
Krasnovsky, Maslovskaya
restarts, readiness failures, or health-check histories, while 𝜌𝑒 can be estimated from trace-level communication errors such as HTTP 503/504, gRPC UNAVAILABLE, service-mesh telemetry, or observed timeout rates; for product-baseline fitting, 𝜌𝑒 denotes dependency usability conditional on live source and target service groups, so samples during known source/target node-failure intervals are censored or represented by a non-product 𝑃. The tuple semantics is independent of the parameter-estimation method: manual whatif parameters, telemetry-derived rates, and non-product failuredomain models all instantiate the same ⟨𝐺, 𝑅, 𝑃, Φ⟩ structure. Edges in 𝐸 encode observed logical dependencies; Φ𝑢 , not 𝐸 alone, determines which dependencies and targets are mandatory for a request class. A checkout endpoint may be successful when it returns HTTP 200, when payment is committed, or when all downstream events have eventually been processed. The compact predicate assumes a semantically homogeneous request class; endpoints with conditional downstream logic are split into scenarios 𝑐 with separate predicates, or summarized as a workload mixture Í 𝐴𝑢 = 𝑐 𝜋𝑢,𝑐 E[Φ𝑢,𝑐 (𝜔)]. These are different predicates on the same reconstructed graph. Making Φ𝑢 explicit prevents the model from confusing immediate endpoint availability with end-to-end business completion.
6
Analysis Properties
Equation (16) shows that the availability of a synchronous chain degrades as the product of service-group live probabilities and edge live probabilities. Long mandatory chains are therefore fragile to both computational and communication faults, even when each individual component appears highly reliable. Proposition 4 (Replication does not remove edge bottlenecks). If every successful realization of Φ𝑢imm requires a particular logical edge 𝑒 to be live, then 𝐴𝑢 ≤ 𝑃 (𝜖𝑒 = 1). Under the product baseline, 𝐴𝑢 ≤ 𝜌𝑒 regardless of the replica counts of the edge target. Proof sketch. Success implies 𝜖𝑒 = 1, so {Φ𝑢 = 1} ⊆ {𝜖𝑒 = 1}. Taking probabilities gives the bound. □ Proposition 5 (Asynchronous invariance for immediate response). Let 𝐺 1 and 𝐺 2 have the same services, replication map, probability measure restricted to synchronous edges and replica states, entry service, and mandatory targets for request 𝑢, but differ only in asynchronous edges. Then 𝐴𝑢 is identical for both models under Φ𝑢imm . sync
The following properties establish consistency checks for the semantics. They make the model falsifiable: if an implementation violates them on the corresponding synthetic families, either the implementation or the predicate definition is wrong. Proposition 1 (Unbiased Monte Carlo estimator). For any request b𝑢(𝑁 ) ] = 𝐴𝑢 . predicate Φ𝑢 and any probability measure 𝑃 over Ω, E[𝐴 Proof sketch. Each sampled value Φ𝑢 (𝜔 ( 𝑗 ) ) is a Bernoulli random variable with expectation 𝐴𝑢 . Linearity of expectation gives the claim. □ Proposition 2 (Monotonicity under product live probabilities). Assume the product baseline in Equations (6)–(8). If all node live probabilities 𝜃 𝑣,𝑖 and edge live probabilities 𝜌𝑒 weakly increase, then 𝐴𝑢 weakly increases for every monotone reachability predicate of the form in Equation (12). Proof sketch. Couple two product measures with shared uniform random variables. The state sampled under larger live probabilities contains every live replica and live edge of the smallerprobability sample, possibly with additional live replicas and edges. Reachability in the live synchronous subgraph is monotone with respect to adding vertices and edges. □ Proposition 3 (Path reliability with node and edge states). Consider a single mandatory synchronous path 𝑣 0 → 𝑣 1 → · · · → 𝑣𝑘 with no alternative route. Under the product baseline, let 𝑎𝑖 = 1 − Î𝑅 (𝑣𝑖 ) 𝑟 =1 (1 − 𝜃 𝑣𝑖 ,𝑟 ) be the live probability of service 𝑣 𝑖 . Then the immediate availability of the path is ! 𝑘 −1 ! 𝑘 Ö Ö 𝐴𝑢 = 𝑎𝑖 𝜌 (𝑣𝑖 ,𝑣𝑖+1 ) . (16) 𝑖=0
Proof sketch. The predicate succeeds exactly when every service on the path is live and every path edge is live. Under the product baseline these events are independent, giving the product. □
𝑖=0
Proof sketch. The predicate Φ𝑢imm is evaluated only on 𝐺𝜔 . Since the live synchronous subgraph is identical in both models for every shared synchronous state, the predicate value and its expectation are identical. □ These properties clarify the scope of the abstraction. They also motivate the synthetic evaluation: chains should follow Eq. (16); replicated bottlenecks should saturate when edge reliability dominates; and asynchronous broker edges should not affect immediate HTTP availability unless the success predicate requires eventual completion.
7
Synthetic Adequacy Analysis
The synthetic evaluation is an adequacy analysis over controlled graph families. It checks semantic invariants with closed-form oracles, then varies assumptions that are difficult to isolate cleanly in real systems, such as failure correlation, timeouts, retries, and trace incompleteness. This complements benchmark evidence by making each semantic variable observable in isolation. The generator produces three classes of scenarios. First, oracle sanity tests use graph families with closed-form expectations: synchronous chains with node and edge reliability, fan-out dependencies, replicated bottlenecks, and single points of failure. Second, semantic contrast tests evaluate the same topology under different predicates, especially immediate HTTP response versus eventual workflow completion. Third, boundary tests compare the baseline independent fail-stop model with scenarios that require richer semantics, such as correlated failure domains, timeout-induced failures, retry policies, and trace incompleteness. The new edge-state dimension enables an additional adequacy question that is not visible in a node-only model: when does improving replica availability stop helping because communication reliability has become the dominant bottleneck?
Stochastic Connectivity as the Foundation of a Runtime Model for Microservice Availability Analysis
,
Table 2: Synthetic adequacy results. Compact oracle Monte Carlo checks use 𝑁 = 200,000 samples per validation cell; large-family sanity checks are summarized in the text. Family
Varied parameter
Adequacy question
Result
Synchronous chain
Length 𝑘 , node live probability 𝜃 , edge live probability 𝜌 Branching degree 𝑑 , edge reliability 𝜌 Replica count 𝑅 (𝑣) , fixed 𝜌𝑒
Does simulation match the node+edge closed form in Eq. (16)?
Closed form matched; max MC error 0.0014
Grid over node live probability 𝜃 and edge live probability 𝜌 imm vs. eventual Φevt Immediate Φ𝑢 𝑢 Co-location and domain failure probability Delay, timeout, retry count Edge/instance omission rate
When does edge reliability dominate node replication?
Fan-out Replicated bottleneck
How quickly do mandatory AND dependencies degrade availability? 𝑑 = 1 → 12 drops 0.894 → 0.364 Does replication help against node failures but saturate at an edge bottleneck? 𝑅 = 1 → 12 rises 0.738 → 0.820, bounded by
𝜌 = 0.82 Node vs. edge sensitivity Async side effect Failure domain Timeout/hang Trace incompleteness
Max replication gain 0.373; edge-dominant cells
94% Are async edges invariant only for immediate response? What gap appears between product and correlated 𝑃 ? Where does pure connectivity produce false positives? What bias follows from partial model discovery?
Figure 1: Node-versus-edge sensitivity. Heatmap color is the exact availability gain from increasing the target service from one to three replicas; the white contour marks 𝜌 equal to the replicated service live probability 1 − (1 − 𝜃 ) 3 . Below this contour, the required edge is less reliable than the replicated service group and can dominate endpoint availability.
Max false positive 0.399; retries recover 0.318 Max absolute bias 0.594; hidden dependencies overestimate by 0.118
smallest large-family availability was 0.00577. Selected sentinel cells were also checked by Monte Carlo sampling with 𝑁 = 50,000; the maximum absolute error was 0.0020, within the maximum 95% confidence half-width of 0.0044. The semantic and boundary tests use artifact-fixed reference models. The asynchronous side-effect scenario compares Φ𝑢imm with Φ𝑢evt on the same topology, giving immediate Δ = 0 and eventual loss 0.289. In the failure-domain case, the product baseline is 𝐴prod = 1 · (1 − 0.13 ) · 0.95 = 0.94905, while the correlated reference ties all three target replicas to one 𝑍 ∼ Bern(0.90), giving 𝐴corr = 1 · 0.90 · 0.95 = 0.855 and gap 0.094. In the timeout cases, a two-edge chain with connectivity 𝐶 = 0.983 · 0.972 = 0.88557 is compared with 𝐶 [1 − (1 − 𝜆𝑇 )𝑟 +1 ], where 𝜆𝑇 ∈ {0.55, 0.78, 0.93} for 50/100/200 ms and 𝑟 ∈ {0, 1, 2}; this yields max false positive 0.399 and retry recovery 0.318. Trace-incompleteness cases compare the full generated fan-out and replica models with expected estimates after independent omissions 𝑞 ∈ {0, 0.10, 0.20, 0.40}, giving max absolute bias 0.594 and hidden-dependency overestimation 0.118. Overall, the synthetic study checks the intended semantics on oracle families and identifies where the baseline product connectivity model requires richer probability or temporal semantics.
8 The oracle families support the semantic consistency of the implementation. The synchronous-chain family matched the nodeand-edge closed form with maximum Monte Carlo error 0.0014, and the exact availability values ranged from 0.1668 to 0.9703 over the evaluated grid. Mandatory fan-out degraded multiplicatively: at 𝜃 = 0.97 and 𝜌 = 0.95, increasing the fan-out degree from 1 to 12 reduced availability from 0.894 to 0.364. The replicatedbottleneck family approached but did not exceed the required edge reliability: increasing target replicas from 1 to 12 raised availability from 0.738 to 0.820, saturating at 𝜌 = 0.82. These results instantiate Proposition 4 on generated topologies. A large-family sanity layer extends the oracle families beyond the compact Table 2 grid. Synchronous chains were generated up to 257 services and 256 required edges, fan-out graphs up to 129 services and 128 required edges, and replicated bottlenecks up to 64 target replicas. Closed-form values preserved the same qualitative regimes: long mandatory paths and fan-outs decayed multiplicatively, while replicated bottlenecks saturated at the required edge reliability. The
Immediate Δ = 0; eventual lower by 0.289 Product overestimates reference by 0.094
Empirical Basis
The formal model is grounded in real-system case studies and in broader evidence that microservice traces expose service dependencies suitable for analysis [20, 25]. On DeathStarBench Social Network [11], prior graph simulation based on service dependencies and replica counts showed strong linear covariation with fault injection (Pearson 𝑟 ≈ 0.992), and its aggregate table implies conditionlevel MAE 0.025 and RMSE 0.049 across the ten mode/failure-rate cells [19]. These results motivate trace-derived topology and replica counts as the node/replica layer of stochastic connectivity under independent fail-stop faults. On the OpenTelemetry Demo, a trace-discovered model identified Kafka-based asynchronous edges and evaluated immediate HTTP predicates whose required targets were synchronous services [18]. The async and all-blocking variants differed by only about 10−5 in predicted availability in that case study, illustrating the predicate distinction formalized in Proposition 5. Together, these studies motivate the node/replica and predicate layers of ⟨𝐺, 𝑅, 𝑃, Φ⟩; Section 7 exercises the added edge-state layer
,
Krasnovsky, Maslovskaya
and the correlation, timing, and observability boundaries under controlled synthetic conditions.
9
Discussion
The edge extension changes the interpretation of common architectural advice. Replication improves the probability that a service type is live, but it does not automatically improve the probability that a request can reach that service through a required logical dependency. In systems where traffic to a replicated service is mediated by a fragile gateway, service-mesh route, DNS entry, broker topic, or load-balancer configuration, the communication edge can dominate the endpoint availability calculation. This is the semantic reason for the node-vs-edge sensitivity experiment in Table 2. The model also clarifies the relationship between stochastic connectivity and classical reliability analysis. A chain, fan-out, or bottleneck graph can be reduced to familiar product formulas, and those formulas are useful oracles for testing the implementation. Microservice endpoints add typed dependencies, replica groups, request-specific targets, and success predicates that may ignore or include asynchronous work depending on the user-level property. Stochastic connectivity is therefore a domain-specific specialization of probabilistic graph reliability for trace-observed microservice systems. Operationally, the model can rank services and dependencies by endpoint sensitivity, making chaos experiments more targeted rather than uniformly selected.
10
Boundary Conditions
The first boundary is the probability measure. The product baseline in Equation (6) is useful for sensitivity analysis, but real outages often involve correlated failures: co-located replicas, shared nodes, shared zones, shared load balancers, shared DNS, or service-mesh control-plane failures. The formal model can represent such cases through a non-product 𝑃, but this requires additional parameterization and validation. The second boundary is time. The canonical predicate in Equation (12) is a connectivity predicate. It can overestimate availability when a path exists but violates a latency or timeout constraint. Hangs, retries, circuit breakers, queue backlog, backpressure, and indirect coupling from asynchronous work to synchronous paths require temporal or state-enriched predicates because changing from crash-only semantics to timeout semantics changes the meaning of success. The third boundary is observability completeness. Trace sampling, missing instrumentation, partial propagation of context, and aggregated service labels can hide edges, collapse distinct instances, or merge dependencies with different operation/protocol/kind semantics. A trace-discovered model should therefore be interpreted as an observed architectural abstraction. The trace-incompleteness synthetic tests are intended to characterize how omissions bias availability estimates. The fourth boundary is endpoint specification and workload heterogeneity. The model makes Φ𝑢 explicit because availability depends on what the user considers successful. Immediate HTTP response, payment commitment, eventual event processing, and business-level workflow completion are different predicates. A
wrong predicate can yield a numerically precise but semantically wrong estimate. A request class that merges conditional branches should therefore be split into scenario predicates or reported as a workload mixture.
11
Artifact and Reproducibility
The companion artifact [1] contains a backend-independent schema for ⟨𝐺, 𝑅, 𝑃, Φ⟩, deterministic generators for the Table 2 families, and a configuration-driven pipeline that regenerates the CSV tables, reports, and Figure 1. Each configuration fixes the graph family, parameter sweep, sample count, seed, and output metrics, so the oracle checks and boundary comparisons can be inspected from generated outputs.
12
Future Plans
Future work will move from controlled synthetic analysis to datadriven runtime estimation: correlated failure-domain models for shared infrastructure, telemetry-derived 𝜃 𝑣,𝑖 and 𝜌𝑒 parameters, and temporal predicates for latency, retries, circuit breakers, queues, and eventual completion. The same reconstructed models can then support CI and observability workflows for deployment comparison and targeted chaos selection.
13
Conclusion
The contribution of stochastic connectivity is primarily a synthesis of existing but usually separate methodological strands for resilience-oriented availability analysis. It brings runtime-model abstractions, trace-derived dependency discovery, probabilistic graph reliability, and endpoint-specific success semantics into one compact basis for quantifying how endpoint availability degrades under explicit fault assumptions. Building on this basis, the paper introduced a formal runtime model for endpoint availability in microservice systems. The model combines a typed dependency graph, replication, a probability measure over node and edge states, and request-specific success predicates. Extending the state space from replicas to replicas plus logical edges removes the implicit perfect-network assumption and exposes an important architectural distinction: replication can compensate for service-instance failures, but it cannot by itself eliminate bottlenecks in required communication dependencies. The model keeps the state space compact: service replicas, logical edges, a probability measure, and endpoint predicates are the only mandatory ingredients. This makes a common operational abstraction explicit while preserving compatibility with richer probability, temporal, and empirical parameterization layers. The synthetic adequacy study checks the expected semantics, quantifies node-versusedge sensitivity, and identifies boundaries where richer probability or temporal semantics are required.
Stochastic Connectivity as the Foundation of a Runtime Model for Microservice Availability Analysis
References [1] Anatoly A. Krasnovsky. 2026. Stochastic Connectivity Synthetic Experiments Artifact. https://github.com/a-a-k/stochastic-connectivity-synthetic-artifact. Accessed: 2026-06-06. [2] Algirdas Avizienis, Jean-Claude Laprie, Brian Randell, and Carl Landwehr. 2004. Basic Concepts and Taxonomy of Dependable and Secure Computing. IEEE Transactions on Dependable and Secure Computing 1, 1 (2004), 11–33. doi:10.1109/ TDSC.2004.2 [3] Ali Basiri, Niosha Behnam, Ruud de Rooij, Lorin Hochstein, Luke Kosewski, Justin Reynolds, and Casey Rosenthal. 2016. Chaos Engineering. IEEE Software 33, 3 (2016), 35–41. doi:10.1109/MS.2016.60 [4] Steffen Becker, Heiko Koziolek, and Ralf Reussner. 2009. The Palladio Component Model for Model-Driven Performance Prediction. Journal of Systems and Software 82, 1 (2009), 3–22. doi:10.1016/j.jss.2008.03.066 [5] Nelly Bencomo, Sebastian Götz, and Hui Song. 2019. [email protected]: A Guided Tour of the State of the Art and Research Challenges. Software and Systems Modeling 18, 5 (2019), 3049–3082. doi:10.1007/s10270-018-00712-x [6] Gordon Blair, Nelly Bencomo, and Robert B. France. 2009. [email protected]. Computer 42, 10 (2009), 22–27. doi:10.1109/MC.2009.326 [7] Franz Brosch, Heiko Koziolek, Barbora Buhnova, and Ralf Reussner. 2012. Architecture-Based Reliability Prediction with the Palladio Component Model. IEEE Transactions on Software Engineering 38, 6 (2012), 1319–1339. doi:10.1109/ TSE.2011.94 [8] Betty H. C. Cheng, Rogério de Lemos, Holger Giese, Paola Inverardi, Jeff Magee, Jesper Andersson, Basil Becker, Nelly Bencomo, Yuriy Brun, Bojan Cukic, Giovanna Di Marzo Serugendo, Schahram Dustdar, Anthony Finkelstein, Cristina Gacek, Kurt Geihs, Vincenzo Grassi, Gabor Karsai, Holger M. Kienle, Jeff Kramer, Marin Litoiu, Sam Malek, Raffaela Mirandola, Hausi A. Müller, Sooyong Park, Mary Shaw, Matthias Tichy, Massimo Tivoli, Danny Weyns, and Jon Whittle. 2009. Software Engineering for Self-Adaptive Systems: A Research Roadmap. In Software Engineering for Self-Adaptive Systems. Lecture Notes in Computer Science, Vol. 5525. Springer, Berlin, Heidelberg, 1–26. doi:10.1007/978-3-642-02161-9_1 [9] Charles J. Colbourn. 1987. The Combinatorics of Network Reliability. Number 4 in International Series of Monographs on Computer Science. Oxford University Press, New York, NY, USA. [10] Nicola Dragoni, Saverio Giallorenzo, Alberto Lluch Lafuente, Manuel Mazzara, Fabrizio Montesi, Ruslan Mustafin, and Larisa Safina. 2017. Microservices: Yesterday, Today, and Tomorrow. In Present and Ulterior Software Engineering. Springer, Cham, Switzerland, 195–216. doi:10.1007/978-3-319-67425-4_12 [11] Yu Gan, Yanqi Zhang, Dailun Cheng, Ankitha Shetty, Priyal Rathi, Nayan Katarki, Ariana Bruno, Justin Hu, Brian Ritchken, Brendon Jackson, Kelvin Hu, Meghna Pancholi, Yuan He, Brett Clancy, Chris Colen, Fukang Wen, Catherine Leung, Siyuan Wang, Leon Zaruvinsky, Mateo Espinosa, Rick Lin, Zhongling Liu, Jake Padilla, and Christina Delimitrou. 2019. An Open-Source Benchmark Suite for Microservices and Their Hardware-Software Implications for Cloud & Edge Systems. In Proceedings of the Twenty-Fourth International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS ’19). ACM, New York, NY, USA, 3–18. doi:10.1145/3297858.3304013 [12] David Garlan, Shang-Wen Cheng, An-Cheng Huang, Bradley Schmerl, and Peter Steenkiste. 2004. Rainbow: Architecture-Based Self-Adaptation with Reusable Infrastructure. Computer 37, 10 (2004), 46–54. doi:10.1109/MC.2004.175 [13] Holger Giese, Nelly Bencomo, Liliana Pasquale, Andres J. Ramirez, Paola Inverardi, Sebastian Wätzoldt, and Siobhán Clarke. 2014. Living with Uncertainty in the Age of Runtime Models. In [email protected]: Foundations, Applications, and Roadmaps.
,
Lecture Notes in Computer Science, Vol. 8378. Springer, Cham, Switzerland, 47– 100. doi:10.1007/978-3-319-08915-7_3 [14] Swapna S. Gokhale. 2007. Architecture-Based Software Reliability Analysis: Overview and Limitations. IEEE Transactions on Dependable and Secure Computing 4, 1 (2007), 32–40. doi:10.1109/TDSC.2007.4 [15] Victor Heorhiadi, Shriram Rajagopalan, Hani Jamjoom, Michael K. Reiter, and Vyas Sekar. 2016. Gremlin: Systematic Resilience Testing of Microservices. In Proceedings of the 36th IEEE International Conference on Distributed Computing Systems (ICDCS). IEEE, Piscataway, NJ, USA, 57–66. doi:10.1109/ICDCS.2016.11 [16] Anne Immonen and Eila Niemelä. 2008. Survey of Reliability and Availability Prediction Methods from the Viewpoint of Software Architecture. Software and Systems Modeling 7, 1 (2008), 49–65. doi:10.1007/s10270-006-0040-x [17] David R. Karger. 1995. A Randomized Fully Polynomial Time Approximation Scheme for the All Terminal Network Reliability Problem. In Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing (STOC ’95). ACM, New York, NY, USA, 11–17. doi:10.1145/225058.225069 [18] Anatoly A. Krasnovsky. 2025. Evaluating Asynchronous Semantics in TraceDiscovered Resilience Models: A Case Study on the OpenTelemetry Demo. arXiv:2512.12314 [cs.SE] doi:10.48550/arXiv.2512.12314 [19] Anatoly A. Krasnovsky. 2026. Model Discovery and Graph Simulation: A Lightweight Gateway to Chaos Engineering. In Proceedings of the 48th IEEE/ACM International Conference on Software Engineering (ICSE ’26). ACM, New York, NY, USA, 5. doi:10.1145/3786582.3786823 [20] Bowen Li, Xin Peng, Qilin Xiang, Hanzhang Wang, Tao Xie, Jun Sun, and Xuanzhe Liu. 2022. Enjoy Your Observability: An Industrial Survey of Microservice Tracing and Analysis. Empirical Software Engineering 27, 1, Article 25 (2022), 28 pages. doi:10.1007/s10664-021-10063-9 [21] OpenTelemetry Authors. 2025. OpenTelemetry Demo Docs. https:// opentelemetry.io/docs/demo/. Accessed: 2026-06-19. [22] OpenTelemetry Authors. 2026. OpenTelemetry Semantic Conventions 1.41.1. https://github.com/open-telemetry/semantic-conventions/tree/v1.41.1/docs. Version 1.41.1; accessed: 2026-06-19. [23] David Oppenheimer, Archana Ganapathi, and David A. Patterson. 2003. Why Do Internet Services Fail, and What Can Be Done About It?. In 4th USENIX Symposium on Internet Technologies and Systems (USITS 03). USENIX Association, Seattle, WA, USA, 14 pages. https://www.usenix.org/conference/usits-03/whydo-internet-services-fail-and-what-can-be-done-about-it [24] Claus Pahl and Pooyan Jamshidi. 2016. Microservices: A Systematic Mapping Study. In Proceedings of the 6th International Conference on Cloud Computing and Services Science (CLOSER 2016). SCITEPRESS, Rome, Italy, 137–146. doi:10.5220/ 0005785501370146 [25] Benjamin H. Sigelman, Luiz André Barroso, Mike Burrows, Pat Stephenson, Manoj Plakal, Donald Beaver, Saul Jaspan, and Chandan Shanbhag. 2010. Dapper, a Large-Scale Distributed Systems Tracing Infrastructure. Technical Report dapper2010-1. Google, Inc. https://research.google.com/archive/papers/dapper-20101.pdf [26] Jacopo Soldani, Damian Andrew Tamburri, and Willem-Jan van den Heuvel. 2018. The Pains and Gains of Microservices: A Systematic Grey Literature Review. Journal of Systems and Software 146 (2018), 215–232. doi:10.1016/j.jss.2018.09.082 [27] Leslie G. Valiant. 1979. The Complexity of Enumeration and Reliability Problems. SIAM J. Comput. 8, 3 (1979), 410–421. doi:10.1137/0208032 [28] Olaf Zimmermann. 2017. Microservices Tenets: Agile Approach to Service Development and Deployment. Computer Science – Research and Development 32, 3–4 (2017), 301–310. doi:10.1007/s00450-016-0337-0