# Edgelet Computing: Enabling Privacy-Preserving Decentralized Data Processing at the Network Edge

Ludovic Javet, Nicolas Anciaux, Luc Bouganim, Philippe Pucheral

<figure><img src="image_1.png" /></figure>

## To cite this version:

Ludovic Javet, Nicolas Anciaux, Luc Bouganim, Philippe Pucheral. Edgelet Computing: Enabling Privacy-Preserving Decentralized Data Processing at the Network Edge. Personal and Ubiquitous Computing, 2024, 10.1007/s00779-024-01821-9. hal-04594280

HAL Id: hal-04594280

https://inria.hal.science/hal-04594280

Submitted on 30 May 2024

HAL is a multi-disciplinary open access archive for the deposit and dissemination of scientific research documents, whether they are published or not. The documents may come from teaching and research institutions in France or abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est destinée au dépôt et à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Edgelet Computing: Enabling Privacy-Preserving Decentralized Data Processing at the Network Edge

Ludovic Javet, Nicolas Anciaux, Luc Bouganim, Philippe Pucheral

► To cite this version:

Ludovic Javet, Nicolas Anciaux, Luc Bouganim, Philippe Pucheral. Edgelet Computing: Enabling Privacy-Preserving Decentralized Data Processing at the Network Edge. Personal and Ubiquitous Computing, 2025, 29, pp.45-75. 10.1007/s00779-024-01821-9. hal-04594280

HAL Id: hal-04594280

https://inria.hal.science/hal-04594280v1

Submitted on 30 May 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Edgelet Computing: Enabling Privacy-Preserving
Decentralized Data Processing at the Network Edge

Ludovic Javet¹,², Nicolas Anciaux¹,², Luc Bouganim¹,², Philippe Pucheral¹,²

(¹)Petrus team, Inria, France, (²)David Lab., U. Versailles St-Quentin-en-Yvelines, France
firstname.lastname@inria.fr

**Abstract**

The convergence of Opportunistic Networks and Trusted Execution Environments at the network edge presents a compelling opportunity for fully decentralized privacy-preserving data processing. Based on this convergence, we define the concept of Edgelet computing, a new paradigm for executing powerful and privacy-preserving distributed queries on personal devices. Our objective is to establish a robust, secure, and scalable execution framework with strong individual privacy guarantees. This paper first proposes a liability model tailored to decentralized executions on crowd members' devices, along with a query evaluation model that differs from the traditional database closed-world assumption. Second, it defines essential properties for ensuring the security, resiliency and validity of executions, and subsequently presents several methods and strategies for their enforcement. Through a comprehensive qualitative analysis and extensive evaluations, we showcase the relevance and effectiveness of the approach, demonstrating that Edgelet Computing holds potential for the emergence of novel and important classes of applications.

**Keywords** Crowd computing · Trusted Execution Environment · Opportunistic Network

# 1 Introduction

The edge of the Internet is expanding at a much higher pace than its core, with 29.3 billion connected devices by 2023 [17]. At the same time, the Internet reliable, server-based, and infrastructure-centric approach already exhibits its limits in terms of efficiency, privacy, and energy consumption. Alternatively, infrastructure-less and self-organizing networking protocols have emerged, from the legacy MANET protocol to the Opportunistic Network (OppNet) paradigm, from which a new people-centric vision of the Internet (IoP) can emerge [19]. However, while this paradigm has attracted a lot of attention from the research community, OppNets have never been deployed at a large scale, mainly due to the lack of killer applications [67].

A game changer is the generalization of Trusted Execution Environments (TEE) [57] at the extreme edge of the network: Intel SGX [22] is becoming ubiquitous on PCs and tablets, ARM's TrustZone [54] on smartphones (Figure 1.a) and even Trusted Platform Module on smart objects (Figure 1.b). TEEs protect code and data from untrusted execution environments and from the devices' owners. They are new building blocks for the organization of fully decentralized and secure computations among data scattered on multiple personal devices, without resorting to any central authority or infrastructure. Hence, powerful large-scale privacy-preserving computations are within reach in a different – and more flexible – manner than with homomorphic cryptography [14], local differential privacy [40], or secure multiparty computation protocols [7]. Our approach leverages the security features of TEEs to enable generic computations and scalable executions, processing cleartext data without any tradeoff between privacy and accuracy.

<figure><img src="image_3.png" /><figcaption>Figure 1: Examples of Trusted Execution Environments</figcaption></figure>
# Edgelet Computing: Enabling Privacy-Preserving Decentralized Data Processing at the Network Edge

Ludovic Javet¹,², Nicolas Anciaux¹,², Luc Bouganim¹,², Philippe Pucheral¹,²

(¹)Petrus team, Inria, France, (²)David Lab., U. Versailles St-Quentin-en-Yvelines, France
firstname.lastname@inria.fr

## Abstract

The convergence of Opportunistic Networks and Trusted Execution Environments at the network edge presents a compelling opportunity for fully decentralized privacy-preserving data processing. Based on this convergence, we define the concept of Edgelet computing, a new paradigm for executing powerful and privacy-preserving distributed queries on personal devices. Our objective is to establish a robust, secure, and scalable execution framework with strong individual privacy guarantees. This paper first proposes a liability model tailored to decentralized executions on crowd members' devices, along with a query evaluation model that differs from the traditional database closed-world assumption. Second, it defines essential properties for ensuring the security, resiliency and validity of executions, and subsequently presents several methods and strategies for their enforcement. Through a comprehensive qualitative analysis and extensive evaluations, we showcase the relevance and effectiveness of the approach, demonstrating that Edgelet Computing holds potential for the emergence of novel and important classes of applications.

**Keywords** Crowd computing · Trusted Execution Environment · Opportunistic Network

## 1 Introduction

The edge of the Internet is expanding at a much higher pace than its core, with 29.3 billion connected devices by 2023 [17]. At the same time, the Internet reliable, server-based, and infrastructure-centric approach already exhibits its limits in terms of efficiency, privacy, and energy consumption. Alternatively, infrastructure-less and self-organizing networking protocols have emerged, from the legacy MANET protocol to the Opportunistic Network (OppNet) paradigm, from which a new people-centric vision of the Internet (IoP) can emerge [19]. However, while this paradigm has attracted a lot of attention from the research community, OppNets have never been deployed at a large scale, mainly due to the lack of killer applications [67].

A game changer is the generalization of Trusted Execution Environments (TEE) [57] at the extreme edge of the network: Intel SGX [22] is becoming ubiquitous on PCs and tablets, ARM's TrustZone [54] on smartphones (Figure 1.a) and even Trusted Platform Module on smart objects (Figure 1.b). TEEs protect code and data from untrusted execution environments and from the devices' owners. They are new building blocks for the organization of fully decentralized and secure computations among data scattered on multiple personal devices, without resorting to any central authority or infrastructure. Hence, powerful large-scale privacy-preserving computations are within reach in a different – and more flexible – manner than with homomorphic cryptography [14], local differential privacy [40], or secure multiparty computation protocols [7]. Our approach leverages the security features of TEEs to enable generic computations and scalable executions, processing cleartext data without any tradeoff between privacy and accuracy.

<figure><img src="image_2.png" /><figcaption>Figure 1: Examples of Trusted Execution Environments</figcaption></figure>
The convergence between OppNets and TEEs, named hereafter *Edgelet computing*, leverages secure personal devices (called edgelets) and promises concrete applications for OppNets involving crowd participation, for example:

**Opportunistic polling.** During events that attract a large audience (e.g., conferences, concerts, museums, sporting events), the participants could contribute with their data (e.g., centers of interest, nationality, age) to global processing to improve their user experience in real-time (i.e., adapting the services to the characteristics of the audience). The proximity of individuals and their personal devices makes the use of traditional communication infrastructures unnecessary, if not inappropriate, and paves the way for Opportunistic Computing [18]. For example, estimating the number of people present at a demonstration is a difficult task, both for the police and for the demonstrators themselves. The deployment of an Edgelet application could enable opportunistic counting of individuals, providing accurate statistics (e.g., based on age or political conviction) without compromising their privacy.

**Data altruism.** Introduced in the EU Data Governance Act [55], this proposal encourages data subjects to consent to process their personal data for purposes such as scientific research or public services improvement (e.g., a health survey organized by Santé Publique France). Privacy protection is paramount in this context, as it is a key element for people to participate with their sensitive data. For instance, the DomYcile Project [24] is a real-case study that proposes a secure personal box for managing the medical records of elderly individuals receiving home assistance. DomYcile allows patient associations and health or statistical agencies to query ephemeral cohorts of several thousands of these boxes, each acting as an edgelet using short-range communications. Such a scenario, detailed in subsection 3.2, could be generalized to all forms of Personal Data Management Systems [5] hosted by their holder.

These scenarios require performing complex processing over personal data, ranging from regular database aggregation queries to machine learning computations, in a highly distributed, failure-prone, and infrastructure-less context, with strong security guarantees. The specificity of this new Edgelet computing paradigm requires the definition of (1) a new liability model adapted to decentralized execution on sets of crowd members devices, which translates the shift of responsibility from cloud providers to crowd members compared to traditional cloud-based liability models and (2) a new query evaluation model where the traditional database closed-world assumption no longer applies: on the contrary, queries must be evaluated on database subsets built opportunistically, drastically changing the query evaluation process. The impact of such liability and query models on security, resiliency and validity is somehow antinomic and thus requires the definition of unusual appropriate solutions. Our objective is then threefold: we aim to build a framework that (1) is both generic and scalable, allowing complex computations on the data of thousands of individuals, (2) ensures security and respects the privacy of the people involved, and (3) is fault-tolerant in a fully decentralized environment, which is prone to failures and message loss.

The existing approaches relying on secure multiparty computation, local differential privacy or secure outsourced computations often struggle to strike an optimal balance between privacy preservation and computation accuracy. Secure multiparty computation [7], although ensuring collaborative privacy, faces difficult challenges in terms of scalability and computational efficiency, particularly when dealing with large, diverse and dynamic sets of participants. Local differential privacy [40], while protecting individual data values, may compromise the utility and accuracy of aggregate computations due to noise injection, and would not provide genericity (in the sense of supporting any type of computation). Secure computations outsourcing [2] would introduce, on the other hand, potential vulnerabilities within centralized authorities or third-party intermediaries which would not be acceptable in our context. In light of these limitations, the Edgelet computing paradigm aims to overcome these challenges by harnessing the capabilities of Trusted Execution Environments (TEE) to enable decentralized, secure, generic, and efficient computations that transcend the inherent trade-offs of existing solutions.

To achieve the objectives listed above and to match the field realities of our crowd contexts, we make the following contributions<fnref n="1" />.

- First, we characterize the Edgelet computing paradigm: a new framework for implementing powerful processing on personal devices in a highly distributed, failure-prone, and infrastructure-less environment. We specify the key features of Edgelet computing, introduce a novel liability model associated with these features, and precisely state the problem addressed through three properties, namely Security, Resiliency and Validity.

<footnote n="1">¹ This paper builds on a CCGRID conference paper [37] with important additions, namely: (1) the Edgelet computing paradigm is more precisely characterized, leading to the definition of a new dedicated liability model (section 2.2) and a snapshot query model along with a strawman execution strategy (section 2.3); (2) new security mechanisms required to enforce the purpose honesty (section 3.2) and computation honesty (section 3.3) related to this liability model; (3) a new resiliency strategy (section 4.3) and its evaluation; (4) new evaluations comparing the proposed strategies in terms of exposure (section 6.1) and (5) the consideration of Stochastic Gradient Descent algorithms that were implemented and validated (section 6.3).</footnote>
The convergence between OppNets and TEEs, named hereafter *Edgelet computing*, leverages secure personal devices (called edgelets) and promises concrete applications for OppNets involving crowd participation, for example:

**Opportunistic polling.** During events that attract a large audience (e.g., conferences, concerts, museums, sporting events), the participants could contribute with their data (e.g., centers of interest, nationality, age) to global processing to improve their user experience in real-time (i.e., adapting the services to the characteristics of the audience). The proximity of individuals and their personal devices makes the use of traditional communication infrastructures unnecessary, if not inappropriate, and paves the way for Opportunistic Computing [18]. For example, estimating the number of people present at a demonstration is a difficult task, both for the police and for the demonstrators themselves. The deployment of an Edgelet application could enable opportunistic counting of individuals, providing accurate statistics (e.g., based on age or political conviction) without compromising their privacy.

**Data altruism.** Introduced in the EU Data Governance Act [55], this proposal encourages data subjects to consent to process their personal data for purposes such as scientific research or public services improvement (e.g., a health survey organized by Santé Publique France). Privacy protection is paramount in this context, as it is a key element for people to participate with their sensitive data. For instance, the DomYcile Project [24] is a real-case study that proposes a secure personal box for managing the medical records of elderly individuals receiving home assistance. DomYcile allows patient associations and health or statistical agencies to query ephemeral cohorts of several thousands of these boxes, each acting as an edgelet using short-range communications. Such a scenario, detailed in subsection 3.2, could be generalized to all forms of Personal Data Management Systems [5] hosted by their holder.

These scenarios require performing complex processing over personal data, ranging from regular database aggregation queries to machine learning computations, in a highly distributed, failure-prone, and infrastructure-less context, with strong security guarantees. The specificity of this new Edgelet computing paradigm requires the definition of (1) a new liability model adapted to decentralized execution on sets of crowd members devices, which translates the shift of responsibility from cloud providers to crowd members compared to traditional cloud-based liability models and (2) a new query evaluation model where the traditional database closed-world assumption no longer applies: on the contrary, queries must be evaluated on database subsets built opportunistically, drastically changing the query evaluation process. The impact of such liability and query models on security, resiliency and validity is somehow antinomic and thus requires the definition of unusual appropriate solutions. Our objective is then threefold: we aim to build a framework that (1) is both generic and scalable, allowing complex computations on the data of thousands of individuals, (2) ensures security and respects the privacy of the people involved, and (3) is fault-tolerant in a fully decentralized environment, which is prone to failures and message loss.

The existing approaches relying on secure multiparty computation, local differential privacy or secure outsourced computations often struggle to strike an optimal balance between privacy preservation and computation accuracy. Secure multiparty computation [7], although ensuring collaborative privacy, faces difficult challenges in terms of scalability and computational efficiency, particularly when dealing with large, diverse and dynamic sets of participants. Local differential privacy [40], while protecting individual data values, may compromise the utility and accuracy of aggregate computations due to noise injection, and would not provide genericity (in the sense of supporting any type of computation). Secure computations outsourcing [2] would introduce, on the other hand, potential vulnerabilities within centralized authorities or third-party intermediaries which would not be acceptable in our context. In light of these limitations, the Edgelet computing paradigm aims to overcome these challenges by harnessing the capabilities of Trusted Execution Environments (TEE) to enable decentralized, secure, generic, and efficient computations that transcend the inherent trade-offs of existing solutions.

To achieve the objectives listed above and to match the field realities of our crowd contexts, we make the following contributions<fnref n="1" />.

- First, we characterize the Edgelet computing paradigm: a new framework for implementing powerful processing on personal devices in a highly distributed, failure-prone, and infrastructure-less environment. We specify the key features of Edgelet computing, introduce a novel liability model associated with these features, and precisely state the problem addressed through three properties, namely Security, Resiliency and Validity.

<footnote n="1">¹ This paper builds on a CCGRID conference paper [37] with important additions, namely: (1) the Edgelet computing paradigm is more precisely characterized, leading to the definition of a new dedicated liability model (section 2.2) and a snapshot query model along with a strawman execution strategy (section 2.3); (2) new security mechanisms required to enforce the purpose honesty (section 3.2) and computation honesty (section 3.3) related to this liability model; (3) a new resiliency strategy (section 4.3) and its evaluation; (4) new evaluations comparing the proposed strategies in terms of exposure (section 6.1) and (5) the consideration of Stochastic Gradient Descent algorithms that were implemented and validated (section 6.3).</footnote>
- Second, we introduce an unusual threat model capturing the aforementioned key features of the Edgelet computing paradigm and propose robust security mechanisms to protect the data of individuals involved in distributed queries under this threat model.

- Third, we propose and analyze three different resiliency strategies producing valid results while tolerating the failures and message losses induced by the fully decentralized environment. The first strategy is an adaptation of the traditional backup-based resiliency strategies aiming at satisfying together Resiliency, Security, and Validity in an OppNet context, whatever the query. The second strategy capitalizes on the open-world assumption inherent to the Edgelet computing paradigm to improve the execution efficiency of a large class of queries. The third strategy tries to combine the generality and the efficiency of the two preceding strategies. The proposed execution strategies are evaluated and compared to assess their relevance.

This paper is structured as follows. Section 2 presents the Edgelet Computing paradigm with its associated crowd liability model and snapshot-compliant query model. It precisely states the problem at hand. Section 3 details the threat model considered and describes the security mechanisms to enforce the security property. Section 4 presents the three proposed execution strategies, focusing on the mechanisms required to ensure resilient and valid execution despite failures or message loss. Section 5 presents a qualitative evaluation of these strategies and proposes some guidelines to help choose the most adequate strategy depending on the context. Section 6 presents an extensive evaluation of the proposed strategies with the help of the Opportunistic Network Environment (ONE) simulator [41]. Related works are discussed in Section 7. We conclude and present research perspectives in the last section.

# 2 Edgelet Computing Paradigm

To tackle the privacy protection, data management, and distributed system issues related to this environment, we define in this section the *Edgelet computing* paradigm. First, we describe the considered underlying architecture, its components, and related assumptions. Second, we propose a new model of responsibility adapted to this architecture, to rely on the participants and their devices rather than a central entity. Third, we define a new query model to enable the processing of sample data (i.e., data from a set of individuals available at the time of evaluation) and propose a strawman query execution plan that supports it. We then study the impact of the Edgelet computing context on this execution, which helps us define three required properties to ensure the security, resiliency, and validity of the query execution.

## 2.1 Key Features of Edgelet Computing

The idea of using the computational resources of personal computers or devices is not new (cf. P2P architectures [6], e.g., BOINC [11]). More recently, [48] proposed to use resources from mobile personal devices, coupled with opportunistic communications to distribute opportunistically some large computations on a set of mobile devices. In this paper, we push this idea a step further by seeking to share both the personal mobile device resources and the personal data of the device owner, as we outlined in the scenarios presented above. To the best of our knowledge, this has never been proposed before probably because of the risks related to the protection of personal data.

