Replication-Aware Placement of Functions and Data in the Edge-Cloud Continuum Dario d’Abate1, Matteo Cenzato , Matteo Briscini1, Arianna Dragoni1, and Alessandro Margara1
arXiv:2609.18932v1 [cs.DC] 16 Sep 2026
1
Politecnico di Milano, Milan, Italy {dario.dabate, arianna.dragoni, alessandro.margara}@polimi.it {matteo.cenzato, matteo.briscini}@mail.polimi.it
Abstract. Function-as-a-Service (FaaS) has emerged as the prominent programming model for the edge-cloud continuum. FaaS inherently decouples stateless functions from their persistent state. We study how to jointly schedule functions and place data to minimize client latency, considering data replication under heterogeneous consistency requirements. We introduce a Binary Linear Programming (BLP) model to compute optimal placements, establishing a rigorous theoretical baseline. Since the BLP scales cubically with the infrastructure nodes, we propose a topology-aware greedy heuristic that efficiently approximates the optimal solution. Our evaluation shows that the heuristic achieves near-optimal placement quality at a fraction of the computational cost, making it suitable for periodic system reconfigurations.
1
Introduction
Cloud computing has long been the de facto target for deploying applications, offering managed environments with virtually unlimited resources. However, the recent emergence of the edge-cloud continuum has fragmented the computing infrastructure landscape [2]. Edge devices, deployed close to end users, enable lower latencies for applications that are sensitive to response times [11]. This is crucial for domains like autonomous driving and industrial IoT, where milliseconds matter. A dominant paradigm for the edge-cloud continuum is serverless computing [5], specifically Function-as-a-Service (FaaS), where managed runtimes handle the scaling and placement of application functions across available nodes. The FaaS model is inherently stateless: in cloud environments, when applications require persistent state, this is delegated to external data stores co-located in the same data center. When functions execute at the edge, accessing a remote cloud-hosted store incurs prohibitive latency, negating the benefits of edge deployment [11]. Removing this limitation gives rise to a challenging optimization problem. In stateful serverless, we must decide not only where to execute each function (function scheduling problem), but also where to place the data items that function accesses (data placement problem). Since multiple functions may access the same data items from different nodes, the placement of each data item involves a trade-off: placing it close to one consumer may penalize another. We refer to the combination of these two decisions as the placement problem. Replication naturally mitigates this trade-off by placing data replicas on various nodes,
2
D. d’Abate et al.
enabling local access. However, replication introduces its own challenges. Additional replicas reduce read latency by bringing data closer to consumers, but updates must be propagated across all copies. Furthermore, different applications impose different consistency requirements on their data, ranging from strong guarantees that synchronize all replicas before serving any read, to weaker guarantees that allow replicas to diverge temporarily and converge over time. A placement framework must therefore account for these consistency semantics, as they fundamentally affect both the feasible placement space and the resulting latency. Existing approaches fail to solve this joint challenge. While some works optimize scheduling without modeling data placement [15, 3], others couple them but neglect variable consistency requirements [4]. Furthermore, existing optimal placement formulations using centralized solvers [1] suffer from prohibitive computational overheads that preclude continuous or periodic scaling. What is missing in the literature is a rigorous evaluation of an optimal joint placement baseline under heterogeneous consistency models and an efficient heuristic capable of approximating this optimum at runtime. In this paper, we address the joint problem of function scheduling and data placement in the edge-cloud continuum under heterogeneous consistency requirements. Our contributions are as follows: (1) We formalize the problem and propose a Binary Linear Programming (BLP) model that jointly optimizes function scheduling and data replica placement under two consistency models: strong replication (SR), and eventual replication (ER). (2) We propose a topology-aware greedy heuristic that approximates the optimal solution efficiently, making it suitable for practical, periodic system reconfigurations. (3) We evaluate both approaches and show that the topology-aware heuristic achieves near-optimal placement quality compared to the BLP model, while reducing the computational cost required to find a solution. The paper is organized as follows. §2 reviews related work. §3 formalizes the placement problem. §4 presents the BLP model. §5 describes the topology-aware greedy heuristic. §6 reports the evaluation results. §7 concludes the paper.
2
Related Work
This section overviews existing approaches focusing on two dimensions: what they model and how they make decisions. Function scheduling without data placement. Several works optimize stateless execution in the edge-cloud continuum without modeling data dependencies. Optimization approaches range from decentralized heuristics using local routing logic (e.g., Cicconetti et al. [3]) to centralized solvers exploiting global capabilities (e.g., Vahabi et al. [15] minimizing energy consumption via ILP, or Baresi et al. [1] modeling multiaccess edge computing infrastructures via MILP). Rausch et al. [9], integrate proximity scores into orchestration frameworks but require manual data annotations. None natively place data, which causes significant latency penalties in stateful scenarios. Joint function scheduling and data placement. Other works recognize that function scheduling and data placement are coupled, but they either exclude replication or ignore different consistency semantics. Nardelli et al. [4] jointly model function offloading and data migration: the offloading part is decentralized, with each node
Replication-Aware Placement
3
deciding based on local knowledge, while data migration assumes a logically centralized migrator. They explicitly leave replication out of their model. Puliafito et al. [8] formulate a centralized MILP that separates the problem into two sequential steps: first allocating stateful microservices whose state is bound to the container, then dispatching invocations to stateless serverless functions whose state remains in the cloud. For the serverless part, data is not placed and replication is not considered. Smith et al. [12] build a platform that routes invocations to clusters holding the required data buckets and supports replication across clusters via asynchronous mirroring (MinIO), but the replication decisions are manual and not automatically optimized. Consistency in stateful serverless. A few platforms address consistency, but primarily at the protocol level rather than a placement variable. Cloudburst [13] leverages dynamic, back-pressure-driven replication and local mutable caches over a key-value store. Pfandzelter et al. [6, 7] integrate the FReD replication middleware to offer multilevel consistency through optimistic replication, but placement remains fully manual and replication targets all designated nodes without cost optimization. Other systems bypass consistency entirely via immutable data models (Lambdata [14]) or treat state migration operationally via locking (LoLa [16]). In all cases, consistency constraints do not guide the systemic decision of where data and functions should be co-optimized.
3
System Model and Problem Statement
Infrastructure. We consider a set N ={n1,...,nN } of heterogeneous nodes spanning the edge-cloud continuum. Each node ni ∈ N is characterized by its computational speed speed i, memory capacity mem i, and storage capacity stor i. Edge-cloud deployments are usually arranged in layered tiers: conventionally Cloud, Fog, and Edge, where each layer may comprise several logical levels [2]. Node density decreases from Edge to Cloud, and traffic typically aggregates uplink toward the root; we therefore model the infrastructure as a hierarchical tree where the Cloud is the root, a logical node with unlimited resources, possibly representing a data-center cluster. The remaining nodes form arbitrary subtrees rooted at the cloud, capturing deployments with any number of intermediate tiers between Cloud and Edge. Nodes are connected through the links of the tree. For every pair of nodes (ni,nj ), we denote by lat ij the network latency between them, computed as the sum of the latencies of the links along the unique path connecting them in the tree, and by ban ij their effective bandwidth, determined by the minimum bandwidth among the links on the same path. We assume symmetric channels, so lat ij =lat ji and ban ij =ban ji. Data retrieval from local storage is considered negligible with respect to network latency. Application Model. Applications are composed of stateful serverless functions. Let F ={f1,...,fF } denote the set of registered functions. Each function f is characterized by a reference execution time ref f and a memory requirement mreq f . When a function is deployed on a node, to serve incoming requests, it incurs this memory footprint mreq f . In our model, this cost is paid only once per node, regardless of the number of concurrent invocations. This captures the shared, read-only memory components that are amortized across multiple concurrent executions on the same host, such as the
4
D. d’Abate et al.
container image layers, the runtime binary, and shared dynamic libraries. End users (clients) invoke functions from anywhere in the hierarchy; the demand is captured by the invocation rate λf,i, which gives the rate at which function f is invoked from node i. We collect all pairs (f,i) with λf,i >0 in the set: I ={(f,i)∈F ×N :λf,i >0}. Scheduling is per pair (f,i) ∈ I, allowing invocations of the same registered function from different sources to be routed independently; when they converge on the same execution node, however, the function is deployed there only once. As data abstraction, we adopt the notion of collection. A collection in our model represents an opaque unit of state whose internal structure is managed by the application or a higher-level middleware: a single collection may wrap a composite data structure (e.g., documents, tables, nested records) or a fine-grained record. What matters for the placement model is the collection as the atomic unit of replication, not its internal layout. Let C ={c1,...,cC } denote the set of collections. Each collection c has a known size size c and a consistency strategy sr c, where sr c =1 denotes strong replication (SR) and sr c =0 denotes eventual replication (ER). Functions access the collections they require either locally, when co-located on the same node, or remotely, by fetching data from another node at the cost of additional network latency. The set of collections accessed by each function, as well as the type of access (read or write), must be known statically for a given problem instance; in practice, this information can be derived from static annotations provided by the developer or automated code analysis. The access relation is modeled through the parameter access c,f ; we write Cf ={c∈C :access c,f =1} for the set of collections accessed by function f. A function is classified as read-only (read f =1) if all its accesses are reads, and as a writing function (read f =0) if it performs at least a write access. Consistency Strategies. Even within a single application, different collections may require different consistency guarantees. Accordingly, each collection is associated with one of two consistency strategies, which determine how it can be replicated and accessed. We refer to collections managed under each strategy as SR collections (sr c =1) and ER collections (sr c =0), respectively. Strong Replication (SR). Under SR, collections can be replicated across multiple nodes while preserving a total order on write operations. We model this guarantee through a single-leader protocol: one replica per collection is designated as the leader and serves all writes, while any replica can serve reads. The leader propagates updates to followers asynchronously, outside the critical path of function invocations. This is the most widely adopted design for strong consistency in modern data stores. We impose two constraints on functions that access SR collections. First, each function accesses at most one SR collection (alongside any number of ER collections). Second, a function that accesses an SR collection must execute on a node that holds a replica of that collection; specifically, a writing function must be co-located with the leader replica, while a read-only function can access any local replica. These constraints are motivated by the prohibitive cost of cross-collection coordination in geo-distributed environments. Traditional strong consistency across independent collections requires global coordination protocols, which impose synchronous barriers out of scale with edge-cloud latencies. Restricting each function to a single SR collection eliminates this need, and is in line with the design decisions of many distributed databases, such as Cassandra. Moreover, leader co-location avoids remote synchronous round-trips.
Replication-Aware Placement
5
Eventual Replication (ER). Under ER, collections can be replicated without a designated leader. Any replica can serve both reads and writes, with updates propagating asynchronously and conflicts resolved through application-level policies (e.g., lastwriter-wins, CRDTs [10]). Because eventual consistency does not enforce a total order on operations, there is no transactional scope to bound: functions are free to access multiple ER collections within a single invocation. Likewise, we relax the co-location requirement: a function may execute without local copies of all its ER collections, fetching missing ones from remote replicas at the cost of additional retrieval latency. Fault tolerance. At least one replica of each collection must persist in the cloud as a recovery baseline. Beyond this, fault tolerance (node failures, leader re-election) is outside the scope of this work. Placement Problem. Given the infrastructure, the set of registered functions with their invocation statistics, and the set of collections with their consistency strategies and access relations, the placement problem consists of two coupled decisions: (1) data placement: on which nodes to place each collection and its replicas, and (2) invocation scheduling: on which node to execute each function invocation originated from a source node. These decisions are tightly connected: where collections are placed constrains where functions can run, and where functions run determines the cost of accessing remote collections (under ER). The primary goal is to minimize the expected invocation latency, which comprises the network delay between the client and the execution node, the function execution time, and, under ER, the cost of fetching collections that are not locally available. At the same time, replication must be kept under control: placing replicas on every node would trivially eliminate remote access latency, but at the cost of saturating the limited storage of edge nodes. The placement must therefore balance data proximity against resource consumption, subject to the finite memory and storage capacity of each node and the co-location requirements imposed by the chosen consistency strategy.
4
Centralized Model
This section formalizes the placement problem (§3) as a BLP. Our formulation handles both SR and ER collections: the sr c parameter activates the appropriate constraints and latency terms. For convenience, we partition the collections accessed by function f into CfSR = {c ∈ Cf : sr c = 1} and CfER = {c ∈ Cf : sr c = 0}, and define the global sets C SR and C ER analogously. As discussed in §3, we require |CfSR| ≤ 1 for every f. Similarly, we partition functions into read-only Fr = {f ∈ F :read f =1} and writing Fw ={f ∈F :read f =0}. Decision Variables and Auxiliary Indicators. The formulation uses four families of primary binary decision variables, encoding the placement, scheduling, leader election, and routing choices. Specifically: xc,j =1 iff a replica of c is placed on j, wf,i,j =1 iff f from i is scheduled on j, lc,j = 1 iff j holds the leader of c, and rf,i,c,j,a = 1 iff the invocation of f from i, executing on j, fetches c from a.
6
D. d’Abate et al.
xc,j ∈{0,1}
∀c∈C,j ∈N ,
wf,i,j ∈{0,1}
∀(f,i)∈I,j ∈N ,
lc,j ∈{0,1}
∀c∈C SR ,j ∈N ,
rf,i,c,j,a ∈{0,1}
(1)
∀(f,i)∈I,c∈CfER ,j ∈N ,a∈N \{j}.
Two binary auxiliary decision variables (hereafter auxiliary indicators) track derived states and linearize logical dependencies: yf,j =1 iff at least one invocation of f is scheduled on j, and zf,i,c,j =1 iff f runs on j and c is not locally available. yf,j ∈{0,1} zf,i,c,j ∈{0,1}
∀f ∈F,j ∈N ,
∀(f,i)∈I,c∈CfER ,j ∈N .
(2)
yf,j lets the memory capacity constraint (Eq. 11) charge mreq f exactly once per node, while zf,i,c,j captures the nonlinear product wf,i,j ·(1−xc,j ), linearized via the McCormick envelopes (Eq. 10). Objective Function. The objective minimizes the average invocation latency, i.e., the mean latencyP over all pairs (f,i)∈I, each weighted by its rate λf,i. Since traffic is stationary, Λ= (f,i)∈I λf,i is constant, so minimizing T/Λ reduces to minimizing the rate-weighted total T . We formalize the placement objective as a lexicographic objective function (Eq. 3): first the model minimizes the rate-weighted total latency T , then selects the placement with the lowest storage footprint S. Both are normalized to [0,1] using theoretical worst-case bounds T max and S max. The rate-weighted total latency T decomposes into an execution component Texec and a retrieval component Tretr, both linear in the decision variables w and r: T S lexmin T max , Smax ,
T =Texec +Tretr .
(3)
Texec aggregates per-invocation execution latency, weighted by the corresponding rate λf,i (Eq. 4). The formulation assumes a sequential execution model in which communication and computation stages are not overlapped. Therefore, the per-invocation exec latency tf,i,j is obtained by summing the round-trip network latency between source node i and execution node j and the on-node computation time: Texec =
exec (f,i)∈I,j∈N λf,i tf,i,j wf,i,j ,
P
exec tf,i,j =2lat i,j +ref f /speed j
∀(f,i)∈I,∀j ∈N .
(4)
Bandwidth is omitted: invocation payloads are assumed negligible compared to the collection data transferred during retrieval. Tretr aggregates per-fetch retrieval latency, again weighted by λf,i (Eq. 5). The perfetch cost is the round-trip latency plus the transfer time of the collection over the available bandwidth, and depends only on the link (j,a) once j is fixed: Tretr =
retr ER ,j∈N ,a∈N \{j} λf,i tc,j,a rf,i,c,j,a , (f,i)∈I,c∈Cf
P
retr tc,j,a =2lat j,a +size c /ban j,a
∀c∈C ER ,∀j ∈N ,∀a∈N \{j}.
(5)
Replication-Aware Placement
7
This component is non-zero only for ER accesses: SR collections are guaranteed locally available by the co-location constraints (Eq. 9). The worst-case rate-weighted latency T max (Eq. 6) assumes, for each (f,i), the most expensive execution node and, for each ER collection, the most expensive retrieval source. The total storage cost S (Eq. 7) aggregates the size of all replicas across all nodes, and its worst-case bound S max corresponds to replicating every collection on every node: T max =
P
(f,i)∈I λf,i maxj∈N
S=
exec P retr tf,i,j + c∈CER maxa∈N \{j} tc,j,a , f
S max =|N |·
P
c∈C,j∈N size c xc,j ,
P
c∈C size c .
(6) (7)
Constraints. Constraints fall into four groups. 1. Structural constraints. Each invocation is scheduled on exactly one node; the presence indicator yf,j activates iff f has at least one invocation on j; every collection has at least one replica: P
j∈N wf,i,j =1
∀(f,i)∈I,
yf,j ≥wf,i,j ∀(f,i)∈I,∀j ∈N , P yf,j ≤ i:(f,i)∈I wf,i,j ∀f ∈F,∀j ∈N , P ∀c∈C. j∈N xc,j ≥1
(8)
2. SR-specific constraints. Each SR collection has exactly one leader, co-located with a replica. Read-only invocations must execute where a replica exists; writing invocations must execute on the leader: P
j∈N lc,j =1
lc,j ≤xc,j
∀c∈C SR ,
∀c∈C SR ,∀j ∈N ,
wf,i,j ≤xc,j
∀(f,i)∈I with f ∈Fr ,∀c∈CfSR ,∀j ∈N ,
wf,i,j ≤lc,j
∀(f,i)∈I with f ∈Fw ,∀c∈CfSR ,∀j ∈N .
(9)
3. ER-specific constraints. The miss indicator z is linearized via McCormick envelopes; on a miss, exactly one provider is selected, and only nodes holding a replica can serve as providers: zf,i,c,j ≤wf,i,j ,
zf,i,c,j ≤1−xc,j ,
zf,i,c,j ≥wf,i,j +(1−xc,j )−1, P a∈N \{j} rf,i,c,j,a =zf,i,c,j ,
(10)
rf,i,c,j,a ≤xc,a , ∀(f,i)∈I,∀c∈CfER ,∀j ∈N ,∀a∈N \{j}.
4. Resource constraints. Stored replicas must fit the per-node storage limit; the memory footprint of deployed functions must fit the per-node memory:
8
D. d’Abate et al.
P size c xc,j ≤stor j ∀j ∈N , P c∈C mreq ∀j ∈N . f yf,j ≤mem j f∈F
(11)
Model Size. All constraints and both objective components are linear in the decision variables, making the formulation a BLP with a lexicographic objective. The routing variables rf,i,c,j,a dominate the model size with O(|I| · |C ER| · |N |2) entries in the worst case. In practice the number is significantly smaller: z and r are instantiated only when access c,f =1 and sr c =0, and each function typically accesses only a small subset of collections. For further tractability, the number of replicas per collection can be bounded by a constant Rmax (e.g., Rmax = 3), reducing routing variables to O(|I|·|C ER|·|N |·Rmax): P
j∈N xc,j ≤Rmax
5
∀c∈C.
(12)
Topology-Aware Heuristic
While the BLP yields optimal solutions, its variable count grows as O(|I|·|C ER|·|N |2), making it impractical for large instances or periodic reconfiguration. We propose a single-pass topology-aware greedy heuristic (hereafter TA) that exploits the hierarchical tree infrastructure. The algorithm involves four sequential phases, each producing a family of decision variables. Feasibility is maintained by offloading excess storage and memory demands up the tree to the root, which we model as a cloud with virtually infinite resources. 1. Collection placement. We place at most Rmax replicas per collection (with Rmax the same bound used in the BLP). For each collection c, we rank nodes by their aggregate access pressure, defined as the sum of invocation rates λf,j over all functions f that read or write c. The top-ranked nodes host the replicas; when a candidate lacks residual storage, the replica is pushed up the tree until a node with sufficient capacity is found. Collections with zero access pressure are placed directly at the cloud, sparing the storage of lower nodes. 2. Leader election. Among the replicas of each SR collection, we elect as leader the one hosted by the node with the highest aggregate write pressure (the sum of λf,j over the writing functions accessing c). Co-locating the leader with the heaviest writers eliminates a synchronous remote round-trip on the most frequent updates. Ties are broken by node index for determinism. 3. Function scheduling. Each invocation (f,i) ∈ I is assigned an execution node according to f’s consistency requirements. If f accesses an SR collection, the co-location constraints (Eq. 9) force execution on the nearest SR replica (reads) or on the leader (writes); if that node lacks memory, the entire SR cluster, the replica plus all invocations anchored to it, migrates upward together to the first ancestor with enough capacity. If f depends only on ER collections, the algorithm targets the Lowest Common Ancestor (LCA) of the nearest replicas of each required collection, walking up the tree if the LCA is full. Functions with no data dependency are scheduled at the source
Replication-Aware Placement
9
node i, again with upward fallback. The memory footprint of f is charged at most once per node, so repeated invocations of the same function on the same node are free. 4. Remote fetch routing. For each ER access missing at the execution node, the provider is selected as the nearest replica by hop count. Complexity. Each phase runs in polynomial time. The dominant cost is incurred by scheduling and routing, which scan all nodes once per accessed collection for every invocation. The overall complexity is O(|I|·|C|·|N |), which is at most O(|F|·|C|·|N |2) since |I|≤|F|·|N |.
6
Evaluation
We structure the evaluation around two research questions. RQ1: How do the problem dimensions (nodes, collections, functions) and the consistency strategy affect the scalability of the BLP in terms of solve time and memory footprint? How does TA scale along the same problem dimensions? RQ2: How closely does TA approximate the BLP optimum in terms of total latency and total storage? How does it compare to naive baselines? RQ1 characterizes the scalability of the two approaches on the same workloads, identifying where BLP becomes intractable and TA keeps producing solutions. RQ2 evaluates, on instances where both complete, how closely TA approximates the optimum, and quantifies the benefit of exploiting topology and data locality against two naive baselines, defined later in this section. Experimental Setup. The BLP, TA, and the baselines are implemented in C++. The BLP uses the Concert Technology of IBM ILOG CPLEX for model construction and solving. All experiments were conducted on a server equipped with a 16-core AMD Ryzen 9 9950X processor (32 threads) and 64 GB of DDR5 RAM, running Fedora Server 42. A 600 s timeout is enforced on the BLP solver, while virtual memory is capped at 50 GB. We generate synthetic scenarios using a parametric workload generator. The topology is a balanced k-ary tree whose root acts as the cloud and leaves as edge nodes, with descending hierarchical capacities and ascending local bandwidths. Following §3, the cloud has unlimited resources as a fallback, while edge nodes accommodate 40% of the demand. Network parameters are normally distributed: latency is N (10,2) ms, bandwidth is N (100,20) Mbps, and node speed is N (1.0,0.2), with unconstrained local bandwidth (109 Mbps). Functions are invoked from U{1,3} sources at U(1,10) req/s, have a memory footprint of N (128,32) MB, an execution time of U(1,10) ms, and a 0.8 read ratio. Finally, collections have a size of N (50,10) MB, with each function accessing U{1,3} collections. The dimensions |N |, |F|, |C| and the consistency-related parameters (srRatio, funcSrRatio, Rmax) are varied systematically in subsequent subsections. Scalability. To answer RQ1, we evaluate how BLP and TA scale as we independently vary the number of nodes |N |, functions |F|, and collections |C|. For each dimension we scale one parameter from 10 to 105 while holding the other two fixed at 10. We further vary two orthogonal axes that affect the structure of the problem. The first is the consistency mix of the workload: ER (only eventually-replicated collections), SR
101 100 10 1 10 2 10 2 10 3 10 4
TA
BLP
Time (s)
D. d’Abate et al.
Time (s)
10
Rmax = 1 101
10 1
10 1
||
104
101 100 10 1 10 2
102
| |
10 4 104
101
102
| |
104
101 10 1
10 1 10 12 10 3 10 4 10
10 2 10 3 10 4
10 2
10 2 10 4 102
Rmax = 3
101
102
||
104
102
| |
10 1 10 2 10 3 10 4 104
SR MIX ER
102
| |
104
Fig. 1: Scalability of BLP and TA. (only strongly-replicated), and MIX (50/50). The second is the replication factor: no replication (Rmax = 1) and 3 replicas (Rmax = 3). Each configuration is solved with 10 different random seeds; we measure the median and interquartile range (IQR) of total execution time (model construction plus solving for BLP, single-pass execution otherwise) and maximum Resident Set Size (RSS). Fig. 1 reports the execution time of BLP (top) and TA (bottom) scalability for both replication factors. Each panel plots the median over 10 seeds for ER, MIX, and SR, with vertical error bars indicating the interquartile range (IQR); missing markers exceeded the 600 s timeout or the 50 GB memory cap. Fig. 1 shows that the BLP exhibits asymmetry across the three scaling dimensions. Collections are the most tractable dimension, as each function accesses at most maxAccess collections regardless of |C|, so the number of active routing variables is bounded. Without replication, all three consistency mixes complete |C|=105 within seconds and a few gigabytes of RSS. Replication amplifies the cost, especially for MIX at |C|=104, where the median execution time jumps to over 255 s, and at |C| = 105 MIX exceeds the timeout. When increasing the number of functions, ER and MIX time out already at |F|=103 with no replication and at |F|=102 with three replicas, while SR tolerates one to two orders of magnitude more (|F|=104 without replication, |F|=103 with three replicas). When scaling nodes, ER times out already at |N |=102 regardless of the replication factor. Starting at |N | =103, both ER and MIX exhaust the 50 GB memory cap. This asymmetry reflects two distinct mechanisms: scaling |N | inflates the model directly (the ER routing variable rf,i,c,j,a grows cubically in |N |), while scaling |F| inflates the branch-and-bound search space. The execution time remains low across all dimensions: even the largest instances we explored (|F|=105 or |C|=105) complete in well under 150 ms with RSS below 150 MB, with only minor differences across ER, MIX, and SR. Scaling the number of nodes is the most demanding regime: at |N |=104 with three replicas TA completes all consistency mixes in about 0.4 s using 2.5 GB of RSS, the cost being dominated by the size of the pairwise hop-count matrix pre-computed for routing decisions. The contrast with the BLP is most pronounced on the nodes dimension, where TA completes |N |=104 for all mixes while the BLP exhausts the memory cap already at |N |=103 for ER and MIX. These results answer RQ1: BLP is suitable as an offline optimum reference at small scale, is impractical for runtime use on realistic edge-cloud infrastructures; TA, instead, bounds the search space and thus retains acceptable cost across all the dimensions we explored. TA Evaluation. To answer RQ2, we evaluate the placement quality of TA against the BLP optimum. We complement the comparison with two naive baselines that ignore parts of the problem structure. For all approaches, we measure the rate-weighted
Replication-Aware Placement
0
10 100 103 104 105
||
25 50 10 100 103 104 105
||
S Diff (%)
250
400
0
T Diff (%)
500
S Diff (%)
T Diff (%)
750
200 0
10
100
103
| |
104
0 50 10
100
103
| |
104
11 TA-ER TA-MIX TA-SR CD-ER CD-MIX CD-SR CO-ER CO-MIX CO-SR
Fig. 2: Solution quality comparison, 3 replicas (Rmax =3). total latency T and the total storage cost S. A Cloud-only (CO) policy places a single replica of every collection at the cloud, schedules every invocation there, and elects the cloud as leader for all SR collections. It represents the canonical FaaS deployment, with compute and data co-located within the data center. A Cloud-data (CD) policy retains CO data placement but executes ER-only invocations at the edge (walking upward in the tree to the first ancestor with sufficient capacity if needed); SR invocations are forced to the cloud by co-location, and every ER access from a non-cloud node triggers a remote fetch from the cloud. CD captures the naive extension of FaaS to the edge, where compute follows the user, but data stays centralized. For each approach, we measure the percentage difference on S and T relative to the BLP optimum on the same instance. We focus on two representative scenarios that bound the spectrum of problem difficulty: scaling collections and scaling nodes, both with 3-replicas factor. Each panel reports per-instance distributions over 10 seeds. BLP-infeasible configurations are excluded. Fig. 2 reports the comparison when scaling collections (left) and nodes (right): TA approaches the BLP optimum across the explored range, while the relative cost of CO and CD depends on the consistency mix. When scaling collections, the latency gap of TA stays small across consistency mixes: TA-SR is within 10% from the smallest scale and converges to zero from |C|=102 onwards; TA-ER and TA-MIX medians start around 75% at |C|=10 and drop below 20% from |C|=102, with a wider IQR reflecting the variance introduced by ER routing decisions. The storage gap of TA is within 10% at small scale and collapses to zero as the workload grows. Both baselines use a single replica, so they consume less storage than BLP at small scale, converging as |C| grows. On SR, CD and CO coincide (∼200% above BLP). On ER/MIX, CD lies above CO (500–600% vs. 200–300%): CD executes ER functions at the edge, saving the client-to-compute hop, but each ER access triggers a cloud fetch, and the cumulative cost of multiple fetches per invocation exceeds CO’s single centralized round-trip. When scaling nodes the same ordering holds but with smaller magnitudes. The number of comparable points is smaller, since the BLP only completes up to |N | = 102 for ER and MIX and up to |N | = 104 for SR; further configurations are excluded as discussed in §6. TA-SR latency remains tightly bounded around 10% above the BLP; TA-ER and TA-MIX show a larger gap (70–100% at |N |=102) with wider IQR. TA storage remains within 10% across all mixes. CD and CO again coincide on SR (∼200%); on ER/MIX, CD stays in the 300–400% range while CO is at 100–200%, confirming the pattern observed on collections. These results answer RQ2: TA produces solutions whose latency and storage remain within a small percentage of the BLP optimum on tractable instances. TA also substantially outperforms both baselines. The CD-CO comparison further shows that pushing computation to the edge without colocating data does not exploit topology: only joint optimization of compute and data placement yields the latency benefits of edge deployment.
12
7
D. d’Abate et al.
Conclusions
We addressed joint function scheduling and data placement in the edge-cloud continuum under heterogeneous consistency requirements, formulating a BLP and proposing a fast topology-aware greedy heuristic. Evaluation shows the BLP becomes intractable beyond a few hundred nodes, while our heuristic scales gracefully, solving 105-element instances in under 150 ms. It produces solutions whose latency and storage are close to the optimum, outperforming alternative baselines. Our formulation targets a static placement for a stationary workload snapshot; addressing runtime dynamics, along with distributed heuristics and validation on real testbeds, is left to future work.
References 1. Baresi, L., Hu, D.Y.X., Quattrocchi, G., Terracciano, L.: NEPTUNE: A comprehensive framework for managing serverless functions at the edge. TAAS 19(1) (2024) 2. Bittencourt, L.F., Rodrigues-Filho, R., Spillner, J., De Turck, F., Santos, J., da Fonseca, N.L., Rana, O., Parashar, M., Foster, I.: The computing continuum: Past, present, and future. Comp. Science Review 58 (2025) 3. Cicconetti, C., Conti, M., Passarella, A.: A decentralized framework for serverless edge computing in the internet of things. TNSM 18(2) (2021) 4. Nardelli, M., Russo, G.R.: Function offloading and data migration for stateful serverless edge computing. In: ICPE. ACM (2024) 5. Nastic, S., Rausch, T., Scekic, O., Dustdar, S., Gusev, M., Koteska, B., Kostoska, M., Jakimovski, B., Ristov, S., Prodan, R.: A serverless real-time data analytics platform for edge computing. Internet Comp. 21 (2017) 6. Pfandzelter, T., Bermbach, D.: Enoki: Stateful distributed FaaS from edge to cloud. In: MiddleWEdge. ACM (2023) 7. Pfandzelter, T., Japke, N., Schirmer, T., Hasenburg, J., Bermbach, D.: Managing data replication and distribution in the fog with FReD. Software: Practice and Experience 53(10) (2023) 8. Puliafito, C., Cicconetti, C., Conti, M., Mingozzi, E., Passarella, A.: Balancing local vs. remote state allocation for micro-services in the cloud-edge continuum. Perv. and Mobile Comp. 93 (2023) 9. Rausch, T., Rashed, A., Dustdar, S.: Optimized container scheduling for data-intensive serverless edge computing. FGCS 114 (2021) 10. Shapiro, M., Preguiça, N., Baquero, C., Zawirski, M.: Conflict-free replicated data types. In: SSS. Springer-Verlag, Berlin, Heidelberg (2011) 11. Shi, W., Cao, J., Zhang, Q., Li, Y., Xu, L.: Edge computing: Vision and challenges. IoT Jour. 3 (2016) 12. Smith, C.P., Jindal, A., Chadha, M., Gerndt, M., Benedict, S.: FaDO: FaaS functions and data orchestrator for multiple serverless edge-cloud clusters. In: ICFEC. IEEE (2022) 13. Sreekanti, V., Wu, C., Lin, X.C., Schleier-Smith, J., Gonzalez, J.E., Hellerstein, J.M., Tumanov, A.: Cloudburst: Stateful functions-as-a-service. VLDB 13(12) (2020) 14. Tang, Y., Yang, J.: Lambdata: Optimizing serverless computing by making data intents explicit. In: CLOUD. IEEE (2020) 15. Vahabi, S., Righetti, F., Vallati, C., Tonellotto, N.: Energy-efficient resource management for real-time applications in faas edge computing platforms. In: UCC. ACM (2023) 16. Wen, Y., Xu, G., Wang, J., Hao, W.: Low-latency state management for real-time tasks in edge serverless. In: ISPA. IEEE (2024)