small $R\sigma$ contexts (e.g., Mall), indeed, a small $R\sigma$ means that latencies are close to the mean, thus a well-calibrated $m/n$ is sufficient to absorb few late messages.

In conclusion, the $m/n$ ratio should not be underestimated and the query deadline should be fixed larger than $\bar{L} \times |hops|$ where $|hops|$ is the number of hops in the query plan (in this case, 4: Data Contributor → Snapshot Builder → Computer → Computing Combiner → Recipient). Both $m/n$ and the deadline should be overestimated when the OppNet latencies have a large $R\sigma$. Thus, the query deadline should be fixed (for a 4 hops query) around 2 days for DomY and 2-3 hours for Mall, values that are quite reasonable given our application context.

## 6.3 Quality of Iterative Computation

In this third subsection, we examine the Edgelet iterative execution of the algorithms presented in subsection 4.2.3. Our approach is empirical: we aim to demonstrate the relevance of the Iterative Brute-Force method by verifying the quality of the results obtained compared with a centralized execution.

<figure><img src="image_20.png" /><figcaption>Figure 19: Heartbeat Execution Quality
(Apriori and K-means)</figcaption></figure>

We first simulate the iterative algorithms Apriori and K-means, considering synthetic and real data sets used to evaluate their quality (e.g., [16] for Apriori). In these Edgelet executions, we employed a QEP with a horizontal partitioning, consisting of $n=10$ partitions and $m=10$ additional partitions. We systematically measure the quality of Edgelet executions against centralized fault-free executions (y-axis on Figure 19). More precisely, for Apriori, we compare the association rules generated after frequent item mining in Edgelet executions to those obtained in centralized ones and use the precision/recall metrics to assess the comparison. Similarly, for K-means, we compute the Percentage Change Inertia (PCI), i.e., the percentage change between the Edgelet inertia (intra-cluster variance) and the centralized one. The x-axis indicates the number of heartbeats during the query. For assessing iterative methods under extreme conditions, we deliberately reduced the heartbeat duration, resulting in observed proportions of late messages of 80%, 90%, and 95% (as depicted in Figure 19).

We observe that even with no iteration, Apriori reaches 65% recall and K-means reaches 30% degradation of its inertia. Both converge quite quickly towards a recall of 100% or a PCI < 0% (4 or 5 heartbeats for 80 or 90% late messages, 7 or 8 with 95% late messages). Note that with Apriori, precision is always 100% (not shown). Indeed, as we verify that the Computing Combiners always receive $n$ or more sub-QEPs results, we can thus remove potential false positives. With K-means, we observe that as the number of heartbeats increases, the PCI can become negative. The reason for this is that an Edgelet calculation with many heartbeats can be better than a centralized calculation, thanks to the fact that it considers up to $m$ additional partitions.
<figure><img src="image_22.png" /><figcaption>Figure 20: Heartbeat Execution Quality (SGD)</figcaption></figure>

We then simulated the iterative Edgelet execution of Stochastic Gradient Descent (SGD) on a classification problem (Adult Income [52]) and a regression problem (California Housing [60]). As for Apriori and K-means, we consider a QEP with a horizontal partitioning of *n*=10 for *m*=10 additional partitions. For classification, the underlying learning model used is a support vector machine, while for regression it is a linear model. For both, we use a constant learning rate and divide the number of maximum local iterations by a factor of 50 compared to centralized executions in order to reduce the amount of work on each edgelet. We then compare the accuracy of the model obtained on test data (mean accuracy for classification and coefficient of determination R² for regression).

Figure 20.a and Figure 20.b display the results of heartbeat executions on the two problems (classification and regression). The y-axis represents the Percentage Change Accuracy (PCA), which is the percentage difference between the model accuracy achieved in an Edgelet execution and that obtained in a centralized execution. At first glance, we can see that models built in Edgelet gradually converge towards the quality of centralized models. Even if the initial PCA is variable (-6% for classification and -40% for regression), since it depends on the learning rate and the maximum number of local iterations chosen, it does not prevent the models from progressing. Then, we notice that the proportion of late messages is not a determining factor for convergence speed. In fact, the SGD algorithm's ability to work on small samples (mini-batches) at each iteration makes it a prime candidate for distributed and decentralized execution [43]. As a result, when the data is correctly distributed over the Computers, they compute a local model that naturally converges toward the best parameters.

## 7 Related Works

A lot of research work has been produced on the different areas encompassed by Edgelet computing: computing architectures, privacy-preserving computation techniques, and fault-tolerant execution strategies. To the best of our knowledge, none of these works considered the conjunction of fully decentralized data-intensive computing on users' devices and the enforcement of validity, resiliency, and security properties. In the following, we overview the closest decentralized computing architectures, then consider user privacy protection, and finally study existing strategies for fault tolerance.

**Decentralized computing architectures.** Crowd Computing [32], Crowdsourcing [26], and Crowd Sensing [30] are all based on the fact that individuals are increasingly connected and can thus participate in the enrichment of the digital sphere, from the sharing of captured data to the realization of individual micro-tasks. However, these approaches are still driven by centralized servers on which most of the processing is done. At the same time, the Edge paradigm has emerged with the goal of offloading services and computation close to data sources to make the cloud more responsive, scalable, and privacy-friendly [62, 70]. Like Cross-Device Federated Learning [13], these technologies operate in connected infrastructures where processing is performed either in micro data centers (or cloudlets) [28, 50, 58], or directly on edge devices with workload distribution [35, 46]. We differ from these architectures by still offering a reliable and privacy-preserving approach, but by relying exclusively on the edges to organize the processing without the need for any infrastructure. In this direction, an approach quite similar to ours is the crowd computing definition by Murray et al. [48] which considers the combination of mobile devices and OppNets to achieve large-scale distributed computations. However, this proposal does not consider privacy or fault tolerance.

**Privacy-preserving computations using cryptography.** To guarantee privacy-preserving computations, our approach relies on TEEs present in edgelets, which promotes computational genericity and execution scaling. Numerous cryptography-based solutions have been proposed for almost thirty years. Initial solutions were designed for wireless sensor networks [30, 73] with
<figure><img src="image_21.png" /><figcaption>Figure 20: Heartbeat Execution Quality (SGD)</figcaption></figure>

We then simulated the iterative Edgelet execution of Stochastic Gradient Descent (SGD) on a classification problem (Adult Income [52]) and a regression problem (California Housing [60]). As for Apriori and K-means, we consider a QEP with a horizontal partitioning of *n*=10 for *m*=10 additional partitions. For classification, the underlying learning model used is a support vector machine, while for regression it is a linear model. For both, we use a constant learning rate and divide the number of maximum local iterations by a factor of 50 compared to centralized executions in order to reduce the amount of work on each edgelet. We then compare the accuracy of the model obtained on test data (mean accuracy for classification and coefficient of determination R² for regression).

Figure 20.a and Figure 20.b display the results of heartbeat executions on the two problems (classification and regression). The y-axis represents the Percentage Change Accuracy (PCA), which is the percentage difference between the model accuracy achieved in an Edgelet execution and that obtained in a centralized execution. At first glance, we can see that models built in Edgelet gradually converge towards the quality of centralized models. Even if the initial PCA is variable (-6% for classification and -40% for regression), since it depends on the learning rate and the maximum number of local iterations chosen, it does not prevent the models from progressing. Then, we notice that the proportion of late messages is not a determining factor for convergence speed. In fact, the SGD algorithm's ability to work on small samples (mini-batches) at each iteration makes it a prime candidate for distributed and decentralized execution [43]. As a result, when the data is correctly distributed over the Computers, they compute a local model that naturally converges toward the best parameters.

