Brief Announcement: Generative Markov Model for Distributed Computing Systems Alfreds Lapkovskis1 # Department of Computer and Systems Sciences, Stockholm University, Sweden
Ali Beikmohammadi # Department of Computer and Systems Sciences, Stockholm University, Sweden
Sindri Magnússon # Department of Computer and Systems Sciences, Stockholm University, Sweden
Praveen Kumar Donta #
arXiv:2606.03061v1 [cs.DC] 2 Jun 2026
Department of Computer and Systems Sciences, Stockholm University, Sweden
Abstract Emerging distributed computing paradigms, such as the computing continuum, are inherently heterogeneous, stochastic, and complex. Efficiently and effectively utilizing all available resources across the continuum demands a unified formal model of the system. To address this gap, we propose a general framework for modeling distributed computing systems as a generative Markov model, factorized over a structured system state. In our model, the state decomposes into high-dimensional variables, each further factorized over its elements, reflecting the sparse dependency structure inherent to distributed systems. This yields a tractable model enabling simulation, inference, and policy learning over otherwise intractable system states, bridging distributed computing with Markov chain theory and reinforcement learning (RL). We demonstrate our framework through a case study of collaborative AI inference, in which a dedicated server combines resources with those volunteered by service users. Our results show that centralized scheduling becomes a bottleneck at scale, while distributing computation across user devices reduces both latency and server resource consumption. These findings highlight the value of adaptive decision-making in distributed computing systems and demonstrate the framework’s utility for modeling, simulation, and optimization. 2012 ACM Subject Classification Computing methodologies → Modeling methodologies; Computing methodologies → Distributed artificial intelligence; Computing methodologies → Markov decision processes; Computing methodologies → Distributed computing methodologies; Computer systems organization → Distributed architectures Keywords and phrases Distributed computing systems, computing continuum, distributed inference, Markov model Acknowledgements The computations were enabled by resources provided by the National Academic Infrastructure for Supercomputing in Sweden (NAISS), partially funded by the Swedish Research Council through grant agreement no. 2022-06725.
1
Introduction
The cloud computing paradigm dominates artificial intelligence (AI) inference due to its various advantages, including on-demand provisioning, rapid elasticity, and pay-as-you-go pricing [6]. However, serving growing inference demand requires proportionally more infrastructure, which becomes costly at scale and carries a substantial environmental burden [4]. In the age of AI, it is therefore critical to investigate more efficient alternatives. One such alternative, explored actively in the past, is volunteer computing, a paradigm that harnesses idle resources from user devices toward a shared computational goal [7, 5].
1
Corresponding author
2
Generative Markov Model for Distributed Computing Systems
Despite renewed interest [5], systems relying on volunteer contributions still struggle to provide stable quality-of-service (QoS) guarantees due to resource heterogeneity and intermittent user availability [7]. More recently, the focus has shifted toward edge computing and computing continuum, paradigms that integrate diverse resources between user devices and cloud data centers [11]. However, computing continuum systems are complex, and their behavior significantly depends on the underlying dynamic infrastructure. This makes traditional methodologies inadequate for such systems [1]. Consequently, large-scale deployments remain scarce due to both technical and economic barriers [8]. Efficiently and effectively utilizing all available resources across such systems demands a unified formal model that accounts for resource heterogeneity, stochastic availability, and the high dimensionality of system state. Without this model, reasoning about performance trade-offs and optimizing decision-making policies at scale remains difficult. To address this gap, we propose a generative Markov modeling framework for distributed computing systems. Our contributions are as follows. Contribution I. We propose to model distributed computing systems as a generative Markov model, factorized over a structured system state. The state decomposes into high-level variables, each further factorized over its elements, reflecting the sparse dependency structure inherent to distributed systems. This factorized structure makes the model tractable and enables simulation, inference, and policy learning over large and complex system states that would otherwise be computationally infeasible to handle. While general, the framework is primarily motivated by computing continuum systems, whose behavior is complex and infrastructure-dependent. Prior work has investigated formulating specific computing-continuum decision problems as Markov decision processes (MDPs) [2, 10]. Furthermore, our framework shares structural similarities with generic factored MDPs and dynamic Bayesian networks [3, 9]. To the best of our knowledge, however, ours is the first work to model the entire distributed computing system as a generative Markov model, bridging distributed computing with Markov chain theory and RL. We further distinguish our framework through a novel two-level sparse factorization and a modular structure that allows each conditional distribution to be estimated independently using techniques suited to the specific system variable. Contribution II. We demonstrate a concrete instantiation of this framework for collaborative AI inference, combining dedicated server resources with volunteered resources from service users. Under low demand, the server handles inference requests directly, ensuring high QoS. As load grows, computation is progressively offloaded to users within their resource constraints, enabling automatic scaling without proportional growth in infrastructure costs.
2
Proposed Modeling Framework
We first establish a general framework for modeling distributed computing systems, which Sec. 3 then instantiates for collaborative inference. The state of a distributed computing system at time t is a tuple of N ∈ N variables (1)
(N )
st ≜ ⟨vt , . . . , vt (n)
⟩,
(1)
where each vt is a high-dimensional variable with scalar or multi-dimensional elements (n) vt ∈ vt , taking values in a domain specific to that variable. To capture the temporal evolution of the system, we model the sequence of states (st )Tt=0 as a joint distribution, which we refer to as a generative model. To make this tractable, we impose the Markov property, yielding the following.
A. Lapkovskis et al.
3
▶ Definition 1 (Generative Markov Model). A generative Markov model MT of a distributed computing system is a joint distribution over a state sequence (st )Tt=0 at discrete time steps, given by MT (s0 , . . . , sT ) ≜ p(s0 )
T Y
p(st | st−1 ).
(2)
t=1
This form imposes the Markov property, limiting dependence on the immediate previous state, and enables sequential sampling via st ∼ p(· | st−1 ). Treating all system variables as mutually dependent within p(st | st−1 ) is computationally infeasible. The structure of a distributed system, however, ensures that each component evolves based on a small subset of other components rather than global state, which we capture through the following. ▶ Definition 2 (Variable Factor). The variable factor of vt ∈ st is a conditional distribution f (vt ) ≜ p(vt | Pa(vt )),
Pa(vt ) ⊆ st ∪ st−1 ,
(3)
where s−1 ≜ ∅, there exists a topological ordering ≺ on st such that for all v, v′ ∈ st , Q v ∈ Pa(v′ ) implies v ≺ v′ , and p(st | st−1 ) = vt ∈st f (vt ). Furthermore, distributed system variables such as node states or resource allocations are naturally indexed over nodes, tasks, and time, making their elements sparsely dependent. We therefore factor them at the finest granularity permitted by the dependency structure. ▶ Definition 3 (Element Factor). The element factor of vt ∈ vt is a conditional distribution g(vt ) ≜ p(vt | Pa(vt )), such that f (vt ) =
Q
Pa(vt ) ⊆ {v | v ∈ v, v ∈ Pa(vt )},
(4)
vt ∈vt g(vt ).
Applying both levels of factorization, the model takes its fully expanded form Y Y Y MT (s0 , . . . , sT ) ≜ g(vt ).
(5)
0≤t≤T vt ∈st vt ∈vt
The following section defines the concrete variables and factors for the collaborative distributed inference setting.
3
Case Study: Collaborative Distributed AI Inference
We instantiate the generative Markov model of Definition 1 for collaborative AI inference. Users i ∈ I and a dedicated server v0 form the set of nodes V = I ∪ {v0 }, each equipped with resources of types r ∈ R. The system serves |K| inference task types, each decomposing into independent subtasks s ∈ Sk . Users i both submit requests for k and contribute idle resources to execute others’ (i′ ∈ I) subtasks. Decision-making is governed by two policy factors, the scheduler π and executor ς, producing actions ut ≜ ⟨utπ , utς ⟩. We model discrete time steps of 1 s. The concrete system state instantiating Eq. (1) is st = ⟨ot , qt , at , xt , yt , ct , dt , ut ⟩.
(6)
4
Generative Markov Model for Distributed Computing Systems
State Variables User availability ot determines whether a user submits requests and contributes resources. It depends on the previous availability ot−1 and duration dot measuring time since the last state change, giving Pa(ot ) = {ot−1 , dot } and Pa(dot ) = {dot−1 , ot−1 }. Each online user may have at most one active inference request. The request state qt ∈ Q|I| , where Q = K ∪ {k0 } with k0 denoting no active request, depends on qt−1 and ot , giving Pa(qt ) = {qt−1 , ot , dqt }. A duration variable dqt additionally depends on execution states yt−1 to detect request completion, giving Pa(dqt ) = {dqt−1 , qt−1 , ot , yt−1 }. Nodes dedicate bounded resources at to the system. Offline users contribute no resources, so ot ∈ Pa(at ). Resource trajectories are autocorrelated in practice, violating the first-order Markov assumption, so we condition on a history ãt−1 ≜ [at−1 , . . . , at−H ] of size H, implicitly included in st , giving Pa(at ) = {ãt−1 , ot }. Subtask execution requires its associated data to be first downloaded to the executing node, tracked by readiness state xt , after which subtasks progress through execution phases tracked by execution state yt . Both variables follow the same pattern: auxiliary variables x̂t , ŷt (treated as deterministic intermediate quantities) apply actions ut−1 to xt−1 , yt−1 , conditioned on ot (since offline nodes cannot progress), giving, e.g., Pa(x̂t ) = π,x ς,x {xt−1 , ot , ut−1 , ut−1 }. Durations dxt , dyt capture the pace of the current phase based on ct , giving e.g. Pa(dxt ) = {dxt−1 , x̂t , cxt }. The actual xt , yt resolve from the auxiliary x̂t , ŷt and dxt , dyt , advancing when the duration signals phase completion. Resource consumption ct ≜ ⟨cxt , cyt ⟩ covers data transfers and subtask execution over RX , RY ⊆ R respectively. Both components are modeled jointly per node since concurrent subtasks share resources non-additively, e.g., bandwidth is split rather than replicated. Consumption is bounded by at ; xt , yt determine consuming subtasks, dxt , dyt identify coscheduled subtasks for batch execution of subtasks, and history terms c̃xt−1 , c̃yt−1 account for autocorrelation, giving Pa(cxt , cyt ) = {c̃xt−1 , c̃yt−1 , at , x̂t , ŷt , dxt−1 , dyt−1 }. Scheduler and Executor Policies The scheduler π(utπ | st \ ut ) runs on the server, deciding on actions for subtask downloads and execution assignments across nodes (utπ = ⟨utπ,x , utπ,y ⟩). The executor ς(utς | st \ ut ) runs on each node, enforcing local resource constraints via aborts and pauses (utς = ⟨utς,x , utς,y ⟩). Executor actions take priority over scheduler actions to guarantee constraint compliance. Dimensionality and Element Factorization System variables are high-dimensional and are indexed over the relevant system entities, e.g., xt ∈ X |V|×|K|×Smax tracks readiness per node, task, and subtask (Smax ≜ maxk |Sk |), while yt ∈ Y |I|×|V|×|K|×Smax is further indexed by requesting user. Most variables, however, evolve independently across these entities, so f (vt ) factorizes into sparse element factors g(vt ), e.g., assuming availability independence across Q users, f (ot ) = i∈I p(ot,i | ot−1,i , dot,i ).
3.1
Problem Formulations
Given the generative Markov model of the collaborative inference system developed before, here we formulate the optimization problems that govern decision-making within it. ▶ Definition 4 (Scheduler Policy Optimization). Given a generative Markov model MT with T → ∞, a fixed executor ς, a reward function r(st ), find a scheduler policy π ∗ such that " # T X 1 π π ∗ = arg max lim inf E r(st ) | s0 , u0:t−1 ∼π . (7) π T →∞ T t=1
A. Lapkovskis et al.
5
The reward r(st ) captures QoS in terms of serving latency. Specifically, r(st ) ≜ −1⊤ δ t ,
(8)
where δ t ≜ δ(qt , dqt ) ∈ {0, 1}|I| are per-user latency increments. This is an average-reward RL problem [12, 13]. While approachable via existing methods, its solution in this context is deferred to future work. ▶ Definition 5 (Dedicated Resource Optimization). Given fixed scheduler and executor policies, a nominal resource vector a† parametrizing the server resource distribution p(at,r,v0 | at−1,r,v0 ; a†,r ) for all r ∈ R, significance levels ϵk ∈ (0, 1), and per-type latency thresholds τk , find a†∗ such that a†∗ = arg min ∥a† ∥w a†
s.t.
(9) ck (st )Tt=0 ∼ MT ≥ 1 − ϵk ,
∀k ∈ K,
P |R| where ∥a† ∥w = r∈R wr a†,r is a weighted ℓ1 norm with per-resource cost weights w ∈ R>0 , and the chance constraints are defined per request type k as ck (st )Tt=0 ≜ P dqt,i ≤ τk | qt+1,i = k0 , qt,i = k . (10) The nominal resource vector a† is necessary because fixing server resources in practice is not always feasible, as uncontrollable factors cause actual availability to deviate from any intended value. The chance constraints ensure that reducing dedicated resources does not degrade QoS below an acceptable level for any request type, with separate thresholds τk allowing different latency requirements per task type.
3.2
Preliminary Results and Discussion
Evaluation We implemented our model to simulate a distributed inference system. We modeled ot , qt , dot and dqt using parametric distributions, and fitted at , ct , dxt , dyt on pre-collected device measurements, assuming i.i.d. user behavior and resources. We defined four task types: light and heavy, each with 5 or 10 subtasks, sampled with probabilities {0.4, 0.3, 0.2, 0.1}. We evaluated two scheduler policies: centralized, scheduling all subtasks on the server, and distributed, distributing subtasks uniformly across the server and online users. The scheduler proactively downloads at most one subtask per online user at a time, subject to sufficient storage, with subtask sizes averaging 21% of allocated user storage (std. 23%). We compared the policies across varying server capacities a† and user counts |I|, measuring P99 latency and server resource consumption over a ≈28 h simulated window. Latency Analysis Fig. 1 shows P99 latencies estimated from simulation. As the number of users grows, the distributed policy progressively outperforms the centralized one: beyond a certain user count, the server becomes a bottleneck under centralized scheduling, and even naive subtask distribution across user nodes yields lower latency. This demonstrates the practical feasibility of distributing inference subtasks to user devices. The distributed policy serves as an informative lower bound on achievable performance. The results suggest that an effective policy would dynamically shift computation toward user devices as load increases, concentrating it on the server under lighter demand. Designing and evaluating such policies, however, requires a formal system model. This is precisely where our contribution lies. Our proposed framework enables simulation under varying conditions,
Generative Markov Model for Distributed Computing Systems
200 100 100
1,000
300 200 100
10,000
100
User Count
1,000
200 150 100 50
10,000
100
User Count
1,000
160 120 80 40
10,000
100
User Count
1,000
10,000
User Count
(c) Centralized 50×
(d) Centralized 100×
500
500
200
160
400 300 200 100 100
1,000
10,000
400 300 200 100 100
User Count
1,000
P99 Latency (s)
(b) Centralized 30× P99 Latency (s)
(a) Centralized 10× P99 Latency (s)
P99 Latency (s)
400
P99 Latency (s)
300
P99 Latency (s)
500
Request type Light 10 Heavy 10 Light 5 Heavy 5
400
P99 Latency (s)
P99 Latency (s)
500
150 100 50
10,000
100
1,000
User Count
(e) Distributed 10×
10,000
120 80 40 100
User Count
(f) Distributed 30×
1,000
10,000
User Count
(g) Distributed 50×
(h) Distributed 100×
Figure 1 P99 request latency estimated over 100,000 simulation steps (≈28 h) for four inference task types. The x-axis denotes the user count |I|, where each user independently transitions between online and offline states over time. Rows correspond to scheduling policy: centralized (a–d) and distributed (e–h). Columns correspond to server capacity relative to a user node: 10, 30, 50, 100×.
policy evaluation, and optimization (cf. Definition 4) via RL methods, as the factorized Markov structure is directly compatible with the RL framework. Its modular nature further allows extending the model to new resource types, task structures, or node behaviors without redesigning the framework. Resource Efficiency Fig. 2 shows dedicated server resource consumption with 1,000 users. The distributed policy consistently achieves lower CPU and memory usage across all server capacity levels. Notably, at 1,000 users both policies yield comparable P99 latency (Fig. 1), yet the distributed policy does so at considerably lower server resource cost. Offloading subtasks to user devices thus provides efficiency gains beyond latency alone, motivating Definition 5: given a fixed policy, one can minimize nominal server resources subject to QoS constraints, directly reducing infrastructure costs. 3000
20
Centralized Distributed
2000
Memory (GB)
CPU (%)
6
1000 0
10
30
50
Server Capacity
100
15 10 5 0
10
30
50
100
Server Capacity
Figure 2 Server CPU and memory usage estimated over 100,000 simulation steps (≈28 h) under centralized and distributed scheduling policies, with user count |I| fixed at 1,000. Curves show the mean, and shaded regions show the standard deviation. The x-axis denotes server capacity relative to a user node.
4
Conclusion
Our case study demonstrates that the proposed framework can model sophisticated distributed computing systems with practical relevance. The results show that centralized scheduling
A. Lapkovskis et al.
becomes a bottleneck at scale, while distributing computation across user devices reduces both latency and server resource consumption, highlighting the value of adaptive decisionmaking. Developing and optimizing such decision-making is infeasible without a formal system model, which our framework provides through a uniform probabilistic structure over heterogeneous system components. Each component can be modeled independently, and the sparse factorization keeps the model tractable, while naturally bridging distributed computing systems with Markov chain theory and RL. Future work will focus on real environment validation, investigating scalability, and scheduler and resource allocation optimization. References 1
2
3 4 5
6
7 8
9
10
11
12 13
Schahram Dustdar, Victor Casamayor Pujol, and Praveen Kumar Donta. On distributed computing continuum systems. IEEE Transactions on Knowledge and Data Engineering, 35(4):4092–4105, 2023. doi:10.1109/TKDE.2022.3142856. Paris Flegkas, Antonis Tseos, Vasilis Sourlas, and Angelos Amditis. A multiobjective dqn framework for dynamic service orchestration in the computing continuum. In 2025 IEEE Conference on Network Function Virtualization and Software-Defined Networking (NFV-SDN), pages 1–6, 2025. doi:10.1109/NFV-SDN66355.2025.11349403. Carlos Guestrin, Daphne Koller, Ronald Parr, and Shobha Venkataraman. Efficient solution algorithms for factored mdps. Journal of Artificial Intelligence Research, 19:399–468, 2003. Pengfei Li, Jianyi Yang, Mohammad A. Islam, and Shaolei Ren. Making ai less ’thirsty’. Commun. ACM, 68(7):54–61, June 2025. doi:10.1145/3724499. Peizhe Ma, Saurabh Garg, and Mutaz Barika. Research allocation in mobile volunteer computing system: Taxonomy, challenges and future work. Future Generation Computer Systems, 154:251–265, 2024. URL: https://www.sciencedirect.com/science/article/pii/ S0167739X24000128, doi:10.1016/j.future.2024.01.015. Peter M. Mell and Timothy Grance. Sp 800-145. the nist definition of cloud computing. Technical report, National Institute of Standards & Technology, Gaithersburg, MD, USA, 2011. Tessema M. Mengistu and Dunren Che. Survey and taxonomy of volunteer computing. ACM Comput. Surv., 52(3), July 2019. doi:10.1145/3320073. Nitinder Mohan, Lorenzo Corneo, Aleksandr Zavodovski, Suzan Bayhan, Walter Wong, and Jussi Kangasharju. Pruning edge research with latency shears. HotNets ’20, page 182–189, New York, NY, USA, 2020. Association for Computing Machinery. doi:10.1145/3422604.3425943. Kevin P. Murphy. Dynamic Bayesian networks: Representation, inference and learning. PhD thesis, 2002. Copyright - Database copyright ProQuest LLC; ProQuest does not claim copyright in the individual underlying works; Last updated - 2026-05-06. URL: https://ezp.sub.su.se/login?url=https://www.proquest.com/dissertations-theses/ dynamic-bayesian-networks-representation/docview/304697812/se-2. Mohammad R Pour-Hosseini, Mahdi Abbasi, Atefeh Salimi, Erik Elmroth, Hassan Haghighi, Parham Moradi, and Bahman Javadi. Tiny machine learning models for autonomous workload distribution across cloud-edge computing continuum. Cluster Computing, 28(6):381, 2025. Victor Casamayor Pujol, Praveen Kumar Donta, Andrea Morichetta, Ilir Murturi, and Schahram Dustdar. Edge intelligence—research opportunities for distributed computing continuum systems. IEEE Internet Computing, 27(4):53–74, 2023. doi:10.1109/MIC.2023. 3284693. Martin L Puterman. Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons, 2014. Richard S. Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction. A Bradford Book, Cambridge, MA, USA, 2018.
7