Vincent Fagnon
email: vincent.fagnon@inria.fr

Giorgio Lucarelli
email: giorgio.lucarelli@univ-lorraine.fr@univ-lorraine.fr

Clément Mommessin
email: c.mommessin@leeds.ac.uk

Denis Trystram
email: denis.trystram@inria.fr

Two-Agent Scheduling with Resource Augmentation on Multiple Machines

Keywords:

We are interested in this paper in studying how to schedule tasks in an extreme edge setting, where some sensors produce data and subsequent tasks are executed locally. They are interacting with some external tasks submitted by a superior authority in the cloud. We first model such a system as a problem of scheduling two sets of tasks, each associated with its own objective. The tasks of the first set are released on-line, they can be preempted and the target objective is the minimization of the mean flow-time. The tasks of the second set are known beforehand and cannot be preempted. The objective is to execute them before a common deadline.

Due to strong lower bounds on the competitive ratio of this problem, we use the technique of resource augmentation to cope with these limitations. Specifically, our analysis is based on both speed augmentation and rejection. First, we give a general lower bound for the problem, even in the case of speed augmentation and rejection. Then, we propose a competitive algorithm and analyze its performance using dual fitting.

Figure 1: Schematic view of a smart building with multiple sensors (fire detector, motion sensor, video surveillance, sound analysis, etc.) and a link to the Internet (Cloud services, weather forecast data, information collected around in the smart city, etc.). The tasks associated to the sensors are collected in a local queue and the external tasks are put in a global queue. Both are managed by the computing units of the smart building.

Introduction

Today, the computing systems are evolving in a continuum of cloud/fog/edge. These systems are always more complex, since they are composed of various types of computing devices. The diversity of the digital components that compose such systems creates new problems in the perspective of managing efficiently the execution of tasks. Most data produced by sensors at the extreme edge should be processed immediately and the analysis of data should be done locally, close to the sensors [START_REF] Dinh C Nguyen | Federated learning for internet of things: A comprehensive survey[END_REF]. Most of these data only have an interest in the local environment where they are produced, and their lifespan is short. Thus, they should be analyzed immediately. When no analysis is performed, the available computing units can be utilized for external or offloaded computing, such as volunteer computing [START_REF] David P Anderson | Boinc: A system for public-resource computing and storage[END_REF]. In this work, we target a computing system composed of multiple computing units connected to some sensors. For instance, think of a smart building with a centralized control and processing units like the one described in Figure 1. A classical edge infrastructure is composed of several of such computing systems, but we will restrict our focus on a single one. Informally, there are two types of tasks to execute in this example, and each type is associated to a distinct objective as it will be described in more details in the next section.

Problem Description

The characteristics of the two types of tasks, each type associated with an agent, are the following:

• The first agent manages the tasks that are generated locally by the sensors. We call these tasks local or dynamic as they arrive on-line, and we should process them as soon as possible. The release time of a local task is not known in advance, but its processing time is known at the time it is released. The target objective of the first agent is to minimize the total flow-time of these tasks. Due to locality and their usually small processing time and memory consumption, the preemption (without migration) of these tasks is allowed.

• The second type of tasks corresponds to the external tasks submitted per batch. We call them global or static as they are submitted off-line.

The processing of such tasks is known, and the objective is to complete this set of tasks in a reasonable amount of time, typically before a common deadline that is fixed, regarding the total computational load during the batch. From their nature and possibly large memory consumption compared to local tasks, a global task cannot be preempted. However, we allow the rejection of a global task during its execution, if this is needed to keep a good overall performance of the system. Intuitively, a rejected global task will be re-submitted in a subsequent batch in the same or in another targeted computing system.

The tasks of both agents are sequential. The overall problem is thus to interleave both sets of tasks on the set of computing machines in the best possible way with respect to the target objectives. To summarize, the inputs of the corresponding scheduling problem are as follows:

• m identical machines,

• n L local tasks and n G global tasks,

• p j the processing time of task j.

The objective is to minimize the sum flow-time of the local tasks, i.e., the total time that a local task remains in the system, such that a global deadline is respected for the global tasks.

Contributions and Organization

In the single agent case, the on-line flow-time minimization problem can be solved to optimality on a single machine if preemptions are allowed, but it is hard to approximate with m ≥ 2 machines [START_REF] Leonardi | Approximating total flow time on parallel machines[END_REF], or in the off-line setting if preemptions are not allowed [START_REF] Kellerer | Approximability and nonapproximability results for minimizing total flow time on a single machine[END_REF][START_REF] Chekuri | Algorithms for minimizing weighted flow time[END_REF]. These inapproximability results led to analyze the problem in the context of resource augmentation, where more power is given to the algorithm, as for instance allowing the algorithm to use more processors or higher speed than the optimal. In the case of speed augmentation, we assume the algorithm is using machines with a speed of 1 + , while the optimal solution is based on a machine speed of 1, where ≥ 0 is a constant. Using these resource augmentation models, we can achieve performance guarantees that depend on the value of [START_REF] Phillips | Optimal time-critical scheduling via resource augmentation[END_REF][START_REF] Kalyanasundaram | Speed is as powerful as clairvoyance[END_REF][START_REF] Anamitra | Rejecting jobs to minimize load and maximum flow-time[END_REF].

With the introduction of tasks from the global agent, we show in this paper that it is hard to approximate the flow-time objective for the local tasks, even though their preemption is allowed and resource augmentation is used. Specifically, any on-line algorithm which uses (1 + s )-speed machines should reject at most k global tasks to achieve a competitive ratio in O (1 -2k n G )W , where W is the ratio between the total work load of the global tasks and the total work load of the local tasks.

On the positive side, we propose an algorithm to solve the addressed twoagent scheduling problem under the resource augmentation model, with both rejection and speed augmentation. Then, we analyze the competitive ratio of the algorithm using the dual fitting approach [START_REF] Anand | Resource augmentation for weighted flow-time explained by dual fitting[END_REF]. In particular we prove that our algorithm is (1 + s )-speed and max W s r + 1+ s 2 s , 1+ s s -competitive by rejecting a fraction of global tasks depending on a parameter r , where s > 0 and 0 < r < 1.

The organization of the paper is as follows: We start by presenting a brief state of the art about the two-agent scheduling problem, the flow-time minimization problem and resource augmentation models in Section 2. Section 3 gives a formal definition of the problem and the notations used throughout the paper, and Section 4 presents our lower bound. In Section 5, we introduce the competitive algorithm for solving the two-agent scheduling problem and analyze its competitive ratio with the dual fitting approach in Section 6. Section 7 ends the paper, with concluding remarks and discussions.

Related Work

The work presented in this paper can be seen as an extension of the twoagent scheduling problem by considering that the tasks of one agent arrive on-line.

The problem of two-agent scheduling has been introduced by Agnetis et al. [START_REF] Agnetis | Scheduling problems with two competing agents[END_REF]. Their seminal paper was dedicated to scheduling two sets of nonpreemptive tasks competing to execute on a single machine, where each agent aims at minimizing its own objective function based on the completion time of its tasks (maximum, sum, due dates, etc.). The authors considered two ways for solving the problem: First, by minimizing an objective function while keeping the second objective under a threshold and, second, by finding the set of non-dominated pairs of objective values on the Pareto front. Later, Agnetis et al. [START_REF] Agnetis | Multiagent Scheduling -Models and Algorithms[END_REF] extended this work to other multi-agent scheduling problems including the execution on parallel machines.

One can find in the literature many variants of the two-agent scheduling problem, for example considering a chain of tasks for each agent [START_REF] Agnetis | Scheduling two agent task chains with a central selection mechanism[END_REF], tasks with due dates [START_REF] Cheng | Scheduling Jobs of Two Competing Agents on a Single Machine[END_REF][START_REF] Yin | Due Date-Related Scheduling with Two Agents -Models and Algorithms[END_REF], or with an additional setup time when a task of one agent is processed directly after a task of the second agent [START_REF] Li | Scheduling two job families on a single machine with two competitive agents[END_REF].

In a similar setting, Baker and Smith [START_REF] Baker | A Multiple-Criterion Model for Machine Scheduling[END_REF] studied the problem of two or three agents on a single machine, where each agent has its own objective function to minimize. However, they considered the single objective approach by minimizing a linear combination of the objective of each agent. Liu et al. [START_REF] Liu | Two-agent scheduling on a single machine with release dates[END_REF] also considered the problem with tasks arriving off-line with release times, with the objective of minimizing a linear combination of the maximum completion times (makespan) of both agents. Saule and Trystram [START_REF] Saule | Multi-users scheduling in parallel systems[END_REF] focused on the problem of an arbitrary number of agents scheduling jobs on parallel machines, where the objective of an agent is either the minimization of the makespan or the sum of completion time of its tasks. They proposed inapproximability bounds and approximation algorithms with performance ratios depending on the number of agents.

Our problem may also be considered as an extension of the problem of total flow-time minimization of on-line tasks on parallel machines, under the additional constraint of the off-line scheduling of tasks from a second agent.

