Emmanuelle Anceaume
email: emmanuelle.anceaume@irisa.fr

Yann Busnel
email: yann.busnel@imt-atlantique.fr

Vasile Cazacu
email: vasile.cazacu@irisa.fr

Finding Top-k Most Frequent Items in Distributed Streams in the Time-Sliding Window Model

I. INTRODUCTION AND PROBLEM STATEMENT

From marketing over social networks to prevention of distributed denial of service (DDoS) attacks, the need to analyze in real time large-scale and distributed data streams has recently became tremendous. Among several important problems raised in this context, the need to dynamically detect heavy-hitters (or hot) items during the most recent time window is essential but highly challenging. The problem of finding the most frequent items has been heavily studied during the last decades with both exact and probabilistic solutions [START_REF] Metwally | Efficient computation of frequent and top-k elements in data streams[END_REF], [START_REF] Anceaume | Identifying global icebergs in distributed streams[END_REF]. Nevertheless, answering this issue over a sliding time window is still an active research field [START_REF] Wei | Persistent data sketching[END_REF]. Very recently, Song et al. [START_REF] Song | Top-k frequent items and item frequency tracking over sliding windows of any sizes[END_REF] formalized this problem as the Windowed Top-k Frequent Items (WTK) problem and proposed an efficient and very elegant solution, named the Floating Top-K (FTK) method, to solve WTK. We improve upon their solution by providing a new algorithm, that we call FTK CE , which is based on a deterministic counting of the most over-represented items in the data streams, which are themselves identified probabilistically. Performances (both in accuracy and memory cost) are astonishingly good, despite an adversary whose objective is to manipulate the order in which items are received at the nodes.

System model. We consider a set of N nodes S 1 , . . . , S N such that each node S i receives a large sequence σ Si of data items or symbols. We assume that streams σ S1 , . . . , σ S N do not necessarily have the same size, i.e., some of the items present in one stream do not necessarily appear in others or their occurrence number may differ from one stream to another one. We also suppose that node S i (1 ≤ i ≤ N ) does not know the length of its input stream. Items arrive regularly and quickly, and due to memory constraints (i.e., nodes can locally store only a small amount of information with respect to the size of their input stream and perform simple operations on them) need to be processed sequentially and in an online manner. Let σ = a 1 , a 2 , a 3 , . . . , a n be a stream of data items that arrive sequentially. Each data item i is drawn from the universe Ω = {1, 2, . . . , N }, where N is very large. A natural approach to study a data stream σ of length n is to model it as a fingerprint vector over the universe Ω, given by X = (x 1 , x 2 , . . . , x N ) where x i represents the number of occurrences of data item i in σ.

Problem statement. The windowed Top-k frequent items definition is borrowed from [START_REF] Song | Top-k frequent items and item frequency tracking over sliding windows of any sizes[END_REF]. Specifically, Definition 1 (Windowed Top-k Frequent Items [START_REF] Song | Top-k frequent items and item frequency tracking over sliding windows of any sizes[END_REF]): Let t be the current time unit. The Windowed Top-k Frequent Item problem consists in returning the k most frequent items for any given time window from time unit t -w to time unit t, denoted as [t -w, t], with w ≤ W , W being a user-defined upper bound of w. More formally, we seek the set Top k = {i ∈ Ω | x i ≥ x j where x j is the k-th greatest value in X}. This query may be asked at any time unit t. Moreover, the time domain is partitioned into time units, which define the granularity of window sliding ("jumping"). Indeed, the time unit acts like a micro-batch for the WTK problem. The top-k most frequent items are generated for each time unit, after what the top-κ most frequent items over the whole past window is returned. Moreover, window's length w ≤ W and number κ ≤ k of items requested are freely chosen by the user at execution time.

II. ALGORITHM DESCRIPTION

Our algorithm FTK CE is based on two steps allowing respectively (i) to select the relevant candidates to integrate the Top k set and (ii) to rank these candidates to answer the problem whatever the value of κ ≤ k provided.

Step 1: Probabilistic selection is inspired by the use of the primitive RANDOMLEVEL proposed in [START_REF] Song | Top-k frequent items and item frequency tracking over sliding windows of any sizes[END_REF]. This primitive associates to any item received a random level value computed on the fly, as follow. At each call of RANDOMLEVEL, the algorithm starts by throwing a coin, and with probability p gets "head", and with probability 1-p gets "tail". This process continues as long as "head" are returned. Once a "tail" is returned, the primitive returns the number of "head" obtained for this item. The random variable level follows a geometric distribution. Given a predetermined threshold θ, this item is then considered as a potential candidate if level ≥ θ. Else, it is simply ignored and do not enter to the next step.

Step 2: The second step of our algorithm is the counting phase. It uses a buffer memory Γ t whose size is dynamic. For each candidate item i ∈ Ω selected in the first step, if item i already has a c i counter in Γ t , this one is simply incremented. Otherwise, a new (i, 1) counter is added to Γ t . The set of all tuples of a unit of time t are grouped into a data structure Γ. This structure brings together subsets from Γ t to Γ t-W arranged in reverse chronological order. Intuitively, if an item is very frequent, its probability of exceeding θ increases due to the large number of calls to RANDOMLEVEL primitive. In comparison, the chance for a rare item to be a candidate is very low. Thus, the expectation for item i of being a candidate is statistically proportional to its frequency x i . Counting how many times an item is candidate allows us to obtain a global ranking which is, in expectation, accurate with the weight of the heavy hitters in X.

Query: When requesting the Top κ set (with κ ≤ k) on a window of size w ≤ W , the algorithm just sums, for each item i of Γ, all the tuples corresponding to i in the different sub-structures Γ τ (for τ ∈ {t -w, . . . , t}). The set of items with the κ highest global counter value is then returned.