# 7 Related Works

A lot of research work has been produced on the different areas encompassed by Edgelet computing: computing architectures, privacy-preserving computation techniques, and fault-tolerant execution strategies. To the best of our knowledge, none of these works considered the conjunction of fully decentralized data-intensive computing on users' devices and the enforcement of validity, resiliency, and security properties. In the following, we overview the closest decentralized computing architectures, then consider user privacy protection, and finally study existing strategies for fault tolerance.

**Decentralized computing architectures.** Crowd Computing [32], Crowdsourcing [26], and Crowd Sensing [30] are all based on the fact that individuals are increasingly connected and can thus participate in the enrichment of the digital sphere, from the sharing of captured data to the realization of individual micro-tasks. However, these approaches are still driven by centralized servers on which most of the processing is done. At the same time, the Edge paradigm has emerged with the goal of offloading services and computation close to data sources to make the cloud more responsive, scalable, and privacy-friendly [62, 70]. Like Cross-Device Federated Learning [13], these technologies operate in connected infrastructures where processing is performed either in micro data centers (or cloudlets) [28, 50, 58], or directly on edge devices with workload distribution [35, 46]. We differ from these architectures by still offering a reliable and privacy-preserving approach, but by relying exclusively on the edges to organize the processing without the need for any infrastructure. In this direction, an approach quite similar to ours is the crowd computing definition by Murray et al. [48] which considers the combination of mobile devices and OppNets to achieve large-scale distributed computations. However, this proposal does not consider privacy or fault tolerance.

**Privacy-preserving computations using cryptography.** To guarantee privacy-preserving computations, our approach relies on TEEs present in edgelets, which promotes computational genericity and execution scaling. Numerous cryptography-based solutions have been proposed for almost thirty years. Initial solutions were designed for wireless sensor networks [30, 73] with
the main aim of transmitting collected data to monitoring stations for analysis, but the field has recently taken off again to meet
the needs of federated learning (FL). A recent survey [44] discusses 40 works for FL, grouped into four classes: masking,
homomorphic encryption, functional encryption, and MPC (or secret shares). The specific scheme proposed may vary
depending on the trade-off offered between the computation and the communication cost, or the tolerance to failures. However,
whatever cryptographic scheme is used, all existing solutions (e.g., [12, 53], Prio [21], and Drynx [29]) rely on a similar
architecture in which one or a few powerful and highly reliable servers collect encrypted user data and then apply costly (albeit
optimized) aggregation algorithms based on masking (e.g., [63]), garbled circuits (e.g., [7, 25]) or secret sharing (e.g., [27, 33]).
For example, distributed database solutions, such as SMCQL [7], are limited to a few dozen participants; existing distributed
computing schemes based on fully homomorphic encryption [14, 31] cannot support any type of operation and scale to a large
number of participants at the same time.

**Privacy-preserving computations using differential privacy or gossip protocols.** Local differential privacy (LDP) has seen significant growth in recent years due to its main advantage over classical differential privacy, namely that it does not require a trusted third party. Existing works address problems such as machine learning [8], federated learning [1, 66, 72], marginal statistics [74], or basic statistics based on range queries [20]. However, LDP accentuates the tension between utility and privacy protection as it requires more noise for the same level of protection as classical differential privacy [3]. This can therefore either affect utility or require a very large number of participants to reduce the impact of noise which limits its applicability in our context. Gossip-based protocols are scalable, fully decentralized, reliable, and have an adjustable accuracy. Unfortunately, classical gossip-based protocols do not protect user privacy. In [8, 56], participants collectively learn a machine learning model while preserving their privacy through differentially private models, impacting accuracy. In [47], participants introduce noise in the first iterations and gradually remove it in subsequent iterations. This approach makes such solutions unreliable in the event of node failures or opportunistic networks. Finally, gossip protocols require the participation of all the nodes of the system, limiting their applicability.

**Strategies for fault-tolerance.** The standard approach to ensure query termination in distributed systems is replication [4, 69]. Recent database systems, such as AnyLog [49], address the case of the edge-cloud continuum, where applications typically have low latency, sporadic connectivity, and generate large amounts of data, raising new resilience issues. Resilience issues in the context of IoT are also more specific. We refer the reader to [10] for a full classification of resilience issues. Fault-tolerance problems increase significantly when considering asynchronous systems, and the duality between safety and liveness still impacts the most recent works. For instance, [51] proposes a redundancy system called Replicated Dataflow Graph (RDG) and suggests a "routing constraint" mechanism to coordinate data sources and replicas. However, as the authors explain, this does not totally prevent the occurrence of routing inconsistencies, although infrequent in practice. Our backup-based strategy, rooted in these same principles, encounters similar challenges. Conversely, overcollection-based strategies (Overcollection and Hybrid) circumvent the problems by replicating operators rather than data, which has the advantage of ensuring data consistency when building snapshots. Regarding the conjunction with privacy protection techniques, some works [12, 44] have investigated device failures and dropouts in the context of reliable aggregation servers. Unfortunately, these methods cannot be applied in a fully decentralized setting for two reasons. First, scalability is an issue because an edgelet is not a high-end server capable of handling thousands of connections and related cryptography. Second, reliability is a concern in our context since the Data Processor nodes are unreliable as they can fail or drop out, rendering their solutions inoperative. Our proposed TEE-coupled resiliency strategies adapt to this fully decentralized environment while ensuring computational genericity and scalability with no compromise on utility.

# 8 Conclusion

In this paper, we explored the Edgelet computing paradigm, a new framework for executing powerful and privacy-preserving distributed queries on personal devices at the extreme edge of the network. Built on the recent convergence between Trusted Execution Environments and Opportunistic Networks, this paradigm opens disruptive ways to handle personal data processing, pushing computations directly onto crowd devices rather than relying on centralized servers. Besides introducing this new paradigm, this paper makes the following contributions. First, to cope with the specificities of the Edgelet context, it introduces a new responsibility model tackling the shift of responsibility from cloud providers to crowd members and a new query model adapted to the open-world assumption. Second, by leveraging the properties of TEEs, it provides several security mechanisms to preserve both execution integrity and data confidentiality under a threat model dedicated to the Edgelet computing context. Third, it proposes three resiliency strategies to make the executions resilient to personal device failures and OppNets-induced message losses: the first one is a thorough adaptation of backup-based strategies, the second one capitalizes on the open world
the main aim of transmitting collected data to monitoring stations for analysis, but the field has recently taken off again to meet
the needs of federated learning (FL). A recent survey [44] discusses 40 works for FL, grouped into four classes: masking,
homomorphic encryption, functional encryption, and MPC (or secret shares). The specific scheme proposed may vary
depending on the trade-off offered between the computation and the communication cost, or the tolerance to failures. However,
whatever cryptographic scheme is used, all existing solutions (e.g., [12, 53], Prio [21], and Drynx [29]) rely on a similar
architecture in which one or a few powerful and highly reliable servers collect encrypted user data and then apply costly (albeit
optimized) aggregation algorithms based on masking (e.g., [63]), garbled circuits (e.g., [7, 25]) or secret sharing (e.g., [27, 33]).
For example, distributed database solutions, such as SMCQL [7], are limited to a few dozen participants; existing distributed
computing schemes based on fully homomorphic encryption [14, 31] cannot support any type of operation and scale to a large
number of participants at the same time.