As stated in the introduction, the Edgelet computing architecture involves the combination of Trusted Execution Environments and Opportunistic Networks. Here, we discuss the key features of the architecture and then explore how this combination results in a new responsibility model (leveraging the TEEs' security properties) and a new query model (due to the open-world nature of OppNets).

**Trusted Execution Environments.** Trusted Executions Environments enforce two security properties, namely (1) *data confidentiality*: data manipulated within a TEE device cannot be observed from the outside; and (2) *code integrity*: an attacker cannot influence the behavior of a program executed within a TEE. In this paper, we assume that each crowd member's personal device (named *edgelet node* or *edgelet* for short) is equipped with a TEE guaranteeing to its owner the two previous properties as long as the device is not physically compromised. Indeed, side-channel attacks compromising data confidentiality cannot be totally ignored (though highly difficult to conduct), placing the device in a "Sealed-Glass Proof" mode [65] (i.e., confidentiality is broken, but not integrity).

**Opportunistic Networks.** The communication infrastructure considered in our scenarios is sidestepping any classical WAN infrastructure (e.g., Internet) for cost or energy constraints, lack of connectivity, security, privacy, or freedom of expression concerns. The communications between edgelet nodes are short-range (e.g., Wi-Fi, Bluetooth) and asynchronous, i.e., there is no time bound on the message transmission delay. For simplicity we consider an epidemic diffusion of the messages, assuming
- Second, we introduce an unusual threat model capturing the aforementioned key features of the Edgelet computing paradigm and propose robust security mechanisms to protect the data of individuals involved in distributed queries under this threat model.

- Third, we propose and analyze three different resiliency strategies producing valid results while tolerating the failures and message losses induced by the fully decentralized environment. The first strategy is an adaptation of the traditional backup-based resiliency strategies aiming at satisfying together Resiliency, Security, and Validity in an OppNet context, whatever the query. The second strategy capitalizes on the open-world assumption inherent to the Edgelet computing paradigm to improve the execution efficiency of a large class of queries. The third strategy tries to combine the generality and the efficiency of the two preceding strategies. The proposed execution strategies are evaluated and compared to assess their relevance.

This paper is structured as follows. Section 2 presents the Edgelet Computing paradigm with its associated crowd liability model and snapshot-compliant query model. It precisely states the problem at hand. Section 3 details the threat model considered and describes the security mechanisms to enforce the security property. Section 4 presents the three proposed execution strategies, focusing on the mechanisms required to ensure resilient and valid execution despite failures or message loss. Section 5 presents a qualitative evaluation of these strategies and proposes some guidelines to help choose the most adequate strategy depending on the context. Section 6 presents an extensive evaluation of the proposed strategies with the help of the Opportunistic Network Environment (ONE) simulator [41]. Related works are discussed in Section 7. We conclude and present research perspectives in the last section.

# 2 Edgelet Computing Paradigm

To tackle the privacy protection, data management, and distributed system issues related to this environment, we define in this section the *Edgelet computing* paradigm. First, we describe the considered underlying architecture, its components, and related assumptions. Second, we propose a new model of responsibility adapted to this architecture, to rely on the participants and their devices rather than a central entity. Third, we define a new query model to enable the processing of sample data (i.e., data from a set of individuals available at the time of evaluation) and propose a strawman query execution plan that supports it. We then study the impact of the Edgelet computing context on this execution, which helps us define three required properties to ensure the security, resiliency, and validity of the query execution.

## 2.1 Key Features of Edgelet Computing

The idea of using the computational resources of personal computers or devices is not new (cf. P2P architectures [6], e.g., BOINC [11]). More recently, [48] proposed to use resources from mobile personal devices, coupled with opportunistic communications to distribute opportunistically some large computations on a set of mobile devices. In this paper, we push this idea a step further by seeking to share both the personal mobile device resources and the personal data of the device owner, as we outlined in the scenarios presented above. To the best of our knowledge, this has never been proposed before probably because of the risks related to the protection of personal data.

As stated in the introduction, the Edgelet computing architecture involves the combination of Trusted Execution Environments and Opportunistic Networks. Here, we discuss the key features of the architecture and then explore how this combination results in a new responsibility model (leveraging the TEEs' security properties) and a new query model (due to the open-world nature of OppNets).

**Trusted Execution Environments.** Trusted Executions Environments enforce two security properties, namely (1) *data confidentiality*: data manipulated within a TEE device cannot be observed from the outside; and (2) *code integrity*: an attacker cannot influence the behavior of a program executed within a TEE. In this paper, we assume that each crowd member's personal device (named *edgelet node* or *edgelet* for short) is equipped with a TEE guaranteeing to its owner the two previous properties as long as the device is not physically compromised. Indeed, side-channel attacks compromising data confidentiality cannot be totally ignored (though highly difficult to conduct), placing the device in a "Sealed-Glass Proof" mode [65] (i.e., confidentiality is broken, but not integrity).

**Opportunistic Networks.** The communication infrastructure considered in our scenarios is sidestepping any classical WAN infrastructure (e.g., Internet) for cost or energy constraints, lack of connectivity, security, privacy, or freedom of expression concerns. The communications between edgelet nodes are short-range (e.g., Wi-Fi, Bluetooth) and asynchronous, i.e., there is no time bound on the message transmission delay. For simplicity we consider an epidemic diffusion of the messages, assuming
that messages are transferred from device to device following a store-carry-forward communication protocol [68]. Other more
optimized protocols, e.g., exploiting moving patterns of users [36], are considered as future work.

As mentioned earlier, we want to explore the possibility of relying exclusively on secure personal devices to perform the
required computations, i.e., without relying on any external infrastructure like central servers. Thus, similar to P2P and cross-
device federated learning architectures, we assume processing to be directly distributed across edge devices, without requiring
the deployment or maintenance of central servers. The execution of computations in the Edgelet architecture is then achieved
in a fully decentralized manner.

To summarize, the Edgelet architecture is characterized by:

- *Edgelet nodes:* Each crowd member's personal device is equipped with a TEE, which provides secure storage and processing capabilities.

- *Opportunistic communications:* Edgelets communicate with each other through Opportunistic Networks whose messages are transmitted at short range with no time limit for their delivery.

- *Fully decentralized execution:* The processing of personal data is fully decentralized on edgelets and does not rely on central servers.

## 2.2 Crowd Liability Model

Responsibility models are usually introduced to help define the respective responsibilities of all actors involved in a given computing infrastructure. Such models guide judges, practitioners, and researchers when confronted with legal questions related to the protection of data and code. For instance, the *Shared Responsibility Model (SRM)* [61] states the responsibilities of cloud service providers and customers to secure all aspects of a cloud environment. To illustrate this, in an *Infrastructure* as a Service (IaaS) context, the customer is responsible for the data, application, and Operation System (OS) parts and the cloud provider for the rest of the infrastructure (virtualization, servers, storage, network), while in a Software as a Service (SaaS) context, the latter endorses also the responsibility of the application and OS.

The SRM is generic enough to apply to a large variety of application domains. Assuming personal data is managed in a SaaS context, the customer is the actor playing the data controller role in the GDPR sense (e.g., a company, an administration, an NGO), and the cloud provider plays the role of data processor. Yet, the individuals themselves are no longer in the loop after having given their consent to the data controller to process their data.

Conversely, in crowd computing applications managing personal data, the individual is at the heart of the infrastructure. However, we are not aware of any similar shared responsibility model adapted to crowd computing. Unsurprisingly, no one would agree to endorse the data processor or data controller responsibility in a fully decentralized computing context where each device is under the control of a distinct individual. The consequence is that crowd computing usually handles use cases where the shared data is not really sensitive (e.g., sensor data like temperature or noise captured by a smartphone) but cannot tackle use cases involving sensitive personal data (e.g., medical data) that require tangible security guarantees. In this section, we define such a shared responsibility model, adapted to the Edgelet computing context, that we call the *Crowd Liability Model (CLM)*.

Crowd liability conveys the idea that the data controller is the crowd (i.e., the result of the processing is expected to benefit, directly or indirectly, the crowd members who agree together to the why and the how of this processing); hence there are as many potential data processors as there are crowd members. The corollary of this idea is that each crowd member is expected to do their best to honestly play the fragment of the data controller and data processor roles assigned to them, but the participation in the processing of some dishonest crowd members or of corrupted devices owned by honest crowd members cannot be precluded.

To translate this idea into a responsibility model, we split the data controller into two roles, (1) the *Recipient* which is the Edgelet selected to issue the processing and fairly disseminate the result to the crowd, and (2) the *Regulator* (an external trusted entity or a set of crowd members) which assesses the *Purpose honesty* (i.e., the honesty of the processing purpose) and approves it on behalf of the crowd. Considering that crowd members usually do not have the technical skills to endorse the data processor role, we limit their responsibility to the usage of a genuine TEE-enabled device (*Edgelet physical integrity*) to contribute to the processing (i.e., the crowd member is not liable for potential corruption of their device but they become liable if they tamper with their TEE). Then, we introduce a *Trusted Assistant* role, which is played on behalf of the Edgelet node owners, and encompasses all technical principles embedded in each edgelet node to help the crowd members endorse the fragment of the data processor roles assigned to them. Basically, the Trusted Assistant is expected to guarantee the so-called *Computation honesty*, namely: (1) any decentralized execution strictly complies with the processing approved by the Regulator, (2) any (honest) crowd member can contribute to the computation without risk, even if they lack the technical ability to secure their
that messages are transferred from device to device following a store-carry-forward communication protocol [68]. Other more
optimized protocols, e.g., exploiting moving patterns of users [36], are considered as future work.

As mentioned earlier, we want to explore the possibility of relying exclusively on secure personal devices to perform the
required computations, i.e., without relying on any external infrastructure like central servers. Thus, similar to P2P and cross-
device federated learning architectures, we assume processing to be directly distributed across edge devices, without requiring
the deployment or maintenance of central servers. The execution of computations in the Edgelet architecture is then achieved
in a fully decentralized manner.

To summarize, the Edgelet architecture is characterized by:

- *Edgelet nodes:* Each crowd member's personal device is equipped with a TEE, which provides secure storage and processing capabilities.

- *Opportunistic communications:* Edgelets communicate with each other through Opportunistic Networks whose messages are transmitted at short range with no time limit for their delivery.

- *Fully decentralized execution:* The processing of personal data is fully decentralized on edgelets and does not rely on central servers.

## 2.2 Crowd Liability Model

Responsibility models are usually introduced to help define the respective responsibilities of all actors involved in a given computing infrastructure. Such models guide judges, practitioners, and researchers when confronted with legal questions related to the protection of data and code. For instance, the *Shared Responsibility Model (SRM)* [61] states the responsibilities of cloud service providers and customers to secure all aspects of a cloud environment. To illustrate this, in an *Infrastructure* as a Service (IaaS) context, the customer is responsible for the data, application, and Operation System (OS) parts and the cloud provider for the rest of the infrastructure (virtualization, servers, storage, network), while in a Software as a Service (SaaS) context, the latter endorses also the responsibility of the application and OS.

The SRM is generic enough to apply to a large variety of application domains. Assuming personal data is managed in a SaaS context, the customer is the actor playing the data controller role in the GDPR sense (e.g., a company, an administration, an NGO), and the cloud provider plays the role of data processor. Yet, the individuals themselves are no longer in the loop after having given their consent to the data controller to process their data.

Conversely, in crowd computing applications managing personal data, the individual is at the heart of the infrastructure. However, we are not aware of any similar shared responsibility model adapted to crowd computing. Unsurprisingly, no one would agree to endorse the data processor or data controller responsibility in a fully decentralized computing context where each device is under the control of a distinct individual. The consequence is that crowd computing usually handles use cases where the shared data is not really sensitive (e.g., sensor data like temperature or noise captured by a smartphone) but cannot tackle use cases involving sensitive personal data (e.g., medical data) that require tangible security guarantees. In this section, we define such a shared responsibility model, adapted to the Edgelet computing context, that we call the *Crowd Liability Model (CLM)*.

Crowd liability conveys the idea that the data controller is the crowd (i.e., the result of the processing is expected to benefit, directly or indirectly, the crowd members who agree together to the why and the how of this processing); hence there are as many potential data processors as there are crowd members. The corollary of this idea is that each crowd member is expected to do their best to honestly play the fragment of the data controller and data processor roles assigned to them, but the participation in the processing of some dishonest crowd members or of corrupted devices owned by honest crowd members cannot be precluded.

To translate this idea into a responsibility model, we split the data controller into two roles, (1) the *Recipient* which is the Edgelet selected to issue the processing and fairly disseminate the result to the crowd, and (2) the *Regulator* (an external trusted entity or a set of crowd members) which assesses the *Purpose honesty* (i.e., the honesty of the processing purpose) and approves it on behalf of the crowd. Considering that crowd members usually do not have the technical skills to endorse the data processor role, we limit their responsibility to the usage of a genuine TEE-enabled device (*Edgelet physical integrity*) to contribute to the processing (i.e., the crowd member is not liable for potential corruption of their device but they become liable if they tamper with their TEE). Then, we introduce a *Trusted Assistant* role, which is played on behalf of the Edgelet node owners, and encompasses all technical principles embedded in each edgelet node to help the crowd members endorse the fragment of the data processor roles assigned to them. Basically, the Trusted Assistant is expected to guarantee the so-called *Computation honesty*, namely: (1) any decentralized execution strictly complies with the processing approved by the Regulator, (2) any (honest) crowd member can contribute to the computation without risk, even if they lack the technical ability to secure their
device, as long as they are using an up-to-date TEE and (3) any (dishonest) crowd member is defeated when attempting a massive attack.

Note that, as we detail in Section 3, point (3) of Computation honesty necessarily leads to (i) decentralizing operators and data to reduce the benefit of a successful attack by a dishonest crowd member and (ii) randomly selecting the crowd member devices that carry out the computations to reduce the risk of a successful attack by a dishonest crowd member. This further justifies the terminology used in our model, which spreads the liability across the crowd.

Table 1 below transcribes the CLM with the distribution of responsibilities according to tasks and roles.

<table><caption>Table 1: Crowd Liability Model (CLM)</caption><thead><tr><th></th><th>Recipient</th><th>Regulator</th><th>Trusted Assistant</th><th>Crowd Members</th></tr></thead><tbody><tr><th>Result dissemination</th><td>X</td><td></td><td></td><td></td></tr><tr><th>Purpose honesty</th><td></td><td>X</td><td></td><td></td></tr><tr><th>Computation honesty</th><td></td><td></td><td>X</td><td></td></tr><tr><th>Edgelet physical integrity</th><td></td><td></td><td></td><td>X</td></tr></tbody></table>

Figure 2 summarizes the Edgelet Computing paradigm: (1) The Regulatory Agent checks the honesty of the processing (Query) purpose; (2) the Recipient (in blue) disseminates the Query to the Crowd members through the OppNet. Each crowd member ensures the physical integrity of its Edgelet and the Trusted Assistant ensures that the computation takes place as decided in the Query Execution Plan. The decentralized query execution then takes place between Data processors, manipulating personal data from Data contributors. Finally, the result is sent to the Recipient which fairly disseminates it to the crowd. Edgelet Computing thus differs from Edge Computing [28] since it relies exclusively on the edges to organize the distributed computations, without the need for any infrastructure (see also Section 7). Hence, the CLM Trusted Assistant is implemented exclusively on edgelets, handling both processing and communications, with code integrity guaranteed by TEEs.

<figure><img src="image_4.png" /><figcaption>Figure 2: Overview of Edgelet Computing</figcaption></figure>

## 2.3 Snapshot-compliant Query Model

We consider distributed computations involving personal data hosted in (potentially large) sets of edgelet nodes from smartphones and tablets to more specific smart objects. Moreover, contrary to participatory sensing or sensor networks that focus on stream queries over elementary data, we consider rich data (e.g., healthcare folders, and spending habits) and advanced processing (e.g., database statistics, data mining, and machine learning). We assume that edgelets data can be queried as a shared database with a uniform schema. More precisely, each device may host a set of database schemas, typically one per application domain. The database schemas may be defined by a government agency (e.g., Ministry of Health), a private consortium (e.g., a group of banks and insurance), or an NGO. Consequently, for a given query expressed on a given database schema, the universe of edgelets data *E* can be seen as a horizontal partitioning of the corresponding global database.

The computations under consideration (called *Query* hereafter) must cope with the uncertainty inherent to the Edgelet setting, making the traditional database closed-world assumption irrelevant. In fact, only a subset of the participants is available
device, as long as they are using an up-to-date TEE and (3) any (dishonest) crowd member is defeated when attempting a massive attack.

Note that, as we detail in Section 3, point (3) of Computation honesty necessarily leads to (i) decentralizing operators and data to reduce the benefit of a successful attack by a dishonest crowd member and (ii) randomly selecting the crowd member devices that carry out the computations to reduce the risk of a successful attack by a dishonest crowd member. This further justifies the terminology used in our model, which spreads the liability across the crowd.

Table 1 below transcribes the CLM with the distribution of responsibilities according to tasks and roles.

<table><caption>Table 1: Crowd Liability Model (CLM)</caption><thead><tr><th></th><th>Recipient</th><th>Regulator</th><th>Trusted Assistant</th><th>Crowd Members</th></tr></thead><tbody><tr><th>Result dissemination</th><td>X</td><td></td><td></td><td></td></tr><tr><th>Purpose honesty</th><td></td><td>X</td><td></td><td></td></tr><tr><th>Computation honesty</th><td></td><td></td><td>X</td><td></td></tr><tr><th>Edgelet physical integrity</th><td></td><td></td><td></td><td>X</td></tr></tbody></table>

Figure 2 summarizes the Edgelet Computing paradigm: (1) The Regulatory Agent checks the honesty of the processing (Query) purpose; (2) the Recipient (in blue) disseminates the Query to the Crowd members through the OppNet. Each crowd member ensures the physical integrity of its Edgelet and the Trusted Assistant ensures that the computation takes place as decided in the Query Execution Plan. The decentralized query execution then takes place between Data processors, manipulating personal data from Data contributors. Finally, the result is sent to the Recipient which fairly disseminates it to the crowd. Edgelet Computing thus differs from Edge Computing [28] since it relies exclusively on the edges to organize the distributed computations, without the need for any infrastructure (see also Section 7). Hence, the CLM Trusted Assistant is implemented exclusively on edgelets, handling both processing and communications, with code integrity guaranteed by TEEs.

<figure><img src="image_3.png" /><figcaption>Figure 2: Overview of Edgelet Computing</figcaption></figure>

## 2.3 Snapshot-compliant Query Model

We consider distributed computations involving personal data hosted in (potentially large) sets of edgelet nodes from smartphones and tablets to more specific smart objects. Moreover, contrary to participatory sensing or sensor networks that focus on stream queries over elementary data, we consider rich data (e.g., healthcare folders, and spending habits) and advanced processing (e.g., database statistics, data mining, and machine learning). We assume that edgelets data can be queried as a shared database with a uniform schema. More precisely, each device may host a set of database schemas, typically one per application domain. The database schemas may be defined by a government agency (e.g., Ministry of Health), a private consortium (e.g., a group of banks and insurance), or an NGO. Consequently, for a given query expressed on a given database schema, the universe of edgelets data *E* can be seen as a horizontal partitioning of the corresponding global database.

The computations under consideration (called *Query* hereafter) must cope with the uncertainty inherent to the Edgelet setting, making the traditional database closed-world assumption irrelevant. In fact, only a subset of the participants is available
for execution, and only a subset of the data arrives at its destination on time. Thus, considering an open-world query model for edgelets leads us to introduce the notion of *snapshot-compliant query*.

**Snapshot-compliant query:** Given $E$ the universe of edgelets data and $Q$ a query targeting a dataset $D \subseteq E$, the representativeness of the snapshot $D$ for $Q$ is defined by a set $P$ of predicates over elements of $E$ (e.g., $age > 65$) and by a cardinality (e.g., $|D| = 2000$). We denote by $\zeta_Q(E)$ the set of all representative snapshots of $E$ enforcing $P$ and $|D|$. The Query $Q$ is *snapshot compliant* if the result of $Q$ considering any snapshot of $\zeta_Q(E)$ is equivalent to the Recipient. In other words, a snapshot-compliant query, evaluated on any representative snapshot (enforcing $P$ and $|D|$), will give a satisfactory result for the Recipient.

We consider that a query is expressed by a *Query Execution Plan* (QEP), which is a directed graph where vertices materialize the operators to be computed and edges represent the dataflow among them, with messages sent through the OppNet. The simplest form of a QEP is a tree with *Data Contributors* (DCs) at the leaves, which are the edgelets of crowd members who gave their consent to contribute to the query with their data. Other operators of the QEP are *Data Processors* (DPs), i.e., edgelets that contribute to the processing of the contributed data to produce the final result for the Recipient (R), the root of the QEP. Thus, the DPs either consume the outputs of a set of DCs or the outputs of other DPs.

**Strawman execution.** Let us introduce the basis for the query model by considering a strawman execution. To satisfy a snapshot-compliant query, we only need to define two types of data processors:

- The *Snapshot Builder* (SB) whose role is to build a dataset, representative from the data transmitted by the DCs.

- The *Computer* (C) whose role is to perform the computation required by the query on the representative snapshot built by SB.

Then, the strawman QEP proceeds in three steps as illustrated in Figure 3.

1. Each Data Contributor $DC_i$ sends its data to the Snapshot Builder.

2. SB builds a snapshot $D = \cup_1^n DC_i$ compliant with the set of predicates $P$ and the cardinality $|D|$ and sends it to the Computer.

3. C performs the computation on $D$ and sends the final result to the Recipient.

<figure><img src="image_5.png" /><figcaption>Figure 3: Strawman Query Execution Plan</figcaption></figure>

Note that, since we consider OppNets, we do not consider pipeline communication between edgelets because (1) it generates too many messages, overloading the OppNet and (2) it is very difficult to manage since there is no bound on the transmission delays. Thus, we consider that a DP works in a blocking mode, i.e., it waits for all its input before processing it and producing the output. Similarly, a DC produces all its output in a single message. Hence, any message is sent atomically through the OppNet, i.e., the payload is either totally received by the recipient or not at all. Furthermore, implementing the Snapshot-compliant Query Model in an OppNet context makes it difficult to manage failures, as communications are completely asynchronous and, consequently, the use of reliable failure detectors is impossible (see the Resiliency property below).

## 2.4 Problem Statement

Ensuring security, fault tolerance, and query validity in our context is difficult because of the conflicting impact of snapshot compliance and crowd liability. Typically, crowd liability inherently requires that the evaluation be distributed across a larger set of devices for security reasons (see the end of subsection 2.2), whereas snapshot compliance would be more easily achieved by using a single crowd member device for processing (typically if a single Data Processor evaluates SB and thus qualifies the snapshot $D$ used for the current query $Q$, a local check is all that is needed to ensure compliance with the set of predicates $P$
for execution, and only a subset of the data arrives at its destination on time. Thus, considering an open-world query model for edgelets leads us to introduce the notion of *snapshot-compliant query*.

**Snapshot-compliant query:** Given *E* the universe of edgelets data and *Q* a query targeting a dataset *D* ⊆ *E*, the representativeness of the snapshot *D* for *Q* is defined by a set *P* of predicates over elements of *E* (e.g., *age* > 65) and by a cardinality (e.g., |*D*| = 2000). We denote by ζ<sub>Q</sub>(*E*) the set of all representative snapshots of *E* enforcing *P* and |*D*|. The Query *Q* is *snapshot compliant* if the result of *Q* considering any snapshot of ζ<sub>Q</sub>(*E*) is equivalent to the Recipient. In other words, a snapshot-compliant query, evaluated on any representative snapshot (enforcing *P* and |*D*|), will give a satisfactory result for the Recipient.

We consider that a query is expressed by a *Query Execution Plan* (QEP), which is a directed graph where vertices materialize the operators to be computed and edges represent the dataflow among them, with messages sent through the OppNet. The simplest form of a QEP is a tree with *Data Contributors* (DCs) at the leaves, which are the edgelets of crowd members who gave their consent to contribute to the query with their data. Other operators of the QEP are *Data Processors* (DPs), i.e., edgelets that contribute to the processing of the contributed data to produce the final result for the Recipient (R), the root of the QEP. Thus, the DPs either consume the outputs of a set of DCs or the outputs of other DPs.

**Strawman execution.** Let us introduce the basis for the query model by considering a strawman execution. To satisfy a snapshot-compliant query, we only need to define two types of data processors:

- The *Snapshot Builder* (SB) whose role is to build a dataset, representative from the data transmitted by the DCs.

- The *Computer* (C) whose role is to perform the computation required by the query on the representative snapshot built by SB.

Then, the strawman QEP proceeds in three steps as illustrated in Figure 3.

1. Each Data Contributor DCᵢ sends its data to the Snapshot Builder.

2. SB builds a snapshot $D = \bigcup_{i=1}^{n} DC_i$ compliant with the set of predicates $P$ and the cardinality $|D|$ and sends it to the Computer.

3. C performs the computation on *D* and sends the final result to the Recipient.

<figure><img src="image_4.png" /><figcaption>Figure 3: Strawman Query Execution Plan</figcaption></figure>

Note that, since we consider OppNets, we do not consider pipeline communication between edgelets because (1) it generates too many messages, overloading the OppNet and (2) it is very difficult to manage since there is no bound on the transmission delays. Thus, we consider that a DP works in a blocking mode, i.e., it waits for all its input before processing it and producing the output. Similarly, a DC produces all its output in a single message. Hence, any message is sent atomically through the OppNet, i.e., the payload is either totally received by the recipient or not at all. Furthermore, implementing the Snapshot-compliant Query Model in an OppNet context makes it difficult to manage failures, as communications are completely asynchronous and, consequently, the use of reliable failure detectors is impossible (see the Resiliency property below).

**2.4 Problem Statement**

Ensuring security, fault tolerance, and query validity in our context is difficult because of the conflicting impact of snapshot
compliance and crowd liability. Typically, crowd liability inherently requires that the evaluation be distributed across a larger
set of devices for security reasons (see the end of subsection 2.2), whereas snapshot compliance would be more easily achieved
by using a single crowd member device for processing (typically if a single Data Processor evaluates SB and thus qualifies the
snapshot *D* used for the current query *Q*, a local check is all that is needed to ensure compliance with the set of predicates *P*
and the desired cardinality $|D|$. This strawman execution hence does not answer any of the challenges posed by the considered context in terms of security, resiliency, and validity. Based on these observations, we then define the properties required to tackle the problem.

**Security.** Even if edgelets are secured by TEEs, they can still be attacked (see subsection 3.1). For instance, an execution relying on a single device, as is the case for SB and C in the strawman execution, gives access to the full dataset, that could be fully leaked in case of a successful attack on SB or C. We thus have to circumscribe this risk by decomposing operators (e.g., using horizontal and/or vertical partitioning) into sub-operators assigned to different edgelets. The liability shift to the crowd must be carried out in a context where a few attacked devices can jeopardize the security of the whole system with no way to detect them, leading to the following property:

**Security property:** Each edgelet integrates mechanisms enforcing the CLM's Purpose honesty and Computation honesty on behalf of the Crowd Members.

**Resiliency.** Edgelets are personal devices and are therefore susceptible to failure and/or voluntary shutdown. In addition, these devices communicate via OppNets that do not guarantee bounds on communication delays. It is thus necessary to proactively introduce mechanisms to withstand these failures or communication problems. A resilient execution should therefore include backup or replication operators. The objective here is to guarantee that the execution has a significant chance of success, especially when the execution is decomposed on a large set of edgelets.

Since reliable failure detectors cannot exist in OppNets due to the unpredictability of message delays, it makes it difficult to predict the time to build a snapshot from random contributors and to execute a query. The system's liveness must then be guaranteed based on fault presumptions only and on the probability of success for queries associated with a deadline (i.e., a maximum time allowed for executions):

**Resiliency property:** Given a probability of fault presumption $p_f$ for any edgelet, a *query deadline*, and an expected probability of success $p_s$, a query $Q$ must be completed before the deadline with a probability greater than $p_s$.

**Validity.** Enforcing the two previous properties leads to a much more complex QEP (with several SBs, several Cs as well as with backup edgelets and/or replicated operators) which could then result in an invalid computation if inconsistencies occur at some point. It is therefore necessary to ensure that the execution is valid, either by adding synchronization mechanisms before the computation, or verification mechanisms after the computation. The snapshot consistency must be preserved all along the query processing despite presumed faults and message loss between Data Processors to guarantee a consistent result:

**Validity property:** The Edgelet query execution result must be identical to a centralized query execution over at least one snapshot of $\zeta_Q(E)$. Formally, $\forall D_i \in \zeta_Q(E), \exists D_j \in \zeta_Q(E) / Q_E(D_i) = Q_C(D_j)$, with $Q_E$ (resp. $Q_C$) denoting the Edgelet (resp. centralized) execution of a query $Q$.

To summarize, we have defined three properties that are particularly challenging to tackle together given their mutual impact. Security is addressed in Section 3 while Resiliency and Validity are addressed in Section 4.

# 3 Security Enforcement

This section is devoted to the security mechanisms and algorithms required for enforcing the Crowd Liability Model (CLM), specific to the Edgelet computing paradigm. The two cornerstones of the CLM are *Purpose honesty*, which deals with the approval by the crowd of the why and the how of the processing, and *Computation honesty*, which ensures the trustworthiness of the processing during its decentralized execution. These two principles are respectively addressed in subsections 3.2 and 3.3. However, since the CLM defines new roles and responsibilities and relies on specific security assumptions, a dedicated threat model must be defined first.

## 3.1 Dedicated Threat Model

A dedicated threat model is required to capture (1) the shift of responsibility from a usual central entity (i.e., the data controller in the GDPR) to the crowd and (2) the TEE trustworthiness. We define this model as follows.

### Ingenuous Recipient.

- *Role:* initiates the processing of a QEP and receives the final results. Does not take part in the execution.

- *Played by:* depending on the use case, one or more crowd members, medical workers, statistical agencies, etc.

- *Trust:* We do not want to impose the Recipient to be equipped with a TEE-enabled device to avoid reducing the targeted
and the desired cardinality $|D|$. This strawman execution hence does not answer any of the challenges posed by the considered context in terms of security, resiliency, and validity. Based on these observations, we then define the properties required to tackle the problem.

**Security.** Even if edgelets are secured by TEEs, they can still be attacked (see subsection 3.1). For instance, an execution relying on a single device, as is the case for SB and C in the strawman execution, gives access to the full dataset, that could be fully leaked in case of a successful attack on SB or C. We thus have to circumscribe this risk by decomposing operators (e.g., using horizontal and/or vertical partitioning) into sub-operators assigned to different edgelets. The liability shift to the crowd must be carried out in a context where a few attacked devices can jeopardize the security of the whole system with no way to detect them, leading to the following property:

**Security property:** Each edgelet integrates mechanisms enforcing the CLM's Purpose honesty and Computation honesty on behalf of the Crowd Members.

**Resiliency.** Edgelets are personal devices and are therefore susceptible to failure and/or voluntary shutdown. In addition, these devices communicate via OppNets that do not guarantee bounds on communication delays. It is thus necessary to proactively introduce mechanisms to withstand these failures or communication problems. A resilient execution should therefore include backup or replication operators. The objective here is to guarantee that the execution has a significant chance of success, especially when the execution is decomposed on a large set of edgelets.

Since reliable failure detectors cannot exist in OppNets due to the unpredictability of message delays, it makes it difficult to predict the time to build a snapshot from random contributors and to execute a query. The system's liveness must then be guaranteed based on fault presumptions only and on the probability of success for queries associated with a deadline (i.e., a maximum time allowed for executions):

**Resiliency property:** Given a probability of fault presumption $p_f$ for any edgelet, a *query deadline*, and an expected probability of success $p_s$, a query $Q$ must be completed before the deadline with a probability greater than $p_s$.

**Validity.** Enforcing the two previous properties leads to a much more complex QEP (with several SBs, several Cs as well as with backup edgelets and/or replicated operators) which could then result in an invalid computation if inconsistencies occur at some point. It is therefore necessary to ensure that the execution is valid, either by adding synchronization mechanisms before the computation, or verification mechanisms after the computation. The snapshot consistency must be preserved all along the query processing despite presumed faults and message loss between Data Processors to guarantee a consistent result:

**Validity property:** The Edgelet query execution result must be identical to a centralized query execution over at least one snapshot of $\zeta_Q(E)$. Formally, $\forall D_i \in \zeta_Q(E), \exists D_j \in \zeta_Q(E) / Q_E(D_i) = Q_C(D_j)$, with $Q_E$ (resp. $Q_C$) denoting the Edgelet (resp. centralized) execution of a query $Q$.

To summarize, we have defined three properties that are particularly challenging to tackle together given their mutual impact. Security is addressed in Section 3 while Resiliency and Validity are addressed in Section 4.

# 3 Security Enforcement

This section is devoted to the security mechanisms and algorithms required for enforcing the Crowd Liability Model (CLM), specific to the Edgelet computing paradigm. The two cornerstones of the CLM are *Purpose honesty*, which deals with the approval by the crowd of the why and the how of the processing, and *Computation honesty*, which ensures the trustworthiness of the processing during its decentralized execution. These two principles are respectively addressed in subsections 3.2 and 3.3. However, since the CLM defines new roles and responsibilities and relies on specific security assumptions, a dedicated threat model must be defined first.

## 3.1 Dedicated Threat Model

A dedicated threat model is required to capture (1) the shift of responsibility from a usual central entity (i.e., the data controller in the GDPR) to the crowd and (2) the TEE trustworthiness. We define this model as follows.

### Ingenuous Recipient.

- *Role:* initiates the processing of a QEP and receives the final results. Does not take part in the execution.

- *Played by:* depending on the use case, one or more crowd members, medical workers, statistical agencies, etc.

- *Trust:* We do not want to impose the Recipient to be equipped with a TEE-enabled device to avoid reducing the targeted
use cases, explaining why we exclude it from the actual processing of the QEP. However, we do not question the good faith of the Recipient. Thus, even if it receives the results of the processing in clear text, we do not consider inference attacks from its side (i.e., crossing the results of multiple queries).

**Wolf in sheepfold Participants.**

- *Role:* contributes with data (*Data Contributor*) and/or processing power (*Data Processor*) in a QEP.

- *Played by:* any participant equipped with a TEE-enabled device.

- *Trust:* as said in subsection 2.1, side-channel attacks on a TEE-enabled device cannot be totally precluded despite their complexity (requires tampering with the device). We assume a large majority of honest participants (the lambs) and a few “sealed glass-proof” ones (the wolves).

**Regulator.**

- *Role:* reviews and approves the processing to be performed. This role is not devoted to the query execution itself.

- *Played by:* either an external entity (e.g., a privacy regulatory agency like the CNIL in France) or a representative group of crowd members engaged in a collective validation process.

- *Trust:* full.

**3.2 Purpose Honesty**

In this subsection, we focus on the initialization of queries and how the Recipient can prove its honesty. To this end, we propose to build on the manifest-based framework [42], so that the recipient can declare the why and how of processing. Here is its implementation in our context:

First, the Recipient specifies a manifest describing the query to be performed. This manifest consists of four elements: (1) the general purpose of the processing expressed in natural language, (2) the Query Execution Plan, (3) the set of representativeness predicates *P* of the targeted dataset *D* as well as its cardinality |*D*| and (4) the source code of the operators to be executed on each edgelet node. Subsequently, the Recipient submits the manifest to the Regulator for verification of its compliance with the expected privacy practices. Once verified, the Regulator signs the manifest and returns it to the Recipient. This certified manifest will be used for the edgelet assignment protocol presented in the next subsection, after which the query manifest will be ready for dissemination in the Opportunistic Network.

Let us now examine how the threat model and the manifest-based framework are applied to the motivating example presented in the introduction, namely, the DomYcile project [24]. In this project, nearly 8,000 patients are each equipped with a secure home box where their medical and social records are stored. These boxes are not connected to the Internet for subscription cost, security/privacy, and acceptability reasons and are only accessible at the patient's home by healthcare workers. They leverage their mobility to transmit messages from their smartphones to the boxes via Bluetooth, applying a store-carry-forward strategy and thus implementing an OppNet. Assuming that a Recipient (e.g., patient associations, statistical agencies, medical workers) wants to query a cohort of consenting elderly patients to obtain statistical results in the spirit of [34] (Share EU project [64]), the query deployment, illustrated in Figure 4, proceeds as follows:

<figure><img src="image_6.png" /><figcaption>Figure 4: Edgelet Query in the DomYcile Project</figcaption></figure>

1. The Recipient specifies the manifest containing the four elements mentioned above, including the general purpose as follows: "Cohort of 2000 patients, having age $\ge$ 65, computes statistics on Age, Education, BMI, Tobacco, Chronic
use cases, explaining why we exclude it from the actual processing of the QEP. However, we do not question the good faith of the Recipient. Thus, even if it receives the results of the processing in clear text, we do not consider inference attacks from its side (i.e., crossing the results of multiple queries).

**Wolf in sheepfold Participants.**

- *Role:* contributes with data (*Data Contributor*) and/or processing power (*Data Processor*) in a QEP.

- *Played by:* any participant equipped with a TEE-enabled device.

- *Trust:* as said in subsection 2.1, side-channel attacks on a TEE-enabled device cannot be totally precluded despite their complexity (requires tampering with the device). We assume a large majority of honest participants (the lambs) and a few “sealed glass-proof” ones (the wolves).

**Regulator.**

- *Role:* reviews and approves the processing to be performed. This role is not devoted to the query execution itself.

- *Played by:* either an external entity (e.g., a privacy regulatory agency like the CNIL in France) or a representative group of crowd members engaged in a collective validation process.

- *Trust:* full.

**3.2 Purpose Honesty**

In this subsection, we focus on the initialization of queries and how the Recipient can prove its honesty. To this end, we propose to build on the manifest-based framework [42], so that the recipient can declare the why and how of processing. Here is its implementation in our context:

First, the Recipient specifies a manifest describing the query to be performed. This manifest consists of four elements: (1) the general purpose of the processing expressed in natural language, (2) the Query Execution Plan, (3) the set of representativeness predicates *P* of the targeted dataset *D* as well as its cardinality |*D*| and (4) the source code of the operators to be executed on each edgelet node. Subsequently, the Recipient submits the manifest to the Regulator for verification of its compliance with the expected privacy practices. Once verified, the Regulator signs the manifest and returns it to the Recipient. This certified manifest will be used for the edgelet assignment protocol presented in the next subsection, after which the query manifest will be ready for dissemination in the Opportunistic Network.

Let us now examine how the threat model and the manifest-based framework are applied to the motivating example presented in the introduction, namely, the DomYcile project [24]. In this project, nearly 8,000 patients are each equipped with a secure home box where their medical and social records are stored. These boxes are not connected to the Internet for subscription cost, security/privacy, and acceptability reasons and are only accessible at the patient's home by healthcare workers. They leverage their mobility to transmit messages from their smartphones to the boxes via Bluetooth, applying a store-carry-forward strategy and thus implementing an OppNet. Assuming that a Recipient (e.g., patient associations, statistical agencies, medical workers) wants to query a cohort of consenting elderly patients to obtain statistical results in the spirit of [34] (Share EU project [64]), the query deployment, illustrated in Figure 4, proceeds as follows:

<figure><img src="image_5.png" /><figcaption>Figure 4: Edgelet Query in the DomYcile Project</figcaption></figure>

1. The Recipient specifies the manifest containing the four elements mentioned above, including the general purpose as follows: "Cohort of 2000 patients, having age $\ge$ 65, computes statistics on Age, Education, BMI, Tobacco, Chronic
diseases, Frailty criteria".

2. The Recipient sends the manifest to the Regulator, e.g., the CNIL (French regulatory agency), which sends back a signed version of the manifest if approved.

3. The Recipient randomly assigns QEP operators to a subset of edgelets (see subsection 3.3.2), making the query manifest ready for dissemination.

4. Healthcare workers broadcast the query through their OppNet.

5. Patients willing to contribute their data to the query will then act as Data Contributors. Edgelets assigned by the Recipient will themselves act as Data Processors.

The challenge is now to protect the confidentiality of the computations despite potential attacks on the edgelets (wolfs), which is the topic of the next subsection.

## 3.3 Computation Honesty

Now that the certified manifest is disseminated to all edgelets in the network, we want to ensure the CLM's Computation honesty reminded here for readability: (1) each decentralized execution must strictly conform to the QEP approved by the Regulator, (2) each honest crowd member must be able to confidently participate to the processing despite potential corruption of their own device, and (3) each dishonest crowd member is defeated in their attempt to perform a massive attack. For the two first points, the question is how to verify that the execution is done in the same order as specified by the certified QEP and how to ensure that the processing performed on the data does not deviate from the original code. This is addressed in subsection 3.3.1 whereas point (3) is the focus of subsection 3.3.2.

### 3.3.1 Global and local integrity of the processing

To enforce points (1) and (2), we leverage the code integrity property provided by the TEE to build a Trusted Assistant, a logical entity taking responsibility for the Computation honesty on behalf of the edgelet owners. Concretely, the Trusted Assistant runs on each edgelet node a piece of code, called *Core* hereafter, which is part of the TEE Trusted Computing Base, a code base guaranteed genuine at boot time. Using remote attestations [42, 45] (cryptographic proof of the authenticity of the TEE), the *Core* enforces point (1) of CLM's Computation honesty by guaranteeing that the predecessors of Data Processors in the QEP are legitimate and produce valid intermediate results. In addition, the *Core* attests to the genuineness of the QEP operator's code assigned to the participating edgelets by verifying the signature of the Regulator on the certified manifest. Note that even if the edgelets' operating system is corrupted by malware or viruses, the isolation property of the TEE ensures that the executed code cannot be altered. Hence, point (2) of CLM's Computation honesty is also enforced.

These two integrity guarantees provided by the Trusted Assistant via the TEEs reinforce the crowd's confidence in the Edgelet computing architecture. As a result, each individual can freely consent to contribute their sensitive data with the reassurance that the decentralized execution will follow precisely the precepts indicated by the certified manifest. As we will see below, the next challenge is to protect executions from dishonest crowd members.

### 3.3.2 Resistance to massive attacks

As mentioned before, we do not exclude the possibility of side-channel attacks on edgelets compromising the confidentiality of the manipulated data. Our objective is then to empower the Trusted Assistant with mechanisms that minimize the risks of massive data leakages in this particular case.

The Recipient is in charge of initiating the query, that is, assigning the QEP operators to the participating edgelets, and then launching the processing. However, the threat model makes no assumption about the integrity of the Recipient(s). Even if we do not question their good faith, we acknowledge that their information system may have been corrupted by some attacker. Thus, the task of assigning operators to edgelets must be protected to prevent a critical operator from being assigned to a corrupt accomplice edgelet, e.g., the operator manipulating the data of a targeted contributor or the operator manipulating a maximum amount of sensitive data. We, therefore, propose a random assignment protocol auditable by the Trusted Assistant.

**Random assignment.** We assume that the set of all crowd members' edgelet is known by the Recipient (e.g., they register to join a community) and that their IDs form a hash ring (as in a Chord DHT). We also assume that each crowd member tacitly consents to contribute to a query execution, which is far less engaging than consenting to contribute their personal data to the query. Under these assumptions, the assignment protocol is as follows (see the pseudocode below):
diseases, Frailty criteria".

2. The Recipient sends the manifest to the Regulator, e.g., the CNIL (French regulatory agency), which sends back a signed version of the manifest if approved.

3. The Recipient randomly assigns QEP operators to a subset of edgelets (see subsection 3.3.2), making the query manifest ready for dissemination.

4. Healthcare workers broadcast the query through their OppNet.

5. Patients willing to contribute their data to the query will then act as Data Contributors. Edgelets assigned by the Recipient will themselves act as Data Processors.

The challenge is now to protect the confidentiality of the computations despite potential attacks on the edgelets (wolfs), which is the topic of the next subsection.

## 3.3 Computation Honesty

Now that the certified manifest is disseminated to all edgelets in the network, we want to ensure the CLM's Computation honesty reminded here for readability: (1) each decentralized execution must strictly conform to the QEP approved by the Regulator, (2) each honest crowd member must be able to confidently participate to the processing despite potential corruption of their own device, and (3) each dishonest crowd member is defeated in their attempt to perform a massive attack. For the two first points, the question is how to verify that the execution is done in the same order as specified by the certified QEP and how to ensure that the processing performed on the data does not deviate from the original code. This is addressed in subsection 3.3.1 whereas point (3) is the focus of subsection 3.3.2.

### 3.3.1 Global and local integrity of the processing

To enforce points (1) and (2), we leverage the code integrity property provided by the TEE to build a Trusted Assistant, a logical entity taking responsibility for the Computation honesty on behalf of the edgelet owners. Concretely, the Trusted Assistant runs on each edgelet node a piece of code, called Core hereafter, which is part of the TEE Trusted Computing Base, a code base guaranteed genuine at boot time. Using remote attestations [42, 45] (cryptographic proof of the authenticity of the TEE), the Core enforces point (1) of CLM's Computation honesty by guaranteeing that the predecessors of Data Processors in the QEP are legitimate and produce valid intermediate results. In addition, the Core attests to the genuineness of the QEP operator's code assigned to the participating edgelets by verifying the signature of the Regulator on the certified manifest. Note that even if the edgelets' operating system is corrupted by malware or viruses, the isolation property of the TEE ensures that the executed code cannot be altered. Hence, point (2) of CLM's Computation honesty is also enforced.

These two integrity guarantees provided by the Trusted Assistant via the TEEs reinforce the crowd's confidence in the Edgelet computing architecture. As a result, each individual can freely consent to contribute their sensitive data with the reassurance that the decentralized execution will follow precisely the precepts indicated by the certified manifest. As we will see below, the next challenge is to protect executions from dishonest crowd members.

### 3.3.2 Resistance to massive attacks

As mentioned before, we do not exclude the possibility of side-channel attacks on edgelets compromising the confidentiality of the manipulated data. Our objective is then to empower the Trusted Assistant with mechanisms that minimize the risks of massive data leakages in this particular case.

The Recipient is in charge of initiating the query, that is, assigning the QEP operators to the participating edgelets, and then launching the processing. However, the threat model makes no assumption about the integrity of the Recipient(s). Even if we do not question their good faith, we acknowledge that their information system may have been corrupted by some attacker. Thus, the task of assigning operators to edgelets must be protected to prevent a critical operator from being assigned to a corrupt accomplice edgelet, e.g., the operator manipulating the data of a targeted contributor or the operator manipulating a maximum amount of sensitive data. We, therefore, propose a random assignment protocol auditable by the Trusted Assistant.

**Random assignment.** We assume that the set of all crowd members' edgelet is known by the Recipient (e.g., they register to join a community) and that their IDs form a hash ring (as in a Chord DHT). We also assume that each crowd member tacitly consents to contribute to a query execution, which is far less engaging than consenting to contribute their personal data to the query. Under these assumptions, the assignment protocol is as follows (see the pseudocode below):
1. The Recipient first checks if the Manifest is genuine (lines 1&2). Then it computes a hash of the manifest (signed by the Regulator and publicly known) as a seed for the random process (line 3) and assigns the first operator to the edgelet having the ID immediately greater than this hash in the ring (line 5). The first hash is rehashed to assign the second operator and so forth until all operators have been assigned (lines 4-7). Finally, the assignment is signed (line 8).

2. The Trusted Assistant, which implements Core on all edgelets, verifies first the signature of the Manifest and the assignment (lines 1&2), then checks the chain of hash in order to detect any fraudulent assignment for the operator intended for them (lines 3-13). Assuming that each edgelet knows at least the ID of its predecessor in the ring, it is sufficient to check that the hash is strictly larger.

### Random Assignment (run by the Recipient)

**Input:** M a manifest; M.S the Regulator's signature of M; M.OP the set of operators to be assigned to edgelets; R a ring with sorted identifiers of registered edgelets

**Output:** A={}(op, id) an assignment of operators to edgelets; A.S a signature of this assignment

1. if M.S is not a valid signature for M then

2. return ERROR

3. seed ← hash(M) // compute a hash of the manifest

4. for each op in M.OP do

5. id ← findEdgelet_id(R, seed) // find an edgelet ID satisfying prev(id) < seed and id > seed

6. seed ← hash(seed) // rehash the current hash value

7. A ← add_assignment(A, op, id) // add (op, id) to A

8. A.S ← sign_assignment(A, Recipient's private key) // Sign the assignment A with the Recipient's private key

9. return A, A.S

### Verify Assignment (run by the Trusted Assistant, with edgelet id = my_id)

**Input:** M a manifest; M.S the Regulator's signature of M; A={}(op, id) an assignment of operators to edgelets; A.S a signature of this assignment

**Output:** boolean (true if the assignment is correct, false otherwise)

1. if M.S is not a valid signature for M or A.S is not a valid signature for A then

2. return false

3. my_op ← op in A such that id = my_id // the operator assigned to "my" edgelet

4. seed ← hash(M) // compute a hash of the manifest

5. prev ← previousEdgelet_id // id of the previous edgelet in the ring

6. for each op in A do

7. if op == my_op then // if the operator is the one assigned

8. if prev < seed and my_id > seed then // if my_id is immediately greater than this hash

9. return true

10. else

11. return false // invalid assignment detected

12. seed ← hash(seed) // rehash the current hash value

13. return false // invalid assignment detected

How does this assignment work when successive hashes lead to collisions? Note that this problem is frequent when there are few edgelet nodes present in the DHT ring, and it becomes highly unlikely otherwise. However, assigning multiple roles to a single node is undesirable for both resiliency and privacy reasons, hence the need for a countermeasure. When a collision occurs, we propose that the Recipient assigns the direct successor of this node in the ring, as the latter has a lower probability (squared) of also being in collision. The Trusted Assistant can still detect a fraudulent assignment, but this time each edgelet must know the IDs of its two predecessors. The proposed method is therefore adjustable to any dimension of the network, it will just be necessary to increase the number of known predecessors.

Next, let us try to restrict the leakage to dishonest crowd members, those for which the edgelet is physically attacked. Trivially, if no Data Processor is compromised, the TEE confidentiality property guarantees that no sensitive data can leak by construction. However, the distributed executions we are considering require intermediate results to be transmitted between the Data Processors (e.g., the representative snapshot *D* sent by the Snapshot Builder to the Computer). The messages sent in the OppNet then need to be encrypted to counter any malicious interception (e.g., by the untrusted smartphone of a healthcare worker).

**Messages encryption.** We assume that the QEP transmitted by the recipient contains the certificates of the assigned data processors, consisting of the IDs of the nodes in the DHT and their public encryption keys. Since the QEP is constructed statically, each node can easily encrypt its output based on its successors in the execution tree. Thus, when an edgelet $e_i$ needs to send a message $m$ to $e_j$, it generates a symmetric key $k_s$ to encrypt its message and uses $e_j$'s public encryption key $pk_j$ to
1. The Recipient first checks if the Manifest is genuine (lines 1&2). Then it computes a hash of the manifest (signed by the Regulator and publicly known) as a seed for the random process (line 3) and assigns the first operator to the edgelet having the ID immediately greater than this hash in the ring (line 5). The first hash is rehashed to assign the second operator and so forth until all operators have been assigned (lines 4-7). Finally, the assignment is signed (line 8).

2. The Trusted Assistant, which implements Core on all edgelets, verifies first the signature of the Manifest and the assignment (lines 1&2), then checks the chain of hash in order to detect any fraudulent assignment for the operator intended for them (lines 3-13). Assuming that each edgelet knows at least the ID of its predecessor in the ring, it is sufficient to check that the hash is strictly larger.

### Random Assignment (run by the Recipient)

**Input:** M a manifest; M.S the Regulator's signature of M; M.OP the set of operators to be assigned to edgelets; R a ring with sorted identifiers of registered edgelets

**Output:** A={`(op, id)`} an assignment of operators to edgelets; A.S a signature of this assignment

1. if M.S is not a valid signature for M then

2. return ERROR

3. seed ← hash(M) // compute a hash of the manifest

4. for each op in M.OP do

5. id ← findEdgelet_id(R, seed) // find an edgelet ID satisfying `prev(id) < seed` and `id > seed`

6. seed ← hash(seed) // rehash the current hash value

7. A ← add_assignment(A, op, id) // add (op, id) to A

8. A.S ← sign_assignment(A, Recipient's private key) // Sign the assignment A with the Recipient's private key

9. return A, A.S

### Verify Assignment (run by the Trusted Assistant, with edgelet id = my_id)

**Input:** M a manifest; M.S the Regulator's signature of M; A={`(op, id)`} an assignment of operators to edgelets; A.S a signature of this assignment

**Output:** boolean (true if the assignment is correct, false otherwise)

1. if M.S is not a valid signature for M or A.S is not a valid signature for A then

2. return false

3. my_op ← op in A such that `id = my_id` // the operator assigned to "my" edgelet

4. seed ← hash(M) // compute a hash of the manifest

5. prev ← previousEdgelet_id // id of the previous edgelet in the ring

6. for each op in A do

7. if `op == my_op` then // if the operator is the one assigned

8. if `prev < seed` and `my_id > seed` then // if `my_id` is immediately greater than this hash

9. return true

10. else

11. return false // invalid assignment detected

12. seed ← hash(seed) // rehash the current hash value

13. return false // invalid assignment detected

How does this assignment work when successive hashes lead to collisions? Note that this problem is frequent when there are few edgelet nodes present in the DHT ring, and it becomes highly unlikely otherwise. However, assigning multiple roles to a single node is undesirable for both resiliency and privacy reasons, hence the need for a countermeasure. When a collision occurs, we propose that the Recipient assigns the direct successor of this node in the ring, as the latter has a lower probability (squared) of also being in collision. The Trusted Assistant can still detect a fraudulent assignment, but this time each edgelet must know the IDs of its two predecessors. The proposed method is therefore adjustable to any dimension of the network, it will just be necessary to increase the number of known predecessors.

Next, let us try to restrict the leakage to dishonest crowd members, those for which the edgelet is physically attacked. Trivially, if no Data Processor is compromised, the TEE confidentiality property guarantees that no sensitive data can leak by construction. However, the distributed executions we are considering require intermediate results to be transmitted between the Data Processors (e.g., the representative snapshot *D* sent by the Snapshot Builder to the Computer). The messages sent in the OppNet then need to be encrypted to counter any malicious interception (e.g., by the untrusted smartphone of a healthcare worker).

**Messages encryption.** We assume that the QEP transmitted by the recipient contains the certificates of the assigned data processors, consisting of the IDs of the nodes in the DHT and their public encryption keys. Since the QEP is constructed statically, each node can easily encrypt its output based on its successors in the execution tree. Thus, when an edgelet $e_i$ needs to send a message $m$ to $e_j$, it generates a symmetric key $k_s$ to encrypt its message and uses $e_j$'s public encryption key $pk_j$ to
encrypt $k_s$. The packet sent in the OppNet is then: {$enc(m, k_s), enc(k_s, pk_j)$}. Following this procedure, all messages in transit in the network are encrypted, making them unreadable to anyone other than their recipients. Therefore, since no cryptographic material is ever shared among edgelets and the TEE integrity property still holds even in sealed-glass proof mode, the potential leakage is reduced to the data processed by a compromised edgelet. Note also that any change in the operator's ordering would make the messages indecipherable and the execution would fail, reinforcing point (1) of the CLM's Computation honesty. Finally, we need to restrict the amount of data manipulated by each edgelet, so that in the event of a physical attack on assigned edgelets, leakage is limited to a small proportion of the data required for a query.

**Horizontal and vertical partitioning.** We observe that computations of interest are often distributive (e.g., MapReduce, Spark), enabling the decomposition of processing into sub-operators. Thus, we propose to distribute the operators of the Data Processors (Snapshot Builder and Computer) among different edgelet nodes. This decomposition can help minimize the amount of data exposed at each edgelet by horizontally partitioning the dataset. This can also preclude the concomitant exposure, in the same edgelet, of data items that become sensitive when combined (e.g., a quasi-identifier) by vertically partitioning the dataset. Note that such distributive executions can also help minimize the workload (e.g., when energy consumption matters) by exploiting the inherent Edgelet computing parallelism. Figure 5 presents both types of partitioning, horizontal and vertical, on the query example of Figure 4. Each Data Contributor performs a hash function of its ID to select the Snapshot Builder to send its data to, so that each partition processes only a fragment of the dataset (here, a tenth) with different Computers depending on the statistics to be computed (each one only sees the attributes strictly necessary for its computation). Note that a Computing Combiner operator must be added in the QEP to combine the outputs of all sub-operators.

<figure><img src="image_7.png" /><figcaption>Figure 5: Horizontal and Vertical Partitioning</figcaption></figure>

Although these partitioning strategies are decided by the Recipient in the design of the QEP, it is the responsibility of the Regulator to approve them. Depending on the application context, the privacy criteria selected may be different (e.g., medical records, spending habits) and involve more or less distribution of the data. Note that since each individual is free to consent to contribute their data, it is in the Recipient's interest to design a privacy-friendly QEP in order to encourage people to participate.

## 4 Resiliency and Validity Enforcement

The execution plans presented earlier are relevant from a logical point of view but are not resilient to failures. Indeed, the slightest failure or unavailability among the assigned edgelets results in the complete failure of the query. Our objective here is then to propose execution strategies that make Edgelet processing resilient to failures and to message losses in the Opportunistic Networks context.

In the following subsections, we present three alternative implementation strategies for enforcing the *Resiliency* property and discuss their impact on *Validity* and *Security* (a more detailed analysis of the exposure of personal data when the confidentiality property of some TEEs is breached is conducted in Sections 5 and 6). First, we consider an extension of traditional resilience solutions based on backups (subsection 4.1). Second, we present an alternative approach, in which, instead of replicating input data contributions, we tolerate an open (over-)set of data contributors typical of the edgelet context and take advantage of this "overcollection" of data to ensure Resiliency (subsection 4.2). Third, we present a "hybrid" approach in which the backup and overcollection modes can coexist for better efficiency (subsection 4.3).
encrypt $k_s$. The packet sent in the OppNet is then: {$enc(m, k_s), enc(k_s, pk_j)$}. Following this procedure, all messages in transit in the network are encrypted, making them unreadable to anyone other than their recipients. Therefore, since no cryptographic material is ever shared among edgelets and the TEE integrity property still holds even in sealed-glass proof mode, the potential leakage is reduced to the data processed by a compromised edgelet. Note also that any change in the operator's ordering would make the messages indecipherable and the execution would fail, reinforcing point (1) of the CLM's Computation honesty. Finally, we need to restrict the amount of data manipulated by each edgelet, so that in the event of a physical attack on assigned edgelets, leakage is limited to a small proportion of the data required for a query.

**Horizontal and vertical partitioning.** We observe that computations of interest are often distributive (e.g., MapReduce, Spark), enabling the decomposition of processing into sub-operators. Thus, we propose to distribute the operators of the Data Processors (Snapshot Builder and Computer) among different edgelet nodes. This decomposition can help minimize the amount of data exposed at each edgelet by horizontally partitioning the dataset. This can also preclude the concomitant exposure, in the same edgelet, of data items that become sensitive when combined (e.g., a quasi-identifier) by vertically partitioning the dataset. Note that such distributive executions can also help minimize the workload (e.g., when energy consumption matters) by exploiting the inherent Edgelet computing parallelism. Figure 5 presents both types of partitioning, horizontal and vertical, on the query example of Figure 4. Each Data Contributor performs a hash function of its ID to select the Snapshot Builder to send its data to, so that each partition processes only a fragment of the dataset (here, a tenth) with different Computers depending on the statistics to be computed (each one only sees the attributes strictly necessary for its computation). Note that a Computing Combiner operator must be added in the QEP to combine the outputs of all sub-operators.

<figure><img src="image_6.png" /><figcaption>Figure 5: Horizontal and Vertical Partitioning</figcaption></figure>

Although these partitioning strategies are decided by the Recipient in the design of the QEP, it is the responsibility of the Regulator to approve them. Depending on the application context, the privacy criteria selected may be different (e.g., medical records, spending habits) and involve more or less distribution of the data. Note that since each individual is free to consent to contribute their data, it is in the Recipient's interest to design a privacy-friendly QEP in order to encourage people to participate.

## 4 Resiliency and Validity Enforcement

The execution plans presented earlier are relevant from a logical point of view but are not resilient to failures. Indeed, the slightest failure or unavailability among the assigned edgelets results in the complete failure of the query. Our objective here is then to propose execution strategies that make Edgelet processing resilient to failures and to message losses in the Opportunistic Networks context.

In the following subsections, we present three alternative implementation strategies for enforcing the *Resiliency* property and discuss their impact on *Validity* and *Security* (a more detailed analysis of the exposure of personal data when the confidentiality property of some TEEs is breached is conducted in Sections 5 and 6). First, we consider an extension of traditional resilience solutions based on backups (subsection 4.1). Second, we present an alternative approach, in which, instead of replicating input data contributions, we tolerate an open (over-)set of data contributors typical of the edgelet context and take advantage of this "overcollection" of data to ensure Resiliency (subsection 4.2). Third, we present a "hybrid" approach in which the backup and overcollection modes can coexist for better efficiency (subsection 4.3).
## 4.1 Backup-Based Strategy

In this subsection, we take a conservative approach to Resiliency, recovering from failures in a general way, independent of query plans, and study its impact on the enforcement of the Validity and Security properties.

### 4.1.1 Enforcing Resiliency

No reliable failure detector exists in our context, and every Data Processor (SB, C, and CC in Figure 6) is a potential Single Point of Failure (SPF). In the Backup-based approach, we simply try to recover from failures, whatever the Data Processor presumed faulty, the benefit of which is to make the handling of Resiliency independent of the form of the QEP. We use timeouts to presume faults and secure the execution of all SPFs by means of backups, as usual [69].

We distinguish between Passive and Active Backups. A Passive Backup replicates the input data of its corresponding SPF, called primary, and is activated and processes this data only in case the primary is presumed faulty. Thus, the data transferred to a Passive Backup is not exposed since it remains encrypted until the backup node is actually required. Conversely, an Active Backup executes in parallel with its primary. Despite a reduced latency, Active Backups incur a higher resource consumption and offer less security (greater exposure of data). Consequently, all SPFs are passively replicated (see Figure 6), except the Computing Combiner which must be actively replicated; otherwise, the Recipient would be forced to take part in the processing, at least to activate the Computing Combiner Backup(s), which would damage the Ingenuous Recipient assumption (see subsection 3.1).

<figure><img src="image_8.png" /><figcaption>Figure 6: Backup-based Strategy</figcaption></figure>

Figure 6 presents the Backup strategy for the QEP of the motivating example with horizontal and vertical partitioning. For this execution plan to be fault tolerant, each SPF in each partition must survive (i.e., Snapshot Builder and Computers), either by means of a primary node or one of its backups (note that in the figure, only one backup per SPF is shown). The number *b*, which represents the number of backups per primary node in each partition, is then determined by the following inequality: $(1 - p_f^{(1+b)})^{|SPF| \times n} \geq p_s$, with $p_f$ the probability of fault presumption, $p_s$ the expected probability of success, and $|SPF|$ the number of SPFs in each of the *n* horizontal partitions of the QEP (*n*=10 in Figure 6). As we will also see in the other strategies, the Computing Combiner is considered separately from the other Data Processors due to its particular role as a proxy for the Recipient. Following the same principle, the number of backups $b_{cc}$ for the Computing Combiner results in the inequality $(1 - p_f^{(1+b_{cc})}) \geq p_s$.

We assume that a start date $T_s$ is set in the query manifest from which all Data Contributor edgelets start responding to the query. This date is then known by the Data Processor edgelets assigned for the query. Given the maximum delay $\delta$ for a sent message to arrive at its destination node (with a very high probability, close to 1), the maximum execution time of the query to successfully terminate can be estimated, which is referred to as the query deadline calibration. To this end, intermediate timeouts must be set at each Data Processor node so that the backups of their predecessor node(s) can be appropriately activated at runtime. For example, in Figure 6, the Computing Combiner and its active backups must allow sufficient time for all predecessor Computers to recursively activate the Snapshot Builder backups. Readers interested in a more detailed presentation of the query deadline calibration are referred to Appendix 1.
## 4.1 Backup-Based Strategy

In this subsection, we take a conservative approach to Resiliency, recovering from failures in a general way, independent of query plans, and study its impact on the enforcement of the Validity and Security properties.

### 4.1.1 Enforcing Resiliency

No reliable failure detector exists in our context, and every Data Processor (SB, C, and CC in Figure 6) is a potential Single Point of Failure (SPF). In the Backup-based approach, we simply try to recover from failures, whatever the Data Processor presumed faulty, the benefit of which is to make the handling of Resiliency independent of the form of the QEP. We use timeouts to presume faults and secure the execution of all SPFs by means of backups, as usual [69].

We distinguish between Passive and Active Backups. A Passive Backup replicates the input data of its corresponding SPF, called primary, and is activated and processes this data only in case the primary is presumed faulty. Thus, the data transferred to a Passive Backup is not exposed since it remains encrypted until the backup node is actually required. Conversely, an Active Backup executes in parallel with its primary. Despite a reduced latency, Active Backups incur a higher resource consumption and offer less security (greater exposure of data). Consequently, all SPFs are passively replicated (see Figure 6), except the Computing Combiner which must be actively replicated; otherwise, the Recipient would be forced to take part in the processing, at least to activate the Computing Combiner Backup(s), which would damage the Ingenuous Recipient assumption (see subsection 3.1).

<figure><img src="image_7.png" /><figcaption>Figure 6: Backup-based Strategy</figcaption></figure>

Figure 6 presents the Backup strategy for the QEP of the motivating example with horizontal and vertical partitioning. For this execution plan to be fault tolerant, each SPF in each partition must survive (i.e., Snapshot Builder and Computers), either by means of a primary node or one of its backups (note that in the figure, only one backup per SPF is shown). The number *b*, which represents the number of backups per primary node in each partition, is then determined by the following inequality: $(1 - p_f^{(1+b)})^{|SPF| \times n} \geq p_s$, with $p_f$ the probability of fault presumption, $p_s$ the expected probability of success, and $|SPF|$ the number of SPFs in each of the *n* horizontal partitions of the QEP (*n*=10 in Figure 6). As we will also see in the other strategies, the Computing Combiner is considered separately from the other Data Processors due to its particular role as a proxy for the Recipient. Following the same principle, the number of backups $b_{cc}$ for the Computing Combiner results in the inequality $(1 - p_f^{(1+b_{cc})}) \geq p_s$.

We assume that a start date $T_s$ is set in the query manifest from which all Data Contributor edgelets start responding to the query. This date is then known by the Data Processor edgelets assigned for the query. Given the maximum delay $\delta$ for a sent message to arrive at its destination node (with a very high probability, close to 1), the maximum execution time of the query to successfully terminate can be estimated, which is referred to as the query deadline calibration. To this end, intermediate timeouts must be set at each Data Processor node so that the backups of their predecessor node(s) can be appropriately activated at runtime. For example, in Figure 6, the Computing Combiner and its active backups must allow sufficient time for all predecessor Computers to recursively activate the Snapshot Builder backups. Readers interested in a more detailed presentation of the query deadline calibration are referred to Appendix 1.
### 4.1.2 Enforcing Validity

Satisfying the Validity property requires that the data flow between the operators is consistent w.r.t. at least one of the $ζ_Q(E)$ snapshots. However, with failure or message loss, a Snapshot Builder and its backups may build different snapshots, each belonging to $ζ_Q(E)$. Therefore, three situations must be distinguished to guarantee that the query result is equivalent to the one obtained with a centralized execution over at least one snapshot built by the Snapshot Builder or one of its backups. This particular snapshot is hereafter called the *reference snapshot*.

1. Without any partitioning, a single Snapshot Builder feeds a single Computer. Hence, a reference snapshot can be identified whatever the execution. It is either the snapshot built by the Snapshot Builder primary if there is no fault presumption, or the snapshot built by one of the activated backups otherwise.

2. Similarly, with horizontal partitioning, the reference snapshot is simply the union of each partition's snapshot (backup or primary).

3. With vertical partitioning, the Snapshot Builder feeds several Computers. Some of these Computers may consider the primary snapshot, while some others may use the backup snapshot in case of fault presumption. This leads to inconsistency, i.e., a result built over a snapshot that does not belong to any snapshot of $ζ_Q(E)$.

Figure 6 illustrates this third situation, where each Computer evaluates a different statistic but must consider the same snapshot belonging to $ζ_Q(E)$. To solve this problem, several solutions can be envisioned but all of them incur a significant overhead. We sketch below two of them that address this issue in a different way:

**Consensus:** Synchronize the snapshot between the primary Snapshot Builder and its backups thanks to a consensus protocol (Figure 7.a). [9] proposes an effective consensus protocol for OppNets that matches the Edgelet context, at the price of a distributed consensus. This consensus stage requires active Snapshots Builders backups in order to agree on a representative reference snapshot. Indeed, if the collected data had to remain encrypted, it would become difficult, if not impossible, to verify the representativeness predicates.

- **QEP restructuring:** Rearrange the QEP so that the parallel branches are serialized, one after the other (Figure 7.b), thus avoiding inconsistencies due to multiple successors, but at the price of losing QEP parallelism and increasing drastically the recursive runtimes. This solution implies extending the deadline, otherwise, the intermediate timeouts would be too short and almost all the backups would be triggered, which would harm the privacy of the contributors since their data would be exposed several times.

<figure><img src="image_9.png" /><figcaption>Figure 7: Methods to guarantee the Validity property</figcaption></figure>

## 4.2 Overcollection-Based Strategy

This subsection introduces a very different way to handle the problem of Resiliency, which integrates the OppNet context by design. Contrary to the backup-based strategy, message delays or loss are no longer considered as faults that must be recovered but rather as legitimate behavior.
### 4.1.2 Enforcing Validity

Satisfying the Validity property requires that the data flow between the operators is consistent w.r.t. at least one of the $ζ_q(E)$ snapshots. However, with failure or message loss, a Snapshot Builder and its backups may build different snapshots, each belonging to $ζ_q(E)$. Therefore, three situations must be distinguished to guarantee that the query result is equivalent to the one obtained with a centralized execution over at least one snapshot built by the Snapshot Builder or one of its backups. This particular snapshot is hereafter called the *reference snapshot*.

1. Without any partitioning, a single Snapshot Builder feeds a single Computer. Hence, a reference snapshot can be identified whatever the execution. It is either the snapshot built by the Snapshot Builder primary if there is no fault presumption, or the snapshot built by one of the activated backups otherwise.

2. Similarly, with horizontal partitioning, the reference snapshot is simply the union of each partition's snapshot (backup or primary).

3. With vertical partitioning, the Snapshot Builder feeds several Computers. Some of these Computers may consider the primary snapshot, while some others may use the backup snapshot in case of fault presumption. This leads to inconsistency, i.e., a result built over a snapshot that does not belong to any snapshot of $ζ_q(E)$.

Figure 6 illustrates this third situation, where each Computer evaluates a different statistic but must consider the same snapshot belonging to $ζ_q(E)$. To solve this problem, several solutions can be envisioned but all of them incur a significant overhead. We sketch below two of them that address this issue in a different way:

**Consensus:** Synchronize the snapshot between the primary Snapshot Builder and its backups thanks to a consensus protocol (Figure 7.a). [9] proposes an effective consensus protocol for OppNets that matches the Edgelet context, at the price of a distributed consensus. This consensus stage requires active Snapshots Builders backups in order to agree on a representative reference snapshot. Indeed, if the collected data had to remain encrypted, it would become difficult, if not impossible, to verify the representativeness predicates.

- **QEP restructuring:** Rearrange the QEP so that the parallel branches are serialized, one after the other (Figure 7.b), thus avoiding inconsistencies due to multiple successors, but at the price of losing QEP parallelism and increasing drastically the recursive runtimes. This solution implies extending the deadline, otherwise, the intermediate timeouts would be too short and almost all the backups would be triggered, which would harm the privacy of the contributors since their data would be exposed several times.

<figure><img src="image_8.png" /><figcaption>Figure 7: Methods to guarantee the Validity property</figcaption></figure>

## 4.2 Overcollection-Based Strategy

This subsection introduces a very different way to handle the problem of Resiliency, which integrates the OppNet context by design. Contrary to the backup-based strategy, message delays or loss are no longer considered as faults that must be recovered but rather as legitimate behavior.
4.2.1 Enforcing Resiliency

As an alternative to securing every SPF in a QEP thanks to backups, we suggest over-collecting the dataset of interest so that the QEP may survive the loss of parts of it. To explain the intuition, let us consider a query over a sample dataset (e.g., 2000 individuals with age > 65) where Data Processors (i.e., Snapshot Builder and Computers) execute distributive operators. Instead of executing the operators on single edgelets, we distribute (using hashing) its execution over *n+m* edgelets where each one processes a partition of the original dataset, with *n* the minimum number of partitions to be collected and *m* the overcollection parameter (see Figure 8).

The Overcollection ratio must be adapted to the presumed fault probability $p_f$ of the OppNet to reach the expected success rate $p_s$ for a query. Given that the probability of success of one partition is $p_p = (1 - p_f)^{|SPF|}$, with $|SPF|$ the number of SPFs in each partition, the number *m* of additional partitions is determined by the inequality $\sum_{i=n}^{n+m} \binom{n+m}{i} \times p_p^i \times (1 - p_p)^{(n+m-i)} \ge p_s$, i.e., at least *n* of the *n+m* partitions must succeed. Concerning the Computing Combiner, we assign Active Backups exactly like those of the Backup strategy.

<figure><img src="image_10.png" /><figcaption>Figure 8: Overcollection-based Strategy</figcaption></figure>

4.2.2 Enforcing Validity

If all QEPs can satisfy the Validity property when executed in backup mode (in some cases by adding a consensus among backups), this does not hold true when they are executed in Overcollection mode. Indeed, (1) the complete QEP must be reorganized to handle a partitioned dataset and (2) a reference snapshot $D \in \zeta_Q(E)$ must remain identifiable despite the arbitrary loss of subparts of this dataset during the processing. To tackle point (1), a brute-force solution is to reorganize the QEP in a set of sub-QEPs, each performing independent processing over a partition of the collected dataset with the Computing Combiner assembling the final result (see Figure 8). This solution applies only if the commutativity rules between operators allow to push all distributive operators down to the sub-QEPs and to push all non-distributive operators up to the Computing Combiner. A QEP satisfying this condition is said *reshapable*. Under this assumption, addressing point (2) can be easily achieved. The reference snapshot *D* is simply the union of all partitions that contributed to the QEP computation up to the Computing Combiner. Assuming that each of the *n+m* partitions locally satisfies the set of representativeness predicates *P* and has a cardinality $|D|/n$, the Validity property is trivially preserved as long as less than *m* partitions are lost.

4.2.3 Relaxing Validity

Most data-intensive queries of interest in our context are inherently distributive, as evidenced by the various implementations in MapReduce or Spark. However, some of the corresponding QEPs cannot be reshaped following the Brute-Force approach and then cannot combine Overcollection and Validity. This is notably the case of general interest machine learning algorithms because they are iterative or need to exchange partial results computed over different data partitions. In these cases, a reference snapshot $D \in \zeta_Q(E)$ can no longer be identified in case of message loss (e.g., two iterations may consider a different snapshot state). On the other hand, strict Validity is not a prerequisite for these algorithms which usually produce an approximate result. We thus suggest another basic preliminary method to handle these cases, called Iterative Brute-Force.

To execute an algorithm $\mathcal{A}$ with Iterative Brute-Force, each edgelet implementing a sub-QEP Computer iterates on (1) a *local convergence* phase where it computes $\mathcal{A}$ on its local partition and improves its local knowledge, initialized by a parameter of the sub-QEP, and broadcasts this knowledge to all others sub-QEPs, and (2) a *synchronization phase* where it receives the
4.2.1 Enforcing Resiliency

As an alternative to securing every SPF in a QEP thanks to backups, we suggest over-collecting the dataset of interest so that the QEP may survive the loss of parts of it. To explain the intuition, let us consider a query over a sample dataset (e.g., 2000 individuals with age > 65) where Data Processors (i.e., Snapshot Builder and Computers) execute distributive operators. Instead of executing the operators on single edgelets, we distribute (using hashing) its execution over *n+m* edgelets where each one processes a partition of the original dataset, with *n* the minimum number of partitions to be collected and *m* the overcollection parameter (see Figure 8).

The Overcollection ratio must be adapted to the presumed fault probability $p_f$ of the OppNet to reach the expected success rate $p_s$ for a query. Given that the probability of success of one partition is $p_p = (1 - p_f)^{|SPF|}$, with $|SPF|$ the number of SPFs in each partition, the number *m* of additional partitions is determined by the inequality $\sum_{i=n}^{n+m} \binom{n+m}{i} \times p_p^i \times (1 - p_p)^{(n+m-i)} \ge p_s$, i.e., at least *n* of the *n+m* partitions must succeed. Concerning the Computing Combiner, we assign Active Backups exactly like those of the Backup strategy.

<figure><img src="image_9.png" /><figcaption>Figure 8: Overcollection-based Strategy</figcaption></figure>

4.2.2 Enforcing Validity

If all QEPs can satisfy the Validity property when executed in backup mode (in some cases by adding a consensus among backups), this does not hold true when they are executed in Overcollection mode. Indeed, (1) the complete QEP must be reorganized to handle a partitioned dataset and (2) a reference snapshot $D \in \zeta_Q(E)$ must remain identifiable despite the arbitrary loss of subparts of this dataset during the processing. To tackle point (1), a brute-force solution is to reorganize the QEP in a set of sub-QEPs, each performing independent processing over a partition of the collected dataset with the Computing Combiner assembling the final result (see Figure 8). This solution applies only if the commutativity rules between operators allow to push all distributive operators down to the sub-QEPs and to push all non-distributive operators up to the Computing Combiner. A QEP satisfying this condition is said *reshapable*. Under this assumption, addressing point (2) can be easily achieved. The reference snapshot *D* is simply the union of all partitions that contributed to the QEP computation up to the Computing Combiner. Assuming that each of the *n+m* partitions locally satisfies the set of representativeness predicates *P* and has a cardinality $|D|/n$, the Validity property is trivially preserved as long as less than *m* partitions are lost.

4.2.3 Relaxing Validity

Most data-intensive queries of interest in our context are inherently distributive, as evidenced by the various implementations in MapReduce or Spark. However, some of the corresponding QEPs cannot be reshaped following the Brute-Force approach and then cannot combine Overcollection and Validity. This is notably the case of general interest machine learning algorithms because they are iterative or need to exchange partial results computed over different data partitions. In these cases, a reference snapshot $D \in \zeta_Q(E)$ can no longer be identified in case of message loss (e.g., two iterations may consider a different snapshot state). On the other hand, strict Validity is not a prerequisite for these algorithms which usually produce an approximate result. We thus suggest another basic preliminary method to handle these cases, called Iterative Brute-Force.

To execute an algorithm $\mathcal{A}$ with Iterative Brute-Force, each edgelet implementing a sub-QEP Computer iterates on (1) a *local convergence* phase where it computes $\mathcal{A}$ on its local partition and improves its local knowledge, initialized by a parameter of the sub-QEP, and broadcasts this knowledge to all others sub-QEPs, and (2) a *synchronization phase* where it receives the
knowledge of the other sub-QEPs it has heard of and integrates them in its own knowledge. Right before the query deadline, the knowledge is sent to the Computing Combiner which combines all received pieces of knowledge and sends the final result to the Recipient.

The main question is when to stop the processing. Fixing the number of iterations a priori (with a minimal number of received messages) is not meaningful in the OppNet context where message delays, then edgelet progression, are unpredictable. Expecting local convergence is also risky due to the instability of the synchronization phase among sub-QEPs. For instance, two edgelets with fast communications could converge locally quickly (without having even received any message from others) and decide to end prematurely their computation. Thus, we enforce the progression of the algorithm on all edgelets thanks to a *Heartbeat*, that is each iteration is cadenced by a clock<fnref n="2" />, whatever the local state of the processing (i.e., a Computer moves to the next iteration even if few or no messages were received). Finally, the local result is delivered when the deadline is imminent.

**Iterative Brute-Force**

### Computer Edgelet (local_partition, initial_knowledge)

knowledge ← initial_knowledge

Heartbeat until (query_deadline - 1 round)

Local conv: knowledge ← A(local_partition) and broadcast knowledge to all

Synchro: knowledge ← received knowledge of others

Send final knowledge to Computing Combiner

**Computing Combiner**

combine all received knowledge and send it to Recipient

We illustrate this method using three classical algorithms: Apriori, K-means, and Stochastic Gradient Descent (SGD). We demonstrate its effectiveness in terms of the proximity of results to centralized executions in subsection 6.3. While the first two algorithms have specific tasks, the SGD algorithm is employed to solve many well-known machine-learning models in the literature [15, 71]. Its relevance in the Edgelet context further emphasizes the applicative potential of this approach.

**Apriori** [59]: mines frequent itemsets to learn association rules.

- *knowledge*: frequent itemsets and their support (initially empty).

- *Local convergence*: A first computes the local support of all frequent itemsets in its partition then iteratively computes the local support of itemsets that are frequent in other sub-QEPs it has heard of.

- *Synchronization*: adds frequent itemsets of others in knowledge.

- *Computing Combiner*: sums the local supports of the common itemsets found in all received knowledge.

**K-means** [23]: forms k clusters minimizing the intra-cluster variance.

- *knowledge*: current centroids (initially, k randomly chosen centroids)

- *Local convergence*: until local convergence or heartbeat, A assigns each element of its own partition to the cluster having the nearest centroid and recomputes the centroids of the new clusters, updating its knowledge.

- *Synchronization*: computes, on a cluster basis, the barycenter of all centroids received from other sub-QEPs, and integrates the result in knowledge.

- *Computing Combiner*: computes the barycenter of all centroids received.

**SGD** [43]: adjusts the weights of a model to minimize its objective function.

- *knowledge*: vector of weights w (initially random).

- *Local convergence*: until local convergence or heartbeat, A computes the gradients associated with the w vector for a small sample of its data (mini-batch) in order to iteratively update the model.

- *Synchronization*: computes the average of all w vectors received from other sub-QEPs it has heard of, and integrates the result in knowledge.

- *Computing Combiner*: computes the average of all w vectors received.

<footnote n="2">² Note that the heartbeat mechanism needs a clock on each edgelet (to know when it is supposed to finish a computation iteration and send the knowledge to others), but those clocks do not need to be synchronized between edgelets.</footnote>
knowledge of the other sub-QEPs it has heard of and integrates them in its own knowledge. Right before the query deadline, the knowledge is sent to the Computing Combiner which combines all received pieces of knowledge and sends the final result to the Recipient.

The main question is when to stop the processing. Fixing the number of iterations a priori (with a minimal number of received messages) is not meaningful in the OppNet context where message delays, then edgelet progression, are unpredictable. Expecting local convergence is also risky due to the instability of the synchronization phase among sub-QEPs. For instance, two edgelets with fast communications could converge locally quickly (without having even received any message from others) and decide to end prematurely their computation. Thus, we enforce the progression of the algorithm on all edgelets thanks to a *Heartbeat*, that is each iteration is cadenced by a clock<fnref n="2" />, whatever the local state of the processing (i.e., a Computer moves to the next iteration even if few or no messages were received). Finally, the local result is delivered when the deadline is imminent.

### Iterative Brute-Force

Computer Edgelet (local_partition, initial_knowledge)

knowledge ← initial_knowledge

Heartbeat until (query_deadline - 1 round)

Local conv: knowledge ← A(local_partition) and broadcast knowledge to all

Synchro: knowledge ← received knowledge of others

Send final knowledge to Computing Combiner

### Computing Combiner

combine all received knowledge and send it to Recipient

We illustrate this method using three classical algorithms: Apriori, K-means, and Stochastic Gradient Descent (SGD). We demonstrate its effectiveness in terms of the proximity of results to centralized executions in subsection 6.3. While the first two algorithms have specific tasks, the SGD algorithm is employed to solve many well-known machine-learning models in the literature [15, 71]. Its relevance in the Edgelet context further emphasizes the applicative potential of this approach.

**Apriori** [59]: mines frequent itemsets to learn association rules.

- *knowledge*: frequent itemsets and their support (initially empty).

- *Local convergence*: A first computes the local support of all frequent itemsets in its partition then iteratively computes the local support of itemsets that are frequent in other sub-QEPs it has heard of.

- *Synchronization*: adds frequent itemsets of others in knowledge.

- *Computing Combiner*: sums the local supports of the common itemsets found in all received knowledge.

**K-means** [23]: forms k clusters minimizing the intra-cluster variance.

- *knowledge*: current centroids (initially, k randomly chosen centroids)

- *Local convergence*: until local convergence or heartbeat, A assigns each element of its own partition to the cluster having the nearest centroid and recomputes the centroids of the new clusters, updating its knowledge.

- *Synchronization*: computes, on a cluster basis, the barycenter of all centroids received from other sub-QEPs, and integrates the result in knowledge.

- *Computing Combiner*: computes the barycenter of all centroids received.

**SGD** [43]: adjusts the weights of a model to minimize its objective function.

- *knowledge*: vector of weights w (initially random).

- *Local convergence*: until local convergence or heartbeat, A computes the gradients associated with the w vector for a small sample of its data (mini-batch) in order to iteratively update the model.

- *Synchronization*: computes the average of all w vectors received from other sub-QEPs it has heard of, and integrates the result in knowledge.

- *Computing Combiner*: computes the average of all w vectors received.

<footnote n="2">² Note that the heartbeat mechanism needs a clock on each edgelet (to know when it is supposed to finish a computation iteration and send the knowledge to others), but those clocks do not need to be synchronized between edgelets.</footnote>
## 4.3 Hybrid-Based Strategy

As the name suggests, the Hybrid strategy proposes a new method that combines the previous mechanisms, namely Backup and Overcollection, with the advantage of being able to adapt and benefit from each method depending on the situation.

### 4.3.1 Enforcing Resiliency

We have seen that the Backup strategy causes inconsistency problems when the QEP includes vertical partitioning. To avoid these problems, the idea of the Hybrid method is to assign backups only to Computers and use the Overcollection principle to compensate for the probability of fault presumption of the Snapshot Builders (see Figure 9). In fact, integrating backups within partitions is a smarter resiliency solution than continuously adding overcollection partitions, especially when the degree of vertical partitioning is high (since each SPF must survive for the partition to succeed). In this configuration, the probability of success of one partition is determined by the equation $p_p = (1 - p_f) \times (1 - p_f^{(1+b)})^{(|SPF|-1)}$, with $p_f$ the probability of fault presumption, $|SPF|$ the number of SPFs in the partition (i.e., Snapshot Builder and Computers) and $b$ the number of backups per Computer. As with the Overcollection strategy, the success for the $n+m$ partitions is constrained by the inequality $\sum_{i=n}^{n+m} \binom{n+m}{i} p_p^i (1-p_p)^{(n+m-i)} \ge p_s$, with $p_s$ the expected probability of success. Once again, we use Active Backups to make the Computing Combiner fault tolerant.

<figure><img src="image_11.png" /><figcaption>Figure 9: Hybrid-based Strategy</figcaption></figure>

Note that both parameters $b$ and $m$ can be adjusted to achieve the success rate $p_s$, thus we can design different optimization strategies depending on whether it is better to have more backups or more overcollected partitions. For example, we can choose them to minimize the number of nodes involved in the QEP or to minimize the number of messages sent over the network.

### 4.3.2 Enforcing Validity

Similar to the “pure” Overcollection strategy, the Hybrid execution plans use only one Snapshot Builder per partition. This mechanism ensures by construction that the snapshot is unique for each partition. Thus, even if the QEP incorporates vertical partitioning, the Computers are guaranteed to be consistent because they process the same snapshot for each partition. However, the Validity is not so trivially guaranteed when the queries are iterative and the Computers of multiple partitions have to exchange information before producing their final result. Indeed, as explained in subsection 4.2.3, the strict Validity property would require that all Computers in all partitions exchange the same information (data, aggregates, or hints) at each iteration to form a consistent view. But if we follow the same approach as before, i.e., relaxing the property to tolerate partial and non-uniform exchanges between Computers, we then lose interest in having added backups to the Computers since each Computer will only need to receive information from a subset of the others, and therefore there is no necessity to activate the backups. This particular issue will be further detailed in the next section.

## 5 Qualitative Analysis

This section first makes a qualitative analysis of the exposure risk associated with each resiliency strategy (backup, overcollection, and hybrid). We then compare these strategies based on their respective scope and provide some guidelines to select the most appropriate strategy.
## 4.3 Hybrid-Based Strategy

As the name suggests, the Hybrid strategy proposes a new method that combines the previous mechanisms, namely Backup and Overcollection, with the advantage of being able to adapt and benefit from each method depending on the situation.

### 4.3.1 Enforcing Resiliency

We have seen that the Backup strategy causes inconsistency problems when the QEP includes vertical partitioning. To avoid these problems, the idea of the Hybrid method is to assign backups only to Computers and use the Overcollection principle to compensate for the probability of fault presumption of the Snapshot Builders (see Figure 9). In fact, integrating backups within partitions is a smarter resiliency solution than continuously adding overcollection partitions, especially when the degree of vertical partitioning is high (since each SPF must survive for the partition to succeed). In this configuration, the probability of success of one partition is determined by the equation $p_p = (1 - p_f) \times (1 - p_f^{(1+b)})^{(|SPF|-1)}$, with $p_f$ the probability of fault presumption, $|SPF|$ the number of SPFs in the partition (i.e., Snapshot Builder and Computers) and $b$ the number of backups per Computer. As with the Overcollection strategy, the success for the $n+m$ partitions is constrained by the inequality $\sum_{i=n}^{n+m} \binom{n+m}{i} p_p^i (1-p_p)^{(n+m-i)} \ge p_s$, with $p_s$ the expected probability of success. Once again, we use Active Backups to make the Computing Combiner fault tolerant.

<figure><img src="image_10.png" /><figcaption>Figure 9: Hybrid-based Strategy</figcaption></figure>

Note that both parameters $b$ and $m$ can be adjusted to achieve the success rate $p_s$, thus we can design different optimization strategies depending on whether it is better to have more backups or more overcollected partitions. For example, we can choose them to minimize the number of nodes involved in the QEP or to minimize the number of messages sent over the network.

### 4.3.2 Enforcing Validity

Similar to the “pure” Overcollection strategy, the Hybrid execution plans use only one Snapshot Builder per partition. This mechanism ensures by construction that the snapshot is unique for each partition. Thus, even if the QEP incorporates vertical partitioning, the Computers are guaranteed to be consistent because they process the same snapshot for each partition. However, the Validity is not so trivially guaranteed when the queries are iterative and the Computers of multiple partitions have to exchange information before producing their final result. Indeed, as explained in subsection 4.2.3, the strict Validity property would require that all Computers in all partitions exchange the same information (data, aggregates, or hints) at each iteration to form a consistent view. But if we follow the same approach as before, i.e., relaxing the property to tolerate partial and non-uniform exchanges between Computers, we then lose interest in having added backups to the Computers since each Computer will only need to receive information from a subset of the others, and therefore there is no necessity to activate the backups. This particular issue will be further detailed in the next section.

## 5 Qualitative Analysis

This section first makes a qualitative analysis of the exposure risk associated with each resiliency strategy (backup, overcollection, and hybrid). We then compare these strategies based on their respective scope and provide some guidelines to select the most appropriate strategy.
## 5.1 Exposure Risk

For the backup strategy, we notice that the risk of exposure of individual data is not the same whether the backups are passive or active. Indeed, as we explained previously, Passive Backups only decrypt data if they are activated, unlike Active Backups which decrypt them anyway. This protection is possible because, even if the edgelet is compromised, the integrity property of the code is still ensured (see subsection 2.1) and guarantees that data can be decrypted only at the reception of an activation message from a successor node. Moreover, we consider that the activation messages are signed with the private key of the successor nodes, making them impossible to forge. Hence, besides horizontal and vertical partitioning, Passive Backups provide an additional layer of protection against confidentiality attacks on edgelets. Their use on all QEP operators is however not always possible, especially with the Computing Combiner which must be actively replicated, and with the Snapshot Builders when the QEP integrates vertical partitioning and a consensus protocol, as explained above.

Ensuring resiliency through Overcollection changes the way data is exposed. On the one hand, the fact that there are no backups ensures by design that individual data is only exposed once, as only the primary nodes will be able to decrypt the data and, in case of compromise, the data leakage is restricted to the compromised edgelets (see subsection 3.3.2). However, the Overcollection mechanism necessitates the involvement of more Data Contributors in the query to ensure the success of the execution. Therefore, the disadvantage of the individual exposure in the Backup strategy is replaced by a higher collective exposure.

Finally, since Hybrid execution considers a single Snapshot Builder per partition, it avoids any backups on Snapshot Builders (active or passive), which limits the exposure of individual data involved in the representativeness predicates to a single node (instead of $1 + b$ for the Backup strategy). Moreover, the mix between backup and overcollection mechanisms allows for a trade-off between individual and collective exposure. Determining which exposure is superior is challenging since it depends on the context. We will see in subsection 6.1 that this exposure is often an order of magnitude lower than Backup alone or Overcollection alone.

## 5.2 Guidelines

The goal of this subsection is to guide a potential Recipient toward the right execution strategy when designing a computation dedicated to the Edgelet computing paradigm. This choice depends on the type of computation, the method for defining a representative snapshot, and the expected query deadline. We can draw some guidelines from the statements summarized in Table 2.

<table><caption>Table 2: Taxonomy of Execution Strategies</caption><thead><tr><th>Resiliency</th><th>Type of computation</th><th>Snapshot definition</th><th>Validity</th><th>Confidentiality</th><th>Success Rate</th></tr></thead><tbody><tr><td rowspan="3">Backup-based Strategy</td><td>Horizontally partitionable</td><td>P partitionable</td><td>By construction</td><td rowspan="3">Activated backup exposed</td><td rowspan="3">Requires large query deadline</td></tr><tr><td>Vertically partitionable</td><td>Any P</td><td>Consensus</td></tr><tr><td>Others</td><td>Any P</td><td>By construction</td></tr><tr><td colspan="6" style="text-align: center;">Iterative</td></tr><tr><td rowspan="2">Over collection-based Strategy</td><td>QEP reshapable</td><td>P partitionable</td><td>By construction</td><td rowspan="2">Over collected data exposed</td><td rowspan="2">Supports very small query deadline</td></tr><tr><td>Iterative reshapable</td><td>P partitionable</td><td>Ground validity</td></tr><tr><td colspan="6" style="text-align: center;">P not partitionable</td></tr><tr><td rowspan="2">Hybrid-based Strategy</td><td>QEP reshapable</td><td>P partitionable</td><td>By construction</td><td>Activated backup and over collected data exposed</td><td>Supports small query deadline</td></tr><tr><td colspan="5" style="text-align: center;">Iterative or P not partitionable</td></tr></tbody></table>

In this table, *Horizontally/Vertically partitionable* refers to the property of the computation to be distributed among several Data Processors, as explained in subsection 3.3.2. Both forms of partitioning greatly make sense when conceiving a computation dedicated to the Edgelet computing paradigm, either to minimize the amount of data exposed at each Data
## 5.1 Exposure Risk

For the backup strategy, we notice that the risk of exposure of individual data is not the same whether the backups are passive or active. Indeed, as we explained previously, Passive Backups only decrypt data if they are activated, unlike Active Backups which decrypt them anyway. This protection is possible because, even if the edgelet is compromised, the integrity property of the code is still ensured (see subsection 2.1) and guarantees that data can be decrypted only at the reception of an activation message from a successor node. Moreover, we consider that the activation messages are signed with the private key of the successor nodes, making them impossible to forge. Hence, besides horizontal and vertical partitioning, Passive Backups provide an additional layer of protection against confidentiality attacks on edgelets. Their use on all QEP operators is however not always possible, especially with the Computing Combiner which must be actively replicated, and with the Snapshot Builders when the QEP integrates vertical partitioning and a consensus protocol, as explained above.

Ensuring resiliency through Overcollection changes the way data is exposed. On the one hand, the fact that there are no backups ensures by design that individual data is only exposed once, as only the primary nodes will be able to decrypt the data and, in case of compromise, the data leakage is restricted to the compromised edgelets (see subsection 3.3.2). However, the Overcollection mechanism necessitates the involvement of more Data Contributors in the query to ensure the success of the execution. Therefore, the disadvantage of the individual exposure in the Backup strategy is replaced by a higher collective exposure.

Finally, since Hybrid execution considers a single Snapshot Builder per partition, it avoids any backups on Snapshot Builders (active or passive), which limits the exposure of individual data involved in the representativeness predicates to a single node (instead of $1 + b$ for the Backup strategy). Moreover, the mix between backup and overcollection mechanisms allows for a trade-off between individual and collective exposure. Determining which exposure is superior is challenging since it depends on the context. We will see in subsection 6.1 that this exposure is often an order of magnitude lower than Backup alone or Overcollection alone.

## 5.2 Guidelines

The goal of this subsection is to guide a potential Recipient toward the right execution strategy when designing a computation dedicated to the Edgelet computing paradigm. This choice depends on the type of computation, the method for defining a representative snapshot, and the expected query deadline. We can draw some guidelines from the statements summarized in Table 2.

<table><caption>Table 2: Taxonomy of Execution Strategies</caption><thead><tr><th>Resiliency</th><th>Type of computation</th><th>Snapshot definition</th><th>Validity</th><th>Confidentiality</th><th>Success Rate</th></tr></thead><tbody><tr><td rowspan="3">Backup-based Strategy</td><td>Horizontally partitionable</td><td>P partitionable</td><td>By construction</td><td rowspan="3">Activated backup exposed</td><td rowspan="3">Requires large query deadline</td></tr><tr><td>Vertically partitionable</td><td>Any P</td><td>Consensus</td></tr><tr><td>Others</td><td>Any P</td><td>By construction</td></tr><tr><td colspan="6" style="text-align:center; font-weight:bold;">Iterative</td></tr><tr><td rowspan="2">Over collection-based Strategy</td><td>QEP reshapable</td><td>P partitionable</td><td>By construction</td><td rowspan="2">Over collected data exposed</td><td rowspan="2">Supports very small query deadline</td></tr><tr><td>Iterative reshapable</td><td>P partitionable</td><td>Ground validity</td></tr><tr><td colspan="6" style="text-align:center; font-weight:bold;">P not partitionable</td></tr><tr><td rowspan="2">Hybrid-based Strategy</td><td>QEP reshapable</td><td>P partitionable</td><td>By construction</td><td>Activated backup and over collected data exposed</td><td>Supports small query deadline</td></tr><tr><td colspan="5" style="text-align:center; font-weight:bold;">Iterative or P not partitionable</td></tr><tr><td colspan="6" style="text-align:center; font-weight:bold;">Inappropriate</td></tr></tbody></table>

In this table, *Horizontally/Vertically partitionable* refers to the property of the computation to be distributed among several Data Processors, as explained in subsection 3.3.2. Both forms of partitioning greatly make sense when conceiving a computation dedicated to the Edgelet computing paradigm, either to minimize the amount of data exposed at each Data
Processor or to avoid the exposure in the same Data Processor of information sensitive when combined or even to minimize the Data Processor workload when energy consumption matters. While vertical partitioning does not impose additional constraints on the processing, horizontal partitioning requires that the set of representativeness predicates P be itself partitionable, i.e., that it can be applied to each partition independently (e.g., *age* > 65 is partitionable while median(*age*) < 10 is not).

QEP reshapable refers to the capacity to reorganize distributive and non-distributive operators in the QEP to be computed. This is a prerequisite for exploiting the Overcollection-based strategy for this QEP. *Ground validity* means that the Validity property defined in subsection 2.4 cannot be enforced; hence, it is up to the Recipient to assess empirically the accuracy of the final result, as we will do in subsection 6.3 for Apriori, K-means, and SGD. Finally, the *Confidentiality* column expresses the additional amount of data exposed by each strategy compared to an ideal strategy without resiliency (i.e., without backups nor overcollection).

Based on this table, we can draw the following conclusions. First, if the QEP implementing the computation cannot be reshaped or if *P* is not partitionable, the Backup strategy is the only solution since applying overcollection would be equivalent to completely duplicating the query. Second, if the computation is iterative, the Overcollection strategy turns out to be the only solution as well. Indeed, using backups, a consensus (or an equivalent mechanism) would be required at each iteration to ascertain that all participants consider *in fine* the same reference snapshot. Otherwise, only a Ground validity can be expected, but Overcollection outperforms Backup and Hybrid in this case (no additional protocols related to interactions with backups). Third, if the QEP is reshapable and *P* is partitionable, the right choice between Backup, Overcollection, and Hybrid is driven by the expected success rate and by privacy considerations. Using Backup or Hybrid strategies, the query deadline must be calibrated to accommodate the number of backups defined at each QEP level (i.e., activate them one after the other in case of fault presumption), a factor which disappears with Overcollection alone for which the query deadline depends only on the average network latency and the number of levels in the QEP. This explains the query deadline requirements, which range from large for the Backup strategy to very small for the Overcollection strategy.

Regarding privacy, the three methods do not expose data in the same way. Indeed, as explained in the previous section, TEEs guarantee that data at rest is not exposed in backups until they are activated. Hence, the same personal data is potentially exposed in as many backups as required by the satisfaction of the Resiliency property and this number increases with the presumed fault rate of the OppNet. With Overcollection alone, in contrast, the same data is never exposed twice. However, data from a larger population of individuals must be involved in the computation due to overcollection. The Hybrid strategy combines both types of exposure, with the advantage of being able to adjust the proportion of each one by calibrating the number of backups and the number of overcollected partitions. This decision made by the Recipient regarding how to expose personal data may impact the approval of the Regulator and the consent of the participants.

The taxonomy of solutions presented in Table 2 is still preliminary and more subtle guidelines can be envisioned. In particular, the Ground validity should be more deeply investigated with the goal of identifying finer classes of algorithms for which better validity guarantees can be expected. For instance, the Apriori implementation sketched in subsection 4.2.3 exhibits the salient feature that Validity can be assessed *a posteriori* by the Computing Combiner. Indeed, (1) the reference dataset is the union of the partitions it received from the Data Processor it has heard of, and (2) a frequent itemset is necessarily frequent in at least one of these partitions. The Computing Combiner must simply check that enough information has been received to compute the support of all these candidate frequent itemsets. We expect also to be able to guarantee the convergence for some algorithms when specific conditions are met but let these issues for future work.

# 6 Quantitative Analysis and Validation

This section presents our quantitative evaluations of the execution strategies presented earlier. Our objective is to validate the relevance of the Edgelet approach, calibrate the system parameters, and verify its effectiveness.

We first compare the three execution strategies, namely Backup (Bak), Overcollection (Ovr), and Hybrid (Hyb), providing insights to properly configure the resiliency parameters. Then, we implement a non-iterative Edgelet execution with the aim of calibrating the query deadline and achieving the targeted success rate. Finally, we test the iterative methods Apriori, K-means, and Stochastic Gradient Descent to evaluate the quality of their results against a centralized execution.
Processor or to avoid the exposure in the same Data Processor of information sensitive when combined or even to minimize the Data Processor workload when energy consumption matters. While vertical partitioning does not impose additional constraints on the processing, horizontal partitioning requires that the set of representativeness predicates P be itself partitionable, i.e., that it can be applied to each partition independently (e.g., *age* > 65 is partitionable while median(*age*) < 10 is not).

QEP reshapable refers to the capacity to reorganize distributive and non-distributive operators in the QEP to be computed. This is a prerequisite for exploiting the Overcollection-based strategy for this QEP. *Ground validity* means that the Validity property defined in subsection 2.4 cannot be enforced; hence, it is up to the Recipient to assess empirically the accuracy of the final result, as we will do in subsection 6.3 for Apriori, K-means, and SGD. Finally, the *Confidentiality* column expresses the additional amount of data exposed by each strategy compared to an ideal strategy without resiliency (i.e., without backups nor overcollection).

Based on this table, we can draw the following conclusions. First, if the QEP implementing the computation cannot be reshaped or if *P* is not partitionable, the Backup strategy is the only solution since applying overcollection would be equivalent to completely duplicating the query. Second, if the computation is iterative, the Overcollection strategy turns out to be the only solution as well. Indeed, using backups, a consensus (or an equivalent mechanism) would be required at each iteration to ascertain that all participants consider *in fine* the same reference snapshot. Otherwise, only a Ground validity can be expected, but Overcollection outperforms Backup and Hybrid in this case (no additional protocols related to interactions with backups). Third, if the QEP is reshapable and *P* is partitionable, the right choice between Backup, Overcollection, and Hybrid is driven by the expected success rate and by privacy considerations. Using Backup or Hybrid strategies, the query deadline must be calibrated to accommodate the number of backups defined at each QEP level (i.e., activate them one after the other in case of fault presumption), a factor which disappears with Overcollection alone for which the query deadline depends only on the average network latency and the number of levels in the QEP. This explains the query deadline requirements, which range from large for the Backup strategy to very small for the Overcollection strategy.

Regarding privacy, the three methods do not expose data in the same way. Indeed, as explained in the previous section, TEEs guarantee that data at rest is not exposed in backups until they are activated. Hence, the same personal data is potentially exposed in as many backups as required by the satisfaction of the Resiliency property and this number increases with the presumed fault rate of the OppNet. With Overcollection alone, in contrast, the same data is never exposed twice. However, data from a larger population of individuals must be involved in the computation due to overcollection. The Hybrid strategy combines both types of exposure, with the advantage of being able to adjust the proportion of each one by calibrating the number of backups and the number of overcollected partitions. This decision made by the Recipient regarding how to expose personal data may impact the approval of the Regulator and the consent of the participants.

The taxonomy of solutions presented in Table 2 is still preliminary and more subtle guidelines can be envisioned. In particular, the Ground validity should be more deeply investigated with the goal of identifying finer classes of algorithms for which better validity guarantees can be expected. For instance, the Apriori implementation sketched in subsection 4.2.3 exhibits the salient feature that Validity can be assessed *a posteriori* by the Computing Combiner. Indeed, (1) the reference dataset is the union of the partitions it received from the Data Processor it has heard of, and (2) a frequent itemset is necessarily frequent in at least one of these partitions. The Computing Combiner must simply check that enough information has been received to compute the support of all these candidate frequent itemsets. We expect also to be able to guarantee the convergence for some algorithms when specific conditions are met but let these issues for future work.

# 6 Quantitative Analysis and Validation

This section presents our quantitative evaluations of the execution strategies presented earlier. Our objective is to validate the relevance of the Edgelet approach, calibrate the system parameters, and verify its effectiveness.

We first compare the three execution strategies, namely Backup (Bak), Overcollection (Ovr), and Hybrid (Hyb), providing insights to properly configure the resiliency parameters. Then, we implement a non-iterative Edgelet execution with the aim of calibrating the query deadline and achieving the targeted success rate. Finally, we test the iterative methods Apriori, K-means, and Stochastic Gradient Descent to evaluate the quality of their results against a centralized execution.
## 6.1 Comparison of Execution Strategies

In this first subsection, we want to study the respective behavior of the execution strategies presented in Section 4. To enable a fair comparison between the three resiliency mechanisms, we assume that the query deadline is correctly calibrated so that each message sent in the OppNet has enough time to reach its destination (see subsection 6.2 for deadline adjustment). Consequently, the probability of fault presumption $p_f$ is reduced to the probability of device failure. Our goal is to observe the consequences of the resiliency methods, particularly in terms of personal data exposure and but also in terms of network overload. Table 3 below shows the notations needed to understand the formulas given in the following.

<table><caption>Table 3: Notations</caption><thead><tr><td>Notation</td><td>Description</td></tr></thead><tbody><tr><td>n</td><td>Number of initial partitions (horizontal partitioning)</td></tr><tr><td>m</td><td>Number of additional partitions (in case of overcollection)</td></tr><tr><td>|C|</td><td>Number of Computers in each partition (vertical partitioning)</td></tr><tr><td>|SPF|</td><td>Number of Single Point of Failure in each partition<br>(1 Snapshot Builder + |C| Computers)</td></tr><tr><td>b</td><td>Number of backup nodes associated with each SPF</td></tr><tr><td>|D|</td><td>Cardinality of the dataset required for the query</td></tr><tr><td>|CC|</td><td>Number of Computing Combiners<br>(1 + b<sub>cc</sub> specific backup nodes)</td></tr></tbody></table>

### 6.1.1 Overall Analysis

To begin with, we examine the general impact of execution strategies on the Query Execution Plans (QEPs). We want to observe the transformations induced by the resiliency mechanisms (Bak, Ovr, and Hyb), and to do so, we count the number of additional nodes introduced in the QEPs. Since these are redundant nodes, their presence in large numbers will be seen as a disadvantage, as they lead to additional data exposure (in case they are compromised) and network overload.

<table><caption>Table 4: Formulas for the Additional Nodes</caption><thead><tr><td></td><td>Passive Nodes</td><td>Active Nodes</td></tr></thead><tbody><tr><td>Bak</td><td>if (|C|=1): |SPF| × b × n else: |C| × b × n</td><td>if (|C|=1): 0 else: b × n</td></tr><tr><td>Ovr</td><td>0</td><td>|SPF| × m</td></tr><tr><td>Hyb</td><td>|C| × b × (n + m)</td><td>|SPF| × m</td></tr></tbody></table>

Table 4 shows the formulas used to determine the number of additional nodes for each strategy. We distinguish two types of nodes: those that are active, working in parallel with the primary nodes (active backups and nodes in overcollected partitions); and those that are passive, waiting to be activated (passive backups). For Bak, the number of backups *b* is calibrated using the formula of subsection 4.1.1. Note that when |C|>1, we consider that the Snapshot Builders' backups must be active to establish a consensus on the dataset (see subsection 4.1.2). For Ovr, the number of additional partitions *m* is adjusted using the formula of subsection 4.2.1. For Hyb, the pair (*b*, *m*) is chosen using the formula of subsection 4.3.1 in order to optimize the sum of the number of additional nodes (passive and active).
## 6.1 Comparison of Execution Strategies

In this first subsection, we want to study the respective behavior of the execution strategies presented in Section 4. To enable a fair comparison between the three resiliency mechanisms, we assume that the query deadline is correctly calibrated so that each message sent in the OppNet has enough time to reach its destination (see subsection 6.2 for deadline adjustment). Consequently, the probability of fault presumption $p_f$ is reduced to the probability of device failure. Our goal is to observe the consequences of the resiliency methods, particularly in terms of personal data exposure and but also in terms of network overload. Table 3 below shows the notations needed to understand the formulas given in the following.

<table><caption>Table 3: Notations</caption><thead><tr><td>Notation</td><td>Description</td></tr></thead><tbody><tr><td>n</td><td>Number of initial partitions (horizontal partitioning)</td></tr><tr><td>m</td><td>Number of additional partitions (in case of overcollection)</td></tr><tr><td>|C|</td><td>Number of Computers in each partition (vertical partitioning)</td></tr><tr><td>|SPF|</td><td>Number of Single Point of Failure in each partition<br>(1 Snapshot Builder + |C| Computers)</td></tr><tr><td>b</td><td>Number of backup nodes associated with each SPF</td></tr><tr><td>|D|</td><td>Cardinality of the dataset required for the query</td></tr><tr><td>|CC|</td><td>Number of Computing Combiners<br>(1 + b<sub>cc</sub> specific backup nodes)</td></tr></tbody></table>

### 6.1.1 Overall Analysis

To begin with, we examine the general impact of execution strategies on the Query Execution Plans (QEPs). We want to observe the transformations induced by the resiliency mechanisms (Bak, Ovr, and Hyb), and to do so, we count the number of additional nodes introduced in the QEPs. Since these are redundant nodes, their presence in large numbers will be seen as a disadvantage, as they lead to additional data exposure (in case they are compromised) and network overload.

<table><caption>Table 4: Formulas for the Additional Nodes</caption><thead><tr><th></th><th>Passive Nodes</th><th>Active Nodes</th></tr></thead><tbody><tr><th>Bak</th><td>if (|C|=1): |SPF| × b × n else: |C| × b × n</td><td>if (|C|=1): 0 else: b × n</td></tr><tr><th>Ovr</th><td>0</td><td>|SPF| × m</td></tr><tr><th>Hyb</th><td>|C| × b × (n + m)</td><td>|SPF| × m</td></tr></tbody></table>

Table 4 shows the formulas used to determine the number of additional nodes for each strategy. We distinguish two types of nodes: those that are active, working in parallel with the primary nodes (active backups and nodes in overcollected partitions); and those that are passive, waiting to be activated (passive backups). For Bak, the number of backups *b* is calibrated using the formula of subsection 4.1.1. Note that when |C|>1, we consider that the Snapshot Builders' backups must be active to establish a consensus on the dataset (see subsection 4.1.2). For Ovr, the number of additional partitions *m* is adjusted using the formula of subsection 4.2.1. For Hyb, the pair (*b*, *m*) is chosen using the formula of subsection 4.3.1 in order to optimize the sum of the number of additional nodes (passive and active).
<figure><img src="image_12.png" /><figcaption>Figure 10: Additional Nodes per Number of Partitions</figcaption></figure>

Figure 10 presents the number of additional nodes for each strategy depending on the number of partitions (horizontal partitioning). We first study a basic setup with a single Computer in each partition ($|C|=1$) and a device failure probability of 10% ($p_f=0.1$) for a success probability of 80% ($p_s=0.8$). We observe that increasing the number of partitions greatly favors strategies exploiting the overcollection principle (Ovr and Hyb). Moreover, Hyb perfectly mimics Ovr by increasing the number of additional partitions *m* while maintaining the number of backups *b* equal to zero. Note that even if the additional nodes are only passive for the Bak strategy, we saw in Section 5 that they necessarily induce extra overhead. Indeed, they generate a lot of communication for data replication, hence the objective to minimize their number.

<figure><img src="image_13.png" /><figcaption>Figure 11: Additional Nodes per Number of Computers (pf =0.1)</figcaption></figure>

Now that we have varied the horizontal partitioning, let us focus on the vertical partitioning, taking the same configuration as in previous chapters, i.e. *n*=10. Figure 11 shows that when the number of Computers per partition is low ($|C|<6$), Ovr and Hyb are identical and outperform Bak. From $|C|\ge 6$, we observe that Hyb begins to distinguish itself by finding a compromise between *b* and *m* that enables it to perform strictly better than the other two strategies. From $|C|\ge 8$, we see an inversion between the Bak and Ovr plots, with the number of additional nodes shifting in favor of Bak. As shown in Figure 12, this inversion occurs earlier as the probability of failure increases.

The explosion in the number of additional nodes for Ovr is explained by the fact that, for the strategy to succeed, at least *n* partitions with all SPFs must "survive" failures, whereas for Bak, only one primary or backup Data Processor per SPF (Snapshot Builder and Computers) is needed in each partition to guarantee successful executions.

Based on these results, we can draw the following conclusions: (1) horizontal partitioning greatly favors strategies based on overcollection (Ovr and Hyb), (2) vertical partitioning is detrimental to the Ovr strategy, especially when the probability of failure increases, and (3) the Hyb strategy can outperform Bak and Ovr by leveraging the strengths of both strategies.
<figure><img src="image_11.png" /><figcaption>Figure 10: Additional Nodes per Number of Partitions</figcaption></figure>

Figure 10 presents the number of additional nodes for each strategy depending on the number of partitions (horizontal partitioning). We first study a basic setup with a single Computer in each partition ($|C|=1$) and a device failure probability of 10% ($p_f=0.1$) for a success probability of 80% ($p_s=0.8$). We observe that increasing the number of partitions greatly favors strategies exploiting the overcollection principle (Ovr and Hyb). Moreover, Hyb perfectly mimics Ovr by increasing the number of additional partitions *m* while maintaining the number of backups *b* equal to zero. Note that even if the additional nodes are only passive for the Bak strategy, we saw in Section 5 that they necessarily induce extra overhead. Indeed, they generate a lot of communication for data replication, hence the objective to minimize their number.

<figure><img src="image_12.png" /><figcaption>Figure 11: Additional Nodes per Number of Computers (pf =0.1)</figcaption></figure>

Now that we have varied the horizontal partitioning, let us focus on the vertical partitioning, taking the same configuration as in previous chapters, i.e. *n*=10. Figure 11 shows that when the number of Computers per partition is low ($|C|<6$), Ovr and Hyb are identical and outperform Bak. From $|C|\ge6$, we observe that Hyb begins to distinguish itself by finding a compromise between *b* and *m* that enables it to perform strictly better than the other two strategies. From $|C|\ge8$, we see an inversion between the Bak and Ovr plots, with the number of additional nodes shifting in favor of Bak. As shown in Figure 12, this inversion occurs earlier as the probability of failure increases.

The explosion in the number of additional nodes for Ovr is explained by the fact that, for the strategy to succeed, at least *n* partitions with all SPFs must "survive" failures, whereas for Bak, only one primary or backup Data Processor per SPF (Snapshot Builder and Computers) is needed in each partition to guarantee successful executions.

Based on these results, we can draw the following conclusions: (1) horizontal partitioning greatly favors strategies based on overcollection (Ovr and Hyb), (2) vertical partitioning is detrimental to the Ovr strategy, especially when the probability of failure increases, and (3) the Hyb strategy can outperform Bak and Ovr by leveraging the strengths of both strategies.
<figure><img src="image_14.png" /><figcaption>Figure 12: Additional Nodes per Number of Computers (pf=0.2)</figcaption></figure>

## 6.1.2 Personal Data Exposure

Let us now consider the influence of these resiliency mechanisms on the exposure of personal data, both individually (i.e., how often the same data is exposed) and collectively (i.e., how many additional contributing individuals are included in the QEP). Note that this is potential exposure since the confidentiality property of TEEs is only broken if the devices are physically compromised (see subsection 2.1).

<table><caption>Table 5: Formulas for the Potential Additional Exposure</caption><thead><tr><th></th><th>Individual</th><th>Collective</th></tr></thead><tbody><tr><td>Bak</td><td>if (|C|=1): min=0, max=2 × b else: min=b, max=2 × b</td><td>0</td></tr><tr><td>Ovr</td><td>0</td><td>m/n</td></tr><tr><td>Hyb</td><td>min=0, max=b</td><td>m/n</td></tr></tbody></table>

Table 5 gives the formulas used to calculate the potential additional exposure. Individual exposure indicates the number of times the same personal data could be exposed. The minimum is determined by the number of active backups in the QEP, whereas the maximum is determined by the number of passive backups. Note that we count two additional exposures for Snapshots Builders and Computers backups, but that the number of Computers |C| is not considered, as they process data of different individuals (otherwise, increasing vertical partitioning would undermine privacy). Regarding collective exposure, we consider the proportion of additional individuals involved in the QEP, which is determined by the *m/n* ratio. Note also that, although these two measures aim to quantify exposure, they don't have the same meaning which makes them very difficult to compare. Individual exposure reveals the risk incurred by each individual, while collective exposure indicates the total number of individuals at risk. Depending on the application scenario and the type of queries, it will be the responsibility of both the Recipient and the Regulator to find the right compromise.

<figure><img src="image_15.png" /><figcaption>Figure 13: Potential Additional Exposure per Number of Computers (pf=0.1)</figcaption></figure>
<figure><img src="image_13.png" /><figcaption>Figure 12: Additional Nodes per Number of Computers (pf=0.2)</figcaption></figure>

## 6.1.2 Personal Data Exposure

Let us now consider the influence of these resiliency mechanisms on the exposure of personal data, both individually (i.e., how often the same data is exposed) and collectively (i.e., how many additional contributing individuals are included in the QEP). Note that this is potential exposure since the confidentiality property of TEEs is only broken if the devices are physically compromised (see subsection 2.1).

<table><caption>Table 5: Formulas for the Potential Additional Exposure</caption><thead><tr><th></th><th>Individual</th><th>Collective</th></tr></thead><tbody><tr><th>Bak</th><td>if (|C|=1): min=0, max=2 × b else: min=b, max=2 × b</td><td>0</td></tr><tr><th>Ovr</th><td>0</td><td>m/n</td></tr><tr><th>Hyb</th><td>min=0, max=b</td><td>m/n</td></tr></tbody></table>

Table 5 gives the formulas used to calculate the potential additional exposure. Individual exposure indicates the number of times the same personal data could be exposed. The minimum is determined by the number of active backups in the QEP, whereas the maximum is determined by the number of passive backups. Note that we count two additional exposures for Snapshots Builders and Computers backups, but that the number of Computers |C| is not considered, as they process data of different individuals (otherwise, increasing vertical partitioning would undermine privacy). Regarding collective exposure, we consider the proportion of additional individuals involved in the QEP, which is determined by the *m/n* ratio. Note also that, although these two measures aim to quantify exposure, they don't have the same meaning which makes them very difficult to compare. Individual exposure reveals the risk incurred by each individual, while collective exposure indicates the total number of individuals at risk. Depending on the application scenario and the type of queries, it will be the responsibility of both the Recipient and the Regulator to find the right compromise.

<figure><img src="image_14.png" /><figcaption>Figure 13: Potential Additional Exposure per Number of Computers (pf=0.1)</figcaption></figure>
Figure 13 shows on the same graph both types of exposure as a function of the number of Computers |C|. Although |C| is not directly considered when calculating personal data exposure, we saw in the previous subsection that it strongly influences the number of backups *b* and the number of additional partitions *m*, which therefore impacts it indirectly. Let us take a look at what happens at |C|=2. For Bak, we observe that the minimal additional individual exposure is at 200%, indicating that the data could be exposed to 2 active backups (corresponding to Snapshot Builders) and that the maximal additional individual exposure is at 400%, meaning that the data may also be exposed to 2 passive backups (those belonging to Computers). For Ovr and Hyb, we see an additional exposure at 50%, meaning that on the *n*=10 initial partitions, it is necessary to add *m*=5 other partitions to reach the target success rate of 80%.

Similar to the analysis in the previous subsection, we see that, as the number of Computers |C| increases, the Ovr strategy deteriorates. For example, when |C|=7 and *p*<sub>f</sub>=0.2, we obtain an overcollection rate of over 600% (see Figure 14). For Hyb, we observe a mixture of the two exposures. Indeed, above a certain threshold, the Hybrid method simultaneously integrates passive backups and additional partitions, with the (*b*, *m*) pair again chosen to reduce the number of nodes in the QEP. In fact, optimizing these parameters according to personal data exposure is rather complicated and application-dependent, as the two measures (individual and collective) are not comparable. Nevertheless, we can see that this strategy seems to be a good compromise when the other two are no longer acceptable (e.g., |C|=8 on Figure 13: one additional backup and 30% additional collective exposure).

<figure><img src="image_16.png" /><figcaption>Figure 14: Potential Additional Exposure per Number of Computers (pf=0.2)</figcaption></figure>

### 6.1.3 Network Overload

To complete this analysis, we propose an evaluation of network overload by counting the number of additional messages generated by each execution strategy. Although our objective is not to optimize network communications (see Section 2), we nevertheless wish to study the impact of strategies on the congestion they may generate. To this end, we are interested in measuring the number of messages containing data sent over the network, ignoring any other type of message (e.g. backup activation messages). As message size depends on the use case and the type of query, we assume a single size for all messages sent (whether data contribution or intermediate result).

<table><caption>Table 6: Formulas for the Additional Messages</caption><thead><tr><th></th><th>Mandatory Messages</th><th>Potential Messages</th></tr></thead><tbody><tr><th>Bak</th><td>if (|C|=1): (|D| + *n*) × *b*<br>else: [|D| + (2 + *b*) × |C| × *n*] × *b</td><td>if (|C|=1): (1 + *b* + |CC|) × *b* × *n*<br>else: |C| × *b* × |CC| × *n</td></tr><tr><th>Ovr</th><td>[|D|/*n* + |C| × (1 + |CC|)] × *m*</td><td>0</td></tr><tr><th>Hyb</th><td>[|D|/*n* + |C| × (1 + |CC|)] × *m* +<br>|C| × *b* × (*n* + *m*)</td><td>|C| × *b* × |CC| × (*n* + *m*)</td></tr></tbody></table>

Table 6 provides formulas for counting the number of additional messages generated by the three resiliency strategies (Bak, Ovr, Hyb). We observe two categories of messages: mandatory messages, which are necessarily sent when the QEP is executed,
Figure 13 shows on the same graph both types of exposure as a function of the number of Computers |C|. Although |C| is not directly considered when calculating personal data exposure, we saw in the previous subsection that it strongly influences the number of backups *b* and the number of additional partitions *m*, which therefore impacts it indirectly. Let us take a look at what happens at |C|=2. For Bak, we observe that the minimal additional individual exposure is at 200%, indicating that the data could be exposed to 2 active backups (corresponding to Snapshot Builders) and that the maximal additional individual exposure is at 400%, meaning that the data may also be exposed to 2 passive backups (those belonging to Computers). For Ovr and Hyb, we see an additional exposure at 50%, meaning that on the *n*=10 initial partitions, it is necessary to add *m*=5 other partitions to reach the target success rate of 80%.

Similar to the analysis in the previous subsection, we see that, as the number of Computers |C| increases, the Ovr strategy deteriorates. For example, when |C|=7 and *p*<sub>f</sub>=0.2, we obtain an overcollection rate of over 600% (see Figure 14). For Hyb, we observe a mixture of the two exposures. Indeed, above a certain threshold, the Hybrid method simultaneously integrates passive backups and additional partitions, with the (*b*, *m*) pair again chosen to reduce the number of nodes in the QEP. In fact, optimizing these parameters according to personal data exposure is rather complicated and application-dependent, as the two measures (individual and collective) are not comparable. Nevertheless, we can see that this strategy seems to be a good compromise when the other two are no longer acceptable (e.g., |C|=8 on Figure 13: one additional backup and 30% additional collective exposure).

<figure><img src="image_15.png" /><figcaption>Figure 14: Potential Additional Exposure per Number of Computers (pf=0.2)</figcaption></figure>

### 6.1.3 Network Overload

To complete this analysis, we propose an evaluation of network overload by counting the number of additional messages generated by each execution strategy. Although our objective is not to optimize network communications (see Section 2), we nevertheless wish to study the impact of strategies on the congestion they may generate. To this end, we are interested in measuring the number of messages containing data sent over the network, ignoring any other type of message (e.g. backup activation messages). As message size depends on the use case and the type of query, we assume a single size for all messages sent (whether data contribution or intermediate result).

<table><caption>Table 6: Formulas for the Additional Messages</caption><thead><tr><th></th><th>Mandatory Messages</th><th>Potential Messages</th></tr></thead><tbody><tr><th>Bak</th><td>if (|C|=1): (|D| + *n*) × *b*<br>else: [|D| + (2 + *b*) × |C| × *n*] × *b</td><td>if (|C|=1): (1 + *b* + |CC|) × *b* × *n*<br>else: |C| × *b* × |CC| × *n</td></tr><tr><th>Ovr</th><td>[|D|/*n* + |C| × (1 + |CC|)] × *m*</td><td>0</td></tr><tr><th>Hyb</th><td>[|D|/*n* + |C| × (1 + |CC|)] × *m* +<br>|C| × *b* × (*n* + *m*)</td><td>|C| × *b* × |CC| × (*n* + *m*)</td></tr></tbody></table>

Table 6 provides formulas for counting the number of additional messages generated by the three resiliency strategies (Bak, Ovr, Hyb). We observe two categories of messages: mandatory messages, which are necessarily sent when the QEP is executed,
and potential messages, which are sent when passive backups are activated. Note that the number of messages sent by Data Contributors can be much higher than the required cardinality of the dataset $|D|$. Indeed, snapshot construction requires an unpredictable number of contributions in order to satisfy the set of representativeness predicates $P$. As this unpredictable quantity of messages is context-dependent, we do not include it in our measurements.

<figure><img src="image_17.png" /><figcaption>Figure 15: Additional Messages per number of Computers</figcaption></figure>

Figure 15 shows the number of additional messages according to the number of Computers. We have calibrated a horizontal partitioning of $n=10$, a failure probability of 10%, and a success rate of 80%. For these parameters, the QEP needs only one Computing Combiner, i.e. no active backups associated ($b_{cc}=0$). The cardinality of the target dataset is set to $|D|=1000$. As expected, the vast majority of additional messages are associated with the contribution phase. Bak is therefore disadvantaged, as every message sent by Data Contributors is replicated on the Snapshot Builder's backups. As for Ovr and Hyb, the strategies are again identical as long as $|C|<6$. This observation, already made in Figure 11, is explained by the fact that Hyb is still optimized to minimize the additional nodes in the QEP.

Let us now look at Figure 16 to see how Hyb behaves when the pair $(b, m)$ is calibrated to optimize the number of additional messages (mandatory and potential). We can see that Hyb is systematically better than the other strategies and that the gap widens as $|C|$ increases. In fact, similar to Ovr, the Hybrid strategy is naturally designed to minimize the number of messages sent during the contribution phase because Snapshot Builders have no backups. The advantage of Hyb over Ovr is its ability to compensate for the probability of partition failure by adding backups to the Computers. This feature proves to be a significant asset, as reducing the number of additional partitions results in a substantial reduction in the number of additional messages sent. Note that this optimization is not without cost, as it inevitably entails modifications in the exposure of personal data. For instance, with $p_f=0.1$ and $|C|=3$, Hyb will count 1 backup per Computer for a 20% overcollection instead of 0 backup for a 70% overcollection (see Figure 13).

<figure><img src="image_18.png" /><figcaption>Figure 16: Additional Messages per number of Computers (Hyb optimization)</figcaption></figure>

## 6.2 Adjustment of the Query Deadline

In this second subsection, we focus on how to calibrate the query deadline such that messages sent in the OppNet have sufficient time to reach their destination. Without loss of generality, we will focus on implementing a non-iterative processing executed
and potential messages, which are sent when passive backups are activated. Note that the number of messages sent by Data Contributors can be much higher than the required cardinality of the dataset $|D|$. Indeed, snapshot construction requires an unpredictable number of contributions in order to satisfy the set of representativeness predicates $P$. As this unpredictable quantity of messages is context-dependent, we do not include it in our measurements.

<figure><img src="image_16.png" /><figcaption>Figure 15: Additional Messages per number of Computers</figcaption></figure>

Figure 15 shows the number of additional messages according to the number of Computers. We have calibrated a horizontal partitioning of $n=10$, a failure probability of 10%, and a success rate of 80%. For these parameters, the QEP needs only one Computing Combiner, i.e. no active backups associated ($b_{cc}=0$). The cardinality of the target dataset is set to $|D|=1000$. As expected, the vast majority of additional messages are associated with the contribution phase. Bak is therefore disadvantaged, as every message sent by Data Contributors is replicated on the Snapshot Builder's backups. As for Ovr and Hyb, the strategies are again identical as long as $|C|<6$. This observation, already made in Figure 11, is explained by the fact that Hyb is still optimized to minimize the additional nodes in the QEP.

Let us now look at Figure 16 to see how Hyb behaves when the pair $(b, m)$ is calibrated to optimize the number of additional messages (mandatory and potential). We can see that Hyb is systematically better than the other strategies and that the gap widens as $|C|$ increases. In fact, similar to Ovr, the Hybrid strategy is naturally designed to minimize the number of messages sent during the contribution phase because Snapshot Builders have no backups. The advantage of Hyb over Ovr is its ability to compensate for the probability of partition failure by adding backups to the Computers. This feature proves to be a significant asset, as reducing the number of additional partitions results in a substantial reduction in the number of additional messages sent. Note that this optimization is not without cost, as it inevitably entails modifications in the exposure of personal data. For instance, with $p_f=0.1$ and $|C|=3$, Hyb will count 1 backup per Computer for a 20% overcollection instead of 0 backup for a 70% overcollection (see Figure 13).

<figure><img src="image_17.png" /><figcaption>Figure 16: Additional Messages per number of Computers (Hyb optimization)</figcaption></figure>

## 6.2 Adjustment of the Query Deadline

In this second subsection, we focus on how to calibrate the query deadline such that messages sent in the OppNet have sufficient time to reach their destination. Without loss of generality, we will focus on implementing a non-iterative processing executed
with the Ovr strategy. Indeed, adding backups (for Bak and Hyb) only shifts the deadline according to the procedure described in subsection 4.1.1. Moreover, we have just seen in the previous subsection that the Ovr strategy is better in most configurations (with Hyb matching it by imitation). So, to study the query deadline, we built an Edgelet computing software on top of the Opportunistic Network Environment (ONE) simulator [41] providing detailed traces of OppNets communications (see Figure 17). We model two representative use cases with messages exchanged using an epidemic routing strategy [68], namely Mall and DomY.

<figure><img src="image_19.png" /><figcaption>Figure 17 Mall simulation with the ONE</figcaption></figure>

**Mall:** Edgelet computing within a Mall of 0.16 km2, where 5,000 edgelets (customer smartphones following a RandomWayPoint movement) are opportunistically executing a query exchanging messages using Bluetooth when meeting. The mean OppNet latency obtained with ONE is $\bar{L} = 1,936$ s for a standard deviation $\sigma = 933$ s, resulting in a relative standard deviation of $R\sigma = \frac{\sigma}{\bar{L}} = 0.48$

**DomY:** The DomYcile project [24], with 8,000 personal home boxes (edgelets) and 800 healthcare workers (with constrained routes in ONE) within the Yvelines district (2,284 km2). We obtained a mean latency $\bar{L} = 27,113$ s with a relative standard deviation $R\sigma = 2.43$, (i.e., $\sigma = 65,794$ s).

Using the latencies computed by ONE, we execute a non-iterative QEP following the Ovr strategy, considering vertical partitioning on 3 Computers with a device failure probability of 10%. We used 3 values of $m/n$, ranging from 0.5 to 1.5. To enable comparisons between Mall and DomY, we used on the x-axis the query deadline divided by $\bar{L}$, called $\alpha$ hereafter, and measured the query success ratio (y-axis on Figure 18). To minimize random variations, we averaged the results of 300 executions. Note that we are only interested in the impact of message transmission along the QEP and not in studying the quality of its processing, the latter being easily assured as long as fewer than $m$ partitions are lost (see subsection 4.2.2). Therefore, we consider an execution successful when at least $n$ partitions transmit their response to the Recipient before the query deadline.

<figure><img src="image_20.png" /><figcaption>Figure 18: Query Deadlines (for Overcollection)</figcaption></figure>

From these plots, we make 3 observations: (1) in the Mall context (small $R\sigma$), all executions complete successfully with $m/n \ge 1$ and $\alpha = 4$ (vertical increase); while the DomY context requires much larger deadlines due to its larger $R\sigma$ which impacts the fault presumption; (2) having an underestimated $m/n$ value is risky: it reduces the ratio of successful queries and requires a significantly higher query deadline in contexts with large $R\sigma$ (e.g., DomY); (3) having a larger $m/n$ value is rather useless for
with the Ovr strategy. Indeed, adding backups (for Bak and Hyb) only shifts the deadline according to the procedure described in subsection 4.1.1. Moreover, we have just seen in the previous subsection that the Ovr strategy is better in most configurations (with Hyb matching it by imitation). So, to study the query deadline, we built an Edgelet computing software on top of the Opportunistic Network Environment (ONE) simulator [41] providing detailed traces of OppNets communications (see Figure 17). We model two representative use cases with messages exchanged using an epidemic routing strategy [68], namely Mall and DomY.

<figure><img src="image_18.png" /><figcaption>Figure 17 Mall simulation with the ONE</figcaption></figure>

**Mall:** Edgelet computing within a Mall of 0.16 km2, where 5,000 edgelets (customer smartphones following a RandomWayPoint movement) are opportunistically executing a query exchanging messages using Bluetooth when meeting. The mean OppNet latency obtained with ONE is $\bar{L} = 1,936$ s for a standard deviation $\sigma = 933$ s, resulting in a relative standard deviation of $R\sigma = \frac{\sigma}{\bar{L}} = 0.48$

**DomY:** The DomYcile project [24], with 8,000 personal home boxes (edgelets) and 800 healthcare workers (with constrained routes in ONE) within the Yvelines district (2,284 km2). We obtained a mean latency $\bar{L} = 27,113$ s with a relative standard deviation $R\sigma = 2.43$, (i.e., $\sigma = 65,794$ s).

Using the latencies computed by ONE, we execute a non-iterative QEP following the Ovr strategy, considering vertical partitioning on 3 Computers with a device failure probability of 10%. We used 3 values of $m/n$, ranging from 0.5 to 1.5. To enable comparisons between Mall and DomY, we used on the x-axis the query deadline divided by $\bar{L}$, called $\alpha$ hereafter, and measured the query success ratio (y-axis on Figure 18). To minimize random variations, we averaged the results of 300 executions. Note that we are only interested in the impact of message transmission along the QEP and not in studying the quality of its processing, the latter being easily assured as long as fewer than $m$ partitions are lost (see subsection 4.2.2). Therefore, we consider an execution successful when at least $n$ partitions transmit their response to the Recipient before the query deadline.

<figure><img src="image_19.png" /><figcaption>Figure 18: Query Deadlines (for Overcollection)</figcaption></figure>

From these plots, we make 3 observations: (1) in the Mall context (small $R\sigma$), all executions complete successfully with $m/n \ge 1$ and $\alpha = 4$ (vertical increase); while the DomY context requires much larger deadlines due to its larger $R\sigma$ which impacts the fault presumption; (2) having an underestimated $m/n$ value is risky: it reduces the ratio of successful queries and requires a significantly higher query deadline in contexts with large $R\sigma$ (e.g., DomY); (3) having a larger $m/n$ value is rather useless for
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_21.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.