The challenging aspect of FTK CE is to properly choose θ. θ must minimize the number of candidates while maximizing the probability for the heavy hitters to be retained. We rely on a former analysis of the coupon collector problem [START_REF] Anceaume | New results on a generalized coupon collector problem using markov chains[END_REF]Formula (5)] and an analysis of a leader election problem [START_REF] Kalpathy | Survivors in leader election algorithms[END_REF]Th. 4.1] to compute θ. Anceaume et al. [START_REF] Anceaume | New results on a generalized coupon collector problem using markov chains[END_REF] analysis allows us to compute the expected number of items to be drawn in order to collect the Top k items we are interested in. We apply next a leader election result from [START_REF] Kalpathy | Survivors in leader election algorithms[END_REF], which allows us to determine θ as the expected number of rounds to elect the expected number of items to be drawn.

III. PERFORMANCE EVALUATION

Our theoretical analysis shows us that FTK CE returns the same Top k items when applied directly over the whole time window or over per time units. This is of utmost importance when considering a malicious environment. Briefly, any ordering manipulation of the input data stream during any time window has no impact on the returned top-k items. The only feature that influences the probability of error of our algorithm is the total items frequency during the time window. This comes from the random and independent level attribution schema, which by construction selects each item independently of each other, and thus independently of the order in which items are received.

In the remaining of the paper, we present a summary of the experiments we have conducted to compare performances of our algorithm with the one of Song et al. [START_REF] Song | Top-k frequent items and item frequency tracking over sliding windows of any sizes[END_REF], which is so far, and to the best of our knowledge, the most impressive solution to solve the windowed top-k problem. Note that these experiments illustrate the nice theoretical properties we are still conducting on our algorithm. Performances of our algorithm are denoted by "FTK CE " on the graphs, and the ones of Song et al. [START_REF] Song | Top-k frequent items and item frequency tracking over sliding windows of any sizes[END_REF] are denoted by "FTK" for "Floating Top-k". Figure 1a compares the precision of both FTK CE and FTK algorithms, fed with a Zipf-α distribution of items, with α = 2, when queried to provide the top-κ, with k = 15. By precision, we mean the number of top-i, with 1 ≤ i ≤ k, correctly detected by the algorithms divided by the total number of detected items. A particularity of the Top-k problem is that precision and recall are equivalent in this case. Indeed, the number of false positives in the returned T op κ set corresponds exactly to the number of false negatives not returned by the algorithm. Figure 1b represents the total number of counters used in both algorithms. Note that we have plotted the x•log(x) function as Song et al. [START_REF] Song | Top-k frequent items and item frequency tracking over sliding windows of any sizes[END_REF] argue in their paper that this should represent a lower memory bound of their algorithm. Figure 1c compares the precision of both solutions as a function of different Zipf-α distributions of items (from a uniform one, i.e., α = 0, to a strongly skewed one, i.e., α = 4.5). FTK CE is capable of detecting frequent items even for very flat item distributions (i.e., Zipf-0.5).

To conclude, we have briefly shown the impressive behavior of our algorithm. We are still analyzing the theoretical behavior of our algorithm (i.e., ( , δ)-approximation and bounds on the memory cost), and we conducting extensive simulations in a particularly adversarial environment.

Fig. 1 .

 1 Fig. 1. Simulation results obtained with 10 6 executions of both FTK CE and FTK fed with input streams of n = 10 6 items made of N = 10 4 distinct items.


Quentin Scanvion

Valéry Hedouin

Damien Charabidze
email: damiencharabidze@univ-lille2.fr

Collective exodigestion favours blowfly colonisation and development on fresh carcasses Authors

Keywords: Adaptive ecology, Aggregation, Allee effect, exodigestion, niche selection

published or not. The documents may come

Collective exodigestion favours blow fly colonization and development on fresh carcasses

Quentin Scanvion, Valéry Hédouin, Damien

INTRODUCTION

Collective behaviour is powerful adaptive strategy to cope with a harsh environment, and cooperation is believed to be a key to the global success of social species [START_REF] Cornwallis | Cooperation facilitates the colonization of harsh environments[END_REF]. Although eusocial Hymenoptera such as bees and ants are well-known insect societies, gregarious insects also provide interesting examples of efficient collective strategies [START_REF] Choe | The Evolution of Social Behaviour in Insects and Arachnids[END_REF][START_REF] Costa | The other insect societies[END_REF]. [START_REF] Grassé | Sociétés animales et effet de groupe[END_REF] defined a part of social behaviour as a Mass effect, i.e., a group effect caused by a modification of the medium by the population itself. A striking example of this idea is provided by terrestrial crustacean woodlice, for which desiccation is a primary concern: in response to this environmental stress, aggregation offers group protection against drying [START_REF] Broly | Effects of group size on aggregation against desiccation in woodlice (Isopoda: Oniscidea)[END_REF]. [START_REF] Deneubourg | Kinetics of larval gregarious behavior in the bark beetle Dendroctonus micans (Coleoptera: Scolytidae)[END_REF] also observed that bark beetle larvae aggregate and use communal feeding as a way to overwhelm the reaction of the tree. Similarly, social spiders collectively inject digesting enzymes and then suck up the liquidised prey content, thereby exploiting a common resource that was jointly created [START_REF] Schneider | Benefits of cooperation with genetic kin in a subsocial spider[END_REF]. In flies, egg aggregations allow larvae to warm and moisten the organic material [START_REF] Barnard | Influence of Larval Density and Temperature in Poultry Manure on Development of the House Fly (Diptera: Muscidae)[END_REF][START_REF] Bryant | Morphometric adaptation of the housefly, Musca domestica L., in the United States[END_REF], improve larval ability to dig and burrow into the food [START_REF] Durisko | Dynamics of social behavior in fruit fly larvae[END_REF], and limit the growth of competitive fungi [START_REF] Rohlfs | Competition with filamentous fungi and its implication for a gregarious lifestyle in insects living on ephemeral resources[END_REF][START_REF] Zvereva | Peculiarities of competitive interaction between larvae of the house fly (Musca domestica) and microscopic fungi[END_REF].