For the flow-time minimization problem, it is well known that the Shortest Remaining Processing Time (SRPT) policy gives an optimal schedule for online tasks on a single machine. Unfortunately, the optimality of SRPT does not hold in our context with a second agent, as will be shown in Section 4. When m ≥ 2 machines are considered, the problem becomes NP-hard [START_REF] Du | Minimizing mean flow time with release time constraint[END_REF], and Leonardi and Raz [START_REF] Leonardi | Approximating total flow time on parallel machines[END_REF] showed that SRPT is O(min{log(P ), log n m })competitive, where P is the ratio between the maximum and minimum processing time of the tasks, and n the number of tasks. They also showed that no on-line algorithm could achieve a better competitive ratio.

Such strong results on the inapproximability of scheduling problems motivated the introduction of the resource augmentation model, where an on-line algorithm is given more power when comparing to the optimal. Such models can be considered with speed augmentation [START_REF] Kalyanasundaram | Speed is as powerful as clairvoyance[END_REF], machine augmentation [START_REF] Phillips | Optimal time-critical scheduling via resource augmentation[END_REF] or rejection [START_REF] Anamitra | Rejecting jobs to minimize load and maximum flow-time[END_REF].

In the context of scheduling on a single machine, Feng et al. [START_REF] Feng | Two-agent scheduling with rejection on a single machine[END_REF] studied the common two-agent problem of Agnetis et al. with the additional feature that jobs can be rejected with a given penalty to the objective value of the corresponding agent. In the on-line setting, Lucarelli et al. also introduced the speed augmentation and rejection models to the total (weighted) flow-time minimization problem on unrelated [START_REF] Lucarelli | Online non-preemptive scheduling in a resource augmentation model based on duality[END_REF][START_REF] Lucarelli | Online non-preemptive scheduling on unrelated machines with rejections[END_REF][START_REF] Lucarelli | Online non-preemptive scheduling to minimize weighted flow-time on unrelated machines[END_REF] and related machines [START_REF] Lucarelli | Online non-preemptive scheduling to minimize maximum weighted flow-time on related machines[END_REF]. The authors proposed several algorithms whose competitiveness was proved using the dual fitting technique. We will use the same approach in the analysis of our algorithm in Section 5.

Problem Formulation and Notations

We consider a set M of m identical machines on which to execute two sets of sequential tasks having different settings. The first set L is composed of n L local tasks that are submitted on-line, while the second set is composed of n G global tasks that are submitted off-line. Only local tasks can be preempted, but migration between machines is not allowed. For a given task j, we denote by r j its release time and by p j its processing time on a machine, only known at the time the task is being released. Note that the release time is 0 for all global tasks, since they are off-line.

Given a schedule, we denote by F j the flow-time of a local task j, defined as the difference between its completion time and its release time. The objective is to minimize the sum flow-time of all local tasks, under the constraint that all global tasks have completed before a common deadline d G . We also consider that the release time of any local task is bounded above by d G . This deadline, defined as

d G = 1 m • j∈G p j -max j∈G {p j } + max j∈G {p j } + j∈L p j ,
guarantees that a schedule interleaving local and global tasks is always feasible. Notice however that, since local tasks are released over time, the value of d G is not known beforehand by the algorithm.

Under the resource augmentation model, we introduce the coefficients of speed augmentation s > 0 and rejection 0 < r < 1. An algorithm to solve the addressed problem can use machines with speed 1 + s times faster than that of an optimal adversary, and can reject a number of global tasks bounded by an r -fraction of the number of local tasks.

We define below some additional notations used in the next sections. In a partial schedule, Q L i (t) denotes the set of local tasks assigned to machine i, but not completed at time t. This set includes all the local tasks waiting to be executed on machine i, as well as the task currently being executed at time t, if it is local. Note that, upon arrival of task j at time r j and assigned to machine i, we assume that it is immediately added to Q L i (r j ). Since preemption of local tasks is allowed, p rem j (t) denotes the remaining processing time of task j at time t. Finally, for a given instance of the problem, we denote by W = j∈G p j / j∈L p j the ratio between the total workload of the global tasks and the total workload of the local tasks.

A Lower Bound

Theorem 1. Let s ≤ 1 3 • W-3 3W+3 and k ∈ {1, 2, . . . , n G 2 }
, where n G is the number of global tasks. Any online algorithm which uses (1 + s )-speed machines should reject at least k global tasks to have a competitive ratio in

O (1 -2k n G )W . Proof.
We consider an instance with a single machine, consisting of 2Z global tasks that are split evenly into two sets of tasks of respective processing times X/3 and 2X/3. We partition the time into Z phases, each one of length X +1: the phase corresponds to the time interval [( -1)(X + 1), (X + 1)), for each = 1, 2, . . . , Z. Let b = ( -1)(X +1), 1 ≤ ≤ Z, denote the beginning of phase . In order to well distinguish the phases, a burst of Y local tasks of processing time 0 is released online at every time (X + 1), 1 ≤ ≤ Z. Moreover, in each phase there is an arrival of a single local task of processing time 1, whose release time will be defined later. We have two cases to consider:

Case 1: If the online algorithm decides to execute one global task of processing time X/3 (say G 1 ) and one global task of processing time 2X/3 (say G 2 ) in each phase , 1 ≤ ≤ Z.

If the algorithm decides to execute G 1 before G 2 , then the earliest time at which the execution of G 1 can finish in the algorithm's schedule is b + X 3(1+ s) , since the algorithm has access to a machine which executes the tasks at speed 1 + s . After the completion of G 1 , the algorithm will start G 2 at some time t ≥ b + X 3(1+ s) . Then, the adversary decides to release the local task L at time b + 2X 3 and the flow time of L will be at least X-2X s+3 3(1+ s) , if G 2 is not rejected; otherwise the flow time of L will be 1 1+ s . The optimal solution executes the tasks in the order G 2 , L and G 1 , resulting in a flow-time of 1.

If the algorithm decides to execute G 2 before G 1 , then let t ≥ b be the starting time of G 2 . Then, the adversary decides to release the local task L at time X 3 and the flow time of L will be at least X-X s+3 3(1+ s) , if G 2 is not rejected; otherwise the flow time of L will be 1 1+ s . The optimal solution executes the tasks in the order G 1 , L and G 2 , resulting in a flow-time of 1.

Assuming that the algorithm decides to reject the corresponding task G 2 in exactly k phases, then its total flow time is at least k

1+ s +(Z-k) X-2X s+3 3(1+ s) = (Z -k) W(1-2 s) 3(1+ s) + Z 1+ s , since W = X.
On the other hand, the total flow time of the optimal schedule is Z. Then, by rejecting k global tasks, the competitive ratio will be at least

Z-k Z W(1-2 s) 3(1+ s) + 1 1+ s = Ω Z-k Z W .
Case 2: Otherwise, there is a phase during which two global tasks of processing time 2X/3 are partially executed. Hence, there exists a phase , at the beginning of which a global task started in the previous phase -1 will be executed for at least q = 1 1+ s 4X 3 -(X + 1) time. Then, the burst of local tasks arrived at time ( -1)(X + 1) will have a total flow-time at least qY . Note that in this case the arrival of local tasks of processing time 1 is not important and we can assume w.l.o.g. that the algorithm will execute all of them just upon their arrival, getting a total flow-time for them equal to Z. On the other hand, the optimal solution will be as in the previous case having a total flow time equal to Z. Therefore, the competitive ratio in this case will be Ω(Y ), which can be chosen large enough such that the first case dominates.

An Algorithm for the Two-Agent Problem

The algorithm is denoted by A and described as follows.

Initialization: At start, we consider a queue of global tasks Q G initialized with all the global tasks sorted in an arbitrary order. For each machine i ∈ M, we initialize an empty queue of local tasks Q L i . Local task allocation: Upon submission of a local task j, we allocate it to the machine i that minimizes

λ ij = l∈Q L i (r j ): p rem l (r j )≤p j p rem l (r j ) + l∈Q L i (r j ): p rem l (r j )>p j p j (1)
and denote by λ j this quantity. Intuitively, we put the task j on the machine minimizing the increase in the total flow-time induced only by the tasks in

Q L i .
Task execution: For each machine i, the tasks in Q L i are executed in the Shortest Remaining Processing Time order. Note that if a newly arrived task is shorter than the local task currently being executed, then preemption occurs and the remaining part of the current task is put back in

Q L i . If Q L
i becomes empty, then we remove a task from Q G and execute it on i, until no more global tasks are left. By not introducing idle times in the schedule before all global tasks are processed, we ensure that the last global task will complete before the common deadline d G . Note that global tasks are removed from the queue in an arbitrary order.

Rejection policy for global tasks: If at any time there are more than 1 r local tasks in the local queue of a machine currently executing a global task, we decide to reject that task. Note that such a rejection can only happen when a local task is released. This way, we ensure that no more than r • n L global tasks are rejected in total.

Analysis by Dual Fitting

