Frédérique Robin
email: frederique.robin@inria.fr

Bruno Sericola
email: bruno.sericola@inria.fr

Emmanuelle Anceaume
email: emmanuelle.anceaume@irisa.fr

Stochastic analysis of algorithms for collecting longitudinal data

This paper proposes and analyses the performance and the vulnerability to attacks of three algorithms for collecting longitudinal data in a large scale system. A monitoring device is in charge of continuously collecting measurements from end-devices. The communication graph is connected but not necessarily complete. For scalability reasons, at each collect, a single end-device is randomly selected among all the end-devices to send the content of its local buffer of data to the monitoring device. Once sent, the enddevice resets its buffer, and resumes its measurement process. Two of the three algorithms are randomized algorithms while the third one is deterministic. The difference between the randomized algorithms stems from the random choice policy: in the first algorithm, choice is uniform while in the second one the random choice is weighted by the current amount of measurements at end-devices. The third algorithm is deterministic. End-devices are successively chosen in a round robin way. We study the transient and stationary maximum load distribution at end-devices when collects are made using the first and third algorithm, and by providing bounds via a coupling argument when the second algorithm is used. While the third algorithm provides the best performance, it is highly vulnerable to attacks.

keywords Collecting longitudinal data, coupling technique, balls and urn models.

Introduction

The objective of this paper is to conduct a thorough analysis of three distributed algorithms (two rely on randomness and one is deterministic) dedicated to the collect of data through longitudinal measurements. A longitudinal study consists, through repeated observations over a long period of time, in collecting information of a cohort of individuals in order to observe the evolution of some measurable variables of interest. Longitudinal studies are highly relevant in epidemiological investigations (including the physiological changes in pregnancy described by [START_REF] Azimi | Missing data resilient decision-making for health care IoT through personalization: A case study on maternal health[END_REF][START_REF] Feig | Continuous glucose monitoring in pregnant women with type 1 diabetes (concept): a multicentre international randomised controlled trial[END_REF], or the follow-up of diabetics of a given age group studied by [START_REF] Lange | Copenhagen City Heart Study: longitudinal analysis of ventilatory capacity in diabetic and nondiabetic adults[END_REF]), the early childhood educational programs addressed by [START_REF] Moor | The Childrens Physical Environment Rating Scale (CPERS): Reliability and Validity for Assessing the Physical Environment of Early Childhood Educational Facilities[END_REF], but also to measure and compare various business and branding initiatives, product feedback, or customer satisfaction. In longitudinal surveys, measurements (e.g., temperature, CO 2 level, physiological indicators, etc.) are collected over time and are interpreted. Interpretation is conducted once outliers are detected and possibly corrected (see [START_REF] Azimi | Personalized Maternal Sleep Quality Assessment: An Objective IoT-based Longitudinal Study[END_REF]).

Internet-of-Things (IoT) technology, which is a growing network of interconnected objects, facilitates developments of such monitoring systems. As described by [START_REF] Dieng | A Study on IoT Solutions for Preventing Cattle Rustling in African Context[END_REF], in most of the IoT architectures, end-devices measure data and route them to one or more processing centers through a network. Hence, in this paper, we consider a processing center that we call the monitoring device, and K end-devices. End-devices do not necessarily know each other, while the monitoring device knows and communicates with each of the K end-devices.

The load balancing problem is close to the data collect problem since the former one consists in distributing tasks among multiple resources (see [START_REF] Azar | Balanced allocations (extended abstract)[END_REF] for more details). The main difference between both is that for longitudinal data collection, all end-devices perform their measurements at the same time when required by the monitoring device. In contrast, in the load balancing problem, only few tasks are allocated at the same time to end-devices and the processing time usually takes a non negligible amount of time. Note that the Age of Information, initially introduced by [START_REF] Kaul | Minimizing age of information in vehicular networks[END_REF], is a measure determining whether a set of information is up-to-date for decision making purpose in communication system.

Providing fine-grain measurements in the data collect problem may require to frequently query enddevices to cope with characteristics that fluctuate very quickly. However, when the cohort of end-devices under study is densely populated, i.e. K is in thousands or millions, very frequent collects of all the enddevices may give rise to vast amount of data that transit towards the monitoring device. This may rapidly overload this device, preventing it accordingly from correctly handling the input stream of information. To cope with such critical issue, the monitoring device periodically samples a small subset of end-devices to collect their measurements instead of collecting data from all the K end-devices. When an end-device is selected, it sends back the content of its buffer of measurements to the monitoring device, empties its buffer and resumes its measurement process. In the following, during each collect, a single end-device is queried.

There are several ways to select end-devices, and the objective of this paper is to study in depth three algorithms that perform this task. The two first algorithms rely on randomization to select end-devices, while the third one is deterministic. In the first algorithm, called Algorithm A in the following, choice is random and uniform. In the second one, called Algorithm B, the choice is random but weighted by the current amount of measurements at end-devices. Finally, in the third algorithm, called Algorithm C, the choice is deterministic and follows a round-robin strategy: each end-device is successively chosen.

In this paper we are interested in analysing the effect of sampling on the size of the local buffer at each end-device at the end of each collect. Indeed, since during a collect a single end-device is queried for sending back its buffer content at the monitoring device, buffers at the other K -1 end-devices continue to grow. To evaluate the performance of these algorithms we study the transient and stationary maximum buffer size distribution at end-devices at the end of the n-th collect, for n ≥ 1. We show that with Algorithm A, the limiting distribution of the buffer size at any end-device k is geometric with parameter 1/K, the stationary distribution of the maximal buffer size of the K end-devices is upper bounded by ≥ K with probability K!S( , K)/K where S( , K) are the Stirling numbers of the second kind, and the stationary average maximal buffer size is Θ(K ln K). For Algorithm B, the impact of the random weighted sampling policy makes the moments of the buffer size at any end-devices not easy to obtain analytically. Hence by using a coupling argument, we provide bounds on the maximal and total buffer size. These bounds show that Algorithm B performs better than Algorithm A. Finally, by an easy argument, we show that Algorithm C provides better performance than Algorithm B, and thus better than Algorithm A.

Since we are considering large scale distributed architectures, the presence of malicious entities that devise adversarial strategies to prevent the correct functioning of algorithms is unavoidable (see [START_REF] Michael | Appraising two decades of distributed computing theory research[END_REF]). In this work we consider an omniscient entity, called the adversary, that has full knowledge of the code run by the different devices, and in particular the one of the monitoring device. We focus on Deny-of-Services (DoS) attacks. A Denial of Service attack tries to take down an Internet resource by flooding this resource with more requests than it is capable of handling. In this work, we assume that the monitoring device includes advanced intrusion prevention and threat management systems, which combine firewalls, VPN, anti-spam, content filtering, load balancing, and other layers of DoS defense techniques. Together they enable constant and consistent network protection to prevent a DoS attack from happening. This includes everything from identifying possible traffic inconsistencies with the highest level of precision in blocking the attack. On the other hand, given the characteristics of end-devices, theses devices are not protected by such mechanisms, and thus are vulnerable to DoS attacks. One way for the adversary to target some victim is through sniffing.

Sniffing corresponds to theft or interception of data by capturing the network traffic using a sniffer (an application aimed at capturing network packets). When data is transmitted across networks, if the data packets are not encrypted, the data within the network packet can be read using a sniffer. By a simple argument, we will show that Algorithm C cannot protect end-devices from DoS attack, while randomization makes Algorithm A less vulnerable than Algorithm B.

The remaining of the paper is organized as follows. Section 2 describes the model of the system in terms of participating entities, and communication capability, as well as the main principles of the three collect algorithms. Section 3 describes the dynamic of the stochastic (resp. deterministic) process as an urn and balls model. Sections 4, 5, and 6 provide an in depth analysis of the algorithms. The trade-off between their performance and their vulnerability to deny-of-service attacks launched by an omniscient adversary is discussed in Section 7. Finally, Section 8 concludes.

Assumptions on the system and data collect algorithm

We consider a set of K ≥ 1 end-devices, 1, 2, . . . K with both measurement and communication capabilities. These K end-devices are monitored by another device, called monitoring device, whose role is to periodically collect measurements from these end-devices. The time needed for each end-device to make a measurement is negligible with respect to the collect periodicity. Those K +1 devices are interconnected through a connected but not necessarily complete communication network.

The monitoring device communicates with the end-devices by invoking a reliable broadcast primitive. Such a primitive guarantees that if the monitoring device broadcasts some message then all the end-devices will eventually receive this message. The end-devices communicate with the monitoring device by invoking a reliable send primitive. This primitive ensures that the sent message is eventually received by the monitoring device. Note that from an implementation point of view, since the communication graph is not necessarily complete, messages may need to be forwarded by intermediate end-devices before being received by the monitoring device.

All the devices have access to public key cryptography (PKC). PKC employs two keys, the private and public keys, that are mathematically related although knowledge of one key does not allow someone to easily determine the other key. Public keys (pk) are publicly known, while private keys (sk) are kept private by their owner. One key is used to encrypt the plaintext into something that appears to be random and meaningless (the ciphertext) and the other key is used to decrypt the ciphertext back to the plaintext. Let sk k and pk k be respectively the secret and public keys of device k. We rely on encryption to keep some pieces of information secret during transmission between the monitoring device and end-devices (this will be detailed later). In the following, encryption of message m is done with the public key of the recipient k of data m and is denoted by enc pk k (m), while decryption at k is done with k's secret key and is denoted by dec sk k (m).