Blowflies (Diptera: Calliphoridae) are the most widespread and abundant necrophagous species and are attracted quickly after death [START_REF] Smith | A manual of forensic entomology[END_REF]. Female flies lay eggs on fresh vertebrates carcasses on which their larvae feed until metamorphosis; larvae are confined to the carrion until reaching a sufficient mass/instar. Although some studies report competition among carrion flies larvae [START_REF] Denno | Niche relationships of a guild of necrophagous flies[END_REF][START_REF] Denno | Competitive interactions and ecological strategies of Sarcophagid and Calliphorid flies inhabiting rabbit carrion[END_REF][START_REF] Feinberg | Evolution of increased "female sex Ratio" in the blowfly (Phaenicia sericata) under laboratory competition with the housefly (Musca domestica)[END_REF][START_REF] Hanski | Carrion fly community dynamics: patchiness, seasonality and coexistence[END_REF][START_REF] Ives | Aggregation and coexistence in a carrion fly community[END_REF], [START_REF] Flores | Nonconsumptive effects of predatory Chrysomya rufifacies (Diptera: Calliphoridae) larval cues on larval Cochliomyia macellaria (Diptera: Calliphoridae) growth and development[END_REF] observed that female flies do not preferentially oviposit on carcasses without larvae, and several studies show that ovipositing gravid blowflies enhance the attractiveness of a carrion [START_REF] Brodie | Is aggregated oviposition by the blow flies Lucilia sericata and Phormia regina (Diptera: Calliphoridae) really pheromone-mediated?[END_REF][START_REF] Denno | Niche relationships of a guild of necrophagous flies[END_REF][START_REF] Jiang | Semiochemicals from ovaries of gravid females attract ovipositing female houseflies, Musca domestica[END_REF][START_REF] Kneidel | Competition and disturbance in communities of carrion-breeding Diptera[END_REF][START_REF] Wall | Evolutionary ecology of communication signals that induce aggregative behaviour[END_REF]. Therefore, egg aggregation is clearly not avoided and is even sought by adult blow flies. Furthermore, during the three feeding instars, calliphorid larvae actively aggregate [START_REF] Boulay | Evidence of active aggregation behaviour in Lucilia sericata larvae and possible implication of a conspecific mark[END_REF][START_REF] Boulay | Interspecific shared collective decision-making in two forensically important species[END_REF]: masses of several thousands of larvae are commonly observed in the field (Fenton et al., 1991;[START_REF] Simkiss | Thermoregulation in larval aggregations of carrion-feeding blow flies (Diptera: Calliphoridae)[END_REF]. Because females and larvae should avoid competition, whether necrophagous larval aggregation is advantageous is a reasonable question (see Table 1). When they reach a sufficient weight, late thirdinstar disperse to find sheltered places for pupation, a process known as postfeeding larval dispersal [START_REF] Gomes | A review of postfeeding larval dispersal in blowflies: implications for forensic entomology[END_REF]. Consequently, postfeeding larvae and pupae are not subject to the same selection pressure than feeding instars.

BENEFITS COSTS

Temperature

The mechanisms remain hypothetical (larval metabolism, permanent friction of larvae, microbial activity), but heat production by large larval masses is clearly demonstrated [START_REF] Charabidze | Larval-mass effect: Characterisation of heat emission by necrophageous blowflies (Diptera: Calliphoridae) larval aggregates[END_REF][START_REF] Gruner | Volume of larvae is the most important single predictor of mass temperatures in the forensically important calliphorid, Chrysomya megacephala (Diptera: Calliphoridae)[END_REF][START_REF] Heaton | Quantifying the temperature of maggot masses and its relationship to decomposition[END_REF][START_REF] Simkiss | Thermoregulation in larval aggregations of carrion-feeding blow flies (Diptera: Calliphoridae)[END_REF]. The microclimate inside the mass should increase the developmental speed of maggots.

When the temperature approaches the thermal tolerance range of the larvae, selfregulation processes within the mass must be initiated, which reduce the time allocated to feeding and therefore the growth rate [START_REF] Charabidze | Discontinuous foraging behavior of necrophagous Lucilia sericata (Meigen 1826) (Diptera Calliphoridae) larvae[END_REF].

Food availability

Cooperative exodigestion was supposed but not experimentally

After a critical number of individuals are reached, the availability of nutrients per demonstrated [START_REF] Rivers | Physiological trade-offs of forming maggot masses by necrophagous flies on vertebrate carrion[END_REF].

individual becomes insufficient, leading to decreases in the speed of development, survival, and weights and sizes (Table A1).

Physicochemical modifications

Increasing the mass may protect larvae against evaporation and temperature decreases [START_REF] Broly | Effects of group size on aggregation against desiccation in woodlice (Isopoda: Oniscidea)[END_REF][START_REF] Huntington | Maggot development during morgue storage and its effect on estimating the post-mortem interval[END_REF][START_REF] Pérez | Evaluating the biological cycle and reproductive and population parameters of Calliphora vicina (Diptera: Calliphoridae) reared on three different diets[END_REF].

Excreta rich in ammonia accumulates [START_REF] Hobson | Studies on the nutrition of blow-fly larvae : I. Structure and function of the alimentary tract[END_REF].

Predators and parasites

High population densities can reduce the risk of predation/parasitism but remains to be demonstrated for necrophagous species [START_REF] Hunter | Gregariousness and repellent defences in the survival of phytophagous insects[END_REF][START_REF] Rohlfs | Spatial aggregation across ephemeral resource patches in insect communities: an adaptive response to natural enemies?[END_REF].

Chemical signals of the larvae and metabolites increase as a result of feeding (no experimental evidence, see [START_REF] Frederickx | Hosthabitat location by the parasitoid, Nasonia vitripennis Walker (Hymenoptera: Pteromalidae)[END_REF].

Other

Repulsion of scavengers and burying beetles: female burying beetles typically exploit carcasses without blowfly larvae (smith, 1986).

Scavengers may avoid carcasses heavily colonised by larvae and/or bacteria (devault et al., 2004).

Increased risk of disease: many pathogens are transmitted in a density-dependent fashion, but this phenomenon has not been demonstrated in necrophagous larvae [START_REF] Pöppel | Antimicrobial peptides expressed in medicinal maggots of the blow fly Lucilia sericata show combinatorial activity against bacteria[END_REF].

Adapted from [START_REF] Rivers | Physiological trade-offs of forming maggot masses by necrophagous flies on vertebrate carrion[END_REF].

Necromass is by nature a discrete and ephemeral food source. Decomposition processes quickly alter flesh (Clark et al., 1997), and the probability of carcass removal by scavengers increase with time and decomposition odour [START_REF] Devault | Factors influencing the acquisition of rodent carrion by vertebrate scavengers and decomposers[END_REF]. As pioneer species, blowflies strategy depends on their ability to quickly colonize carrions [START_REF] Denno | Niche relationships of a guild of necrophagous flies[END_REF]. Furthermore, many birds, wasps and necrophagous insects prey on maggots. [START_REF] Voss | Hymenopteran parasitoids of forensic importance: host associations, seasonality, and prevalence of parasitoids of carrion flies in Western Australia[END_REF] report an overall 11.8% paratism of maggots, and [START_REF] Frederickx | The community of Hymenoptera parasitizing necrophagous Diptera in an urban biotope[END_REF] observed that on average, 48% of fly pupae were killed by hymenopteran parasitoids (from 3.5% in May to 90% in September). When the larvae develop rapidly, less time is spent on the cadaver and probability of a food shortage, predation, parasitism and interspecific competition decrease [START_REF] Devault | Factors influencing the acquisition of rodent carrion by vertebrate scavengers and decomposers[END_REF][START_REF] Rivers | Oviposition restraint and developmental alterations in the ectoparasitic wasp, Nasonia vitripennis, when utilizing puparia resulting from different size maggot masses of Lucilia illustris, Protophormia terraenovae, and Sarcophaga bullata[END_REF]. That can noticeably be achieved by favouring high-temperatures that increase their development speed [START_REF] Aubernon | Thermoregulation in gregarious dipteran larvae: evidence of species-specific temperature selection[END_REF][START_REF] Grassberger | Effect of temperature on Lucilia sericata (Diptera: Calliphoridae) development with special reference to the isomegalen-and isomorphendiagram[END_REF]. In this respect, a well-known adaptive strategy of blow flies larvae is the socalled maggot-mass effect, a local temperature increase attributed to larval metabolism [START_REF] Charabidze | Larval-mass effect: Characterisation of heat emission by necrophageous blowflies (Diptera: Calliphoridae) larval aggregates[END_REF][START_REF] Simkiss | Thermoregulation in larval aggregations of carrion-feeding blow flies (Diptera: Calliphoridae)[END_REF]. Because additional heat gain reduces developmental time, aggregated larvae benefit from this larval-mass effect with faster development than that of isolated individuals [START_REF] Erzinçlioglu | Blowflies[END_REF][START_REF] Heaton | Quantifying the temperature of maggot masses and its relationship to decomposition[END_REF][START_REF] Johnson | Effect of massing on larval growth rate[END_REF]. In the same way, aggregation can protect larvae from abrupt decreases in temperature [START_REF] Huntington | Maggot development during morgue storage and its effect on estimating the post-mortem interval[END_REF][START_REF] Magni | Effect of continuous and cyclic exposure to a cold environment on the development of larvae of Lucilia sericata (Diptera: Calliphoridae) in different sized larval masses[END_REF][START_REF] Rivers | Physiological trade-offs of forming maggot masses by necrophagous flies on vertebrate carrion[END_REF]. However, these thermal effects mostly occurs during late feeding instars and only within large masses above a thousand larvae [START_REF] Charabidze | Larval-mass effect: Characterisation of heat emission by necrophageous blowflies (Diptera: Calliphoridae) larval aggregates[END_REF][START_REF] Heaton | Quantifying the temperature of maggot masses and its relationship to decomposition[END_REF]. Here, we postulated that beside maggot-mass effect, gregariousness favours necrophagous larvae feeding and their early exploitation of fresh carcasses.

According to [START_REF] Disney | Morphological and other observations on Chonocephalus (Phoridae) and phylogenetic implications for the Cyclorrhapha (Diptera)[END_REF], the switch to ingesting liquid instead of solid food could be a fundamental revolution in the evolution and diversification of flies. Necrophagous larvae are actually unable to ingest solid particles other than those that are microscopic, and their buccal apparatus is not suitable for mastication [START_REF] Guyénot | L'appareil digestif et la digestion de quelques larves de mouches[END_REF].

Therefore, larvae must liquefy the food before ingestion (i.e., exodigestion). The necrophagous larvae of calliphorid flies excrete/secrete various proteolytic enzymes, including trypsin, lipases and amylases [START_REF] Chambers | Degradation of extracellular matrix components by defined proteinases from the greenbottle larva Lucilia sericata used for the clinical debridement of nonhealing wounds[END_REF][START_REF] Hobson | Studies on the nutrition of blow-fly larvae : I. Structure and function of the alimentary tract[END_REF][START_REF] Rivers | Physiological trade-offs of forming maggot masses by necrophagous flies on vertebrate carrion[END_REF][START_REF] Terra | Insect digestive enzymes: properties, compartmentalization and function[END_REF]. The sharing of enzymes has been reported as a likely benefit of calliphorid larval aggregation, but this idea has never been demonstrated [START_REF] Ireland | The effects of larval crowding and food type on the size and development of the blowfly, Calliphora vomitoria[END_REF][START_REF] Reis | Larval aggregation and competition for food in experimental populations of Chrysomya putoria (Wied.) and Cochliomyia macellaria (F.) (Dipt., Calliphoridae)[END_REF][START_REF] Rivers | Physiological trade-offs of forming maggot masses by necrophagous flies on vertebrate carrion[END_REF]. To test the hypothesis of collective benefits through exodigestion, L. sericata larvae were bred at different larval densities. Two hypotheses were experimentally tested: (1) larval development speed and survival increases with increasing larval density, and ( 2) larval development speed and survival increases with increasing food digestibility.

MATERIALS AND METHODS

Ethical note

This research adheres to the ASAB/ABS Guidelines for the Use of Animals in Research, the legal requirements of the country in which the work was conducted, and all institutional guidelines. During the design of the study, a minimum of manipulation with a minimum of used animals was sought.

Insect rearing

Lucilia sericata larvae were obtained from adult flies bred in the laboratory and maintained in tulle cages (50x50x50 cm) at room temperature (23±2°C). Wild flies, 100 to 200, were added every 2 months. The flies were fed caster sugar and water ad libitum. After each new generation, minced beef liver was added for 7 days to provide proteins for vitellogenesis and then removed. Laying of eggs was triggered with the placement of 25±5 g of beef liver for 2 h (from 10 a.m. to midday) in cages. Oviposition time (precision ±1 h) was noted as D -1 (see Fig. 1).

Larval development

A density-dependent increase in competition is found in many blowfly developmental studies (see Table A1). In some studies, measurements were conducted during the feeding of instars, which likely disrupts aggregates and prevents detection of any social benefit [START_REF] Martinez Sanchez | Geographic origin affects larval competitive ability in European populations of the blowfly, Lucilia sericata[END_REF][START_REF] Simkiss | Thermoregulation in larval aggregations of carrion-feeding blow flies (Diptera: Calliphoridae)[END_REF]. Many others suffer from a lack of statistical power (few replications, time between measures too long) [START_REF] Martinez Sanchez | Geographic origin affects larval competitive ability in European populations of the blowfly, Lucilia sericata[END_REF][START_REF] Reigada | Larval density, temperature and biological aspects of Chrysomya megacephala (Diptera: Calliphoridae)[END_REF]Saunders & Bee, 1995;[START_REF] Serra | Allee effect in exotic and introduced blowflies[END_REF]. Finally, many authors used mixed liver or synthetic medium to feed larvae [START_REF] Martinez Sanchez | Geographic origin affects larval competitive ability in European populations of the blowfly, Lucilia sericata[END_REF][START_REF] Reis | Larval aggregation and competition for food in experimental populations of Chrysomya putoria (Wied.) and Cochliomyia macellaria (F.) (Dipt., Calliphoridae)[END_REF][START_REF] Simkiss | Thermoregulation in larval aggregations of carrion-feeding blow flies (Diptera: Calliphoridae)[END_REF][START_REF] Smith | Asymmetric competition between larvae of the blowflies Calliphora vicina and Lucilia sericata in carrion[END_REF]. These food sources are more digestible and less nutritious than muscular tissues and significantly affect larval development [START_REF] Barnes | Rearing bacteria and maggots concurrently: a protocol using Lucilia sericata (Diptera: Calliphoridae) as a model species[END_REF][START_REF] Bernhardt | Of pigs and mencomparing the development of Calliphora vicina (Diptera: Calliphoridae) on human and porcine tissue[END_REF][START_REF] El-Moaty | Developmental variation of the blow fly Lucilia sericata (Meigen, 1826) (Diptera: Calliphoridae) by different substrate tissue types[END_REF][START_REF] Pérez | Evaluating the biological cycle and reproductive and population parameters of Calliphora vicina (Diptera: Calliphoridae) reared on three different diets[END_REF][START_REF] Pérez | Evaluating the biological cycle and reproductive and population parameters of Calliphora vicina (Diptera: Calliphoridae) reared on three different diets[END_REF][START_REF] Rueda | Lucilia sericata strain from Colombia: experimental colonization, life tables and evaluation of two artificial diets of the blowfy Lucilia sericata (Meigen) (Diptera: Calliphoridae), Bogotá, Colombia Strain[END_REF][START_REF] Tachibana | An artificial diet for blow fly larvae, Lucilia sericata (Meigen) (Diptera: Calliphoridae)[END_REF]. By contrast, our experiments were performed with relevant larval densities feeding on beef muscle, a realistic food source.

All experiments on development were conducted from January to May 2017 in a thermostatic chamber set at 25±0.1°C with constant ventilation (ST4; POL-EKO Aparatura®, Wodzisław Śląski, Poland). A 12:12 h photoperiod cycle was obtained with a fluorescent tube placed inside the incubator (430 lumens, light from 9:30 a.m. to 9:30 p.m.).

Eggs obtained at Day -1 were incubated for 22 h, and then first instars were counted and placed in boxes containing food (D0). Each box was placed in a second box containing 1 cm of sand. All experiments were performed at 25°C. Two independent variables were studied: the initial number of larvae (i.e., larval density) and the digestibility of the food. Six replications for densities d10, d50, d100, and d250 and three replications for density d500 were prepared for each food type.

Two independent variables were studied: the initial larval population (i.e., larval density) and the digestibility of the food. The larval densities (d) tested were 10, 50, 100, 250 and 500 larvae per 50±1 g of food, low enough to prevent maggot-mass effect (i.e significant local temperature increase, [START_REF] Charabidze | Larval-mass effect: Characterisation of heat emission by necrophageous blowflies (Diptera: Calliphoridae) larval aggregates[END_REF]. Two types of food were used: the control food (C) was 50±1 g of minced beef muscle at 15% fat mixed with 15 mL of 0.9% NaCl, and pre-digested food (Tr) was obtained with the same meat mixed with 50±0.5 mg of trypsin (Trypsin T4799, porcine pancreas; Sigma-Aldrich®) diluted in 15 mL of 0.9% NaCl. The addition of trypsin changes food digestibility (the size of the molecules) but not the composition or nutritional value of the meat. The beef muscle was thawed for 6h at ambient temperature, mixed according to the twoabovementioned modalities and placed in translucent polypropylene boxes (100x75x63 mm). Six replications for densities d10, d50, d100, and d250 and three replications for density d500 were prepared for each food type.

Experimental procedure

The eggs obtained at D-1 were incubated at 25°C for 22 h (first instar; see Fig. 1) [START_REF] Grassberger | Effect of temperature on Lucilia sericata (Diptera: Calliphoridae) development with special reference to the isomegalen-and isomorphendiagram[END_REF]. The next day (D0), young first instars were counted and placed in the boxes containing food. Each box was placed in a second translucent polypropylene box (180x135x195 mm) containing 1 cm of sand. To preserve aggregation and avoid disturbance of feeding larvae, no measurements were performed on feeding instars. Only wandering larvae (also called post-feeding larvae,

i.e., third instar larvae that had finished feeding and left the food) were measured. The post-feeding larvae and adult flies were checked three times a day (10:00 a.m., 4:00 p.m., 10:00 p.m.).

Post-feeding larvae found in the sand were quickly rinsed with water and dried on absorbent paper. After weighing (Kern® ALT310-4, Grass Valley, USA), these postfeeding larvae were placed in new boxes (100x75x63 mm) containing 1 cm of sand.

The few larvae that left the food before the third instar or weighed less than 25 mg (below the first percentile) were not counted as post-feeding larvae. The mortality rate to post-feeding and the weighted mean of larval weights per replication were calculated.

Newly emerged flies were sampled, left in development for at least 6 h, and then sacrificed by freezing. The flies were sorted by sex using cephalic morphology [START_REF] Erzinçlioglu | Blowflies[END_REF]. The area of the right wing was measured to estimate the sizes of males and females (Saunders & Bee, 1995). Data were recorded by taking pictures of dissected and flattened right wings, with the surface area determined using ImageJ software (version 1.51j8, Wayne Rasband, National Institutes of Health, USA, public domain). All female and male flies from densities 10 and 50 were analysed. Random samples of 25 male flies and 25 female flies per replication were analysed for the densities 100, 250 and 500.

Statistical analyses

Statistical tests were conducted bilaterally, with a significance threshold of α=0.05.

When appropriate, 95% bilateral confidence intervals are presented. All data were analysed with R software via R studio (R version 3. The odds ratio (OR) of each explicative variable was calculated, which provides an estimate (with confidence interval) for the relationship between two binary variables: when the OR is greater than 1, the two variables are considered associated.

Chi-square tests were used to compare mortality rates by food type, and when significance was detected, pairwise post hoc tests were applied.

Two-way ANOVAs (density, food) were used to compare morphometric parameters (size and mass). The data for size of flies from the few individuals of the d10 larval density were insufficient (or even absent for one sex); therefore, we excluded the d10 data from the ANOVAs: only descriptive results are presented.

RESULTS

Effects of larval density

The proportions of post-feeding larvae according to development time are shown in

Effects of food digestibility (addition of trypsin)

The addition of trypsin reduced larval development time at low densities, but did not eliminated the benefits of gregariousness at highest densities (P<0.001; see Fig. 2(b)).

Compared with the control food, the average larval development time on trypsin-added food was shorter at d10 and d50 (P<0.001), was similar at d100 (P=0.27) and was longer at d250 and d500 (P<0.001 and P=0.01, respectively) (see Fig. 5). Development = 31.4 [8.7-207.4] and 74.9 [20.7-499.8], respectively; see Fig. 3(b) and Fig. A1).

Larval mortality rates on trypsin-added food were also influenced by larval density (X²=45.5, P<0.001), with the mortality at d500 significantly lower than that at other densities (P<0.001, pairwise post hoc tests, see Fig. 4). No significant effect of trypsin on the total development time was detected, with the following p-values: d10: P=0.08; d50: P=0.30; d100: P=0.91; d250: P=0.97; and d500, P=0.17).

Morphometrics

The mean weight (± standard error) of post-feeding larvae was 55±0.4 mg (all conditions combined). Larval density (F=1.41, P=0.24) or food type (F=1.93, P=0.17)

did not affect the weight (see Fig . A2).

The male to female sex ratio was 0.99±0.

DISCUSSION

Experiments demonstrated (1) a decrease in development time and mortality with increasing larval density and (2) a decrease in development time and mortality on highdigestible food compared with low-digestible food (at low densities of larvae). These results provide evidence of the benefits of collective exodigestion and aggregation and possibly of much larger consequences at the community level such as niche partitioning.

Aggregation of necrophagous larvae is consistent with the Allee effect

Increasing larval density resulted in better development of L. sericata larvae on the control fresh meat. With the increase in larval density, (i) L. sericata development time was reduced, and (ii) mortality decreased. Due to the selection pressure on the feeding maggots (competition with scavengers, food shortage, parasitism and interspecific/interkingdom competition), their survival notably depends on development time [START_REF] Benbow | Carrion Ecology, Evolution, and Their Applications[END_REF][START_REF] Devault | Factors influencing the acquisition of rodent carrion by vertebrate scavengers and decomposers[END_REF][START_REF] Frederickx | The community of Hymenoptera parasitizing necrophagous Diptera in an urban biotope[END_REF][START_REF] Hanski | Carrion fly community dynamics: patchiness, seasonality and coexistence[END_REF][START_REF] Jordan | Abiotic and biotic factors regulating interkingdom engagement between insects and microbe activity on vertebrate remains[END_REF]. Thus, the observed difference in developmental time with density might have even more dramatic impact on larval survival in the field.

Furthermore, larval density did not affect adult fly morphometrics: larvae growing in the large groups assimilated sufficient food fast enough not to affect their metamorphosis and final size/weight [START_REF] Charabidze | Discontinuous foraging behavior of necrophagous Lucilia sericata (Meigen 1826) (Diptera Calliphoridae) larvae[END_REF]. As the fertility of a female depends on its size (Saunders & Bee, 1995), we reasonably concluded that increased density had no deleterious effect and positively affected population fitness, which is a result consistent with the predictions of the Allee effect (i.e., a positive relationship between fitness and population size) [START_REF] Allee | Animal Aggregations[END_REF][START_REF] Courchamp | Allee Effects in Ecology and Conservation[END_REF].

Inside larval masses, two collective strategies likely act synergistically. Maggot-mass effect, which is a local temperature increase inside large aggregates, was formerly postulated as one of the primary benefits of larval pre-social behaviour [START_REF] Rivers | Physiological trade-offs of forming maggot masses by necrophagous flies on vertebrate carrion[END_REF][START_REF] Rivers | Oviposition restraint and developmental alterations in the ectoparasitic wasp, Nasonia vitripennis, when utilizing puparia resulting from different size maggot masses of Lucilia illustris, Protophormia terraenovae, and Sarcophaga bullata[END_REF]. However, significant local warming requires many more larvae than those used for this study (see Fig. A4). As an example, a 24-h decrease in development time as we observed with 250 larvae groups in the present work would require a local temperature shift from 25°C to 34°C [START_REF] Grassberger | Effect of temperature on Lucilia sericata (Diptera: Calliphoridae) development with special reference to the isomegalen-and isomorphendiagram[END_REF], which is warming that is only reached above 5690 aggregated larvae [START_REF] Charabidze | Larval-mass effect: Characterisation of heat emission by necrophageous blowflies (Diptera: Calliphoridae) larval aggregates[END_REF]. By contrast, exodigestion occurs at the scale of a single egg-batch (circa 200 larvae) and is fully efficient as soon as a few hundred larvae aggregate and feed together. This initial benefit can be reinforced by the aggregation of additional larvae, resulting in maggot masses sufficiently large to increase local temperature (see Fig. 6 and7).

This aggregation strategy of necrophagous blowflies may rely on the genetic proximity of feeding larvae, a result previously described in caterpillars [START_REF] Tsubaki | Group feeding as a strategy for exploiting food resources in the burnet moth Pryeria sinica[END_REF]. Indeed, the genetic affinity within aggregated larvae is inherently close: each female fly lays egg batches of circa 200 eggs, resulting in hundreds of aggregated offspring [START_REF] Wall | Evolutionary ecology of communication signals that induce aggregative behaviour[END_REF]. [START_REF] Picard | The population genetic structure of North American Lucilia sericata (Diptera: Calliphoridae), and the utility of genetic assignment methods for reconstruction of postmortem corpse relocation[END_REF] also found that gravid females ready to oviposit on the same carcass showed a pattern of relatively high relatedness.

Gregariousness may be a blowfly adaptive strategy to breed on fresh carcasses

The results obtained with trypsin-added food also highlight the benefits of aggregation.

Compared with those fed fresh control food, larvae fed on high-digestibility food had reduced average mortality and slightly faster development. Therefore, we assumed that the increased development and reduced mortality of aggregated larvae resulted in part from chemical degradation (pooling of enzymes). Consistent with this idea, [START_REF] Wilson | The impacts of larval density and protease inhibition on feeding in medicinal larvae of the greenbottle fly Lucilia sericata[END_REF] demonstrated that the addition of a trypsin inhibitor drastically reduces exodigestion and slows L. sericata larval growth. [START_REF] Green | Does the size of larval groups influence the effect of metabolic inhibitors on the development of Phormia regina (Diptera: Calliphoridae) larvae?[END_REF] also showed that feeding activity of groups of Phormia regina larvae has a greater effect on the chemical nature of the diet surfaces than the feeding of isolated larvae. However, while trypsinadded food significantly decreased mortality rates at d10, this increased survival was offset by a higher mortality during post-feeding instars (see Fig. 4). This "catching up" effect resulted in a similar global (i.e. first instar to emergence) mortality on both food types. One likely hypothesis is that the addition of trypsin facilitates the ingestion and digestion of the food, and thus allows the weakest larvae (those whom died on control experiments) to survive artificially [START_REF] Barnard | Influence of Larval Density and Temperature in Poultry Manure on Development of the House Fly (Diptera: Muscidae)[END_REF]. However, many of these larvae were living on borrowed time and they died during post-feeding or pupal development. Furthermore, the addition of trypsin did not completely eliminate the benefits of gregariousness in terms of development time (electronic Table A1). Two cofactors of exodigestion might explain why trypsin does not fully imitate the properties of aggregated larvae. First, larval alkalisation of the medium can increase the pHdependent enzymatic degradation [START_REF] Hobson | Studies on the nutrition of blow-fly larvae : I. Structure and function of the alimentary tract[END_REF]. Second, a density-dependent selection of competing bacteria may be an important consequence of larval aggregation [START_REF] Arce | Antimicrobial secretions and social immunity in larval burying beetles, Nicrophorus vespilloides[END_REF]. Indeed, Janzen's "spoiling theory" [START_REF] Janzen | Why fruits rot, seeds mold, and meat spoils[END_REF] hypothesises that bacterial decomposers should produce compounds that cause rich and ephemeral resources to rot, rendering them unpalatable, whereas animals should evolve adaptive strategies of avoidance or detoxification. Thus, carrion is the site of an intense interkingdom competition between insects and microbial decomposers [START_REF] Burkepile | Chemically mediated competition between microbes and animals: microbes as consumers in food webs[END_REF][START_REF] Jordan | Abiotic and biotic factors regulating interkingdom engagement between insects and microbe activity on vertebrate remains[END_REF][START_REF] Young | An investigation of red fox (Vulpes vulpes) and eurasian badger (Meles meles) scavenging, scattering, and removal of deer remains: forensic implications and applications[END_REF]. In this context, burying beetles can cooperate to bury a carcass and limit microbial proliferation [START_REF] Eggert | Timing of oviposition enables dominant female burying beetles to destroy brood-parasitic young[END_REF][START_REF] Sun | Climate-mediated cooperation promotes niche expansion in burying beetles[END_REF][START_REF] Trumbo | Feeding upon and preserving a carcass: the function of prehatch parental care in a burying beetle[END_REF], and blowfly larvae secrete/excrete efficient antimicrobial peptides, which is a property used in larval debridement therapies [START_REF] Teh | Determination of antibacterial activity and minimum inhibitory concentration of larval extract of fly via resazurin-based turbidometric assay[END_REF]. Therefore, larval aggregation may be an adaptive response that locally limits bacterial proliferation and spoiling (see Fig. 7).

Conclusions

The present work demonstrates that calliphorid larvae pre-social behaviour not only results in significant benefits throughout larval development but also may act as a niche-separation mechanism. It has been demonstrated that fly egg-laying strategies can facilitate coexistence in carrion fly communities [START_REF] Hanski | An interpolation model of assimilation by larvae of the blowfly Lucilia illustris (Calliphoridae) in changing temperatures[END_REF][START_REF] Ives | The optimal clutch size when many females oviposit per patch[END_REF][START_REF] Ives | Aggregation and coexistence in a carrion fly community[END_REF][START_REF] Kouki | Population aggregation facilitates coexistence of many competing carrion fly species[END_REF][START_REF] Kuusela | The structure of carrion fly communities : the size and the type of carrion[END_REF][START_REF] Prinkkilá | Complex competitive interactions in four species of Lucilia blowflies[END_REF][START_REF] Spindola | Attraction and oviposition of Lucilia eximia (diptera: calliphoridae) to resources colonized by the invasive competitor Chrysomya albiceps (Diptera: Calliphoridae)[END_REF]. Progressing through the stages of decomposition, a carcass becomes attractive to a relatively predictable sequence of insects [START_REF] Matuszewski | Insect succession and carrion decomposition in selected forests of Central Europe. Part 3: Succession of carrion fauna[END_REF][START_REF] Megnin | La faune des cadavres: application de l'entomologie à la médecine légale[END_REF]. Although highly nutritional, fresh meat is more difficult to ingest and digest than decayed meat [START_REF] Benbow | Carrion Ecology, Evolution, and Their Applications[END_REF]. By mutualising exodigestion, calliphorid larvae (i.e., pioneer species) possibly make a food source avoided by other necrophagous species more edible. This hypothesis is consistent with the idea that cooperation may enable species to expand their niches (the so-called 'social conquest hypothesis') [START_REF] Brooks | Ecological generalism facilitates the evolution of sociality in snapping shrimps[END_REF].

Figure 1 :

 1 Figure 1: Chronological diagram of the experimental process. D -1 is the time of oviposition (±1 h). Larvae were counted and placed on food on the next day (D 0 ). D x is the first post-feeding larva and D y is the first emerging fly.

  3.2©2016; The R foundation for Statistical Computing | Version 1.0.136©2009-2016 RStudio Inc.). A logistic regression model (quasibinomial with a link function cauchit) was used for the statistical analysis of larval development times. The variables to explain were (i) the proportion of post-feeding larvae and (ii) the flies present during the respective periods from D2 to D5 and D11 to D15. A step-by-step selection technique was used to improve the model. The AIC criterion (Akaike Information Criterion) was used to determine the quality of a model. For this reason, the model was applied to each food type separately, with time and larval density as explicative factors. Then, the model was applied to compare the effect of food at each density, with time and substrate the explicative factors. ANOVA was used to determine the significance of the model factors.

Fig. 2 (

 2 Fig.2(a) (control food condition). The logistic regression model showed a significant effect of larval density on the proportion of post-feeding larvae (P<0.001). The

Figure 2 :

 2 Figure 2: Kinetics of transition from larvae to post-feeding instars: (a). control food; (b).food with addition of trypsin. Percentages ± SE of post-feeding larvae are given in relation to larval densities. Odds ratios with 95% confidence interval of the logistic

Figure 3 :

 3 Figure 3: Kinetics of imago emergence: (a) control food; (b) food with addition of trypsin. Percentages ± SE of imagos are given in relation to larval densities. Odds ratios with 95% confidence interval of the logistic regressions are also given. d = no. of larvae / 50 g of food; NS. = not significant; *** P<0.001.

Figure 4 :

 4 Figure 4: Average mortality rate (numbers in bars) ± SE from first instar (a) to postfeeding and (b) to emergence. C = control food; Tr = trypsin-added food; densities = no. of larvae / 50 g food. Columns with the same letters are not significantly different (P>0.05).

Figure 5 :

 5 Figure 5: Odds ratios with 95% confidence interval of the effect of trypsin-added food versus control food for larval development time (first instar to post-feeding). d = no. of larvae / 50 g of food; Tr = trypsin-food; C = control food; NS. = not significant; ** P<0.01, *** P<0.001.

Figure 6 :

 6 Figure 6: Schema of the benefit to development speed (i.e. gain) of increasing numbers of aggregated larvae. .

Figure 7 :

 7 Figure 7: Summary of demonstrated (solid arrows) or hypothetical (dotted arrows) benefits of necrophagous larvae gregariousness.

Figure A1 Figure A1 :

 A1A1 Figure A1

Figure A2 Figure A2 :

 A2A2 Figure A2

Figure A3 Figure A3 :Figure A4 Figure A4 :

 A3A3A4A4 Figure A3

Table 1 :

 1 The benefits and costs of gregariousness necrophagous larvae of calliphorids flies.

  003 and was not modified by experimental conditions (X²=5.84, P=0.76). Wing surface area of the flies (see Fig A3) was not affected by larval density or by food type for either females (F=1.81, P=0.14; F=0.40,

	P=0.53, respectively) or males (F=2.24, P=0.08; F=1.63, P=0.20, respectively). The
	mean right wing surface area was 15.7±0.1 mm² for females and 13.1±0.1 mm² for
	males. As expected, males were smaller than females (F=922.2, P<0.001).

Prinkkilä et al. ,

 Dos Reis et al. ,

Acknowledgments

We thank M. Lihoreau for his helpful comments and the referees who helped us improve the manuscript significantly.

We received no funding for this study.