We analyze our algorithm by dual fitting [START_REF] Anand | Resource augmentation for weighted flow-time explained by dual fitting[END_REF]. We first provide an expression of the total flow-time achieved by the algorithm in Section 6.1 and give a By definition, the total flow-time of local tasks achieved by the algorithm is equal to the sum of ∆ j for all local tasks. Due to the rejection policy, the impact of global tasks on the total flow-time of local tasks is limited. There cannot be more than 1 r local tasks in the queue during the execution of a global task, so a global task j will contribute at maximum to p j r (1+ s) on the total flow-time of the algorithm. Therefore, we have the following:

j∈L F j = j∈L ∆ j ≤ j∈L      l∈Q L i (r j ): p rem l (r j )≤p j p rem l (r j ) 1 + s + l∈Q L i (r j ): p rem l (r j )>p j p j 1 + s      + j∈G p j r (1 + s ) (2)

Linear Programming Formulation

We define a decision variable x ij (t) which is equal to 1 if the task j ∈ L ∪ G is running on machine i ∈ M at time t ≥ 0, and 0 otherwise. By convention, we assume that x ij (t) = 0 for local tasks when t < r j .

Consider this linear programming formulation, with the constant Γ ≥ 1 2 :

min.

i∈M j∈L ∞ r j (t -r j ) p j + Γ x ij (t)dt s.t. i∈M ∞ r j x ij (t)dt ≥ p j ∀j ∈ (L ∪ G) (3a) j∈(L∪G) x ij (t) ≤ 1 ∀i ∈ M, ∀t ≥ 0 (3b) i∈M ∞ 0 t p j + 1 2 x ij (t)dt ≤ d G ∀j ∈ G (3c) x ij (t) ∈ {0; 1} ∀i ∈ M, ∀j ∈ (L ∪ G), ∀t ≥ 0
Constraint (3a) verifies that each task j ∈ L ∪ G is executed for at least p j units of time, Constraint (3b) indicates that a machine can execute at most one task at any moment t ≥ 0, and the left-hand side of Constraint (3c) computes the completion time of a global task j.

Note that the quantity ∞ r j (t-r j )

p j x ij (t)dt in the objective function corresponds to the well-known fractional flow-time of the job j [START_REF] Anand | Resource augmentation for weighted flow-time explained by dual fitting[END_REF]. This is a lower bound to the flow-time of j. Moreover, with Γ = 1 2 , the objective value of an optimal solution for the linear program is at most the flow-time of an optimal schedule for our problem [START_REF] Anand | Resource augmentation for weighted flow-time explained by dual fitting[END_REF]. During our analysis, we will use a larger value of Γ and the objective value of the program will be at most (Γ + 1 2 ) that of the optimal value of the problem.

Note also that the above formulation does not exactly model the addressed problem, as it does not forbid preemption of global task or their migration between machines. Instead, the formulation is a relaxation, but it is sufficient to analyse our algorithm and prove its approximation ratio via dual fitting and resource augmentation.

After relaxing the integrality constraint on the variables x ij (t) in the primal program, its dual program can be expressed as follows. max.

j∈L∪G α j p j - i∈M ∞ 0 β i (t)dt - j∈G d G γ j s.t. α j -β i (t) - t -r j p j + Γ ≤ 0 ∀i ∈ M, ∀j ∈ L, ∀t ≥ r j (4a)
α j -β i (t) - t p j + 1 2 γ j ≤ 0 ∀i ∈ M, ∀j ∈ G, ∀t ≥ 0 (4b) α j ≥ 0 ∀j ∈ (L ∪ G) β i (t) ≥ 0 ∀t ≥ 0, ∀i ∈ M γ j ≥ 0 ∀j ∈ G

Dual Variables

For the purpose of the analysis via dual fitting, we define the variables of the dual program according to the decisions taken by the algorithm. We define the first dual variable for local tasks as α j = λ j (1+ s)pj + Γ. Note that the value of α j is only set at the arrival of j, and it does not change afterward. For the other variables, we define α j = 0 and γ j = 0 for any global task j; and

β i (t) = |Q L i (t)|
1+ s , ∀t ≥ 0.

Competitive Analysis

With the two following lemmas, we show that our definition of the dual variables leads to a feasible solution of the dual program.

Lemma 1. For every every machine i ∈ M, every local task j ∈ L and every time t ≥ r j , the dual constraint (4a) is satisfied, that is:

α j -β i (t) - t -r j p j + Γ ≤ 0
Proof. First of all, the constant term Γ in the α j is compensated with the Γ of the constraint. By multiplying all remaining terms by (1 + s )p j , we have to prove:

λ j -|Q L i (t)| • p j -(1 + s )(t -r j )
≤ 0 If more local tasks arrive after j, the quantity |Q L i (t)| will increase and the constraint will be easier to satisfy. For this reason, we assume that there is no other task arrival after j. Thus |Q L i (t)| can only decrease over time, when a task finishes its execution. Moreover, due to the dispatching policy of local tasks we have λ j ≤ λ ij .

Assume that a task k is currently being executed at time r j and finishes at time t = r j + p rem k (r j ) 1+ s . For any time t ∈ [r j , t ), |Q L i (t)| will remain constant and it is sufficient to prove the constraint at the beginning of the interval, when t = r j . We have

λ ij ≤ l∈Q L i (r j ): p rem l (r j )≤p j p j + l∈Q L i (r j ): p rem l (r j )>p j p j = |Q L i (r j )| • p j
and thus the constraint is satisfied for any time t in this interval. Let now k be the first task in Q L i (r j ) after k, such that when k finishes its execution at time t then k starts executing during the interval t , t +

p rem k (r j ) 1+ s
. Again, it is sufficient to verify the constraint at the beginning of the interval, at time t = r j + p rem k (r j ) 1+ s . We have

λ ij ≤ p rem k (r j ) + l∈Q L i (r j )\{k}: p rem l (r j )≤p j p j + l∈Q L i (r j ): p rem l (r j )>p j p j = p rem k (r j ) + |Q L i (t )| • p j and p rem k (r j ) -(1 + s )(r j + p rem k (r j ) 1 + s -r j ) ≤ 0.
Thus, the constraint is satisfied for any t in the interval. A similar reasoning for every time interval during the execution of any local task in Q L i (r j ) can be made. Note that, if a global task was rejected on the arrival of the local task j, it would not change the above reasoning. Hence, the dual constraint (4a) is satisfied for any time t ≥ 0. Lemma 2. For every machine i ∈ M, every global task j and every time t ≥ 0, the dual constraint (4b) is satisfied, that is:

α j -β i (t) -( t p j + 1 2 )γ j ≤ 0
Proof. The smallest possible value of β i (t) is when the queue of local tasks is empty. Thus, for any t we have β i (t) ≥ 0. Provided that α j = 0 and γ j = 0 the dual constraint (4b) is satisfied.

Recall that F j denotes the flow-time of task j in the schedule produced by algorithm. Then, the following lemma shows the relation between the total flow-time of local tasks achieved by the algorithm and the objective value of the dual program. Lemma 3. Given our definitions of α j , β i (t) and γ j , the dual objective value verifies:

j∈L∪G α j p j - i∈M ∞ 0 β i (t)dt - j∈G d G γ j ≥ s 1 + s j∈L F j
Proof. With our definition of α j (recall α j = 0, ∀j ∈ G) we have j∈L∪G

α j p j = j∈L      l∈Q L i * (r j ): p rem l (r j )≤p j p rem l (r j ) 1 + s + l∈Q L i * (r j ): p rem l (r j )>p j p j 1 + s + Γ • p j      + 1 1 + s j∈G p j r - j∈G p j r ≥ j∈L F j + Γ • j∈L p j - j∈G p j r (1 + s )
, where the inequality holds due to Equation [START_REF] Agnetis | Scheduling problems with two competing agents[END_REF]. With the definition of β i (t), we have:

i∈M ∞ 0 β i (t)dt = i∈M ∞ 0 |Q L i (t)| 1 + s dt = 1 1 + s j∈L F j
Recall the notation W = j∈G p j j∈L pj , which is the ratio between the total work load of the global tasks and the total work load of the local tasks. By choosing

Γ = max W r (1 + s ) , 1 2 ,
and knowing that γ j = 0, ∀j ∈ G, the objective value of the dual program can be expressed as follows:

j∈L∪G α j p j - i∈M ∞ 0 β i (t)dt - j∈G d G γ j ≥ j∈L F j + Γ • j∈L p j - j∈G p j r (1 + s ) - 1 1 + s j∈L F j = s 1 + s j∈L F j + Γ • j∈L p j - j∈G p j r (1 + s ) ≥ s 1 + s j∈L F j
We now have enough to conclude on the competitive ratio of our algorithm.

Theorem 2. For any 0 < r < 1 and s > 0, the algorithm A is (1 + s )speed, max W s r + 1+ s 2 s , 1+ s s -competitive and rejects at most ( r • n L ) global tasks.