Main principles of the collect algorithms

We propose three algorithms to collect measurements from a set of K ≥ 1 end-devices. Only new measurements are collected, that is, once an end-device k has sent its buffer of measurements to the monitoring device, then k resets its buffer, and continues its data measurement process. So the next time end-device k will be queried by the monitoring device, k will (only) provide measurements it has performed since the last time it was queried.

Algorithm A

Algorithm A consists of a potentially infinite sequence of collects. Each collect is triggered by the monitoring device. At the n-th collect, n ≥ 1, the monitoring device draws at random and uniformly an integer k in {1, . . . , K}. Integer k represents the end-device that will provide its buffer of measurements to the monitoring device during this n-th collect. To prevent the adversary from discovering that end-device k is the one whose data will be collected, the monitoring device encrypts k's identifier using k's public key, i.e enc pk k (k), and broadcasts a collect query parameterized with enc pk k (k) to all the end-devices. Upon receipt of this nth collect query, all the K end-devices perform d new data measurements and store them in their buffer. However, prior to do that, end-device k that successively discovered that it is the one that must send its buffer of measurements to the monitoring device, i.e., dec sk k (enc pk k (k))= k, sends back its buffer to the monitoring device, and locally resets its. Thus at the end of collect n, the buffer of end-device k contains exactly d data, while for all the other end-devices, the size of their buffer is equal to the one after collect n -1 plus d. Without loss of generality, we assume in the following that d = 1.

Algorithm B

Algorithm B differs from Algorithm A only in the way the monitoring device randomly chooses the end-device from which it collects measurements. Specifically, at the n-th collect, n ≥ 1, the monitoring device draws at random an integer k in {1, . . . , K}, with a probability proportional to the size of the buffer of end-device k. Thus an end-device whose buffer of measurements has not been collected for a long time will be more likely to be chosen during this collect.

Algorithm C

Algorithm C queries end-devices according to the round-robin schema: at the n-th collect, n ≥ 1, the chosen end-device is end-device k = n mod (K) + K {n mod (K)=0} , where K {E} is the function equal to K if E is true and 0 otherwise. Thus each end-device is chosen in circular order without priority, starting by end-device k = 1 when n = 1.

Modeling Algorithms A, B, and C

We model those three algorithms to determine, at any collect n ≥ 1, the amount of data measurements at any end-device k, i.e., the size of its buffer, denoted by buffer k, and the total amount of measurements over all the K buffers.

Modeling Algorithm A

Let {A(n), n ≥ 0} be a discrete time stochastic process, with A(n) = (A 1 (n), . . . , A K (n)), where A k (n) represents the total amount of data measurements in the buffer of end-device k at the n-th collect. The dynamic of this stochastic process can be seen as an urn and balls problem. There are K urns, each one modeling the local buffer of end-devices. Balls represent the number of measurements in the local buffer of each end-device, i.e., one ball represents one measurement (recall that d = 1). We suppose that initially, i.e., at n = 0, all the local buffers contain one data measurement and the collect process start at n ≥ 1. Thus at n = 0 there is one ball in each of the K urns.