**Privacy-preserving computations using differential privacy or gossip protocols.** Local differential privacy (LDP) has seen significant growth in recent years due to its main advantage over classical differential privacy, namely that it does not require a trusted third party. Existing works address problems such as machine learning [8], federated learning [1, 66, 72], marginal statistics [74], or basic statistics based on range queries [20]. However, LDP accentuates the tension between utility and privacy protection as it requires more noise for the same level of protection as classical differential privacy [3]. This can therefore either affect utility or require a very large number of participants to reduce the impact of noise which limits its applicability in our context. Gossip-based protocols are scalable, fully decentralized, reliable, and have an adjustable accuracy. Unfortunately, classical gossip-based protocols do not protect user privacy. In [8, 56], participants collectively learn a machine learning model while preserving their privacy through differentially private models, impacting accuracy. In [47], participants introduce noise in the first iterations and gradually remove it in subsequent iterations. This approach makes such solutions unreliable in the event of node failures or opportunistic networks. Finally, gossip protocols require the participation of all the nodes of the system, limiting their applicability.

**Strategies for fault-tolerance.** The standard approach to ensure query termination in distributed systems is replication [4, 69]. Recent database systems, such as AnyLog [49], address the case of the edge-cloud continuum, where applications typically have low latency, sporadic connectivity, and generate large amounts of data, raising new resilience issues. Resilience issues in the context of IoT are also more specific. We refer the reader to [10] for a full classification of resilience issues. Fault-tolerance problems increase significantly when considering asynchronous systems, and the duality between safety and liveness still impacts the most recent works. For instance, [51] proposes a redundancy system called Replicated Dataflow Graph (RDG) and suggests a "routing constraint" mechanism to coordinate data sources and replicas. However, as the authors explain, this does not totally prevent the occurrence of routing inconsistencies, although infrequent in practice. Our backup-based strategy, rooted in these same principles, encounters similar challenges. Conversely, overcollection-based strategies (Overcollection and Hybrid) circumvent the problems by replicating operators rather than data, which has the advantage of ensuring data consistency when building snapshots. Regarding the conjunction with privacy protection techniques, some works [12, 44] have investigated device failures and dropouts in the context of reliable aggregation servers. Unfortunately, these methods cannot be applied in a fully decentralized setting for two reasons. First, scalability is an issue because an edgelet is not a high-end server capable of handling thousands of connections and related cryptography. Second, reliability is a concern in our context since the Data Processor nodes are unreliable as they can fail or drop out, rendering their solutions inoperative. Our proposed TEE-coupled resiliency strategies adapt to this fully decentralized environment while ensuring computational genericity and scalability with no compromise on utility.

# 8 Conclusion

In this paper, we explored the Edgelet computing paradigm, a new framework for executing powerful and privacy-preserving distributed queries on personal devices at the extreme edge of the network. Built on the recent convergence between Trusted Execution Environments and Opportunistic Networks, this paradigm opens disruptive ways to handle personal data processing, pushing computations directly onto crowd devices rather than relying on centralized servers. Besides introducing this new paradigm, this paper makes the following contributions. First, to cope with the specificities of the Edgelet context, it introduces a new responsibility model tackling the shift of responsibility from cloud providers to crowd members and a new query model adapted to the open-world assumption. Second, by leveraging the properties of TEEs, it provides several security mechanisms to preserve both execution integrity and data confidentiality under a threat model dedicated to the Edgelet computing context. Third, it proposes three resiliency strategies to make the executions resilient to personal device failures and OppNets-induced message losses: the first one is a thorough adaptation of backup-based strategies, the second one capitalizes on the open world
assumption to improve the efficiency of a subclass of queries and the last one is a hybridization aiming at combining the generality and the efficiency of the two preceding strategies. It then provides guidelines for determining the most appropriate strategy when designing a computation under Edgelet computing. Finally, we present qualitative and quantitative evaluations of the proposed methods and strategies to validate them and study their limits.

To the best of our knowledge, this work represents the first attempt to combine TEEs and Opportunistic Networks to introduce fully decentralized privacy-preserving computations. Our initial findings [37], alongside our demonstrations illustrating the concrete use case of DomYcile [39] and the versatility of the framework [38] (with various weakly connected TEE devices), give confidence in the relevance and feasibility of Edgelet Computing. However, several new research challenges deserve to be studied by the scientific community to enhance the generality of the approach, among others:

**Optimization of resource consumption.** The first challenge is to explore the multiple optimization tradeoffs that exist between data confidentiality, query success rate, and (local and global) resource consumption. As explained in subsection 2.1, we chose an epidemic diffusion of message in the Opportunistic Network. This simplistic routing protocol maximizes the message delivery rate and minimizes message latency, at the cost of significant network congestion and overhead. A significant improvement would be to incorporate individuals' social patterns into routing (e.g., BUBBLE Rap [36]) and facilitate query processing by assigning operators to the most connected devices (e.g., doctors, teachers). Such optimizations would lead to revisiting the enforcement of the security property, in particular the random assignment protocol to allow a (limited and controlled) degree of bias in favor of socially well-connected crowd members.

**Management of long-lasting snapshots.** A second challenge is to integrate long-lasting snapshots (i.e., persistent datasets) to support processes routinely used in data analysis. Such processes start with an initial set of exploration queries to capture data frequency distributions before running precise database queries, data mining, or machine learning algorithms. Long-lasting snapshots could resort to specific indexing schemes to re-access sets of participating edgelets or materialized snapshot partitions kept (encrypted) on sets of edgelets. Obviously, persistent data management would have various impacts on the properties of security, resiliency, and validity. How to prevent data at rest from being the target of malicious attacks? How to preserve the consistency of successive queries in a fully decentralized environment?

**Enhancing the validity of iterative algorithms.** A third challenge is to study classes of iterative algorithms compatible with Edgelet computing for which it is possible to prove the strict validity of the results. For example, as mentioned in subsection 5.2, we observe that the Apriori algorithm executed in Edgelet can produce exactly the same results as a centralized execution. To go further and deepen our first experimental evaluations, it would be essential to theoretically prove the convergence of the algorithms. The research work of Lian et al. [43] on the convergence of the Asynchronous Decentralized Parallel Stochastic Gradient Descent particularly illustrates the interest of this type of proof. Thus, in the same direction, a theoretical and systematic analysis of iterative processing in Edgelet would be a valuable asset for deploying new applications.

# 9 Acknowledgement

This work has been supported by the ANR 22-PECY-0002 IPOP (Interdisciplinary Project on Privacy) project of the Cybersecurity PEPR.

# 10 References

[1] Agarwal, N. et al. 2018. cpSGD: Communication-efficient and differentially-private distributed SGD. NeurIPS 2018, Montréal, Canada, 7575-7586.

[2] Agrawal, D. et al. 2009. Database Management as a Service: Challenges and Opportunities. ICDE 2009, Shanghai, China, 1709-1716.