Proof. From the three previous lemmas we know that the dual variables as we defined them form a feasible solution of the dual program, and that the objective value of the dual program is an upper bound of the total flow-time achieved by the algorithm multiplied by a constant factor. From the rejection policy, a global task is rejected the first time when there are more than 1 r local tasks waiting in the queue. Thus, no more than r • n L global tasks are rejected. By definition, the algorithm uses a machine with speed (1 + s ) times the machine speed of an optimal solution.

It remains to express the relation between the total flow-time of our algorithm with that of an optimal solution. As Γ ≥ 1 2 , the objective value of the primal program is at most Γ + 1 2 times the flow-time of an optimal solution, denoted by OP T . Finally, using the duality theorem, we can write the relation:

s 1 + s • j∈L F j ≤ (Γ + 1

Concluding Remarks

We introduced in this paper a new scheduling problem with two agents targeting each a different objective. As far as we know, it is the first time a mixed off-line/on-line setting was studied for this problem. We provided a lower bound on the competitive ratio of any algorithm for solving the problem, and proposed an algorithm with a proof of its competitive ratio via dual fitting under a resource augmentation framework (speed and rejection). The objective of the global tasks is taken as a constraint, while its value is specified by the scheduling policy of global tasks. Using List Scheduling in our case, the common deadline was taken as the classical Graham's bound plus the total work load of the local tasks. It is possible to refine the value of the deadline in accordance with a change in the scheduling policy of global tasks in the algorithm A: Using any algorithm X for P ||C max with known approximation ratio ρ to construct a fixed allocation of global tasks to the machines prior to the submission of any local task, it is guaranteed that a value of the deadline d G = C X max + j∈L p j will be respected. Doing so, the dynamic allocation of global tasks is lost, but it gives a "bi-objective" vision to the problem: the minimization of both the total flow-time of local tasks and the global deadline.

Going further with the model, we believe it is possible to remove the speed augmentation, which is only used in the algorithm's analysis, as it was successfully done in another work on a single agent problem with on-line tasks [START_REF] Lucarelli | Online non-preemptive scheduling on unrelated machines with rejections[END_REF]. Another interesting perspective is to extend the model to the weighted case, or with related/unrelated machines.

Acknowledgment

This work was partly supported by the french ANR Energumen project 18-CE25-0008, by the research program on Edge Intelligence of the MIAI@Grenoble Alpes (ANR-19-P3IA-0003), and by the EPSRC funded project EP/T01461X/1 "Algorithmic Support for Massive Scale Distributed Systems".

linear programming formulation of our problem in Section 6.2, as well as the corresponding relaxed dual program. Then, in Section 6.3 we propose an assignment of the dual variables based on the choices made by our algorithm. In Section 6.4, we prove that this assignment satisfies the dual constraints and we give the competitive ratio of our algorithm.

Algorithm's Flow-Time

First, let ∆ j be the increase in the total flow-time of the current solution of our algorithm incurred by the dispatch of a local task j on machine i. This value corresponds to the flow-time of the task j, plus the increase in flowtime of all tasks being delayed by the arrival of j. Following our scheduling and rejection policies, and assuming the task k was being executed at time r j , the detailed definition of ∆ j is expressed as follows:

l∈Q L (r j ): p rem l (r j )>p j p j 1 + s Note that, due to speed augmentation, any value of processing time for our algorithm is divided by (1 + s ).


Ludovic Javet

Nicolas Anciaux

Luc Bouganim

Philippe Pucheral

Edgelet Computing: Pushing Query Processing and Liability at the Extreme Edge of the Network

Keywords: Edge computing, TEE, OppNet, Resiliency

We call edgelet computing the current convergence between Opportunistic Network (OppNet) and Trusted Execution Environment (TEE) at the very edge of the network. We believe that this convergence bears the seeds of a novel and important class of applications leveraging fully decentralized and highly secure computations among data scattered on multiple personal devices. This paper introduces the Edgelet computing paradigm, defines properties that guarantee the safety, liveness and security of executions in this unusual context and proposes alternative strategies satisfying these properties. Preliminary performance evaluations and an ongoing real-case study highlights the practicality of the approach. Finally, the paper draws future research challenges for the database and distributed system community.

I. INTRODUCTION

The edge of the Internet is expanding at a much higher pace than its core, with 29.3 billion of connected device by 2023 [START_REF]Cisco Annual Internet Report[END_REF]. At the same time, the reliable, server-based and infrastructurecentric approach of the internet already exhibits its limits in terms of efficiency, privacy and energy consumption. Alternatively, infrastructureless and self-organizing networking protocols have emerged, from the legacy MANET protocol to the Opportunistic Network (OppNet) paradigm, on top of which a new peoplecentric vision of the Internet (IoP) can be drawn [START_REF] Conti | The Internet of People (IoP): A new wave in pervasive mobile computing[END_REF]. However, while this paradigm has attracted a lot of attention from the research community, OppNets have never been deployed at large scale, mainly due to the lack of killer applications [START_REF] Trifunovic | A Decade of Research in Opportunistic Networks: Challenges, Relevance, and Future Directions[END_REF].

A game changer is the generalization of Trusted Execution Environments (TEE) [START_REF] Sabt | Trusted Execution Environment: What It is, and What It is Not[END_REF] at the extreme edge of the network: Intel SGX [START_REF] Costan | Intel SGX Explained[END_REF] is becoming ubiquitous on PC and tablets, ARM's TrustZone [START_REF] Pinto | Demystifying Arm TrustZone: A Comprehensive Survey[END_REF] on smartphones (Fig. 1.a) and even Trusted Platform Module on smart objects (Fig. 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 -way than with homomorphic cryptography [START_REF] Boneh | Private Database Queries Using Somewhat Homomorphic Encryption[END_REF], differential privacy [START_REF] Dwork | Differential Privacy[END_REF] or secure multiparty computation protocols [START_REF] Bater | SMCQL: Secure Query Processing for Private Data Networks[END_REF]. Our approach leverages the security features of TEEs to enable generic computation and scalable execution, processing cleartext data without any tradeoff between privacy and accuracy.

The convergence between OppNets and TEEs, named hereafter Edgelet computing, leverages secure personal devices (called edgelets) and holds the promise of concrete killer applications for OppNets by exploiting three non-exclusive dimensions: -Data altruism: This concept introduced in the EU Data

Governance Act [START_REF]Proposal for a Regulation of the European Parliament and of the Council on European Data Governance (Data Governance Act)[END_REF] fosters data subjects to give consent to process their personal data for purposes such as scientific research or public services improvement. Privacy protection is paramount in this context. Notably, a real-case study [START_REF]DomYcile Project[END_REF] aiming at querying ephemeral cohorts over 8,000 elderly patients falls in this category and has motivated part of this work. In this study, detailed next, patients hold their medical records in a secure personal box at home (Fig. 1.b) acting as an edgelet using short range communications. Such scenario could be generalized to all forms of Personal Data Management Systems (PDMS) [START_REF] Anciaux | Personal Data Management Systems: The security and functionality standpoint[END_REF] hosted by their holder.

-Crowd-liable data processing: Companies and administrations are often interested in analyzing personal data from their customers or citizens, but are reluctant to shoulder the responsibility for treatment due to high legal risk in case of data leakage and to the image deficit incurred by adopting solutions perceived as intrusive. Edgelet computing provides them a mean to convince the targeted users -by any form of reward -to voluntary contribute to a global processing task while letting the computing infrastructure and personal data in their hands. This liability shift from the data controller (in the GDPR sense) to the crowd is made possible by leveraging the security of Edgelets' TEE.

-Contextual data processing: Some data processing tasks are relevant only at specific times and/or geographic areas, and of interest only for specific groups of users (e.g., tourists visiting a city, customers in a mall). This motivated the emergence of Mobile Social Networks (MSN) [START_REF] Bellavista | Mobile social networking middleware: A survey[END_REF]. Edgelet computing provides the required trust among MSN participants to dynamically organize data processing tasks, taking advantage of location-based homophily that exists among people having social relationships [START_REF] Pelechrinis | Socio-spatial affiliation networks[END_REF].

Edgelet computing scenarios require performing complex processing over personal data -from database queries to machine learning -in a highly distributed, failure-prone and infrastructureless context, with strong security guarantees. This paper is a first attempt to tackle the data management and distributed system issues related to this environment and makes the following contributions:

(1) it characterizes the Edgelet computing paradigm by a combination of architectural and computing assumptions, an unusual threat model and three properties that guarantee the liveness, safety and security of executions;

(2) it proposes two alternative execution strategies enforcing liveness in opposite ways and discuss their impact on safety;

(3) it provides quantitative and qualitative evaluations of these strategies and derives design rules for adapting centralized computations to the Edgelet computing paradigm.

Section II presents the Edgelet Computing paradigm and precisely states the problem at hand. Section III introduces the basics (execution plans and task-to-edgelet assignment) to handle distributed computations in this paradigm. Section IV and V detail the two execution strategies mentioned above. Section VI provides a preliminary performance evaluation while Section VII presents a qualitative evaluation and design rules. Section VIII focuses on related works. Finally, we conclude and present important research challenges for the database and distributed system community in Section IX.

II. EDGELET COMPUTING PARADIGM

A. Architecture and Computation of Interest

As mentioned above, Edgelet Computing refers to the convergence between OppNets and TEEs at the extreme edge of the network, namely up to personal devices and smart objects sidestepping the classical communication infrastructure for cost or energy constraints, lack of connectivity, security or even freedom of expression concerns. Hence, we consider that the communications are short range (e.g., Bluetooth, Wi-Fi) and asynchronous, i.e., there is no bound on the message transmission delay. Connections among devices then form a non-connected time-varying graph as in traditional OppNets [START_REF] Benchi | Solving Consensus in Opportunistic Networks[END_REF]. For simplicity, we consider an epidemic diffusion of the messages, i.e., messages are transferred from device to device following a store-carry-forward strategy. We let optimized routing protocols exploiting moving patterns of users for future work.

We assume that any edgelet is equipped with a TEE which guarantees (1) data confidentiality: data manipulated by a TEE cannot be observed from the outside; and (2) code integrity: an attacker cannot influence the behavior of a program executing within a TEE. Although highly difficult to conduct and requiring physical instrumentation, side-channel attacks compromising data confidentiality cannot however be totally ignored [START_REF] Wang | Leaky Cauldron on the Dark Land: Understanding Memory Side-Channel Hazards in SGX[END_REF].

Finally, we consider computations involving personal data hosted in distributed edgelets, constituting a multitude of disconnected instances of PDMS [START_REF] Anciaux | Personal Data Management Systems: The security and functionality standpoint[END_REF] or Databoxes [START_REF] Mortier | Personal Data Management with the Databox: What's Inside the Box?[END_REF]. Contrary to participatory sensing or sensor networks which focus on stream queries over elementary data, we consider rich data (e.g., healthcare folders, spending habits) and complex processing (e.g., machine learning, data mining) over edgelets data seen as a horizontal partitioning of a shared database. In this context, the computations (called Query hereafter) must cope with the uncertainty inherent to the Edgelet paradigm, making the traditional database closed-world assumption irrelevant. Let E be 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 C (e.g., C = 2000). We denote by zQ(E) the set of all snapshots of E enforcing P and C. The Query Q is thus said snapshot compliant if the result of Q considering any snapshot of zQ(E) is semantically equivalent for the Querier.

B. Edgelet Computing Threat Model

Edgelet computing requires the introduction of a dedicated threat model to capture (1) the shift of responsibility from the data controller to the crowd and (2) the TEE trustworthiness.

Indigent Querier.

Trust: we do not question the good faith of the Querier but rather its ability or willingness to set up and endorse a secure infrastructure. In case of an attack, the Querier may have punctually a Malicious behavior, but recurring inference attacks from its side are precluded and not further considered. Role: publish the processing for approval, initiate the processing and get the final result without taking part to the computation. Examples: a public or private agency, the moderator of a Mobile Social Network.

Wolf in sheepfold Participants.

Trust: all participant's devices are equipped with TEE, but as said above, side-channel attacks cannot be totally precluded despite their complexity. A compromised TEE behaves in a "sealed glass proof" mode [START_REF] Tramer | Sealed-Glass Proofs: Using Transparent Enclaves to Prove and Sell Knowledge[END_REF], where code integrity is preserved but data confidentiality is lost. We assume a large majority of honest participants (the lambs) and a few "sealed glass proof" ones (the wolves). Role: contribute with their data (Data Contributor) and/or their processing power (Data Processor). Example: a smartphone or home box secured with a TEE.

Trusted Regulatory Agent.

Trust: full. Role: review and approve (i.e., sign) the code published by the Querier. This role is not devoted to the query execution itself. Example: a privacy regulatory agency.

Untrusted environment. covers the rest of the infrastructure, device's OS and network notably.

C. Motivating Example

Fig. 2 illustrates Edgelet computing with a real example taken from the DomYcile project [START_REF]DomYcile Project[END_REF], where 8,000 elderly patients are equipped with secure boxes (edgelets) storing their medical/social folder. These boxes are not connected to the Internet for subscription cost, security and acceptability reasons and can only be accessed at patient's home by healthcare workers. The Yvelines district (Querier), in charge of health and social cares, wants to query ephemeral cohorts of consenting people to obtain statistical results in the spirit of [START_REF] Herr | Frailty, polypharmacy, and potentially inappropriate medications in old people: findings in a representative sample of the French population[END_REF] (Share EU project [START_REF]The Survey of Health, Ageing and Retirement in Europe (SHARE): Home[END_REF]), without endorsing the responsibility of this processing. The query example given in Fig. 2 illustrates the necessity to compute all statistics on the same snapshot for consistency reasons. The query is approved by the CNIL (French regulatory agency) then broadcast by healthcare workers who implement the OppNet using a store-carry-forward strategy with encrypted messages (untrusted environment) between Edgelets. Secure boxes act as Data Contributor edgelets; some are randomly selected to act as Data Processors, this randomness limiting the action of compromised edgelets.

D. Problem Statement

Edgelet computing opens exciting opportunities to organize secure decentralized computations but combines unusual hypotheses. First, reliable failure detectors cannot exist in OppNets due to the unpredictability of message delays, making difficult to predict the time to build a snapshot from random contributors and to execute a query. The system liveness must then be guaranteed based on fault presumptions only and on probability of success for queries associated to a deadline. Second, the snapshot consistency must be preserved all along the query processing despite presumed faults and message loss between Data Processors to guarantee the system safety, i.e., a consistent result. Third, the liability shift to the crowd must be endorsed in a context where a few "sealed glass proof" devices may endanger the security of the whole system with no way to detect them. We introduce below three properties that must be met together to tackle this problem.

Resiliency (liveness property). Given a probability of fault presumption pf for any edgelet, a query deadline, and an expected probability of success ps, a query Q must complete before the deadline with a probability greater than ps, otherwise Q is aborted.

Validity (safety property). The result of an edgelet execution of a query Q must be identical to a centralized execution of Q over at least one snapshot of zQ(E), a sufficient condition to guarantee the equivalence of the results from the Querier perspective.

Crowd liability (security property). (1)

The liability of data processing must be equally distributed among the edgelets by a random process auditable by any participant. (2) Any edgelet involved as a Data Processor is liable only for the processing and data assigned to it. Note. Condition (1) precludes targeted attacks by a compromised edgelet which could try to self-assign some operators. Condition [START_REF] Conti | The Internet of People (IoP): A new wave in pervasive mobile computing[END_REF] guarantees that a data leakage must be circumscribed to the data processed by a compromised edgelet, with no possibility of inducing data leakage in honest edgelets, i.e., only data from compromised edgelets can leak through the network. This guarantee is the strongest possible in the Edgelet context where the TEE security is leveraged to perform processing on clear-text data, allowing any type of processing.

These properties are particularly challenging to tackle together given their mutual impact. We present in Sections IV and V two execution strategies answering this challenge in two opposite ways, both sharing basic principles presented in the next Section.

III. EXECUTION PLAN AND DATA PROCESSOR ASSIGNMENT

Before discussing how computations (i.e., query executions) can be made resilient and how the validity of their result can be assessed, we need first to introduce which form takes these computations and how the tasks involved in these computations are assigned to the participating edgelets complying with the Crowd liability property.

A. General Form of Query Plans

We consider that a computation is expressed by a Query Execution Plan (QEP), that 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. Operators are assigned randomly to Data Processors (see Section III.B) taking in charge the execution of the operator's code. To simplify the presentation, we consider that any message is sent atomically through the OppNet (i.e., the payload is either totally received by the recipient or not at all) and that each edgelet executes a single operator.

The simplest form of a QEP is a tree with Data Contributors at the leaves (one per edgelet contributing to the query with its data) sending the requested data to a Snapshot Builder operator, the role of which is to collect a representative snapshot of cardinality C, satisfying P. The Snapshot Builder then sends the representative snapshot to a Computer operator which in turn computes the final result and finally delivers it to the Querier.

The Computer can be decomposed into sub-operators assigned to different edgelets for privacy or performance concerns. This can help minimizing 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 information that become sensitive when combined (e.g., a quasiidentifier) by vertically partitioning the dataset. This can finally help minimizing the Data Processor workload (e.g., when energy consumption matters) or exploit the inherent Edgelet computing parallelism. A Computing Combiner operator must then be added in the QEP to combine the outputs of all sub-operators.

In this section, we impose no restriction on the operators to be computed nor on the form of the QEP: we consider them as given by the Querier. Fig. 3 presents the QEP for the query example of Fig. 2, using horizontal partitioning (Data Contributors are assigned to Snapshot Builders, e.g., by hashing their public key) and vertical partitioning (each Computer manages a single statistic).

B. Data Processor Assignment

The assignment of tasks to Data Processors must be done with care to avoid violating the Crowd liability property. Condition (1) of this property imposes a random assignment of Edgelets to QEP Operators. This is to guarantee that a compromised Data Processor cannot freely choose to execute e.g., the operator manipulating the data of a targeted contributor or the operator manipulating a maximum amount of sensitive data. This process must also be made auditable by any participant to establish trust among the crowd.

The assignment process we propose works as follows. It assumes that the set of edgelets in E are known by the Querier (e.g., they register to join a community) and it organizes the ID of their edgelets in a hash ring (as in a Chord DHT). It computes a hash of the query (signed by the Trusted Regulatory Agent and publicly known) as a seed for the random process and assigns the first operator to the edgelet having the ID immediately greater than this hash. The first hash is rehashed to assign the second operator and so forth until all operators have been assigned. Note that this is consistent with the Indigent Querier threat model, in that any participant can reproduce this chain of hash and can thus detect a fraudulent assignment for the operator intended for them, assuming they know at least the ID of their predecessor in the ring.

Let's now examine the impact of Condition (2) of the Crowd liability property. It expresses two things. First, it states the absence of data leakage if no Data Processor is compromised. It is trivially guaranteed on the one hand by the TEE confidentiality property and on the other hand by the encryption of all messages in transit, the latter being simplified by the assignment protocol presented above (i.e., any edgelet can encrypt its output according to the targeted recipients since they are statically defined in the QEP). Second, this condition states that a data leakage must be restricted to the data handled by compromised Data Processors. This is achieved by the fact that (1) no cryptographic material (e.g., keys) is ever shared among edgelets and (2) TEE code integrity still holds even in sealed-glass proof mode, thus reducing the potential leakage to the data processed by a compromised edgelet.

IV. BACKUP-BASED EXECUTION STRATEGY

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

A. Enforcing Resiliency

As already stated, no reliable failure detector exists in our context and every Data Processor (SB, C and CC edgelets in Fig. 3) is a potential Single Point of Failure (SPF). In this approach, we simply try to recover from failures, whatever the Data Processor presumed faulty, the benefit of which being to make the handling of resiliency independent of the form of the QEP. Therefore, we use timeouts to presume faults and secure the execution of all SPFs by means of backups, as usual [START_REF] Wiesmann | Understanding replication in databases and distributed systems[END_REF].

We distinguish 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 higher data exposure (see Fig. 4). Consequently, all SPFs are passively replicated, except the Computing Combiner which must be actively replicated; otherwise, the Querier would be forced to take part in the processing, at least to activate the Computing Combiner Backup; this would have an impact on data exposure and would hurt the Indigent Querier assumption.

The number b of backups per primary is determined by the inequality (1 -pf b+1 ) |SPF| ≥ ps, with pf the probability of fault presumption, ps the expected probability of success, and |SPF| the number of SPFs in each horizontal partition of the QEP. Given a query deadline, the timeouts are chosen so that any Data Processor has the ability to activate all of its children's backups if needed. This simple recursive calculation is not detailed here for brevity.

B. Impact on Validity

Satisfying the Validity property requires that (i) the operators involved in the QEP are genuine and correctly executed in the right order and (ii) the dataflow between these operators is consistent wrt. at least one of the zQ(E) snapshots.

We leverage the code integrity property provided by the TEE to enforce condition (i) as follows. Each edgelet runs a piece of code called Core hereafter, which is part of the TEE Trusted Computing Base, that is a code base guaranteed genuine at boot time. In turn, the Core attests the genuineness of the QEP operator's code assigned to the edgelet and guarantees the integrity of the intermediate results in cascade [START_REF] Ladjel | Trustworthy Distributed Computations on Personal Data Using Trusted Execution Environments[END_REF] in the spirit of remote attestations [START_REF] Costan | Intel SGX Explained[END_REF]. Moreover, the QEP is built statically (as said above), thus all communications are predetermined and can easily be cryptographically secured. Hence, any change in the operators ordering would make the messages indecipherable and the execution would fail.

In a perfect world, condition (ii) directly stems from condition (i). With failure or message loss however, a Snapshot Builder and its backup(s) may build different snapshots, each belonging to zQ(E). Due to this, 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 of zQ(E), called hereafter the reference snapshot.

Without 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 backup otherwise. 2. Similarly, with horizontal partitioning, the reference snapshot is simply the union of each partition's snapshot (either backup or primary). 3. With vertical partitioning however, the Snapshot Builder feeds several Computers, some of them potentially considering the primary snapshot and some others the backup ones in case of fault presumption. This leads to an inconsistency, i.e., a result built over a snapshot that does not correspond to any snapshot belonging to zQ(E).

Fig. 4 illustrates this concern, where each Computer evaluates a different statistic but must consider a same snapshot belonging to zQ(E). To solve this problem, several solutions can be envisioned but all of them incur a significant overhead. We cite only two of them for conciseness: (1) Synchronize the snapshot between the primary Snapshot Builder and its backup(s) thanks to a consensus protocol. [START_REF] Benchi | Solving Consensus in Opportunistic Networks[END_REF] proposes an effective consensus protocol for OppNets that matches the Edgelet context, at the price of a distributed consensus; (2) Rearrange the QEP so that the parallel branches are serialized, one after the other, at the price of losing the QEP parallelism.

V. OVERCOLLECTION-BASED EXECUTION STRATEGY

This section introduces a very different way to handle the problem stated in Section II, which integrates the OppNet context by design. Contrary to the backup-based strategy, messages delays or loss are no longer considered as faults that must be recovered but rather as a legitimate behavior.

A. Enforcing Overcollection-based 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 SPF that executes a distributive operator. Instead of executing this operator on a single edgelet, we distribute (using hashing) its execution over n edgelets, each processing a partition of the initial dataset (in Figs. 3, 4 and5, n=10). The Overcollection ratio must be adapted to the presumed fault probability pf of the OppNet to reach the expected success rate ps for a query. Hence, the probability of failure of a SPF over-collecting m more partitions is

∑ " !"# $ #𝑝 % $ (1 -𝑝 % ) (!"#'$) !"# $)#"*
. Note that we could also have increased the number of collected data per partition, keeping n unchanged, but preliminary experiments showed that this solution is less effective in terms of data exposure. The challenge, detailed next, is to apply this intuition to a complete QEP.

B. Impact of Overcollection on Validity

If all QEPs can satisfy the Validity property when executed in a backup mode (in some cases by adding a consensus among backups), this is no longer true when executed in an Overcollection mode. Indeed, (1) the complete QEP must be reorganized to handle a partitioned dataset and (2) a reference snapshot DÎzQ(E) must remain identifiable despite 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 an independent processing over a partition of the collected dataset with a root process assembling the final result (see Fig. 5). This solution applies only if the commutativity rules between operators allow to push all distributive operators down to the sub-QEPs and to push Fig. 5. Overcollection for the QEP of Fig. 3 all non-distributive operators up to the root. A QEP satisfying this condition is said reshapable. We consider this brute-force solution next and let more subtle designs for future work. Under this assumption, point (2) can be easily tackled. The reference snapshot D is simply the union of all partitions that contributed to the QEP computation up to its root. Assuming that each of the n+m partitions locally satisfies predicate P and have a cardinality C/n, the execution validity is trivially preserved as long as less than m partitions are lost.

C. Relaxing Validity

Most data intensive queries of interest in our context are distributive by nature (as confirmed by various MapReduce or Spark implementations). 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 (ML) algorithms, because they are iterative or need to exchange partial results computed over different data partitions. In these cases, a reference snapshot DÎzQ(E) can no longer be identified in case of messages 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 and sketched in Fig. 6.

To execute an algorithm A with Iterative Brute-Force, each edgelet implementing a sub-QEP Computer iterates on (1) a local convergence phase where it computes 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 knowledges and sends the final result to the Querier.

The main question is when to stop the processing. Fixing a number of iterations a priori (with a minimal number of received messages) has little sense in the OppNet context where message delays, then edgelet progression, are unpredictable. Expecting a local convergence is also hazardous 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 We illustrate this method on two classical algorithms, namely Apriori (data mining representative) and k-means (ML representative), and show its effectiveness in terms of proximity of results wrt. centralized executions in Section VI.

Apriori [START_REF] Savasere | An Efficient Algorithm for Mining Association Rules in Large Databases[END_REF]: mine 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 [START_REF] Dhillon | A Data-Clustering Algorithm on Distributed Memory Multiprocessors[END_REF]: form k clusters minimizing the intra-cluster variance.

-knowledge: current centroids (initially, k initial 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 newly created clusters, updating its knowledge. -Synchronization: computes, on a cluster basis, the barycenter of all centroids received from other sub-QEPs it has heard of, and integrates the result in knowledge. -Computing Combiner: computes, on a cluster basis, the barycenter of all centroids received.

VI. PRELIMINARY EVALUATIONS The goal of these evaluations is threefold: to validate the relevance of the approach, to calibrate the system and to verify its effectiveness. We first compare the backup-based strategy (Bak) and the Overcollection strategy (Ovr), providing insights to properly configure the parameters. Then, we evaluate Ovr on a non-iterative query to calibrate the query delay with respect to the probability of success (ps). Finally, we test the iterative methods Apriori and k-means and evaluate the quality of their results against a centralized execution.

To this end, we built an Edgelet computing simulator on top of the Opportunistic Network Environment (ONE) simulator [START_REF] Keränen | The ONE Simulator for DTN Protocol Evaluation[END_REF] providing detailed traces of OppNets communications (see Fig. 7). We model two representative use cases with messages exchanged using an epidemic routing strategy [START_REF] Vahdat | Epidemic Routing for Partially-Connected Ad Hoc Networks[END_REF]: DomY: the DomYcile project, with 8,000 personal home boxes (edgelets), 800 healthcare workers (with constrained routes in ONE) within the Yvelines district (2,284 km 2 ). The mean OppNet latency obtained with ONE is 𝐿 * = 27,113 s with a relative standard deviation Rσ = 2.43, (i.e., σ = 65,794 s).

Mall: Edgelet computing within a Mall of 0.16 km 2 , where 5,000 edgelets (customer smartphones following a RandomWayPoint movement) are opportunistically executing a query exchanging messages using Bluetooth when meeting. We obtained 𝐿 * = 1,936 s and Rσ = 0.48 (σ = 933 s).

Our simulator can process real data on simulated edgelets, using the latencies computed by ONE. The experiments are done on both use cases. To minimize random variations, we averaged the results of 300 executions. We consider the QEPs of figures 4 (Exp. 1), 5 (Exp. 1 & 2), and 6 (Exp. 3), all being horizontally partitioned on n = 10 partitions (plus potentially over-collected ones) as in the figures. Other experiment parameters are indicated on the graphs. Experiment 1: Bak vs Ovr. Fig. 8.a and 8.b compare the replication degree (i.e., b for Bak) and the Overcollection degree (i.e., m/n for Ovr), for each SPF (SB or C in Fig. 3 and4). These values (y-axis) are indicative of the potential exposure in case of compromised Data Processors. We vary the degree of vertical partitioning (v on x-axis), i.e., the number of Computers in each partition, to avoid concomitant exposure of, e.g., a quasiidentifier, and consider large values to check the behavior of Bak and Ovr in extreme cases (partitioning in 2 or 3 subsets is generally sufficient). We calibrate b and m using the formulas of Section IV.A and Section V, and, to simplify the analysis, we assume an infinite deadline, i.e., there is only effective failures. Thus, b and m/n values are identical for DomY or Mall contexts.

Observations: (1) Bak shows steps since b is an integer while Ovr is smoothly increasing (m/n); (2) when v is large (e.g., v > 6) and there are many failures (15%), m/n increases considerably for Ovr while b stays reasonable for Bak. Indeed, with Ovr, at least n partitions with all SPFs must "survive" failures while Bak needs at least one survival primary or backup Data Processor per SPF in each partition. Experiment 2: Query deadline (non-iterative queries). We execute the QEP of Fig. 5 with Ovr, considering vertical partitioning on 3 Computers (v = 3). We used 3 values of m/n, ranging from 0.5 to 1.5 wrt. the first experiment. To enable comparisons between DomY and Mall, we used on x-axis the query deadline divided by 𝐿 * , called ⍺ hereafter, and measure the query success ratio (y-axis on Fig. 9.a and 9.b).

Observations: [START_REF]Cisco Annual Internet Report[END_REF] In the Mall context (small Rσ), all executions complete successfully with m/n ≥ 1 and ⍺ = 4 (vertical increase); while the DomY context requires much larger deadlines due to its larger Rσ 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σ (e.g., DomY); (3) having a larger m/n value is rather useless for small Rσ contexts (e.g., Mall), indeed, a small Rσ means that latencies are close to the mean, thus a well calibrated m/n is sufficient to absorb few late messages.

Conclusion: m/n should not be underestimated and the query deadline should be fixed larger than 𝐿 * ×|hops| where |hops| is the number of hops in the query plan (in this case, 4: Contributor➛Snapshot Builder➛Computers➛ Computing Com biners➛Querier). Both m/n and the deadline should be overestimated when the OppNet latencies have a large Rσ. 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. Experiment 3: Iterative computations quality. We simulate the iterative algorithms Apriori and k-means, considering synthetic and real data sets used to evaluate their quality (e.g., [START_REF] Brijs | Retail market basket data set[END_REF] for Apriori). Thanks to the simulator, we systematically measure the quality of Edgelet executions against centralized fault-free executions (y-axis on Fig. 10.a and 10.b). 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. To evaluate iterative methods in extreme conditions, we reduced artificially the HeartBeat duration such that the observed proportion of late messages (i.e., messages arrived after the HeartBeat) is 80%, 90% and 95% (see Fig. 10.a and 10.b). As a consequence, DomY and Mall contexts produce approximately the same results (DomY results are shown).

Observations: (1) Even with no iteration, Apriori reaches 65% recall and k-means reaches 30% degradation of its inertia;

(2) 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); (3) with Apriori, precision is always 100% (not shown). We verified that Computing Combiners always receive n or more sub-QEPs results and can then remove potential false positive; (4) with k-means, we observe a negative PCI. Indeed, the Edgelet computation with many heartbeats is better than the centralized one since it may consider up to m additional partitions.

Conclusion:

HeartBeat execution shows quite good results on Apriori and k-means despite an (artificially) high ratio of late messages. Other classical iterative algorithms deserve further study.

These evaluation results are only preliminary but they suggest that regular queries can be executed in the Edgelet context while enforcing Resiliency, Validity and Crowd liability with performance compatible with the targeted applications, and that even ML algorithms could be supported with a pretty good accuracy of their results.

VII. BACKUP VS. OVERCOLLECTION: SOME DESIGN RULES This section compares qualitatively the two execution strategies proposed in Sections IV and V. Our goal is to guide a potential Querier towards the right execution model when designing a computation dedicated to the Edgelet computing paradigm. This choice depends on the type of computation to be performed, the way to define a representative snapshot for this computation and the expected query deadline. We can draw some design rules from the statements summarized in Table 1.

In this table, Horizontally/Vertically partitionable refers to the property of the computation to be distributed among several Data Processors, as explained in Section III.A. 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 constraint on the processing, horizontal partitioning requires that predicate 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 to exploit the Overcollectionbased strategy for this QEP. Ground validity means that the Validity property defined in Section II cannot be enforced; hence, it is up to the Querier to assess empirically the accuracy of the final result, as we did in Section VI for Apriori and kmeans. Finally, The Crowd liability 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. Second, if the computation is iterative, the Overcollection strategy turns to be the only solution as well. Indeed, using Backup, 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 in this case. Third, if the QEP is reshapable and P is partitionable, the right choice between Backup and Overcollection is driven by the expected success rate and by privacy considerations. Using Backup, 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 for which the query deadline depends only on 𝐿 * and |hops|; this is especially true if the fault presumption rate pf is high, making this criterion dependent of the OppNet quality. Regarding privacy, both methods do not expose data in the same way. Indeed, as explained in Section IV, TEEs guarantee that data at rest is not exposed in backups until the backup is 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. In the Overcollection model, 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. This factor may influence the approval of the Trusted Regulatory Agent and the participants' consent as well and finally depends on the privacy model exposed by the Querier.

Resiliency

The taxonomy of solutions presented in Table 1 is only preliminary and more subtle design rules can be envisioned. Hybrid strategies mixing backups and Overcollection deserve to be considered in the future, with the goal to decrease the extra amount of data exposed by each strategy (e.g., exploit overcollected partitions only if initial once are lost or backup the root of an over-collected QEP statically instead of pushing it in the Computing Combiner directly). Similarly, Ground validity should be more deeply investigated with the goal to identify finer classes of algorithms for which better validity guarantees can be expected. For example, the Apriori implementation sketched in Section V.C 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 be able to guarantee the convergence for some algorithms when specific conditions are met but let these issues for future work.

VIII. RELATED WORKS

A lot of research work has been produced on the different areas encompassed by Edgelet computing: computing architectures, types of communication, resiliency strategies and confidential computing techniques. To the best of our knowledge, none of the aforementioned topics considered the conjunction of fully decentralized architecture on users' devices and opportunistic networks while computing data-intensive algorithms and ensuring safety, liveness and security properties.

Crowd processing and Edge Computing. Crowd Computing [START_REF] Guo | Mobile Crowd Sensing and Computing: The Review of an Emerging Human-Powered Sensing Paradigm[END_REF], Crowdsourcing [START_REF] Estellés-Arolas | Towards an integrated crowdsourcing definition[END_REF], Crowd Sensing [START_REF] Ganti | Mobile crowdsensing: current state and future challenges[END_REF] are all based on the fact that individuals are increasingly connected and can thus participate in the enrichment of the digital sphere, from the sharing of captured data to the realization of individual micro-tasks. However, these approaches are still driven by centralized servers on which most of the processing is done. At the same time, the Edge paradigm has emerged with the goal of offloading services and computation close to data sources to make the cloud more responsive, scalable, and privacyfriendly [START_REF] Shi | Edge Computing: Vision and Challenges[END_REF], [START_REF] Xu | Edge Intelligence: Empowering Intelligence to the Edge of Network[END_REF]. Like Cross-Device Federated Learning [START_REF] Bonawitz | Towards Federated Learning at Scale: System Design[END_REF], these technologies operate in connected infrastructures where processing is performed in micro data centers (MDCs) [START_REF] Ferrer | Towards the Decentralised Cloud: Survey on Approaches and Challenges for Mobile, Ad hoc, and Edge Computing[END_REF] or small clouds (Cloudlets) [START_REF] Satyanarayanan | The Case for VM-Based Cloudlets in Mobile Computing[END_REF]. We differ from these architectures by still offering a reliable and privacy-preserving approach, but by relying exclusively on the edges to organize the processing, without the need for any infrastructure. An approach quite similar to ours is the system of composable services "Zoo" [START_REF] Zhao | Privacy-Preserving Machine Learning Based Data Analytics on Edge Devices[END_REF], but the authors focused on a framework for composing ML algorithms on connected edge devices, while we focused on defining a general paradigm in a disconnected environment.

Data processing in WSN. Wireless Sensor Networks were introduced to address monitoring and tracking needs [START_REF] Yick | Wireless sensor network survey[END_REF]. They are based on weakly connected sensors with low computational capabilities. Their primary purpose is to transmit the collected data to monitoring stations for analysis. The processing performed on these devices is then streamed queries [START_REF] O'keeffe | Frontier: Resilient Edge Processing for the Internet of Things[END_REF], [START_REF] Zeuch | The NebulaStream Platform for Data and Application Management in the Internet of Things[END_REF], the majority of which is executed at the end of the chain in a centralized manner. Most use-cases consider sensors for the environment or for animal tracking and do not raise privacy issues. Our approach is therefore quite different. We are closer to [START_REF] Paparrizos | VergeDB: A Database for IoT Analytics on Edge Devices[END_REF] which proposes a database system that leverages the capabilities of edge devices to run complex algorithms in a distributed manner to alleviate IoT data pressure. This decentralization of processing also allows us to reduce the exposure of personal data, a key concern in our approach.

Fault-tolerance strategies. The standard approach to ensure queries termination in distributed systems is replication [START_REF] Wiesmann | Understanding replication in databases and distributed systems[END_REF], [START_REF] Alwan | A Survey on Fault Tolerant Routing Techniques in Wireless Sensor Networks[END_REF]. Fault-tolerance issues significantly raise in complexity when asynchronous systems are considered, and the duality between safety and liveness still impacts the most recent works. For instance, [START_REF] O'keeffe | Frontier: Resilient Edge Processing for the Internet of Things[END_REF] proposes a redundancy system called Replicated Dataflow Graph (RDG) and suggests a "routing constraint" mechanism to coordinate data sources and replicas. But as the authors explain, this does not totally prevent the occurrence of routing inconsistencies, although infrequent in practice. Our backup-based solution, based on these same principles, faces the same difficulties. In contrast, the Overcollection approach circumvents the problems by replicating only the operators and not the data, which makes it easier to guarantee the validity property with the advantage of limiting the exposure of individual data.

Privacy-preserving computations. In order to ensure confidentiality of processing, our approach relies on TEEs present in edgelets, which promotes computational genericity and execution scaling. Existing distributed computing schemes based on fully homomorphic encryption [START_REF] Boneh | Private Database Queries Using Somewhat Homomorphic Encryption[END_REF] or secure Multi-Party Computation (MPC) cannot support any type of operation and scale to a large number of participants at the same time. For example, distributed database solutions, such as SMCQL [START_REF] Bater | SMCQL: Secure Query Processing for Private Data Networks[END_REF], are limited to a few dozen participants. Only specific operations can scale up for ad hoc constructions only (e.g., secure sum [START_REF] Sheikh | A Distributed k-Secure Sum Protocol for Secure Multi-Party Computations[END_REF]). Similarly, confidential distributed computing using gossip protocols [START_REF] Allard | Chiaroscuro: Transparency and Privacy for Massive Personal Time-Series Clustering[END_REF] and differential privacy techniques [START_REF] Dwork | Differential Privacy[END_REF] are limited to a small set of operations and produce approximate results. Moreover, "central" differential privacy relies on a trusted server, which contradicts our assumptions. The "local" differential privacy approach addresses this problem, but at the price of reducing further the utility of the computational results.

IX. CONCLUSIONS AND FUTURE CHALLENGES

In this paper, we introduce the Edgelet Computing paradigm, a new framework for executing complex and privacy-preserving distributed queries on personal devices at the extreme edge of the network. This paradigm builds on the recent convergence between Trusted Execution Environments and Opportunistic Networks and opens disruptive ways to handle personal data management problems. First, the paper precisely characterizes this paradigm through an ad-hoc threat model and properties guaranteeing the soundness of the executions. Second, it presents two alternative computing strategies satisfying these properties under this threat model. Third, it evaluates quantitatively and qualitatively these strategies and draws preliminary design rules to adapt computations to the Edgelet computing paradigm.

While our first experiments give confidence in the relevance and feasibility of the approach, we now aim at validating it through a field deployment of the solution. So far, 4,000 over 8,000 edgelets (i.e., patient's box) have been deployed in the DomYcile project [START_REF]DomYcile Project[END_REF] and we are working hard to make decentralized queries operational in the very near future. The ability to query cohorts of disconnected patients in few days and the unusual threat model provided by the Edgelet paradigm has been a strong incentive for the Yvelines district to adopt this technology.

However, this paper is still a preliminary study and several challenges remain to be tackled.

A first challenge is to explore the multiple optimization tradeoffs that exist between data exposure, query success rate and (local and global) resource consumption. New design rules should be introduced to accommodate existing algorithms to the Edgelet context in a way that facilitates the calibration between these optimization objectives.

A second challenge is to optimize the task-to-edgelet assignment. A large bunch of work has been devoted to the exploitation of social relationships and location-based homophily to improve network routing in OppNets [START_REF] Bellavista | Mobile social networking middleware: A survey[END_REF], [START_REF] Pelechrinis | Socio-spatial affiliation networks[END_REF]. The same kind of optimization could be envisioned to improve the query processing by assigning operators to the most connected devices (e.g. doctors, teachers) or to devices having the highest probability of meeting. This would lead to revisit the Crowd liability property, notably its randomness assumption to allow a (limited and controlled) degree of bias in favor of edgelets with good social relationships.

A third challenge is to accommodate long-lasting snapshots to support processes routinely used in data analysis. Such processes start with an initial set of exploration queries to capture data frequency distributions before running precise database queries, data mining or machine learning algorithms. Long-lasting snapshots could resort to specific indexing schemes to re-access sets of participating edgelets or materialized snapshot partitions kept (encrypted) on sets of edgelets, with various impacts on Resiliency, Validity and Crowd liability.

Other challenges are multi-disciplinary. Crowd liability has never been considered so far in the legislation protecting personal data. For example, the GDPR considers as liable a single so-called "data controller" entity, while liability is scattered among the crowd in our context. Jurists and computer scientists should remedy this shortfall by translating the Edgelet threat model in appropriate obligations for each party in the computation. It makes also sense in some contexts to track the participants in a processing (e.g., to provide them feedbacks or rewards or alert them from a leakage). This requires designing a provenance mechanism compatible with the new-defined properties. The acceptability of such mechanisms raises also new multidisciplinary challenges with social scientists.

Hence, we strongly believe that the Edgelet computing paradigm raises many exciting and promising challenges for the database and distributed systems community and that it can play a major role in the emergence of a new important class of applications related to the management of sensitive data.

X. REFERENCES

Fig. 1 .

 1 Fig. 1. Examples of Trusted Execution Environments. On the right, the Trusted Platform Module ensures the authenticity of the MCU2 Trusted Computing Base and keeps safely the encryption keys of the database (DB).

Fig. 2 .

 2 Fig. 2. Motivating example : Edgelet query in the DomYcile project

Fig. 3 .

 3 Fig. 3. Vertically & horizontally partitionned QEP

Fig. 4 .

 4 Fig. 4. Active and Passive Backups

  Fig. 6. Overcollected APriori/K-means QEPs

Fig. 7 .Fig. 8 .

 78 Fig. 7. Mall simulation with the ONE (reduced to 40 nodes for readability)

Fig. 9 .

 9 Fig. 9. Query deadlines (for Overcollection)

Fig. 10 . 12 ⍺

 1012 Fig. 10. Heartbeat execution quality

Table 1 :

 1 A taxonomy of computing strategies

		Type of computation	Snapshot definition	Validity	Crowd liability	Success Rate
		Horizontally	P	By
	Backup based resiliency	partitionable Vertically partitionable Others	partitionable Any P Any P	construction Consensus By construction	Activated backup exposed	Requires large query deadline
		Iterative				Unrealistic
	Over collection based resiliency	QEP reshapable Iterative reshapable Others	P partitionable P partitionable	By construction Ground validity Invalid	Over collected data exposed	Supports small query deadline