At the n-th collect, end-device k is chosen randomly and uniformly, i.e. with probability 1/K. All the balls of urn k are withdrawn from it, and one ball is added to each of the K urns (see Section 2.2). For n ≥ 1, A k (n) is equal to the number of balls in urn k at collect n (i.e., is equal to the amount of data measurements in k's buffer at collect n).

We denote by S A (n) the total number of balls in the K urns at collect n, which thus corresponds to the total amount of measurements over all the K buffers at the end of the n-th collect. This quantity is defined by

S A (n) = K k=1 A k (n). (1)
Let (U n ) n≥0 be a sequence of random variables independent and identically uniformly distributed on interval [0, 1]. This sequence is used in Relation (2) to determine the urn which is selected at each instant. We suppose that, for all k = 1, . . . , K, random variables A k (n) and U n are independent. For all n ≥ 0, we define the sequence of random variables J A (U n ) by

J A (U n ) = K k=1 k1 {(k-1)/K≤Un<k/K} , (2)
which gives the urn selected by the monitoring device, using Algorithm A, to collect its balls at time n. The evolution of process {A(n), n ≥ 0} is thus given, for all k = 1, . . . , K, by A k (0) = 1 and, for all n ≥ 1, by

A k (n) = A k (n -1) + 1 if J A (U n-1 ) = k 1 if J A (U n-1 ) = k. (3)
It is easily checked from this definition that for each n ≥ 1, there exists a unique urn u such that

A u (n) = 1 and A k (n) ≥ 2, for k = 1, . . . , K, with k = u.
To analyse the maximum amount of uncollected measurements at any end-device k, we introduce the process {A (n), n ≥ 0}, where

A (n) = (A 1 (n), . . . , A K (n))
, which is obtained by reordering the entries of vector A(n) in the ascending order, that is with

A 1 (n) = 1 < A 2 (n) ≤ • • • ≤ A K (n).
More precisely, for all k = 1, . . . , K, we define the A k (n) by A k (0) = 1 and, for n ≥ 1, by A 1 (n) = 1 and for k = 2, . . . , n, by

A k (n) = A k-1 (n -1) + 1 if J A (U n-1 ) ≥ k A k (n -1) + 1 if J A (U n-1 ) ≤ k -1.
Note that for the definition of process {A (n), n ≥ 0}, we keep the notation J A (U n ) since it does not depend on the number of balls in each urn but only on urn k. Note in particular that S A (n) D = S A (n), which means that S A (n) and S A (n) have the same distribution. This relation can also be written as

A k (n) = A k-1 (n -1)1 {J A (Un-1)≥k} + A k (n -1)1 {J A (Un-1)≤k-1} + 1. (4)

Modeling Algorithm B

Let {B(n), n ≥ 0} be a discrete time stochastic process, with B(n) = (B 1 (n), . . . , B K (n)), where B k (n) represents the total amount of uncollected measurements in the buffer of end-device k at the n-th collect.

Similarly to Algorithm A, the dynamic of the stochastic process {B(n), n ≥ 0} can be represented by an urn and balls model. There are K urns, each one modeling the local buffer of end-devices. Balls represent the number of measurements in the local buffer of each end-device. Similarly to Algorithm A, we suppose that initially, i.e., at n = 0, all the local buffers contain d data measurements and the collect process start at n ≥ 1. Recall that wlog we assume that d = 1, thus at n = 0 there is one ball in each of the K urns. We denote by S B (n) the total number of balls in the K urns at collect n, which corresponds to the total number of uncollected measurements at the n-th collect. This quantity is defined by

S B (n) = K k=1 B k (n). ( 5
)
At the n-th collect, a node k is chosen with probability B k (n)/S B (n), and all the balls of urn k are withdrawn from that urn, and one ball is added in each of the K urns. For n ≥ 1, B k (n) is equal to the number of balls in urn k at collect n.

Let (V n ) n≥0 be a sequence of random variables independent and identically uniformly distributed on interval [0, 1]. This sequence is used in Relation [START_REF] Kaul | Minimizing age of information in vehicular networks[END_REF] to determine the urn which is selected at each instant. We suppose that, for all k = 1, . . . , K, random variables B k (n) and V n are independent. The evolution of process B is thus given by B(0) = A(0) = (1, . . . , 1) and, for n ≥ 1 and k = 1, . . . , K, by

B k (n) = B k (n -1) + 1 if J B (V n-1 ) = k 1 if J B (V n-1 ) = k, (6)
where J B (V n ) is defined, for all n ≥ 0, by

J B (V n ) = K k=1 k1 {s B (n,k-1)≤Vn<s B (n,k)} , with s B (n, k) = 1 S B (n) k j=1 B j (n). (7)
Note that, as for Algorithm A, J B (V n ) is the urn selected by the monitoring device, using Algorithm B, to collect its balls at time n. As we did for stochastic process {A(n), n ≥ 0}, we reorder the entries of random vector (B 1 (n), . . . , B K (n)) in the ascending order. Thus, we introduce the process {B (n), n ≥ 0}, where

B (n) = (B 1 (n), . . . , B K (n)), with B k (0) = 1 and, for n ≥ 1, B 1 (n) = 1 < B 2 (n) ≤ • • • ≤ B K (n) is defined by B 1 (n) = 1 and B k (n) = B k-1 (n -1) + 1 for k = 2, . . . , J B (V n-1 ) B k (n -1) + 1 for k = J B (V n-1 ) + 1, . . . , K. (8)
In the same way the distribution of the total number of balls S B (n) at collect n remains unchanged, that is

S B (n) D = S B (n).

Modeling Algorithm C

Let {C(n), n ≥ 0} be a discrete time deterministic process, with

C(n) = (C 1 (n), . . . , C K (n))
, where C k (n) represents the total amount of uncollected measurements in the buffer of end-device k at the n-th collect. Since Algorithm C queries end-devices according to the round-robin schema, at the n-th collect, n ≥ 1, the chosen end-device (or the chosen urn) is end-device (or urn) k = n mod (K) + K {n mod (K)=0} . For n ≥ 1, C k (n) is equal to the number of balls in urn k at collect n.

The sequence C(n) is thus given by C(0) = (1, . . . , 1), for n = 1, . . . K -1 by

C k (n) =        n if k = 1 C k-1 (n -1) if k = 2, . . . , n -1 1 if k = n C k-1 (n -1) + 1 if k = n + 1, . . . , K,
and, for all n ≥ K and k = 1, . . . , K, by

C k (n) = n mod (K) + K {n mod (K)=0} if k = 1 C k-1 (n -1) if k = 2, . . . , n -1.
For instance, for K = 5, we obtain

C(0) = (1, 1, 1, 1, 1), C (5)
= (5, 4, 3, 2, 1), C(10) = (5, 4, 3, 2, 1),

• • • C(1) = (1, 2, 2, 2, 2), C(6) = (1, 5, 4, 3, 2), C(11) = (1, 5, 4, 3, 2), • • • C(2) = (2, 1, 3, 3, 3), C(7) = (2, 1, 5, 4, 3), C(12) = (2, 1, 5, 4, 3), • • • C(3) = (3, 2, 1, 4, 4), C(8) = (3, 2, 1, 5, 4), C(13) = (3, 2, 1, 5, 4), • • • C(4) = (4, 3, 2, 1, 5), C(9) = (4, 3, 2, 1, 5), C(14) = (4, 3, 2, 1, 5), • • •
We denote by S C (n) the total number of balls in the K urns at collect n, which corresponds to the total number of uncollected measurements at the n-th collect. This quantity is defined by

S C (n) = K k=1 C k (n). (9)
As we did for stochastic processes {A(n), n ≥ 0} and {B(n), n ≥ 0}, we reorder the entries of random vector (C 1 (n), . . . , C K (n)) in the ascending order. Thus, we introduce the process {C (n), n ≥ 0}, where C (n) = (C 1 (n), . . . , C K (n)), with C (0) = (1, . . . , 1) and, for n ≥ 1,

C 1 (n) = 1 and C k (n) = C k (n -1) + 1, for k = 2, . . . , K -2.
For K = 5, we easily get C (0) = (1, 1, 1, 1, 1), C (1) = (1, 2, 2, 2, 2), C (2) = (1, 2, 3, 3, 3), C (3) = (1, 2, 3, 4, 4) and C (n) = (1, 2, 3, 4, 5), for all n ≥ 4. In the same way the total number of balls S C (n) at collect n remains unchanged, that is S C (n) = S C (n). This quantity is easily obtained by

S C (n) = S C (n) = (n + 1) K - n 2 1 {0≤n≤K-2} + K(K + 1) 2 1 {n≥K-1} . ( 10
)

Analysis of Algorithm A

We study in this section the stochastic processes {A(n), n ≥ 0} and {A (n), n ≥ 0}.

Distribution of A k (n)

We start by analyzing the amount of uncollected measurements at any end-device k at any collect n ≥ 1.

Theorem 4.1 For all n ≥ 0, k = 1, . . . , K and = 1, . . . , n + 1, we have

P{A k (n) = } = 1 - 1 K -1 1 K 1 { ≤n} + 1 { =n+1} .
Proof. Proof. From the definition of A k (n) in Relation (3), we have, for all k = 1, . . . , K, A k (0) = 1 and for all n ≥ 1,

A k (n) = (A k (n -1) + 1)1 {J A (Un-1) =k} + 1 {J A (Un-1)=k} = A k (n -1)1 {J A (Un-1) =k} + 1.
Note that this relation implies that A k (n) ≤ A k (n -1) + 1, which means that the random variable A k (n) takes its values in the set {1, . . . , n + 1}. By conditioning on A k (n -1) and using the fact that A k (n -1) and U n-1 are independent, we obtain, for all , j ≥ 1,

P{A k (n) = | A k (n -1) = j} = P{A k (n -1)1 {J A (Un-1) =k} + 1 = | A k (n -1) = j} = P{1 {J A (Un-1) =k} = ( -1)/j | A k (n -1) = j} = P{1 {J A (Un-1) =k} = ( -1)/j} =    P{J A (U n-1 ) = k} if = 1 P{J A (U n-1 ) = k} if ≥ 2 and j = -1 0 otherwise. =    1/K if = 1 1 -1/K if j = -1 and ≥ 2 0 otherwise. Unconditioning, we obtain P{A k (n) = 1} = 1/K and, for ≥ 2, P{A k (n) = } = 1 - 1 K P{A k (n -1) = -1}.
This simple recurrence relation leads to

P{A k (n) = } =        1 K 1 - 1 K -1 if 1 ≤ ≤ n 1 - 1 K n if = n + 1,
which completes the proof.

Observe that, at each collect instant n, the amount of measurements A k (n), collected at any device k has the same distribution for k = 1, . . . , K. This is due to the fact that the U n are uniformly distributed. Note that A 1 (n), . . . , A K (n) are not independent. We get from Theorem 4.1 that, as expected, the uncollected measurements of any end-device k follows a kind of geometric law with parameter 1/K. Corollary 4.2 highlights that the expected amount of uncollected measurements in any buffer at collect n is not exactly K but increases towards K when the number n of collects goes to infinity. It also shows that the expected total amount of uncollected measurements at collect n, E(S A (n)), converges increasingly to K 2 when the number of collects n goes to infinity. Corollary 4.2 For all k = 1, . . . , K, we have

E(A k (n)) = K 1 -1 - 1 K n+1 and E(S A (n)) = K 2 1 -1 - 1 K n+1 . Moreover, lim n-→∞ E(A k (n)) = K and lim n-→∞ E(S A (n)) = K 2 .
Proof. Proof. From Theorem 4.1, we have, for all = 0, . . . , n,

P{A k (n) > } = n+1 j= +1 P{A k (n) = j} = 1 K n j= +1 1 - 1 K j-1 + 1 - 1 K n = 1 - 1 K .
We thus get

E(A k (n)) = n =0 P{A k (n) > } = n =0 1 - 1 K = K 1 -1 - 1 K n+1 .
The second equality follows immediately from Relation (1) and the limits are trivial.

lim n-→∞ P{A k (n) = } = 1 - 1 K -1 1 K .
Proof. Proof. The proof is straightforward from Theorem 4.1 and Corollary 4.2.

Distribution of A k (n)

In this section, we study the maximum amount of uncollected measurements distribution of end-devices, that is the distribution of

A K (n). Recall that A 1 (n) = 1 for all n ≥ 0 and that A 2 (n) ≤ . . . ≤ A K (n), with A k (0) = 1 for all k = 1, . . . , K and 2 ≤ A k (n) ≤ n + 1 for all n ≥ 1. The distribution of A 2 (n) is given in Theorem 4.4.
Theorem 4.4 A 2 (0) = 1 and for all n ≥ 1 and = 2, . . . , n + 1, we have

P{A 2 (n) = } = 1 K -2 1 - 1 K 1 { ≤n} + 1 { =n+1} .
Proof. Proof. By definition of A k (n), see Relation (4), we have A 2 (0) = 1 and for all n ≥ 1,

A 2 (n) = 1 {J A (Un-1)≥2} + A 2 (n -1)1 {J A (Un-1)=1} + 1.
By conditioning on A 2 (n -1) and using the fact that A k (n -1) and U n-1 are independent, we obtain, for all ≥ 1 and j ≥ 2,

P{A 2 (n) = | A 2 (n -1) = j} = P{1 {J A (Un-1)≥2} + j1 {J A (Un-1)=1} + 1 = } =    P{J A (U n-1 ) ≥ 2} if = 2 P{J A (U n-1 ) = 1} if ≥ 3 and j = -1 0 otherwise. =    1 -1/K if = 2 1/K if ≥ 3 and j = -1 0 otherwise. Unconditioning, we obtain P{A 2 (n) = 2} = 1 -1/K and, for ≥ 3, P{A 2 (n) = } = 1 K P{A 2 (n -1) = -1}.
This simple recurrence relation leads, for = 2, . . . , n + 1, to

P{A 2 (n) = } = 1 K -2 1 - 1 K 1 { ≤n} + 1 { =n+1} ,
which completes the proof.

The next result gives the expected value of A 2 (n).

Corollary 4.5 For all n ≥ 0, we have

E(A 2 (n)) = 1 + K (1 -(1/K) n ) K -1 .
Proof. Proof. The relation is true for n = 0. For n ≥ 1, From Theorem 4.4, we have, for all = 1, . . . , n,

P{A 2 (n) > } = n+1 j= +1 P{A 2 (n) = j} = 1 - 1 K n j= +1 1 K j-2 + 1 K n-1 = 1 K -1
.

We thus get

E(A 2 (n)) = n =0 P{A 2 (n) > } = 1 + n =1 1 K -1 = 1 + K (1 -(1/K) n ) K -1 ,
which completes the proof.

The distribution of A k (n) for all k is given in Theorem 4.6.

Theorem 4.6 For all k ≥ 2, we have A k (1) = 2. For all k ≥ 3, n ≥ 2 and = 3, . . . , n + 1, we have

P{A k (n) = } = 1 - k -1 K P{A k-1 (n -1) = -1} + k -1 K P{A k (n -1) = -1}.
Proof. Proof. By definition of A k (n) given in Relation (4), we have A k (0) = 1, for all k ≥ 1, anf for all k ≥ 2 and n ≥ 1,

A k (n) = A k-1 (n -1)1 {J A (Un-1)≥k} + A k (n -1)1 {J A (Un-1)≤k-1} + 1. Since A k-1 (0) = 1 and A k (0) = 1, we obtain A k (1) = 2.
Now, for k ≥ 3, by conditioning on A k-1 (n -1) and A k (n -1) and using the fact that A k (n -1) and U n-1 are independent, we obtain, for all n ≥ 2 and , i, j ≥ 2,

P{A k (n) = | A k-1 (n -1) = i, A k (n -1) = j} = P{i1 {J A (Un-1)≥k} + j1 {J A (Un-1)≤k-1} = -1} =        0 if = 2 1 -(k -1)/K if ≥ 3 and i = -1 (k -1)/K if ≥ 3 and j = -1 0 otherwise.
Unconditioning, we obtain for all n ≥ 2 and ≥ 3,

P{A k (n) = } = 1 - k -1 K P{A k-1 (n -1) = -1} + k -1 K P{A k (n -1) = -1}.
which completes the proof.

The expected value of A k (n) is obtained by recurrence in the following result.

Corollary 4.7 For all n ≥ 0, we have E(A 1 (n)) = 1. For all k = 1, . . . , K, we have E(A k (0)) = 1. For all n ≥ 1 and k = 2, . . . , K, we have

E(A k (n)) = 1 - k -1 K E(A k-1 (n -1)) + k -1 K E(A k (n -1)) + 1.
Proof. Proof. Let n ≥ 1 and k ≥ 2. By taking the expectation in Relation (4) and using the fact that A k (n -1) and U n-1 are independent, we obtain

E(A k (n)) = E(A k-1 (n -1))P{J A (U n-1 ) ≥ k} + E(A k (n -1))P{J A (U n-1 ) ≤ k -1} + 1 = 1 - k -1 K E(A k-1 (n -1)) + k -1 K E(A k (n -1)) + 1,
which completes the proof.

Using Theorem 4.6, we compute in Figure 1, P{A K (n) ≥ } for different values of K and n.

We analyze in the following theorem the limiting behavior of the distribution of the A k (n). We denote by π k ( ), for all k = 1, . . . , K, this stationnary distribution, that is

π k ( ) = lim n-→∞ P{A k (n) = }.
The existence of this limit follows by recurrence as shown in Theorem 4.8. Theorem 4.8 We have π 1 ( ) = 1 { =1} and, for k = 2, . . . , K,

π k ( ) = k-1 r=1 1 - r K k-1 r=1 a r (k) r K -k 1 { ≥k} , (11)
where the coefficients a r (k) are given by a 1 (2) = 1 and, for k ≥ 3, Proof. Proof. For k = 1, the result is trivial since A 1 (n) = 1, for all n ≥ 0. For k = 2, by taking the limit when n tends to infinity in Theorem 4.4, we easily get

           a r (k) = - r k -r -1 a r (k -1) for r = 1, . . . , k -2 a k-1 (k) = 1 - k-2 r=1 a r (k).
π 2 ( ) = 1 - 1 K 1 K -2 1 { ≥2} , (12)
which is exactly Relation [START_REF] Moor | The Childrens Physical Environment Rating Scale (CPERS): Reliability and Validity for Assessing the Physical Environment of Early Childhood Educational Facilities[END_REF] when k = 2.

For k ≥ 3, we take the limit when n tends to infinity in Theorem 4.6. We obtain

π k ( ) = k -1 K π k ( -1) + 1 - k -1 K π k-1 ( -1). ( 13
)
It is easily checked by recurrence, using Relation [START_REF] Peres | The (1 + β)-Choice Process and Weighted Balls-into-Bins[END_REF], that π k ( ) = 0, for ≤ k -1. Using this property in Relation ( 13) with = k, we get

π k (k) = k -1 K π k (k -1) + 1 - k -1 K π k-1 (k -1) = 1 - k -1 K π k-1 (k -1),
which leads to

π k (k) = 1 - k -1 K • • • 1 - 2 K π 2 (2).
Since, from Relation (12), we have π 2 (2) = 1 -1/K, it follows that

π k (k) = k-1 r=1 1 - r K .
We now verify that the right hand side of Relation [START_REF] Moor | The Childrens Physical Environment Rating Scale (CPERS): Reliability and Validity for Assessing the Physical Environment of Early Childhood Educational Facilities[END_REF] satisfies Relation [START_REF] Quaintance | Combinatorial Identities for Stirling Numbers[END_REF]. In order to do that, we denote by p k ( ) the right-hand side of [START_REF] Moor | The Childrens Physical Environment Rating Scale (CPERS): Reliability and Validity for Assessing the Physical Environment of Early Childhood Educational Facilities[END_REF], that is

p k ( ) = k-1 r=1 1 - r K k-1 r=1 a r (k) r K -k 1 { ≥k} ,
where a 1 (2) = 1 and, for k ≥ 3,

a r (k) = - r k -r -1 a r (k -1) for r = 1, . . . , k -2 (14) a k-1 (k) = 1 - k-2 r=1 a r (k), (15)
For = k, we have, using Relation (15),

p k (k) = k-1 r=1 1 - r K k-1 r=1 a r (k) = k-1 r=1 1 - r K = π k (k).
For ≥ k + 1, we have

k -1 K p k ( -1) = π k (k) k-1 r=1 a r (k) k -1 K r K -1-k = π k (k) k-1 r=1 a r (k) k -1 r r K -k = π k (k) k-2 r=1 a r (k) k -1 r r K -k + a k-1 (k) k -1 K -k .
In the same way, we have, for

≥ k + 1, 1 - k -1 K p k-1 ( -1) = π k (k) k-2 r=1 a r (k -1) r K -k
.

By adding these two expressions, we obtain

k -1 K p k ( -1) + 1 - k -1 K p k-1 ( -1) = π k (k) k-2 r=1 a r (k) k -1 r + a r (k -1) r K -k + a k-1 (k) k -1 K -k
.

Observing that Relation (14) can be written, for r = 1, . . . , k -2, as

a r (k) = a r (k) k -1 r + a r (k -1), we get k -1 K p k ( -1) + 1 - k -1 K p k-1 ( -1) = p k ( ), which proves that π k ( ) = p k ( ).
Explicit expressions of coefficients a r (k) and properties of these coefficients are given in the following corollary. Let us first recall that the Stirling numbers of the second kind are defined by S( , 1) = S( , ) = 1 for ≥ 1 and by S( , k) = kS( -1, k) + S( -1, k -1), for ≥ k.

Corollary 4.9 shows that the distribution of all the order statistics of the A k (n) are easily obtained using the Stirling numbers of the second kind. Corollary 4.9 For all k = 2, . . . , K and r = 1, . . . , k -1, we have

a r (k) = (-1) k-1-r r k-1 r!(k -1 -r)! . (16)
For all k = 2, . . . , K and ≥ k, we have

lim n-→∞ P{A k (n) = } = π k ( ) = (K -1)!S( -1, k -1) (K -k)!K -1 , (17)
and

lim n-→∞ P{A k (n) ≥ } = ∞ m= π k (m) = (K -1)! (K -k)!K -2 k-1 r=1 (-1) k-1-r r -1 r!(k -1 -r)!(K -r) . (18)
Proof. Proof. It is easily checked that Relation (16) satisfies a 1 (2) = 1 and the recursive definition of the a r (k) given in Theorem 4.8, for k ≥ 3 and r = 1, . . . , k -2. It remains to study the case r = k -1. In that case, using the Euler's finite difference theorem (see for instance Relation (6.19) of [START_REF] Quaintance | Combinatorial Identities for Stirling Numbers[END_REF]), which tells us that

k-1 r=1 (-1) k-1-r r k-1 r!(k -1 -r)! = 1, for k ≥ 2 we get a k-1 (k) = 1 - k-2 r=1 a r (k) = (k -1) k-1 (k -1)! ,
which completes the proof of Relation (16).

In order to prove Relation (17), observe first that

k-1 r=1 1 - r K = k-1 r=1 K -r K = (K -1)! (K -k)!K k-1 .
Using this relation and the expression of the a r (k) obtained in Relation (16) that we insert in Relation [START_REF] Moor | The Childrens Physical Environment Rating Scale (CPERS): Reliability and Validity for Assessing the Physical Environment of Early Childhood Educational Facilities[END_REF], we obtain, for all k = 2, . . . , K and ≥ k,

π k ( ) = (K -1)! (K -k)!K k-1 k-1 r=1 (-1) k-1-r r k-1 r!(k -1 -r)! r K -k = (K -1)! (K -k)!K -1 k-1 r=1 (-1) k-1-r r!(k -1 -r)! r -1 . (19)
The Euler's finite difference theorem (see for instance Relation (6.20) of [START_REF] Quaintance | Combinatorial Identities for Stirling Numbers[END_REF]) also tells us that for ≥ k, we have

k-1 r=1 (-1) k-1-r r -1 r!(k -1 -r)! = S( -1, k -1), (20)
where S( , k) are the Stirling numbers of the second kind defined above. Using this relation, we get

π k ( ) = (K -1)!S( -1, k -1) (K -k)!K -1 .
To prove Relation (18), we use Relation (19) which leads to

∞ m= π k (m) = (K -1)! (K -k)! k-1 r=1 (-1) k-1-r r!(k -1 -r)! ∞ m= r K m-1 = (K -1)! (K -k)! k-1 r=1 (-1) k-1-r r!(k -1 -r)! r K -1 K K -r = (K -1)! (K -k)!K -2 k-1 r=1 (-1) k-1-r r -1 r!(k -1 -r)!(K -r) ,
which completes the proof.

Theorem 4.10 The stationary distribution of the maximal amount of uncollected data over the K enddevices is upper bounded by ≥ K with probability K!S( , K)/K . More precisely, we have

lim n-→∞ P{A K (n) ≤ } = m=K π K (m) = K!S( , K) K ,
Proof. Proof. By definition of the A k (n), the maximal amount of uncollected data is obtained by end-device number K. Thus, applying Relation (18) of Corollary 4.9 with k = K and + 1 instead of , we obtain for all ≥ K,

∞ m= +1 π K (m) = (K -1)! K -1 K-1 r=1 (-1) K-1-r r r!(K -r)! = (K -1)! K -1 - K r=1 (-1) K-r r r!(K -r)! + K K! .
Using Relation (20), we get

∞ m= +1
π K (m) = 1 -(K -1)!S( , K) K -1 = 1 -K!S( , K) K , which completes the proof.

Figure 2 illustrates, for Algorithm A, the stationary maximal amount of uncollected data over the K end-devices (see Theorem 4.10). Specifically, let T ( , K) be defined, for all ≥ K, by T ( , K) = K!S( , K) K , and let (K, ε) be the smallest value of for which T ( , K) is greater than or equal to 1 -ε, for ε ∈ (0, 1), that is (K, ε) = inf{j | T (j, K) ≥ 1 -ε}.

Observe that T ( , K) can be computed, for ≥ K, as

T ( , K) = T ( -1, K) + 1 - 1 K -1 T ( -1, K -1)
with T ( , 2) = 1 -(1/2) -1 , for ≥ 2. For instance, Figure 2 indicates that when K = 3 and ε = 10 -3 , the amount of accumulated measurements at any end-device does not exceed 11 with probability greater than or equal to 0.999. Table 1 gives the values of (K, ε = 10 -3 ) for some large values of K.

To complete our analysis, we give in Corollary 4.11 the expected value of the stationary maximal amount of measurements collected at any end-device. Proof. Proof. In order to simplify the writing we introduce the notation x k = lim n-→∞ E(A k (n)). By taking the limit when n tends to infinity in Corollary 4.7, we get x 1 = 1 and, for all k = 2, . . . , K,

x k = 1 - k -1 K x k-1 + k -1 K x k + 1,
which can be written as x k = x k-1 + K, that is

x k = K K =K-k+1 1 ,
which completes the proof.

Taking k = K, we get from Corollary 4.11 that the average of the maximum amount of uncollected measurement A K (n) converges to K K =1 1/ when n goes to infinity. This indicates that the stationary average maximum uncollected measurements is Θ (K ln K).

Corollary 4 .

 4 [START_REF] Azimi | Missing data resilient decision-making for health care IoT through personalization: A case study on maternal health[END_REF] shows that the limiting distribution of the uncollected measurements of end-device k is geometric with parameter 1/K.

Corollary 4 . 3

 43 For all k = 1, . . . , K and ≥ 1, we have

Figure 1 :

 1 Figure 1: Using Theorem 4.6, we compute P{A K (n) ≥ } for different values of K (K = 100, 200 and 300) and at different collects n (n = 5K, 8K and 10K). The plain lines represent P{A 5K (n) ≥ }, the dotted lines represent P{A 8K (n) ≥ } and the dashed lines represent P{A 10K (n) ≥ }.

Figure 2 :

 2 Figure 2: Illustration of the stationary maximal amount of uncollected data over the K end-devices. For K = 100, 150 and 200 and for each = K, . . . , 2, 800, we compute T ( , K) and thresholds (K, ε) for ε = 10 -3 (i.e., (100K, ε) = 1171, (150K, ε) = 1808, and (200K, ε) = 2462). The purple line represents 1-ε = 0.999. K 250 500 750 1,000 10,000 (K, 10 -3 ) 3,101 6,555 10,139 13,809 161,168

Table 1 :

 1 Thresholds (K, ε) of the stationary maximal amount of measurements collected at any end-device for large values of K when ε = 10 -3 . Corollary 4.11 For all k = 1, . . . , K, we havelim n-→∞ E(A k (n)) = K K =K-k+11 .

Analysis of Algorithm B

This section is devoted to the study of the impact of the "random weighted sampling policy" on the distribution and the moments of the uncollected measurements of any end-devices. Actually both of them are not easy to obtain analytically, nevertheless we show in this section that stochastic process {A(n), n ≥ 0} is, in terms of distribution, an upper bound of stochastic process {B(n), n ≥ 0}.

To derive an upper bound of stochastic process {B(n), n ≥ 0} from process {A(n), n ≥ 0}, we apply a coupling technique consisting in using the same sequences of independent and uniformly distributed random variables for both processes. In this subsection, we thus assume that the two sequences of independent and uniformly distributed random variables U n and V n are equal. We denote by A and B the two coupled stochastic processes constructed from processes {A(n), n ≥ 0} and {B(n), n ≥ 0} respectively. We first need two lemmas which allow us to compare the quantities s B (n, k) and k/K as well as variables J B (U n ) and J A (U n ). As we did for processes {A(n), n ≥ 0} and {B(n), n ≥ 0}, we introduce the process A and B which are obtained by reordering the entries of vectors A(n) and B(n) in the ascending order. Lemma 5.1 For all n ≥ 0 and for all k = 1, . . . , K, we have

Otherwise, the sequence B k (n)/S B (n) being non-decreasing with k and since we have s B (n, K) = 1, there exists a unique index i ∈ {1, . . . , K -1} such that

It follows that, for all k = 1, . . . , i, we have s B (n, k) ≤ k/K. For k = i + 1, . . . , K, we have

which completes the proof.

Lemma 5.2 For all n ≥ 0, we have

Proof. Proof. The definition of J B (U n ) given in Relation [START_REF] Kaul | Minimizing age of information in vehicular networks[END_REF], with B instead of B, is

in which we set s B (n, 0) = 0, for all n ≥ 0. This relation and the fact that the s B (n, k) are non decreasing in k imply that

Similarly, from the definition of J A (U n ) in Relation (2), we get that

We prove this Lemma by contradiction. Suppose that there exists an index n such that J B (U n ) < J A (U n ). Using this assumption and applying Lemma 5.1, we have from Relation (21) that

Using again the assumption

We thus have both U n < J B (U n )/K and U n ≥ J B (U n )/K, which is a contradiction. We thus have that for all n ≥ 0, we have

Proof. Proof. We prove the first result by recurrence on n. When n = 0, we trivially have

We thus distinguish the following four disjoints cases:

Note that if J B (U n ) = K then only the first three cases have to be considered and if J A (U n ) = K then only the first two cases have to be considered.

For each case, we use Relations ( 8) and ( 4) and the recurrence hypothesis.

• For k ∈ {J B (U n ) + 1, . . . , K}, we have

This completes the proof of the first inequality. The second one is now trivial since

which completes the proof.

We are now able to prove the main result of this section, that is that Algorithm B performs better than Algorithm A. We first recall the following lemma, see [START_REF] Lindvall | Lectures on the Coupling Method[END_REF].

Proof. Proof. Combining Lemma 5.4 and Lemma 5.3, we directly deduce that for all n ≥ 0 and k = 1, . . . , K, we have B k (n)

S A (n). Then, using the fact that S A (n)

Theorem 5.5 shows that the amount of accumulated measurements at any end-device is lower for algorithm B than for Algorithm A, i.e. for any ≥ 0

In other words, the probability that the maximum uncollected measurements exceeds with Algorithm B is greater than or equal to the probability that the maximum uncollected measurements exceeds with Algorithm A. Then, we also get that the total sum of uncollected measurements over all end-devices is also lower for Algorithm B than for Algorithm A (in the sense that S B (n) is stochastically dominated by S A (n)).

Analysis of Algorithm C

We show in this section that Algorithm C performs better than algorithm B. More precisely we show that deterministic process {C(n), n ≥ 0} is a lower bound of stochastic process {B(n), n ≥ 0} Theorem 6.1 For any n ≥ 0 and for all k = 1, . . . , K, we have

Proof. Proof. We prove the first inequality by recurrence. The result is clearly true for n = 0, since

From Relation (8) and using the fact that the sequence B k (n) is non decreasing in k we obtain

The second inequality is then immediate by definition of S C (n) and S B (n).

Discussion : performance and vulnerability to attacks

We have shown in the previous section that Algorithm C performs better than Algorithm B which in turn performs better than Algorithm A and we have obtained several performance measures for both Algorithms A and C. This means that from a pure performance criterion it is better to use Algorithm C. Now let us investigate the capacity of these three algorithms to tolerate the presence of deny-of-service attacks against end-devices. We model such an attack by an omniscient entity that has a full knowledge of the code run by both the monitoring devices and end-devices. In particular the adversary knows the distribution of the random variable used by the monitoring device to select the next end-device to be queried, but not the values of the random variable.

Let us first consider the randomized algorithms A and B. The random variable used by the monitoring device to select the end-device from which data is collected at collect n has been denoted by U n , for Algorithm A and by V n , for Algorithm B. The distribution of U n is uniform over {1, . . . , K} and the distribution of V n is proportional to the number of balls in each urn at collect n and thus depends on n. The adversary knows the distributions of U n and V n and tries to determine using these distributions which urn (i.e., end-user) is selected by the monitoring device at each collect n. We denote by Y the random variable used by the adversary at each collect n to mimic the distribution of U n and V n Consider first Algorithm A. By definition of the adversary, random variables Y and U n are independent and identically uniformly distributed. The adversary will succeed in determining the end-user to be queried by the monitoring device at collect n with probability P{Y = U n }. We thus define the vulnerability Vu(A) of algorithm A by the probability P{Y = U n }. It is given by

Concerning Algorithm B, again by definition of the adversary, the random variables Y and V n are independent and identically distributed, but non uniform. The adversary will succeed in determining the end-user to be queried by the monitoring device at collect n with probability P{Y = V n }. The vulnerability Vu(B) of algorithm B at collect n is then given by

Clearly, Vu(B) is not easy to obtain because the random variables V n depends on n, but we have the following bound. The function f (x) = x 2 being strictly convex, the Jensen inequality gives easily

It follows that Vu

, which means that Algorithm A is strictly less vulnerable than Algorithm B. Observe that since Algorithm C is deterministic, we clearly have Vu(C) = 1. Finally, the global result of this analysis shows a trade-off between the performance and vulnerability aspects of these algorithms. Algorithm C performs better than Algorithm B, which performs better than Algorithm A Algorithm A is less vulnerable than Algorithm B, which is less vulnerable than Algorithm C to deny-of-service attacks.

Conclusion

In this paper, we have proposed and analyzed the performance of three algorithms for collecting longitudinal data in a large scale system. A monitoring device is in charge of continuously collecting measurements from K end-devices. We have studied the transient and stationary distributions of the uncollected data at enddevices as a function of the collect policy implemented by the monitoring device. We have also compared their capability to be resilient to deny-of-service attacks launched by an omniscient adversary and have shown a trade-off between vulnerability and performance. It would be relevant to explore other collect policies, starting with those proposed to solve the load balancing problem such as selecting uniformly a end-device among the d end-devices with the most uncollected measurements (multiple-choice paradigm [START_REF] Azar | Balanced allocations (extended abstract)[END_REF]), the two choice paradigm [START_REF] Mocquard | Balanced allocations and global clock in population protocols: An accurate analysis[END_REF] or the (1 + β)-choice [START_REF] Peres | The (1 + β)-Choice Process and Weighted Balls-into-Bins[END_REF].

The algorithms studied in this paper are based on the hypothesis that at each collect, the selected end-device sends its measurements in time. It would be interesting to challenge these algorithms in an environment where some end-device may not respond due to transient partitions. By transient partitions, we mean that among the K end-devices, some of them can be temporarily partitioned from the remaining of the devices, in the sense that communications between these end-devices and the remaining of the system are temporarily delayed.


Gavin Dalton

Don Scott Trager

Don Carlos Abrams

Piercarlo Bonifacio

Alfonso Aguerri

Antonella Vallenari

Georgia Bishop

Kevin Middleton

Chris Benn

Kevin Dee

J Alfonso

L Aguerri

Shan Mignot

Ian Lewis

Johannes Pragt

Sergio Pico

Nic Walton

Juerg Rey

Carlos Allende Prieto

Emilie Lhome

Marc Balcells

David Terrett

Matthew Brock

Andy Ridings

Marc Verheijen

Iain Steele

Remko Stuik

Gabby Kroes

Neils Tromp

Jan Kragt

Dirk Lesman

Chris Mottram

Stuart Bates

Frank Gribbin

Jose Alonso Burgal

José Miguel Herreros

José Miguel Delgado

Carlos Martin

Diego Cano

Ramon Navarro

Mike Irwin

Luis Peralta De Arriba

Neil O'mahony

Andrea Bianco

Alireza Molaeinezhad

Rik Ter Horst

Emilio Molinari

Marcello Lodi

José Guerra

Andrea Baruffolo

Esperanza Carrasco

Szigfrid Farcas

Ellen Schallig

Sarah Hughes

Vanessa Hill

Dan Smith

Janet Drew

Bianca Poggianti

Angela Iovino

Mat Pieri r Shoko Jin

Lillian Dominguez

Cecilia Fariña

Adrian Martín

Clare Worley

David Murphy

Steve Guest

Huw Morris

Eddy Elswijk

Menno De Haan

Hiddo Hanenburg

Bernardo Salasnich

Divakara Mayya

Rafael Izazaga-Pérez

Emanuel Gafton

Elisabetta Caffau

David Horville

Francisco Paz Chinchón

Jesus Falcón-Barosso

Boris Gänsicke

Jose San

Nauzet Hernandez

Integration and Early Testing of WEAVE: The next-generation spectroscopy facility for the William Herschel Telescope

Keywords: Multi-Object Spectroscopy, Fibre Optics, High Resolution Spectroscopy

des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

INTRODUCTION

The WEAVE [START_REF] Balcells | Proc. SPIE[END_REF][START_REF] Dalton | Proc. SPIE[END_REF] project began in early 2010 with a series of national meetings within the partner countries (The UK, The Netherlands, and Spain) of the Isaac Newton Group of telescopes, aimed at developing a comprehensive strategy for the 4.2 William Herschel Telescope (WHT) for the next decade. These meetings identified the need for a dedicated highmultiplex spectroscopic facility to complement upcoming large-scale survey programs in Galactic and extra-Galactic astrophysics, particularly from new facilities such as ESA's Gaia satellite [START_REF] Prusti | [END_REF] and the European Low Frequency Array (LOFAR [4] ). Gaia is already providing [5,6] an unprecedented picture of the structure and dynamics of the Milky Way from measurements of precise positions and parallaxes for more than 10 9 objects with (V ≤ 20) over the whole sky, with still more to come, but is unable to measure the radial component of velocity for the majority of the stars (V>16.5), and has limited spectroscopic capabilities that restrict chemical abundance measurements to only the brightest (V<12) stars in the survey. LOFAR's ongoing surveys will detect more than 10 7 radio sources from high-resolution radio imaging at 30, 60, 120 and 200 MHz over 10000 square degrees of the Northern Sky, but the majority of these are continuum detections with no spectroscopic information to provide redshifts or information on the evolutionary state of the sources. APERTIF [START_REF] Oosterloo | Proc. ISKAF Science Meeting[END_REF] will provide detailed information on the kinematics and dynamics of neutral hydrogen in galaxies at low and intermediate redshifts (z~0.3), but complementary observations are required at visible wavelengths to connect these data with the stellar populations and star-formation activity.

WEAVE was initially developed as a joint project between the UK, Spain and the Netherlands, but the project has been open to wider participation, and the partnership now includes France, Italy, the Konkoly Observatory and INAOE. A number of other individuals and institutes have contributed to join the WEAVE science consortium but are not participating directly in the construction of the facility. The final design of WEAVE was reported in 2016 [START_REF] Dalton | Proc SPIE[END_REF] , and the aim here is not to repeat what has already been set out, but rather to report on the progress towards realization of the design. Many of the WEAVE systems are now close to completion, but there have been some surprises and the inevitable delays along the way. Many of the design details of the individual systems have been reported previously in these proceedings [START_REF] Bogunivic | Proc SPIE[END_REF][START_REF] Tomàs | Proc SPIE[END_REF][START_REF] Murga | Proc SPIE[END_REF][START_REF] Delgado | Proc SPIE[END_REF][START_REF] Schallig | Proc SPIE[END_REF][START_REF] Dalton | Proc SPIE 9913[END_REF][START_REF] Rogers | Proc SPIE[END_REF][START_REF] Izazaga | Proc SPIE[END_REF][START_REF] Izazaga | Proc SPIE[END_REF][START_REF] Bianco | Proc SPIE[END_REF][START_REF] Bates | Proc SPIE[END_REF][START_REF] Salasnich | Proc SPIE[END_REF][START_REF] Pico | Proc SPIE[END_REF][START_REF] Fariña | Proc SPIE[END_REF] , and so we aim here to focus on the progress that has been realised in recent years, and a view of the updated schedule for first light: In Section 2 we cover the new prime focus infrastructure, Section 3 summarises the final status of the fibres themselves, while Section 4 addresses the WEAVE fibre positioning system. The as-built spectrograph is presented in Section 5, and Section 6 discusses the diverse components of the software infrastructure required to operate and exploit the WEAVE facility. Section 6 includes the description of a set of ongoing detailed operational simulations that are designed to test the end-toend operation of the software infrastructure and validate the final scientific performance. We conclude with a summary of the overall project schedule to completion as it sits at the time of writing, an outline of science verification, and a brief overview of the science surveys that will occupy the first 5 years of WEAVE operations.

PRIME FOCUS ASSEMBLY

The original top-end structure of the WHT provided for a prime-focus instrument package, but was unable to accommodate the mass or the size required for WEAVE. After initial attempts to design a drop-in replacement for the original inner flip-ring structure, it was decided to remove this ring altogether, and mount a new set of spiders directly to the fixed outer ring of the structure. Focus and tilt adjustment of the top end is achieved by cam adjusters within the mounting points to the outer ring, referred to as the Focus Translation System (FTS) [START_REF] Casalta | Proc SPIE[END_REF] . The centre-section located by these spiders provides a 3-point mount for the wide-field corrector (PFC) and a mounting flange to support the instrument rotator unit (PFR), which in turn supports the fibre positioner. The design of the FTS units was modified to increase the stiffness of the interfaces, and the full system was shown to be within specification for stability on-telescope in July 2018.

The PFR was first delivered to La Palma in March 2019 but was returned to IDOM for rework of the mounting flange, and returned to the telescope in June 2019. Full details of the rotator can be found in ref [27]. The 6 lenses for the PFC were polished by Kiwistar Optics [START_REF] Bogunivic | Proc SPIE[END_REF] and delivered to the IAC. The lenses were shipped to SENER Aerospatiale for integration [START_REF] Tomàs | Proc SPIE[END_REF] in December 2018, and the completed corrector was delivered to La Palma in June of 2020. The optical design of the corrector permitted assembly to be achieved by mechanical tolerances only, obviating the need for interferometric measurements during integration. Due to travel restrictions, final testing of the corrector at SENER and integration and alignment of the corrector to the top end structure, and on the telescope, have relied heavily on intensive remote presence of project staff via zoom, with remarkable success.

Performance of the ADC elements was verified using a 3-colour laser system, and the final optical performance verified on-sky with the telescope and a Shack-Hartmann camera mounted on a translation stage within the mass-dummy for the positioner system. The on-sky measurements were carried out in August through October of 2020, with the conclusion that the system delivers 80% encircled energy with 0.71", corresponding to an image quality of 0.41" FWHM (both seeing deconvolved), which is in excellent agreement with the design analysis. Subsequent observations with a pair of imaging cameras mounted on-axis and close to the edge of the field suggested the presence of a residual tilt of the focal plane arising from a misalignment of the corrector axis to the rotator. This has now been adjusted on-telescope, and validatory measurements are now in progress.

FIBRES

WEAVE supports 3 distinct modes: 960 single fibres (MOS), 20 deployable 37-fibre mini integral field units (mIFU) and 1 monolithic (603-fibre) static integral field (LIFU). Two instances of the MOS mode exist in the positioner, to allow configuration of the next field to take place in parallel with the current observation, and so there are 4 fibre cable bundles [START_REF] Mignot | Proc SPIE[END_REF] routed from the positioner through the rotator cable wrap, out along the spiders and down the telescope structure to where the spectrograph is housed in GHRIL. Each of these ~36m cables is terminated at the spectrograph in a slit assembly with, respectively, 40, 40, 20 and 27 slitlets which are abutted to a field lens within their own slit unit. The input focal surface of the spectrograph is curved in two directions. The LIFU cable, terminated at one end with slitlets was delivered to NOVA in the summer of 2019 and sorted into rows according to a science-led prescription aimed at keeping adjacent fibres on the sky well-separated at the slit, and of spreading the fibres in the offset sky-sampling apertures evenly along the slit. These rows were then assembled into the two halves of the LIFU 'head' with an additional 3 fibre wide buffer annulus of unused short fibres to support the array. The head was then polished and installed behind its field lens within a unit that also houses an off-axis guide camera, and which mounts to the outside of the positioner tumbler structure (see below). The LIFU was delivered to Oxford at the end of June 2020.

The slit unit for the LIFU was assembled in Dwingeloo, prior to shipping to Oxford along with the integration bench, with the intent that the NOVA team would assemble the MOS and mIFU slits in Oxford once the fibres were installed in the positioner. Travel restrictions due to Covid-19 meant that this approach was impossible, and so the installation of these was carried out by the positioner team.

POSITIONER

The integration and testing of the positioner is described in detail in ref [29]. Each cable is packaged such that the fibres for each retractor are grouped separately. These were extracted, identified, and the inevitable tangles that had been introduced along the 2m length of the PEEK tubing were worked out by hand. The six buttons were then stowed on a small steel plate attached to a length of plastic trunking that was used to guide the fibres along the axis of the tumbler to where they can be collected, the steel plate removed from the trunking, and the group of buttons fed through one of the apertures in the side wall of the tumbler structure. There is sufficient length of PU tubing between the 1:4 breakout box and the 1:6 breakout box that the latter can be drawn out to a workbench next to the positioner. The 2m lengths of PEEK tubing were then installed into the retractor and the 1:6 breakout box forms the entry interface. The retractor unit was then tested by hand on the bench to ensure that all six channels were running freely, and the PU tube was drawn back through the tumbler structure and the retractor unit fixed in place. It was estimated that 1 hour should be sufficient for each retractor to be assembled with this process, although any issues that were encountered could increase this by up to a factor of 3 in the worst cases. Adequate preparation of the retractor and components was key to the ease of assembly, and on the plus side it did prove possible to install the final 12 retractors in a single day. The mIFU cables were installed in a very similar fashion, 2 units to each of 10 retractors. The mIFU retractors follow a similar design to the MOS, but with the notable exceptions that they are single-sided, there is only sufficient transverse space in the spare length box for a single PU-PU tube crossing (hence a shorter length within the retractor), and the spring tensioners on the lower-pulleys had to be doubled up with stronger springs (approximately 6x more spring force than the MOS) in order to overcome friction between the PU tube and the retractor casing.

The guide fibre bundles also required a slight modification to the MOS retractors in terms of a stronger spring (the same used for the mIFUs) and some additional space to allow free path of the fibre down from the top pulley. Again, the main issue here is friction between the outer sleeve (PEEK in this case) and the wall of the retractor unit. The assembly of the guide fibres into their retractors was complicated by the short available length of the coherent bundles used, and so they were assembled on the tumbler unit before other MOS fibres had been installed. On the MOS A side the guide fibres each inhabit a retractor of their own. On the MOS B side the other 5 slots are occupied by fibres that have been displaced by the mIFUs, and which would otherwise have been lost. This was achieved by installing 5 fibres into the retractor, moving back into the tumbler structure and then installing the guide fibre last. The final MOS fibre that would otherwise have been installed was coiled up inside the spare length box of this retractor, and is available to be swapped-in if desired. A consequence of this sharing of space between the MOS and guide fibres was that the first MOS cable installed into plate B maps to 8 different locations around the periphery of the field.

Once the fibre installation was complete, the two field plates were installed. The original plan was that the field plates would be machined from solid invar (stress-relieved) with a pocketed rear structure to achieve substantial lightweighting. These were manufactured in-house and sent for lapping, but subsequent metrology revealed a relaxation of the surface form in the ~3 months post-lapping. The process was repeated using solid plates, but yielded effectively the same results. It was therefore decided to artificially age the plates by temperature cycling through liquid nitrogen, and then re-machine by turning the surface on a lathe. Initial calibration of these offsets, prior to shipping the positioner to La Palma, showed that it is possible to achieve a single move to place a fibre within 5µm of the desired target position. Iterative placement is implemented to allow the final position to be adjusted to tolerance as required. These offsets will be revisited post-shipping once any handlinginduced movement of the tumbler relative to the robots has been accommodated. The final part of the positioning scheme is the calibration between the robots and the field plate itself. A grid of ~400 reference spots, 20mm pitch, was etched into the surface of each field plate and can be illuminated and imaged by the onboard camera. Each robot scans a subset of this grid at the start of each configuration to compensate for any movement of the tumbler due to changes in zenith distance. A full scan of this grid with each robot is used to determine the straightness and perpendicularity of the robot axes. This configuration uses a direct optical path to the plate, rather than the folded path used to image the fibre core. Calibration of the precise (virtual) location of the centre of rotation on the CCD in this configuration (~32mm off-axis) is critical to ensure that both robots agree on the position of all fibres in the field, which we validate using a sparse grid of 25 fibres positioned on the plate and then measured in-situ by both robots.

As a final stage in pre-shipping checks, we ran a quadrant of a test configuration through the full software system to follow the fibre moves. The software [START_REF] Terrett | Proc SPIE 9152[END_REF] keeps track of the order in which fibres have been placed in the field, and each potential move is checked to ensure that only the upper fibre of any crossing pair can be moved. The software determines the next available move for each robot based on the current positions and planned move for both robots. As expected, the system used only a single robot to deploy the chosen quadrant (at this stage, 25 minutes for ~200 fibre moves), but was able to make efficient use of the second robot in returning the fibres to their parked positions.

SPECTROGRAPH

In August of 2018 the 5 th lens for the red camera of the spectrograph suffered a catastrophic failure at INAOE (rapid unscheduled disassembly) during the final phase of manufacture. This is one of 4 S-FPL51 lenses in the spectrograph, and it was immediately possible to repurpose the blue-arm element as a replacement to complete integration of the red camera while a replacement blank could be sourced. It was, however, found to be difficult to source a replacement blank for this material (298mm diameter x 67mm thick), with projected lead-time of more than 1 year, and some nervousness from Ohara as to the success rate of producing blanks of this size in this material, which has the combination of a relatively high CTE and very low thermal conductivity. Fortunately, Ohara were able to locate a single remaining blank from their last production run, but with a size of 390x125mm, which they were (understandably) unwilling to downsize.

We were therefore able to secure this blank and arrange (with Hellma) to slice it diagonally to achieve a replacement for lens 5 and a suitable spare for future contingency. The reworked red lens 5 was completed in February 2019, and the sliced replacement blank was delivered to INAOE from NOVA at the end of April 2019, and the finished lens (the final lens for the spectrograph) delivered to NOVA at the end of July 2019. Mounting of the spectrograph optics was completed by mid-December. Throughout the testing phase of the spectrograph we experienced issues with the reliability and noise performance of the detector system. Some of this was tracked to issues with older driver boards being used with INGs ULTRADAS system, but an investigation of the noise performance suggested that a redesign of the detector PCBs was in order. This was implemented by Simon Tulloch of QCAM. When the spectrograph was packed for shipping to La Palma the cryostats were therefore returned to LJMU for installation of the new boards, final installation of the science detectors, and a repair to a leak in the pipework for the LN2 tank in the red cryostat. It was discovered that some damage to the red window had occurred during handling, and proposed to coat the spare window for replacement, but this was also damaged during removal from its location in the blue arm. Two new windows (one red, one spare) are now expected imminently for final installation. The blue cryostat installation and test was completed in time for this to join the positioner for shipping to La Palma.

SOFTWARE SYSTEMS

Integration of the prime focus system control elements (FTS, PFR, ADC) to the telescope control system is complete.

Testing of the spectrograph and positioner control systems with the top-level instrument control have been completed at unit level. The full software suite for WEAVE begins with submission of catalogues for survey observations and manages the flow of data and observations through field configuration, scheduling [START_REF] Fariña | Proc SPIE[END_REF] and management of observations [START_REF] Pico | Proc SPIE[END_REF] , quality control, data processing [START_REF] Walton | Proc SPIE 9152[END_REF] and analysis and ends with a complete archive [START_REF] Guerra | Proc SPIE 9913[END_REF] that will be used to manage visualization and staged releases of the data.

We have conducted a set of operational simulations [START_REF] Jin | [END_REF] , covering 3 full months of WEAVE observations selected from an 18 month window, to evaluate the performance of the software systems in terms of scheduling efficiency and final data quality. The simulations take template spectra for all observed targets, apply the geometry of the input beam from the telescope to the fibre in put at that location in the field, and trace the light through the ray-trace model of the spectrograph to the sampling of the detector pixels. Throughput, noise and sky background appropriate to the date, time and position of the observation are applied, together with seeing and atmospheric transmission from archived weather logs. The data 'observed' in this way are then passed to the processing chain for reduction and analysis, and then distributed back to the science team via the archive. These simulations have proved invaluable in troubleshooting the interfaces and specifications required to make this complex system operate seamlessly, and in tuning the detailed designs of the surveys themselves to try to maximise the scientific output from the facility.

SUMMARY AND PROSPECTS

After some delays in shipping, due to the current global situation, the positioner has now reached the Canaries, and will hopefully be delivered to the observatory before the Christmas break. Check-out and integration to the top end will commence mid-January with final calibration of the positioner taking place in-situ. Integration of the detector cryostats to the spectrograph will dovetail into the first mounting of the full top-end to the telescope and installation of the fibre slits to the spectrograph. Actual first light is therefore expected to take place in February-March, with up to 50 nights expected for on-sky commissioning, including a weather allowance. First science data is therefore expected before mid-2021. The 5-year survey programme for WEAVE is described in detail in ref [24], and was extensively and positively reviewed in January 2020. In parallel with the surveys, the remaining 30% of the WHT time is available for normal PI-mode observations, with an expectation that much of this time will also be allocated to WEAVE projects. These PI projects will have the benefit of the full data management infrastructure available to the surveys. The first full public data release of the 1 st year of survey data is scheduled for 1 year after the last observation in that set is obtained.

Figure 1 :

 1 Figure 1: Illustration of the components of WEAVE showing the new top end structure and the route of the fibres to GHRIL.

Figure 2 (

 2 Figure 2 (left) The PFR under test in the WHT dome. (right) The corrector installed in the top end and ready for testing on-sky.

Figure 3 :

 3 Figure 3: Rendering of the layout of a single MOS fibre bundle (lengths not to scale!)The design of the fibre cables reflects the modularity of the system, in that a single slitlet of 24 fibres maps to a group of 4 retractors (6 fibres each) at the positioner, and cables for 4 slitlets are grouped together into a single conduit for routing through the prime focus cable-wrap and around the telescope structure. This cable of 96 fibres with 4 slitlets and 16 sets of 6 MOS fibres forms one deliverable unit. The first MOS cable was delivered to Oxford in August 2019 after testing in Paris. The final cable for MOS A was delivered in mid-March 2020, just as France entered the first full lockdown for Covid-19. Delivery of the MOS B cables commenced in mid-June 2020, together with the mIFUs, with the last cable arriving in Oxford the 1 st week in August.

Figure 4 :

 4 Figure 4: (left) Sorted rows of fibres being installed into one half of the LIFU head. (right) A view of the completed LIFU head after polishing.

Figure 5 :

 5 Figure 5: (left)The completed positioner in the lab. (upper right) A subset of the parked fibres for MOS B illustrating the tiered arrangement of the retractors, 2 mIFU retractors can be seen interspersed with the MOS fibres, and one guide fibre button (bottom tier, 2 nd fibre from the right) can be discerned. (lower right) A view of the field of MOS A ready for deployment with both robots in play.

Figure 6 :

 6 Figure 6: (left) A subset of the upper tier fibres being deployed in a circle during calibration. (right) A single quadrant of a full field deployed for software testing, illustrating the full 3-dimensional nature of the fibre crossings.

Figure 7 :

 7 Figure 7: (left) Lens groups of the red camera during integration. (center) The complete spectrograph under test in the lab at ASTRON. (right) The spectrograph being lifted into the GHRIL enclosure.

Figure 8 :

 8 Figure 8: Organisational map of the operational rehearsal data flow showing interactions between the science teams, the submission platform (WASP), the simulations (SIM) through the telescope and Observatory Control System (OCS) and to the elements of the data processing chain (CPS/APS) and the archive (WAS).

Figure 9 :

 9 Figure 9: (left) The shape of things to come: top end with corrector, rotator and dummy positioner being installed on the telescope, with boxes to show the space envelope of the transport boxes for the fibre cables and slit units. (right) A 'first light' image of M74 obtained on-axis during on-sky testing of the corrector system.

https://ingconfluence.ing.iac.es:8444/confluence//display/WEAV/The+WEAVE+Project

https://ingconfluence.ing.iac.es:8444/confluence/display/WEAVEDEV/WEAVE+Publications#WEAVEPublications-Acknowledgements

ACKNOWLEDGMENTS

Funding for the WEAVE facility has been provided by UKRI STFC, by the University of Oxford, by NOVA, by NWO, by Instituto de Astrofísica de Canarias (IAC), by the Isaac Newton Group partners (STFC, NWO, and Spain, led by the IAC), by INAF, by CNRS-INSU, by the Observatoire de Paris, by Région Île-de-France, by Région Franche Comté, by Observatoire de Besançon, by ConaCyt through INOAE, by Konkoly Observatory of the Hungarian Academy of Sciences, by Max-Planck-Institut für Astronomie (MPIA Heidelberg), by Lund University, Uppsala University, AIP and the University of Pennsylvania. The WEAVE Survey Consortium consists of the ING, its three partners, represented by UKRI STFC, NWO, and the IAC, NOVA, INAF, GEPI, INAOE, and individual WEAVE Participants. The WEAVE website 1 and the full list of granting agencies and grants supporting WEAVE 2 are available from the project web pages.

Over the 10+ years of the WEAVE project it has been a great pleasure to benefit from discussions with colleagues in the field, many of which have been 'hosted' by the SPIE conferences. We have benefitted enormously from our interactions with our industrial partners at Kiwistar, Schunk, SENER Aerospatiale, IDOM, SEDI-ATI, KOSI, Fibertech Optica, AMS and Fiberguide. We are also particularly grateful to those who have been able to join us in various reviews of the project to contribute their insight and wisdom, and to take a fresh view of things.