[3] Alvim, M.S. et al. 2018. Local Differential Privacy on Metric Spaces: Optimizing the Trade-Off with Utility. CSF 2018, Oxford, United Kingdom, 262-267.

[4] Alwan, H. and Agarwal, A. 2009. A Survey on Fault Tolerant Routing Techniques in Wireless Sensor Networks. 2009 Third International Conference on Sensor Technologies and Applications, Athens, Greece, 366-371.

[5] Anciaux, N. et al. 2019. Personal Data Management Systems: The security and functionality standpoint. Information Systems. 80, 13-35.

[6] Androutsellis-Theotokis, S. and Spinellis, D. 2004. A survey of peer-to-peer content distribution technologies. ACM Comp. Surveys. 36, 4, 335-371.

[7] Bater, J. et al. 2017. SMCQL: Secure Query Processing for Private Data Networks. Proc. VLDB Endow. 10, 6, 673-684.

[8] Bellet, A. et al. 2018. Personalized and Private Peer-to-Peer Machine Learning. AISTATS 2018, Spain, 473-481.

[9] Benchi, A. et al. 2015. Solving Consensus in Opportunistic Networks. ICDCN 2015, Goa, India, 1-10.
assumption to improve the efficiency of a subclass of queries and the last one is a hybridization aiming at combining the generality and the efficiency of the two preceding strategies. It then provides guidelines for determining the most appropriate strategy when designing a computation under Edgelet computing. Finally, we present qualitative and quantitative evaluations of the proposed methods and strategies to validate them and study their limits.

To the best of our knowledge, this work represents the first attempt to combine TEEs and Opportunistic Networks to introduce fully decentralized privacy-preserving computations. Our initial findings [37], alongside our demonstrations illustrating the concrete use case of DomYcile [39] and the versatility of the framework [38] (with various weakly connected TEE devices), give confidence in the relevance and feasibility of Edgelet Computing. However, several new research challenges deserve to be studied by the scientific community to enhance the generality of the approach, among others:

**Optimization of resource consumption.** The first challenge is to explore the multiple optimization tradeoffs that exist between data confidentiality, query success rate, and (local and global) resource consumption. As explained in subsection 2.1, we chose an epidemic diffusion of message in the Opportunistic Network. This simplistic routing protocol maximizes the message delivery rate and minimizes message latency, at the cost of significant network congestion and overhead. A significant improvement would be to incorporate individuals' social patterns into routing (e.g., BUBBLE Rap [36]) and facilitate query processing by assigning operators to the most connected devices (e.g., doctors, teachers). Such optimizations would lead to revisiting the enforcement of the security property, in particular the random assignment protocol to allow a (limited and controlled) degree of bias in favor of socially well-connected crowd members.

**Management of long-lasting snapshots.** A second challenge is to integrate long-lasting snapshots (i.e., persistent datasets) to support processes routinely used in data analysis. Such processes start with an initial set of exploration queries to capture data frequency distributions before running precise database queries, data mining, or machine learning algorithms. Long-lasting snapshots could resort to specific indexing schemes to re-access sets of participating edgelets or materialized snapshot partitions kept (encrypted) on sets of edgelets. Obviously, persistent data management would have various impacts on the properties of security, resiliency, and validity. How to prevent data at rest from being the target of malicious attacks? How to preserve the consistency of successive queries in a fully decentralized environment?

**Enhancing the validity of iterative algorithms.** A third challenge is to study classes of iterative algorithms compatible with Edgelet computing for which it is possible to prove the strict validity of the results. For example, as mentioned in subsection 5.2, we observe that the Apriori algorithm executed in Edgelet can produce exactly the same results as a centralized execution. To go further and deepen our first experimental evaluations, it would be essential to theoretically prove the convergence of the algorithms. The research work of Lian et al. [43] on the convergence of the Asynchronous Decentralized Parallel Stochastic Gradient Descent particularly illustrates the interest of this type of proof. Thus, in the same direction, a theoretical and systematic analysis of iterative processing in Edgelet would be a valuable asset for deploying new applications.

# 9 Acknowledgement

This work has been supported by the ANR 22-PECY-0002 IPOP (Interdisciplinary Project on Privacy) project of the Cybersecurity PEPR.

# 10 References

[1] Agarwal, N. et al. 2018. cpSGD: Communication-efficient and differentially-private distributed SGD. NeurIPS 2018, Montréal, Canada, 7575-7586.

[2] Agrawal, D. et al. 2009. Database Management as a Service: Challenges and Opportunities. ICDE 2009, Shanghai, China, 1709-1716.

[3] Alvim, M.S. et al. 2018. Local Differential Privacy on Metric Spaces: Optimizing the Trade-Off with Utility. CSF 2018, Oxford, United Kingdom, 262-267.

[4] Alwan, H. and Agarwal, A. 2009. A Survey on Fault Tolerant Routing Techniques in Wireless Sensor Networks. 2009 Third International Conference on Sensor Technologies and Applications, Athens, Greece, 366-371.

[5] Anciaux, N. et al. 2019. Personal Data Management Systems: The security and functionality standpoint. Information Systems. 80, 13-35.

[6] Androutsellis-Theotokis, S. and Spinellis, D. 2004. A survey of peer-to-peer content distribution technologies. ACM Comp. Surveys. 36, 4, 335-371.

[7] Bater, J. et al. 2017. SMCQL: Secure Query Processing for Private Data Networks. Proc. VLDB Endow. 10, 6, 673-684.

[8] Bellet, A. et al. 2018. Personalized and Private Peer-to-Peer Machine Learning. AISTATS 2018, Spain, 473-481.

[9] Benchi, A. et al. 2015. Solving Consensus in Opportunistic Networks. ICDCN 2015, Goa, India, 1-10.
[10] Berger, C. et al. 2022. A Survey on Resilience in the IoT: Taxonomy, Classification, and Discussion of Resilience Mechanisms. *ACM Comput. Surveys*. 54, 7, 1–39.

[11] BOINC: https://boinc.berkeley.edu.

[12] Bonawitz, K. et al. 2017. Practical Secure Aggregation for Privacy-Preserving Machine Learning. *Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security*, Dallas, Texas, USA, 1175–1191.

[13] Bonawitz, K.A. et al. 2019. Towards Federated Learning at Scale: System Design. *MLSys 2019*, Stanford, CA, USA.

[14] Boneh, D. et al. 2013. Private Database Queries Using Somewhat Homomorphic Encryption. *ACNS 2013*, Banff, AB, Canada, 102–118.

[15] Bottou, L. 2010. Large-Scale Machine Learning with Stochastic Gradient Descent. *19th International Conference on Computational Statistics, COMPSTAT 2010*, Paris, France, 177–186.

[16] Brijs, T. 2003. Retail market basket data set. *Workshop on Frequent Itemset Mining Implementations (FIMI'03)*.

[17] Cisco Annual Internet Report (2018–2023) White Paper: 2020. https://tinyurl.com/cisco-internet-report.

[18] Conti, M. et al. 2010. From opportunistic networks to opportunistic computing. *IEEE Communications Magazine*. 48, 9, 126–139.

[19] Conti, M. et al. 2017. The Internet of People (IoP): A new wave in pervasive mobile computing. *Pervasive Mob. Comput*. 41, 1–27.

[20] Cormode, G. et al. 2019. Answering Range Queries Under Local Differential Privacy. *Proc. VLDB Endow*. 12, 10, 1126–1138.

[21] Corrigan-Gibbs, H. and Boneh, D. 2017. Prio: Private, Robust, and Scalable Computation of Aggregate Statistics. *NSDI 2017*, Boston, MA, USA, 259–282.

[22] Costan, V. and Devadas, S. 2016. Intel SGX Explained. *IACR Cryptol. ePrint Arch.*, 86.

[23] Dhillon, I.S. and Modha, D.S. 1999. A Data-Clustering Algorithm on Distributed Memory Multiprocessors. *SIGKDD*, San Diego, CA, USA, 245–260.

[24] DomYcile Project: https://tinyurl.com/domycile, Salon E-Tonomy: https://tinyurl.com/e-tonomy.

[25] Dong, Y. et al. 2021. FLOD: Oblivious Defender for Private Byzantine-Robust Federated Learning with Dishonest-Majority. *ESORICS 2021*, Darmstadt, Germany, 497–518.

[26] Estellés-Arolas, E. and González-Ladrón-de-Guevara, F. 2012. Towards an integrated crowdsourcing definition. *Journal of Information Science*. 38, 2, 189–200.

[27] Fereidooni, H. et al. 2021. SAFELearn: Secure Aggregation for private FEderated Learning. *SP Workshops 2021*, San Francisco, CA, USA, 56–62.

[28] Ferrer, A.J. et al. 2019. Towards the Decentralised Cloud: Survey on Approaches and Challenges for Mobile, Ad hoc, and Edge Computing. *ACM Comput. Surveys*. 51, 6, 1–36.

[29] Froelicher, D. et al. 2020. Drynx: Decentralized, Secure, Verifiable System for Statistical Queries and Machine Learning on Distributed Datasets. *IEEE Trans. Inf. Forensics Secur*. 15, 3035–3050.

[30] Ganti, R.K. et al. 2011. Mobile crowdsensing: current state and future challenges. *IEEE Commun. Mag*. 49, 11, 32–39.

[31] González-Manzano, L. et al. 2016. PAgIoT – Privacy-preserving Aggregation protocol for Internet of Things. *Journal of Network and Computer Applications*. 71, 59–71.

[32] Guo, B. et al. 2015. Mobile Crowd Sensing and Computing: The Review of an Emerging Human-Powered Sensing Paradigm. *ACM Comp. Surveys*. 48, 1, 1–31.

[33] Gupta, P. et al. 2019. Obscure: information-theoretic oblivious and verifiable aggregation queries. *Proc. VLDB Endow*. 12, 9, 1030–1043.

[34] Herr, M. et al. 2017. Frailty, polypharmacy, and potentially inappropriate medications in old people: findings in a representative sample of the French population. *European Journal of Clinical Pharmacology*. 73, 9, 1165–1172.

[35] Huba, D. et al. 2022. PAPAYA: Practical, Private, and Scalable Federated Learning. *MLSys 2022*, Santa Clara, CA, USA.

[36] Hui, P. et al. 2011. BUBBLE Rap: Social-Based Forwarding in Delay-Tolerant Networks. *IEEE Trans. Mob. Comput*. 10, 11, 1576–1589.

[37] Javet, L. et al. 2022. Edgelet Computing: Pushing Query Processing and Liability at the Extreme Edge of the Network. *CCGrid 2022*, Taormina, Italy, 160–169.

[38] Javet, L. et al. 2023. Pushing Edge Computing one Step Further: Resilient and Privacy-Preserving Processing on Personal Devices. *EDBT 2023*, Ioannina, Greece, 835–838.

[39] Javet, L. et al. 2023. Secure Computations in Opportunistic Networks: An Edgelet Demonstration with a Medical Use-Case. *PerCom Workshops 2023*, Atlanta, GA, USA, 331–333.

[40] Kasiviswanathan, S.P. et al. 2011. What Can We Learn Privately? *SIAM J. Comput*. 40, 3, 793–826.

[41] Keränen, A. et al. 2009. The ONE Simulator for DTN Protocol Evaluation. *SIMUTools 2009*, Rome, Italy.

[42] Ladjel, R. et al. 2019. Trustworthy Distributed Computations on Personal Data Using Trusted Execution Environments. *TrustCom 2019*, Rotorua, New Zealand, 381–388.

[43] Lian, X. et al. 2018. Asynchronous Decentralized Parallel Stochastic Gradient Descent. *ICML 2018*, Stockholm, Sweden, 3049–3058.

[44] Mansouri, M. et al. 2023. SoK: Secure Aggregation Based on Cryptographic Schemes for Federated Learning. *Proc. on Privacy Enhancing Technologies*. 1, 140–157.

[45] Ménétrey, J. et al. 2022. An Exploratory Study of Attestation Mechanisms for Trusted Execution Environments. arXiv.

[46] Mirval, J. et al. 2023. Federated Learning on Personal Data Management Systems: Decentralized and Reliable Secure Aggregation Protocols. *SSDBM 2023*, Los Angeles, CA, USA, 1–12.

[47] Mo, Y. and Murray, R.M. 2017. Privacy Preserving Average Consensus. *IEEE Trans. Autom. Control*. 62, 2, 753–765.

[48] Murray, D.G. et al. 2010. The case for crowd computing. *ACM SIGCOMM 2010*, New Delhi, India, 39–44.

[49] Nawab, F. and Shadmon, M. 2024. The Tipping Point of Edge-Cloud Data Management. *CIDR 2024*, Chaminade, CA, USA.

[50] Nguyen, J. et al. 2022. Federated Learning with Buffered Asynchronous Aggregation. *AISTATS 2022*, Virtual Event, 3581–3607.
[10] Berger, C. et al. 2022. A Survey on Resilience in the IoT: Taxonomy, Classification, and Discussion of Resilience Mechanisms. *ACM Comput. Surveys*. 54, 7, 1–39.

[11] BOINC: https://boinc.berkeley.edu.

[12] Bonawitz, K. et al. 2017. Practical Secure Aggregation for Privacy-Preserving Machine Learning. *Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security*, Dallas, Texas, USA, 1175–1191.

[13] Bonawitz, K.A. et al. 2019. Towards Federated Learning at Scale: System Design. *MLSys 2019*, Stanford, CA, USA.

[14] Boneh, D. et al. 2013. Private Database Queries Using Somewhat Homomorphic Encryption. *ACNS 2013*, Banff, AB, Canada, 102–118.

[15] Bottou, L. 2010. Large-Scale Machine Learning with Stochastic Gradient Descent. *19th International Conference on Computational Statistics, COMPSTAT 2010*, Paris, France, 177–186.

[16] Brijs, T. 2003. Retail market basket data set. *Workshop on Frequent Itemset Mining Implementations (FIMI'03)*.

[17] Cisco Annual Internet Report (2018–2023) White Paper: 2020. https://tinyurl.com/cisco-internet-report.

[18] Conti, M. et al. 2010. From opportunistic networks to opportunistic computing. *IEEE Communications Magazine*. 48, 9, 126–139.

[19] Conti, M. et al. 2017. The Internet of People (IoP): A new wave in pervasive mobile computing. *Pervasive Mob. Comput*. 41, 1–27.

[20] Cormode, G. et al. 2019. Answering Range Queries Under Local Differential Privacy. *Proc. VLDB Endow*. 12, 10, 1126–1138.

[21] Corrigan-Gibbs, H. and Boneh, D. 2017. Prio: Private, Robust, and Scalable Computation of Aggregate Statistics. *NSDI 2017*, Boston, MA, USA, 259–282.

[22] Costan, V. and Devadas, S. 2016. Intel SGX Explained. *IACR Cryptol. ePrint Arch.*, 86.

[23] Dhillon, I.S. and Modha, D.S. 1999. A Data-Clustering Algorithm on Distributed Memory Multiprocessors. *SIGKDD*, San Diego, CA, USA, 245–260.

[24] DomYcile Project: https://tinyurl.com/domycile, Salon E-Tonomy: https://tinyurl.com/e-tonomy.

[25] Dong, Y. et al. 2021. FLOD: Oblivious Defender for Private Byzantine-Robust Federated Learning with Dishonest-Majority. *ESORICS 2021*, Darmstadt, Germany, 497–518.

[26] Estellés-Arolas, E. and González-Ladrón-de-Guevara, F. 2012. Towards an integrated crowdsourcing definition. *Journal of Information Science*. 38, 2, 189–200.

[27] Fereidooni, H. et al. 2021. SAFELearn: Secure Aggregation for private FEderated Learning. *SP Workshops 2021*, San Francisco, CA, USA, 56–62.

[28] Ferrer, A.J. et al. 2019. Towards the Decentralised Cloud: Survey on Approaches and Challenges for Mobile, Ad hoc, and Edge Computing. *ACM Comput. Surveys*. 51, 6, 1–36.

[29] Froelicher, D. et al. 2020. Drynx: Decentralized, Secure, Verifiable System for Statistical Queries and Machine Learning on Distributed Datasets. *IEEE Trans. Inf. Forensics Secur*. 15, 3035–3050.

[30] Ganti, R.K. et al. 2011. Mobile crowdsensing: current state and future challenges. *IEEE Commun. Mag*. 49, 11, 32–39.

[31] González-Manzano, L. et al. 2016. PAgIoT – Privacy-preserving Aggregation protocol for Internet of Things. *Journal of Network and Computer Applications*. 71, 59–71.

[32] Guo, B. et al. 2015. Mobile Crowd Sensing and Computing: The Review of an Emerging Human-Powered Sensing Paradigm. *ACM Comp. Surveys*. 48, 1, 1–31.

[33] Gupta, P. et al. 2019. Obscure: information-theoretic oblivious and verifiable aggregation queries. *Proc. VLDB Endow*. 12, 9, 1030–1043.

[34] Herr, M. et al. 2017. Frailty, polypharmacy, and potentially inappropriate medications in old people: findings in a representative sample of the French population. *European Journal of Clinical Pharmacology*. 73, 9, 1165–1172.

[35] Huba, D. et al. 2022. PAPAYA: Practical, Private, and Scalable Federated Learning. *MLSys 2022*, Santa Clara, CA, USA.

[36] Hui, P. et al. 2011. BUBBLE Rap: Social-Based Forwarding in Delay-Tolerant Networks. *IEEE Trans. Mob. Comput*. 10, 11, 1576–1589.

[37] Javet, L. et al. 2022. Edgelet Computing: Pushing Query Processing and Liability at the Extreme Edge of the Network. *CCGrid 2022*, Taormina, Italy, 160–169.

[38] Javet, L. et al. 2023. Pushing Edge Computing one Step Further: Resilient and Privacy-Preserving Processing on Personal Devices. *EDBT 2023*, Ioannina, Greece, 835–838.

[39] Javet, L. et al. 2023. Secure Computations in Opportunistic Networks: An Edgelet Demonstration with a Medical Use-Case. *PerCom Workshops 2023*, Atlanta, GA, USA, 331–333.

[40] Kasiviswanathan, S.P. et al. 2011. What Can We Learn Privately? *SIAM J. Comput*. 40, 3, 793–826.

[41] Keränen, A. et al. 2009. The ONE Simulator for DTN Protocol Evaluation. *SIMUTools 2009*, Rome, Italy.

[42] Ladjel, R. et al. 2019. Trustworthy Distributed Computations on Personal Data Using Trusted Execution Environments. *TrustCom 2019*, Rotorua, New Zealand, 381–388.

[43] Lian, X. et al. 2018. Asynchronous Decentralized Parallel Stochastic Gradient Descent. *ICML 2018*, Stockholm, Sweden, 3049–3058.

[44] Mansouri, M. et al. 2023. SoK: Secure Aggregation Based on Cryptographic Schemes for Federated Learning. *Proc. on Privacy Enhancing Technologies*. 1, 140–157.

[45] Ménétrey, J. et al. 2022. An Exploratory Study of Attestation Mechanisms for Trusted Execution Environments. arXiv.

[46] Mirval, J. et al. 2023. Federated Learning on Personal Data Management Systems: Decentralized and Reliable Secure Aggregation Protocols. *SSDBM 2023*, Los Angeles, CA, USA, 1–12.

[47] Mo, Y. and Murray, R.M. 2017. Privacy Preserving Average Consensus. *IEEE Trans. Autom. Control*. 62, 2, 753–765.

[48] Murray, D.G. et al. 2010. The case for crowd computing. *ACM SIGCOMM 2010*, New Delhi, India, 39–44.

[49] Nawab, F. and Shadmon, M. 2024. The Tipping Point of Edge-Cloud Data Management. *CIDR 2024*, Chaminade, CA, USA.

[50] Nguyen, J. et al. 2022. Federated Learning with Buffered Asynchronous Aggregation. *AISTATS 2022*, Virtual Event, 3581–3607.
[51] O'Keeffe, D. et al. 2018. Frontier: Resilient Edge Processing for the Internet of Things. Proc. VLDB Endow. 11, 10, 1178-1191.

[52] OpenML Adult dataset: http://www.openml.org/d/1590.

[53] Phong, L.T. et al. 2018. Privacy-Preserving Deep Learning via Additively Homomorphic Encryption. IEEE Trans. Inf. Forensics Secur. 13, 5, 1333-1345.

[54] Pinto, S. and Santos, N. 2019. Demystifying Arm TrustZone: A Comprehensive Survey. ACM Comp. Surveys. 51, 6, 1-36.

[55] Proposal for a Proposal for a Regulation of the European Parliament and of the Council on European data governance: https://tinyurl.com/data-governance-act.

[56] Sabater, C. et al. 2022. An accurate, scalable and verifiable protocol for federated differentially private averaging. Mach. Learn. 111, 11, 4249-4293.

[57] Sabt, M. et al. 2015. Trusted Execution Environment: What It is, and What It is Not. TrustCom 2015, 57-64.

[58] Satyanarayanan, M. et al. 2009. The Case for VM-Based Cloudlets in Mobile Computing. IEEE Pervasive Comput. 8, 4, 14-23.

[59] Savasere, A. et al. 1995. An Efficient Algorithm for Mining Association Rules in Large Databases. PVLDB'95, Zurich, Switzerland, 432-444.

[60] Scikit-learn California dataset: https://tinyurl.com/california-housing-dataset.

[61] Shared Responsibility Model - Amazon Web Services: https://aws.amazon.com/compliance/shared-responsibility-model/.

[62] Shi, W. et al. 2016. Edge Computing: Vision and Challenges. IEEE Internet of Things Journal. 3, 5, 637-646.

[63] So, J. et al. 2022. LightSecAgg: a Lightweight and Versatile Design for Secure Aggregation in Federated Learning. Proceedings of Machine Learning and Systems 2022, MLSys 2022, Santa Clara, CA, USA.

[64] The Survey of Health, Ageing and Retirement in Europe (SHARE): http://www.share-project.org/.

[65] Tramer, F. et al. 2017. Sealed-Glass Proofs: Using Transparent Enclaves to Prove and Sell Knowledge. EuroS&P 2017, 19-34.

[66] Triastcyn, A. and Faltings, B. 2019. Federated Learning with Bayesian Differential Privacy. IEEE BigData 2019, Los Angeles, CA, USA, 2587-2596.

[67] Trifunovic, S. et al. 2017. A Decade of Research in Opportunistic Networks: Challenges, Relevance, and Future Directions. IEEE Commun. Mag. 55, 1 (2017), 168-173.

[68] Vahdat, A. and Becker, D. 2000. Epidemic Routing for Partially-Connected Ad Hoc Networks.

[69] Wiesmann, M. et al. 2000. Understanding replication in databases and distributed systems. Proceedings 20th IEEE International Conference on Distributed Computing Systems, Taipei, Taiwan, 464-474.

[70] Xu, D. et al. 2021. Edge Intelligence: Empowering Intelligence to the Edge of Network. Proceedings of the IEEE. 109, 11, 1778-1837.

[71] Xu, Y. et al. 2023. Towards machine-learning-driven effective mashup recommendations from big data in mobile networks and the Internet-of-Things. Digit. Commun. Networks. 9, 1, 138-145.

[72] Yang, G. et al. 2021. Federated Learning with Personalized Local Differential Privacy. ICCCS 2021, Chengdu, China, 484-489.

[73] Yick, J. et al. 2008. Wireless sensor network survey. Computer Networks. 52, 12, 2292-2330.

[74] Zhang, Z. et al. 2018. CALM: Consistent Adaptive Local Marginal for Marginal Release under Local Differential Privacy. CCS 2018, Toronto, ON, Canada, 212-229.

## Appendix 1: Query Deadline Calibration

The backup-based strategy presented in subsection 4.1 requires calibrating the query deadline according to the query plan to be executed, to the expected probability of success $p_s$ for this query, and to the maximum transmission delay $\delta$ for a sent message. The intermediate timeouts for each query plan node can be obtained using a simple recursive calculation based on the following principles:

- For each data processor, a timeout $\Delta$ is associated with each of its predecessor nodes, whether primary or backup. When this timeout $\Delta$ expires, a fault of the corresponding predecessor node is presumed and an activation message is sent to the appropriate backup node (the first backup of a primary if the primary is presumed faulty, the second backup if the first backup is presumed faulty, etc.). After the activation message has been sent, only the first message received from either the presumed faulty primary or any of its activated backups will be considered and processed.

- Primary and active backup nodes follow a push message pattern for all their successors (whether primary or backup nodes), meaning that messages are sent to successor nodes on their own initiative. Conversely, passive backup nodes follow a pull message pattern, i.e., messages are sent after a successor node's activation message is received.

**Level 0: Snapshot Builder and its backups.** Since the Data Contributors are never recalled, there is no timeout defined at the Snapshot Builders level and their backups.

**Level 1: Computer and its backups.** The Computer nodes (primary and backups) should receive their input data from the Snapshot Builder primary node after a maximum time delay of ~2$\delta$. Indeed, the Snapshot Builders and their backups are supposed to receive the messages from the Data Contributors after a delay $\delta$. Assuming that the data processing time of a node is negligible compared to the message latency, an additional maximum delay of $\delta$ is needed for the Snapshot Builder to transmit
[51] O'Keeffe, D. et al. 2018. Frontier: Resilient Edge Processing for the Internet of Things. Proc. VLDB Endow. 11, 10, 1178-1191.

[52] OpenML Adult dataset: http://www.openml.org/d/1590.

[53] Phong, L.T. et al. 2018. Privacy-Preserving Deep Learning via Additively Homomorphic Encryption. IEEE Trans. Inf. Forensics Secur. 13, 5, 1333-1345.

[54] Pinto, S. and Santos, N. 2019. Demystifying Arm TrustZone: A Comprehensive Survey. ACM Comp. Surveys. 51, 6, 1-36.

[55] Proposal for a Proposal for a Regulation of the European Parliament and of the Council on European data governance: https://tinyurl.com/data-governance-act.

[56] Sabater, C. et al. 2022. An accurate, scalable and verifiable protocol for federated differentially private averaging. Mach. Learn. 111, 11, 4249-4293.

[57] Sabt, M. et al. 2015. Trusted Execution Environment: What It is, and What It is Not. TrustCom 2015, 57-64.

[58] Satyanarayanan, M. et al. 2009. The Case for VM-Based Cloudlets in Mobile Computing. IEEE Pervasive Comput. 8, 4, 14-23.

[59] Savasere, A. et al. 1995. An Efficient Algorithm for Mining Association Rules in Large Databases. PVLDB'95, Zurich, Switzerland, 432-444.

[60] Scikit-learn California dataset: https://tinyurl.com/california-housing-dataset.

[61] Shared Responsibility Model - Amazon Web Services: https://aws.amazon.com/compliance/shared-responsibility-model/.

[62] Shi, W. et al. 2016. Edge Computing: Vision and Challenges. IEEE Internet of Things Journal. 3, 5, 637-646.

[63] So, J. et al. 2022. LightSecAgg: a Lightweight and Versatile Design for Secure Aggregation in Federated Learning. Proceedings of Machine Learning and Systems 2022, MLSys 2022, Santa Clara, CA, USA.

[64] The Survey of Health, Ageing and Retirement in Europe (SHARE): http://www.share-project.org/.

[65] Tramer, F. et al. 2017. Sealed-Glass Proofs: Using Transparent Enclaves to Prove and Sell Knowledge. EuroS&P 2017, 19-34.

[66] Triastcyn, A. and Faltings, B. 2019. Federated Learning with Bayesian Differential Privacy. IEEE BigData 2019, Los Angeles, CA, USA, 2587-2596.

[67] Trifunovic, S. et al. 2017. A Decade of Research in Opportunistic Networks: Challenges, Relevance, and Future Directions. IEEE Commun. Mag. 55, 1 (2017), 168-173.

[68] Vahdat, A. and Becker, D. 2000. Epidemic Routing for Partially-Connected Ad Hoc Networks.

[69] Wiesmann, M. et al. 2000. Understanding replication in databases and distributed systems. Proceedings 20th IEEE International Conference on Distributed Computing Systems, Taipei, Taiwan, 464-474.

[70] Xu, D. et al. 2021. Edge Intelligence: Empowering Intelligence to the Edge of Network. Proceedings of the IEEE. 109, 11, 1778-1837.

[71] Xu, Y. et al. 2023. Towards machine-learning-driven effective mashup recommendations from big data in mobile networks and the Internet-of-Things. Digit. Commun. Networks. 9, 1, 138-145.

[72] Yang, G. et al. 2021. Federated Learning with Personalized Local Differential Privacy. ICCCS 2021, Chengdu, China, 484-489.

[73] Yick, J. et al. 2008. Wireless sensor network survey. Computer Networks. 52, 12, 2292-2330.

[74] Zhang, Z. et al. 2018. CALM: Consistent Adaptive Local Marginal for Marginal Release under Local Differential Privacy. CCS 2018, Toronto, ON, Canada, 212-229.

## Appendix 1: Query Deadline Calibration

The backup-based strategy presented in subsection 4.1 requires calibrating the query deadline according to the query plan to be executed, to the expected probability of success $p_s$ for this query, and to the maximum transmission delay $\delta$ for a sent message. The intermediate timeouts for each query plan node can be obtained using a simple recursive calculation based on the following principles:

- For each data processor, a timeout $\Delta$ is associated with each of its predecessor nodes, whether primary or backup. When this timeout $\Delta$ expires, a fault of the corresponding predecessor node is presumed and an activation message is sent to the appropriate backup node (the first backup of a primary if the primary is presumed faulty, the second backup if the first backup is presumed faulty, etc.). After the activation message has been sent, only the first message received from either the presumed faulty primary or any of its activated backups will be considered and processed.

- Primary and active backup nodes follow a push message pattern for all their successors (whether primary or backup nodes), meaning that messages are sent to successor nodes on their own initiative. Conversely, passive backup nodes follow a pull message pattern, i.e., messages are sent after a successor node's activation message is received.

**Level 0: Snapshot Builder and its backups.** Since the Data Contributors are never recalled, there is no timeout defined at the Snapshot Builders level and their backups.

**Level 1: Computer and its backups.** The Computer nodes (primary and backups) should receive their input data from the Snapshot Builder primary node after a maximum time delay of ~2$\delta$. Indeed, the Snapshot Builders and their backups are supposed to receive the messages from the Data Contributors after a delay $\delta$. Assuming that the data processing time of a node is negligible compared to the message latency, an additional maximum delay of $\delta$ is needed for the Snapshot Builder to transmit
its result to the Computers. A first intermediate timeout at the Computer is hence fixed at $\Delta_1=2\delta$, at which the first backup of the Snapshot Builder will be activated. Recursively, as we expect the result of this first backup to be received after a maximum additional $2\delta$ delay, we can define the second intermediate timeout (activating the second backup) at $\Delta_2=\Delta_1+2\delta$, and so on for the next backups.

We can generalize this to obtain the timeout $\Delta_b$ for any passive backup node in the tree. Indeed, this timeout is determined by adding $2\delta$ (activation and response delays) to the Maximum Execution Time of a given Backup node (METB). At tree level $l+1$, METB is equal to the sum of:

- The consecutive activation time of all direct predecessor backup nodes and their corresponding response time: $b \times 2 \times \delta$, with $b$ the number of backup nodes.

- The recursive runtime of these backup nodes if they are not yet provisioned. This value depends directly on the number of levels $l$ in the sub-QEP (i.e., the tree height): $b \times \text{METB}(l)$

$$ \text{Thus, } \text{METB}(l+1) = b \times (2 \times \delta + \text{METB}(l)) $$

Similarly, the Maximum Execution Time of a Primary node (METP) at tree level $l+1$ is equal to the sum of:

- The emission time of its direct predecessor primary node and its recursive runtime: $\delta + \text{METP}(l)$

- The successive activation time of the direct predecessor backup nodes and their corresponding response time: $b \times 2 \times \delta$

- The recursive runtime of these backup nodes if they are not yet provisioned: $b \times \text{METB}(l)$

$$ \text{METP}(l+1) = \delta + \text{METP}(l) + b \times (2 \times \delta + \text{METB}(l)) $$

<figure><img src="image_23.png" /><figcaption>Figure 21: Example of Deadline Calibration</figcaption></figure>

Figure 21 shows an example of the query deadline calibration with the QEP of Figure 6, setting $b=2$ for the passive backups of the Snapshot Builders and Computers and $b_{cc}=1$ for the active backups of the Computing Combiner. We can see that at level 0, the SB has a MEPT equal to $\delta$, which corresponds to the emission time of the DCs' contributions, while the SB's backups have a METB equal to 0. Indeed, the execution time of the backups is only counted from their activation time, since the data replication is done in parallel with the primary node and the emission time is therefore already integrated. From this figure, we can see that the calculation of the deadline is strongly influenced by the height of the tree and the number of backups. Note that the horizontal and vertical partitioning have no impact on the deadline calibration as long as they do not change the height of the QEP and the number of backups per partition.

## Conflicts of Interest:

On behalf of all authors, the corresponding author states that there is no conflict of interest.

## Data Availability Statement

The datasets generated during and/or analyzed during the current study are available from the corresponding author upon reasonable request.
its result to the Computers. A first intermediate timeout at the Computer is hence fixed at $\Delta_1=2\delta$, at which the first backup of the Snapshot Builder will be activated. Recursively, as we expect the result of this first backup to be received after a maximum additional $2\delta$ delay, we can define the second intermediate timeout (activating the second backup) at $\Delta_2=\Delta_1+2\delta$, and so on for the next backups.

We can generalize this to obtain the timeout $\Delta_b$ for any passive backup node in the tree. Indeed, this timeout is determined by adding $2\delta$ (activation and response delays) to the Maximum Execution Time of a given Backup node (METB). At tree level $l+1$, METB is equal to the sum of:

- The consecutive activation time of all direct predecessor backup nodes and their corresponding response time: $b \times 2 \times \delta$, with $b$ the number of backup nodes.

- The recursive runtime of these backup nodes if they are not yet provisioned. This value depends directly on the number of levels $l$ in the sub-QEP (i.e., the tree height): $b \times \text{METB}(l)$

$$ \text{Thus, } \text{METB}(l+1) = b \times (2 \times \delta + \text{METB}(l)) $$

Similarly, the Maximum Execution Time of a Primary node (METP) at tree level $l+1$ is equal to the sum of:

- The emission time of its direct predecessor primary node and its recursive runtime: $\delta + \text{METP}(l)$

- The successive activation time of the direct predecessor backup nodes and their corresponding response time: $b \times 2 \times \delta$

- The recursive runtime of these backup nodes if they are not yet provisioned: $b \times \text{METB}(l)$

$$ \text{METP}(l+1) = \delta + \text{METP}(l) + b \times (2 \times \delta + \text{METB}(l)) $$

<figure><img src="image_22.png" /><figcaption>Figure 21: Example of Deadline Calibration</figcaption></figure>

Figure 21 shows an example of the query deadline calibration with the QEP of Figure 6, setting $b=2$ for the passive backups of the Snapshot Builders and Computers and $b_{cc}=1$ for the active backups of the Computing Combiner. We can see that at level 0, the SB has a MEPT equal to $\delta$, which corresponds to the emission time of the DCs' contributions, while the SB's backups have a METB equal to 0. Indeed, the execution time of the backups is only counted from their activation time, since the data replication is done in parallel with the primary node and the emission time is therefore already integrated. From this figure, we can see that the calculation of the deadline is strongly influenced by the height of the tree and the number of backups. Note that the horizontal and vertical partitioning have no impact on the deadline calibration as long as they do not change the height of the QEP and the number of backups per partition.

### Conflicts of Interest:

On behalf of all authors, the corresponding author states that there is no conflict of interest.

### Data Availability Statement

The datasets generated during and/or analyzed during the current study are available from the corresponding author upon reasonable request.