I S I S S A N P E R A -C A L B E T * , † , A N T O I N E L E C E R F * , † A N D E R I C C H A U V E T

Isis Sanpera-Calbet

Leaf diversity influences in-stream litter decomposition through effects on shredders

Keywords: biodiversity, leaf mixing, litter breakdown, shredders, terrestrial-aquatic linkage

1. The functioning of many aquatic ecosystems is controlled by surrounding terrestrial ecosystems. In a view of growing interest in linking biodiversity to ecosystem-level processes, we examined whether and how leaf diversity influences litter decomposition and consumers in streams. 2. We tested experimentally the hypothesis that the effects of leaf diversity on decomposition are determined by the responses of leaf consumers to resource-habitat heterogeneity. Leaves from three common riparian trees, beech (Fagus sylvatica), hazel (Corylus avellana) and ash (Fraxinus excelsior), were exposed alone and in all possible mixtures of two and three species in a stream. We analysed individual leaf species for decomposition rate, microbial respiration and mycelial biomass, and we determined the species composition, abundance and biomass of shredders in leaf bags. 3. We found that the decomposition of the fastest decomposing leaves (hazel and ash) was substantially stimulated (up to twofold higher than single species leaf packs) in mixtures containing beech leaves, which are refractory. In contrast, the decomposition of beech leaves was not affected by leaf mixing. Such species-specific behaviour of leaves in species mixtures has been overlooked in previous studies that examined the overall decomposition of litter mixtures. 4. The effects of leaf diversity on decomposition varied with the abundance and biomass of shredders but not with microbial parameters. Beech leaves alone were less attractive to shredders than leaf packs made of hazel, ash or any mixture of species. Moreover, the presence of beech leaves in mixtures led to higher shredder abundance and biomass than we had expected from data from single species exposed alone. Lastly, we found that early instars of the caddisfly Potamophylax (the dominant shredder in terms of biomass) almost exclusively used the toughest material (i.e. beech leaves) to construct their cases. 5. Leaf pack heterogeneity may have altered shredder-mediated decomposition. Shredders colonising diverse leaf packs benefited from the stable substratum provided by beech leaves, whereas ash and hazel leaves were primarily used as food. Thus, our findings provide strong evidence for an intimate linkage between the diversity of riparian vegetation and aquatic communities.

Introduction

Leaf litter supplied by riparian vegetation is an essential resource to the food webs of forest streams [START_REF] Cummins | Shredders and riparian vegetation[END_REF][START_REF] Wallace | Multiple trophic levels of a forest stream linked to terrestrial litter inputs[END_REF]. There is compelling evidence that the amount of litter input is a limiting factor for in-stream secondary production [START_REF] Richardson | Seasonal food limitation of detritivores in a montane stream: an experimental test[END_REF][START_REF] Dobson | A test of resource limitation among shredding detritivores in low order streams in southern England[END_REF][START_REF] Wallace | Multiple trophic levels of a forest stream linked to terrestrial litter inputs[END_REF]. A complementary issue is the consequence for streams of qualitative variations in litterfall, such as those resulting from differences in forest structure and composition [START_REF] Cummins | Shredders and riparian vegetation[END_REF][START_REF] Griffith | Leaf pack processing in two Appalachian mountain streams draining catchments with different management histories[END_REF][START_REF] Pozo | Afforestation with Eucalyptus globulus and leaf litter decomposition in streams of northern Spain[END_REF][START_REF] Benfield | Long-term patterns in leaf breakdown in streams in response to watershed logging[END_REF][START_REF] Lecerf | Riparian plant species loss alters trophic dynamics in detritus-based stream ecosystems[END_REF]Lecerf et al., , 2007a;;Ferreira et al., 2006a).

According to [START_REF] Cummins | Shredders and riparian vegetation[END_REF], diverse riparian vegetation that produces leaf litter of different degradability would promote efficiency of resource use by leaf-shredding detritivores (hereafter shredders). Degradability refers to variation in the rate of leaf decomposition associated with various physical (e.g. toughness) and chemical (e.g. contents in nutrients and soluble and insoluble organic compounds) leaf traits [START_REF] Gessner | Importance of stream microfungi in controlling breakdown rates of leaf litter[END_REF]Lecerf & Chauvet, 2008b;[START_REF] Hladyz | Resource quality and stoichiometric constraints on stream ecosystem functioning[END_REF]. Labile leaf species are rapidly exploited by shredders, whereas microbial decomposers largely account for initial processing of slow decomposing leaf species and improve leaf palatability [START_REF] Cummins | Shredders and riparian vegetation[END_REF].

Consistently, leaf decomposition rate has been found to be higher in streams lined by species-rich forest than in adjacent streams lined by species-poor forest [START_REF] Pozo | Afforestation with Eucalyptus globulus and leaf litter decomposition in streams of northern Spain[END_REF][START_REF] Lecerf | Riparian plant species loss alters trophic dynamics in detritus-based stream ecosystems[END_REF]Ferreira et al., 2006a). This may be due to the effect of resource-habitat heterogeneity on the structure and activity of consumer assemblages in streams running through species-rich forests [START_REF] Lecerf | Riparian plant species loss alters trophic dynamics in detritus-based stream ecosystems[END_REF](Lecerf et al., , 2007a;;[START_REF] Kominoski | Nonadditive effects of leaf litter species diversity on breakdown dynamics in a detritus-based stream[END_REF][START_REF] Swan | The role of native riparian tree species in decomposition of invasive Tree of Heaven (Ailanthus altissima) leaf litter in an urban stream[END_REF]. It is possible, however, that the amount of labile litter (i.e. fast decomposing species) among that retained in streams is more important than leaf diversity per se in controlling the effect of forest diversity on litter dynamics [START_REF] Griffith | Leaf pack processing in two Appalachian mountain streams draining catchments with different management histories[END_REF][START_REF] Benfield | Long-term patterns in leaf breakdown in streams in response to watershed logging[END_REF].

How the diversity and composition of riparian vegetation really influences stream ecosystems can be properly addressed through in situ experimental manipulation of leaf species number and identity. With the notable exception of an earlier study conducted at the reach scale [START_REF] Sweeney | Growth and production of a stream stonefly: influences of diet and temperature[END_REF], such experiments have been carried out at the patch scale using leaf bags exposed in streams (e.g. [START_REF] Swan | Leaf diversity alters litter breakdown in a Piedmont stream[END_REF][START_REF] Kominoski | Nonadditive effects of leaf litter species diversity on breakdown dynamics in a detritus-based stream[END_REF]Lecerf et al., 2007b). Mixing leaves has been reported to have non-additive effects on leaf decomposition, such as those measured by the deviation between observed decomposition rate and an expected value calculated from single species alone [START_REF] Wardle | Biodiversity and plant litter: experimental evidence which does not support the view that enhanced species richness improves ecosystem function[END_REF][START_REF] Swan | Leaf diversity alters litter breakdown in a Piedmont stream[END_REF]Lecerf et al., 2007b).

Non-additive effects have been hypothesised to be due: (i) to the presence ⁄ absence of leaf species having particular characteristics [START_REF] Wardle | Biodiversity and plant litter: experimental evidence which does not support the view that enhanced species richness improves ecosystem function[END_REF] or (ii) to emergent effects of leaf pack heterogeneity [START_REF] Epps | Chemical diversity -highlighting a species richness and ecosystem function disconnect[END_REF]. Hypothesis 1 assumes that a single leaf species with atypical traits invariably has the same directional effect on the decomposition of other component species. This may be due to the translocation of stimulating (nutrients, vitamins, labile carbon) or inhibitory (polyphenols) compounds from leaf species with high concentrations to those poor in such elements [START_REF] Mcarthur | Interspecific leaf interactions during decomposition in aquatic and floodplain ecosystems[END_REF]. Alternatively, tough leaves may decelerate the decomposition of fragile leaves affected by intense physical abrasion (i.e. an armouring effect: [START_REF] Swan | The role of native riparian tree species in decomposition of invasive Tree of Heaven (Ailanthus altissima) leaf litter in an urban stream[END_REF]. Hypothesis 2 assumes that differences in physical and chemical traits among individual leaf species create a heterogeneous micro-environment and food resources that enhance coexistence and complementarity of leaf consumers, ultimately resulting in higher consumption rates of all the leaf component species [START_REF] Leff | The effect of leaf pack composition on processing: a comparison of mixed and single species packs[END_REF][START_REF] Bastian | Effects of diversity loss on ecosystem function across trophic levels and ecosystems: a test in a detritus-based tropical food web[END_REF].

Elucidating the relative importance of key leaf species and leaf pack heterogeneity in mediating the effects of leaf diversity on decomposition can be achieved by examining: (i) the decomposition rate of individual leaf species in mixtures [START_REF] Ostrofsky | A comment on the use of exponential decay models to test non-additive processing hypotheses in multi-species mixtures of litter[END_REF] and (ii) leaf consumer assemblages. It is worth noting that the conclusions of most in situ studies rely on the decomposition rate of leaf mixtures as a whole. This approach can mask the species-specific behaviour of leaves in diverse mixtures [START_REF] Ha ¨ttenschwiler | Biodiversity and litter decomposition in terrestrial ecosystems[END_REF]. The few studies that have isolated leaf species effects were limited either to a single mixture of leaves [START_REF] Leff | The effect of leaf pack composition on processing: a comparison of mixed and single species packs[END_REF][START_REF] Mcarthur | Interspecific leaf interactions during decomposition in aquatic and floodplain ecosystems[END_REF][START_REF] Moretti | Leaf breakdown in two tropical streams: differences between single and mixed species packs[END_REF] or a single leaf species isolated from several mixtures [START_REF] Swan | The role of native riparian tree species in decomposition of invasive Tree of Heaven (Ailanthus altissima) leaf litter in an urban stream[END_REF].

In this study, we examined whether and how mixtures of leaves, which reflect the riparian vegetation diversity, influence decomposition and stream consumers. From the results of a previous field survey [START_REF] Lecerf | Riparian plant species loss alters trophic dynamics in detritus-based stream ecosystems[END_REF], we predicted decomposition of a refractory leaf species (beech) to be faster when mixed with more labile leaves. We also expected this increase to be proportional to the degree of heterogeneity of leaf packs. To conduct our experiment we selected a stream with a very high diversity of shredders and leaf litter.

Methods

Study area

The experiment was conducted in the Ruisseau de Peyreblanque, a second-order forested stream situated in the Montagne Noire, SW France (43°25¢52¢¢N, 2°13¢12¢¢E, altitude 750 m). Riparian vegetation consisted of mixed deciduous tree species dominated by beech (Fagus silvatica L.). The streambed was composed of heterogeneous sediments dominated by sand and gravel along with large boulders. In this region, there is a variety of shredders, such as amphipods, stoneflies and caddisflies [START_REF] Dobson | Microhabitat as a determinant of diversity: stream invertebrates colonizing leaf packs[END_REF][START_REF] Lecerf | Riparian plant species loss alters trophic dynamics in detritus-based stream ecosystems[END_REF]. The slightly acidic water (pH: 5.5-6.4; alkalinity: 2.0-8.0 mg CaCO 3 L )1 ) in the study stream has probably prevented amphipods (Gammarus) from dominating the shredder assemblage. Microbial activity is limited by the low P concentration (1.4-2.4 lg SRP L )1 ). In contrast, biological N demand was probably saturated by the high nitrate concentrations (>300 lg NO 3 -N L )1 ; Lecerf & Chauvet, 2008a;Ferreira, Gulis & Grac ¸a, 2006b). Water temperature ranged from 2.5 to 7.0 °C during the course of the experiment.

Leaf bags

We selected three co-occurring tree species known to produce leaf litter of contrasting quality. Ash (Fraxinus excelsior L.) and beech leaves are among the fastest and slowest decomposing species within this region, respectively, which is consistent with their N content (Lecerf et al., 2007b; Table 1). Hazel (Corylus avellana L.) was chosen for its intermediate degradability and toughness as indicated by acid detergent fibre content, i.e. fibre containing cellulose and lignin (Table 1). These three leaf species were exposed in the stream alone and in all possible species combinations.

Freshly abscised leaves were collected from the ground. These leaves were returned to the laboratory shortly after collection. Leaves were not air-dried before leaf bag construction in order to preserve their physical and chemical integrity [START_REF] Gessner | Differences in processing dynamics of fresh and dried leaf litter in a stream ecosystem[END_REF]. Due to differences in the moisture content of the leaf species, we standardised leaf batch size by leaf area. The total size of each batch of leaves was 1116.5 ± 6.5 cm 2 (mean ± SE), which was divided evenly among component species in mixtures. Leaf area was estimated by weighing the fresh leaves and using the mass-to-surface area ratios determined for this study. On a dry mass basis, the beech-ash mixture contained equal amounts of both, whereas other mixtures contained a lower proportion of hazel leaves than of beech or ash (Table 1).

The leaf packs were enclosed in 10-mm mesh bags constructed of rigid plastic net and closed in a tetrahedral shape [START_REF] Jonsson | Leaf litter breakdown rates in boreal streams: does shredder species richness matter?[END_REF]. They were stored overnight in plastic bags at 4 °C and then transported to the field. Iron bars driven into the sediment were used to secure the bags in the stream. The seven species combinations were replicated four times using four shallow riffles as random blocks. Leaf bags were harvested after 10, 40 and 81 days of exposure in the stream to achieve roughly 25%, 50% and 75% of leaf mass loss in the three-species mixture. The samples were stored individually in zip-lock bags and transported to the laboratory in a coolbox. Four extra batches of each leaf species were used to determine the initial leaf dry mass by unit of leaf fresh mass.

Leaves were carefully washed with tap water to remove fine debris and sediment. The invertebrates retained in a 0.5-mm sieve were preserved in 70% alcohol until processing. Remaining leaves in mixtures were sorted by species, and each leaf species was analysed individually for leaf dry mass and microbial parameters. For the determination of leaf-associated microbial respiration rate and mycelial biomass, two sets of five 10-mm leaf discs were cut from three to five leaves of each species (avoiding central veins). Due to rapid decomposition of hazel and ash leaves, there was insufficient leaf material remaining to cut whole discs of these species from several samples collected at the second and third sampling occasions. The remaining leaf material was oven-dried at 105 °C for 48 h and weighed by species to the nearest 0.01 g.

Invertebrates

Shredders were identified to genus and counted [START_REF] Tachet | Inverte ´bre ´s d'eau douce. Syste ´matique[END_REF]. Other taxa with different feeding habits and diets were disregarded. After measurement of animal length to the nearest 0.5 mm, individual body mass was calculated using body length-dry mass relationships for European fauna [START_REF] Smock | Relationships between body size and biomass of aquatic insects[END_REF][START_REF] Meyer | The relationship between body length parameters and dry mass in running water invertebrates[END_REF][START_REF] Burgherr | Regression analysis of linear body dimensions vs. dry mass in stream macroinvertebrates[END_REF].

Microbial parameters

Microbial respiration was measured as the rate of oxygen consumption by microbial communities in decomposing leaves incubated at 10 °C. Five leaf discs of each species were placed in 3 mL of filtered (Whatman International, Florham Park, NJ, U.S.A.; 0.45 lm pore size) stream water in respiration chambers (Strathkelvin Instruments, Motherwell, U.K.). Oxygen concentration was recorded every second over a 1-h period. Oxygen consumption rate (lg O 2 g )1 leaf DM s )1 ) was estimated from the slope of the regression line of oxygen concentration versus time and related to leaf disc mass. This value was corrected for oxygen loss in a control chamber without leaf discs.

Mycelial biomass in leaves was assessed through the content of ergosterol [START_REF] Gessner | Ergosterol-to-biomass conversion factors for aquatic hyphomycetes[END_REF]. The method required a chemical extraction of ergosterol in each set of leaf discs, purification of the extracts using a solid-phase extraction cartridge and ergosterol quantification by high-performance liquid chromatography (procedure slightly modified from [START_REF] Gessner | Methods to Study Litter Decomposition: A Practical Guide[END_REF]. Mycelial biomass was calculated by applying a general conversion factor of 182 to the ergosterol mass. Results were expressed as fungal mass per leaf dry mass.

Statistics

An exponential daily decay rate (k) was calculated for each species decomposing alone or in mixtures, using a nonlinear regression of the proportion of leaf mass remaining versus time. Better R 2 for all regressions were achieved with a floating intercept, which did not significantly differ from the theoretical value of 1. Decomposition rates of a leaf species were compared among species combinations using generalised linear models based on the log-link function (Lecerf & Chauvet, 2008a). When k-values differed among species combinations according to a likelihood type III test, we conducted a likelihood type I test and sequential introduction of categorical variables to perform planned contrasts.

We used a two-way factorial A N O V A A N O V A to assess differences in shredder biomass per bag across leaf species combinations and exposure time. We then conducted a stepwise multiple regression to assess the relationship between shredder biomass and leaf mass remaining. A forward selection procedure was applied to identify the most important predictor among inter-correlated variables.

Observed shredder biomass in leaf mixtures was compared to the expected value from the component species exposed alone. This was calculated as the mean of total shredder biomass (by leaf mass) found in single species bags from the same riffle, weighted by the leaf mass remaining of each component species in mixtures (e.g. Lecerf et al., 2007b). Leaf mixing effects on the total number of shredders were assessed in the same way.

We compared shredder assemblages between species combinations using abundance data pooled across sampling dates and riffles. An individualbased rarefaction algorithm was used to correct generic richness for differences in the total number of invertebrates [START_REF] Gotelli | EcoSim: Null Models Software for Ecology. Version 7[END_REF]. We used the Mann-Whitney test to assess differences between treatment groups. Besides differences in diversity, we assessed differences in both structure and composition of shredder assemblages using the Bray-Curtis similarity index.

We assessed treatment effects on the body mass of the dominant shredder. We first calculated the median body mass of individuals for each leaf bag. The median was preferred over the mean due to a skewed distribution of body mass [START_REF] Sokal | Statistica 6.0: Electronic Statistics Text[END_REF].

A N O V A

A N O V A was then used to compare median body mass per leaf bag between treatments. Since the median was determined on samples of different size, each median was weighted by the ratio of the number of individuals per leaf bag to the grand sum of individuals.

A two-way factorial M A N O V A M A N O V A was used to assess variation in microbial parameters on a given leaf species, between species combinations and across time.

'Riffle' was included as a random factor in the linear models

, A N O V A A N O V A s and M A N O V A M A N O V A s
(see Table 2). Total shredder biomass and median body mass of Potamophylax were log-transformed to meet the assumptions of A N O V A A N O V A . Leaf mixing effects on total shredder biomass were indicated when the deviation between observed and expected values was significantly different from zero (one sample t-test).

S T A T I S T I C A

S T A T I S T I C A 6.0 (StatSoft Inc., 2001) was used for all statistical analyses.

Results

Leaf decomposition

Leaf decomposition rate varied by a factor of up to five among species exposed alone, representing a broad gradient of leaf degradability (Fig. 1). Ash leaves had been decomposed almost entirely before the last sampling date, so the rate for this species was calculated from the first two sampling dates only. The decomposition rate of beech leaves did not differ across species combination (Table 2: cf. interaction time-by-combination). In contrast, the decomposition rates of hazel (P = 0.0043) and ash (P = 0.0003) leaves were not consistent across species combinations (Table 2). Leaves of these two species decomposed up to twice as slowly when alone or mixed together as when mixed with beech leaves (Fig. 1). The presence ⁄ absence of beech leaves in leaf bags was thus a significant predictor of the decomposition rates of hazel (v 2 = 9.4, P = 0.0021) and ash (v 2 = 17.8, P < 0.0001). The residual variation of these two generalised linear models was not significantly related to species composition (likelihood type I test: v 2 < 3.7, P > 0.156), indicating that the presence ⁄ absence of beech leaves in leaf bags was a key determinant of mixing effects on decomposition.

Shredders

Although beech leaves persisted longer in the stream, shredders were half as abundant in beech-only leaf bags as in other species combinations (Table 3). On the first two sampling dates, total shredder biomass in leaf bags was found to be up to seven times lower in beech leaves exposed alone than in other monospecific or species mixture combinations (Fig. 2a). Such a difference was not observed on the later sampling date (Fig. 2a). Indeed, the effect of leaf species combination on total shredder biomass depended on time (interaction time-by-combination, P = 0.0114), and species combination per se had no significant effect (Table 2). Total shredder biomass significantly varied with time of exposure (Table 2). The amount of high quality leaves (sum of hazel and ash leaf mass) was the only significant variable in the stepwise multiple regression between shredder biomass and leaf mass remaining (F-to-enter = 21.1, P < 0.0001).

Total leaf quantity and the mass of each individual species were less powerful predictors of shredder biomass in bags (F-to-enter <10) and did not account for the residual variation (P > 0.50).

The total count of shredders from species mixtures with beech leaves was 25-30% higher than expected values calculated from single leaf species bags. In contrast, such a non-additive effect of leaf mixing on shredder abundance accounted only marginally (1%) for the total observed number of shredders in hazelash bags. Consistently, shredder biomass in leaf mixtures often deviated from values expected from biomasses associated with the component species alone in the same riffle (Fig. 2b). The deviation between observed and expected values was significantly different from zero overall (t 47 = 2.0, P = 0.0057). However, it is clear that the hazel-ash mixture did not behave like the three mixtures with beech leaves (Fig. 2b). In the former, observed shredder biomass was not statistically different than expected (t 11 = )0.27, P = 0.79), whereas the latter (i.e. mixtures including beech leaves) had higher shredder biomass than expected (t 35 = 2.9, P = 0.0021).

The shredder assemblage differed among species combinations in terms of diversity and structure. Estimated richness was higher in leaf bags with beech leaves than without (Mann-Whitney test: P = 0.0339; Table 3). Shredder assemblages did not strikingly differ among leaf species combinations (Bray-Curtis similarity index; n = 7 treatments; grand mean = 82%, SE = 1.9%). Twelve genera of shredders were identified (Table 3). Plecoptera dominated the assemblage numerically, with Amphinemura and Nemoura together representing more than half of the individuals counted. Non-plecopteran shredders consisted of Potamophylax, Gammarus and five rarer taxa. Potamophylax was found in 74 of the 84 leaf bags, accounting for an average of 72% of the total biomass of shredders. Biomass of other taxa was <5% of the total biomass.

Body size structure of the Potamophylax population varied in time and between leaf species combinations (Table 2). Median body mass per leaf bag increased from 10 to 40 days in all leaf species combinations (Fig. 3a). It fell below these values from 40 to 81 days in leaf bags without beech and the combination beech + hazel (Fig. 3a). Leaf bags with beech alone, in combination with ash leaves, and the three-species mixtures were colonised by bigger individuals than other leaf bags (Table 2: cf. species combination, Richness was estimated for 500 individuals. P = 0.0015), a fact that became even more obvious at the last sampling date (Table 2: cf. interaction time-bycombination: P = 0.0246; Fig. 3a).

Microbial parameters

Microbial parameters varied across leaf species and in time, whereas mixing leaf species had at most a weak and inconsistent effect. Microbial respiration rate on beech leaves was on average half that on hazel and ash (Fig. 4a). Mycelial biomass also differed among leaf species, with beech and ash having higher biomass than hazel (Fig. 4b). The time of leaf exposure was also an important determinant of the variability of microbial parameters across samples of a given leaf species (MANOVA M A N O V A s; P < 0.0001; Table 2). By contrast, microbial parameters did not significantly vary according to species combination per se (Table 2). In addition, the time-by-combination interaction did not account for variation in microbial parameters associated with beech and ash leaves (Table 2). There were only subtle differences for hazel leaves at certain time (interaction time-by-combination: P = 0.0024; Table 2). Notably, mycelial biomass on the second sampling date was 1.4 times higher in hazel leaves decomposing in mixtures than alone (Fig. 4b).

Discussion

Our results indicate that leaf diversity can considerably alter the decomposition of particular species. Diversity of the riparian vegetation can therefore be an important factor controlling leaf decomposition in streams, since the diversity of leaf litter inputs to streams is primarily controlled by the nature of the riparian vegetation [START_REF] Cummins | Shredders and riparian vegetation[END_REF][START_REF] Griffith | Leaf pack processing in two Appalachian mountain streams draining catchments with different management histories[END_REF][START_REF] Lecerf | Riparian plant species loss alters trophic dynamics in detritus-based stream ecosystems[END_REF]Lecerf et al., , 2007a)). In the same region as the present study, leaf decomposition rate exhibited up to a 2.7-fold difference between streams lined by species-poor and species-rich riparian forest [START_REF] Lecerf | Riparian plant species loss alters trophic dynamics in detritus-based stream ecosystems[END_REF]. We found that leaf mixing consistently produced up to a twofold increase in the decomposition rate of single leaf species. [START_REF] Swan | Leaf diversity alters litter breakdown in a Piedmont stream[END_REF] reported antagonistic leaf diversity effects but, more importantly, there were large deviations between observed and expected decomposition rates of their leaf mixtures. Such fairly large diversity effects should be considered in perspective, however, as they are small in comparison to intra-and interspecific variability in leaf degradability, which can range over orders of magnitude [START_REF] Webster | Vascular plant breakdown in freshwater ecosystems[END_REF]Lecerf & Chauvet, 2008b;[START_REF] Hladyz | Resource quality and stoichiometric constraints on stream ecosystem functioning[END_REF]. In this study, the most refractory leaf species (beech) enhanced the decomposition of the fastest decomposing leaf species (hazel and ash). Our finding challenges our prior hypothesis, which was based on the general assumption that the highest quality leaves enhance the decomposition of the lowest quality leaves [START_REF] Gartner | Decomposition dynamics in mixed-species leaf litter[END_REF]. The occurrence of labile leaves, similar to these in the present study, resulted in accelerated decomposition of refractory leaves in previous research [START_REF] Lecerf | Riparian plant species loss alters trophic dynamics in detritus-based stream ecosystems[END_REF]. Our result is consistent with preferential feeding by shredders, however, a mechanism reported from a microcosm study (Swan & Palmer, 2006b). The rationale is that, when a choice of leaf quality is offered to shredders, they consume preferentially the highest quality leaves available. If so, this mechanism would have been accompanied by a sharp decrease in the decomposition rate of beech leaves as a result of shredders aggregating on the highest quality leaves. Rather, beech leaves were decomposed at a fairly similar rate across all species combinations, suggesting that additional mechanisms mediated leaf mixing effects on decomposition observed in this study. Beech leaves significantly influenced leaf mixing effects on decomposition, making it a key species (sensu [START_REF] Wardle | Biodiversity and plant litter: experimental evidence which does not support the view that enhanced species richness improves ecosystem function[END_REF]. Physical traits rather than nutritional value per se may have been the determinant of this effect. It is obvious that shredders avoid eating beech leaves, at least in the initial stages, i.e. when leaves have not yet been conditioned by microbial decomposers [START_REF] Dobson | Microhabitat as a determinant of diversity: stream invertebrates colonizing leaf packs[END_REF]Dangles & Chauvet, 2003). Shredders can take advantage of the high structural stability of beech leaves, however, which may enhance invertebrate diversity (Table 3; [START_REF] Dobson | Microhabitat as a determinant of diversity: stream invertebrates colonizing leaf packs[END_REF]. The importance of refractory leaves in streams is also highlighted by the fact that early instars of the cased caddisfly Potamophylax used beech leaves almost exclusively for case construction (Fig. 3b; also noted by [START_REF] Otto | The significance of case material selection for the survival of caddis larvae[END_REF]. This behaviour did not directly alter decomposition of beech in leaf mixtures (Fig. 1), probably because of a limited demand for case materials by Potamophylax in our bags. The selection of the strongest and most durable materials available for case construction may reduce energy cost of case maintenance ⁄ renewal [START_REF] Kochi | Green leaves enhance the growth and development of a stream macroinvertebrate shredder when senescent leaves are available[END_REF]. In addition, cases made of beech leaves are not attractive to other shredders, which reduces the risk of case material being eaten.

The presence of beech leaves in species mixtures also implied that co-occurring leaf species (hazel and ⁄ or ash) were less abundant relative to single species bags, whereas shredder biomass was broadly similar in these bags. The ratio of shreddersto-preferred resource (hazel and ash leaves) was thus increased by the presence of beech leaves, which probably accounted for the accelerated decomposition rate of hazel and ash leaves in such mixtures. Accordingly, functional evenness of leaf mixtures (i.e. the balance between refractory and palatable leaves) may be as important as the number of functional leaf types (refractory versus palatable) or leaf species richness in mediating leaf diversity effects. Disentangling the effects of the different facets of plant diversity on leaf decomposition should help to elucidate how changes in the riparian vegetation, for instance by the invasion of non-native plants or by forest management, may alter in-stream litter dynamics [START_REF] Lecerf | Riparian plant species loss alters trophic dynamics in detritus-based stream ecosystems[END_REF](Lecerf et al., , 2007a)). Missing data for hazel and ash on the second and third sampling dates are due to insufficient leaf material remaining to determine microbial parameters.

Leaf mixing influenced shredders more than it did microbial consumers. It is thus unlikely that microbial consumers directly mediated leaf mixing effects on decomposition. Consistently, Swan & Palmer (2006a,b) did not find any clear evidence from their microcosm experiments that microbial decomposition leads to non-additive effects. The small and inconsistent effect of leaf mixing on mycelial biomass and microbial respiration in our study may indicate that micro-environment conditions on the surface of leaves were not altered in mixtures or, if so, that resident communities were relatively insensitive to these alterations. This is apparently opposite to predictions that the performance of microbial communities on low-quality leaves should have been enhanced by the release of soluble nutritional compounds from high quality leaves in mixtures [START_REF] Gartner | Decomposition dynamics in mixed-species leaf litter[END_REF]. However, such a transfer of soluble compounds among leaf species is more likely to occur in soils or standing waters than in running waters, where leaf leachates are constantly washed out.

To conclude, our study lends support to the prediction that riparian vegetation diversity is important for stream ecosystem processes [START_REF] Cummins | Shredders and riparian vegetation[END_REF]. Consistent with our data and previous studies [START_REF] Lecerf | Riparian plant species loss alters trophic dynamics in detritus-based stream ecosystems[END_REF]Swan & Palmer, 2006a,b), shredders may be instrumental in mediating plant diversity effects on litter decomposition. We propose that mixing leaf species of contrasting quality can alter shredder populations and assemblages through improvements to resource quality and microhabitat. It is, however, intriguing that diverse litter types did not affect the use of refractory leaf species (beech) by consumers in this study. Further investigations should elucidate the mechanisms involved in the decomposition of low-quality leaf species alone and in species mixtures in a longer-term study than the one reported here.

Fig. 1

 1 Fig.1Decomposition rates of beech, hazel and ash leaves exposed in single-and mixed-species bags. Note that the scales are different on the y-axes for each species.

Fig. 2

 2 Fig. 2 Total shredder biomass in leaf bags after 10, 40 and 81 days of exposure. (a) Mean (+SE) by species combination. (b) Differences (+SE) between observed and expected shredder biomass in mixed-species bags (see Methods for the calculation of expected values). Deviations from zero indicate non-additive effects of leaf mixing on shredder biomass.

Fig. 3

 3 Fig. 3 (a) Median body mass of the cased caddisfly Potamophylax (mean + SE) determined after 10, 40 and 81 days of exposure (number of leaf bags colonised by this taxon displayed above bars). (b) Picture of cases of early instars of Potamophylax individuals and a beech leaf from which circular leaf discs were cut out by the larvae for case construction.

Fig. 4

 4 Fig.4Microbial respiration rate (a) and mycelial biomass (b) of beech, hazel and ash leaves exposed in single-and mixedspecies bags and determined after 10, 40 and 81 days of exposure (mean + SE). Missing data for hazel and ash on the second and third sampling dates are due to insufficient leaf material remaining to determine microbial parameters.

Table 1

 1 Total leaf dry mass (mean and SE) enclosed in mesh bags for the seven experimental assemblages of leaf species. Initial leaf chemistry (N, C, ADF) and percent dry mass of the component leaf species in mixtures are also given

		Initial	N	C	ADF
	Treatments	DM (g)	(% DM)	(% DM)	(% DM)
	Single species
	Beech	6.0 (0.1)	1.2 (0.1)	47.3 (0.7)	67.9 (0.1)
	Hazel	4.5 (0.1)	1.7 (0.1)	45.9 (0.9)	47.8 (0.2)
	Ash	6.3 (0.1)	1.8 (0.1)	43.2 (0.2)	34.5 (0.8)
			Beech	Hazel	Ash
			(% DM)	(% DM)	(% DM)
	Mixtures
	Hazel +	5.4 (0.1)		42	58
	ash
	Beech +	5.5 (0.1)	59	41
	hazel
	Beech +	6.4 (0.1)	51		49
	ash
	Beech +	5.8 (0.1)	38	26	36
	hazel +
	ash

N, nitrogen; C, carbon; ADF, acid detergent fibre content of each species in percentage of leaf dry mass (mean and SE).

Table 2

 2 Summary of statistical analyses

					Species combination
			Time (T)	(S)		S • T		Riffle
	Analysis		Statistic d.f.	P-value Statistic d.f. P-value Statistic d.f. P-value Statistic d.f. P-value
	GLZ	Mass remaining of	v 2	1 = 68.7	<0.0001 v 2	3 = 1.7	0.63	v 2	3 = 0.7	0.87	v 2	3 = 2.7	0.44
		beech leaves
	GLZ	Mass remaining of	v 2	1 = 113.8	<0.0001 v 2	3 = 0.5	0.91	v 2	3 = 13.1	0.0043	v 2	3 = 0.8	0.85
		hazel leaves
	GLZ	Mass remaining of	v 2	1 = 105.0	<0.0001 v 2	3 = 7.1	0.0687	v 2	3 = 19.2	0.0003	v 2	3 = 2.8	0.42
		ash leaves
	A N O V A A N O V A	Total shredder	F 2,58 = 7.5	0.0013 F 6,58 = 1.6	0.16	F 12,58 = 2.5 0.0114	F 3,58 = 2.2	0.0947
		biomass (log)
	A N O V A A N O V A	Median value of	F 2,53 = 16.0	<0.0001 F 6,53 = 4.2	0.0015	F 12,53 = 2.2 0.0246	F 3,53 = 1.5	0.21
		Potamophylax body
		mass by leaf bags (log)
	M A N O V A M A N O V A	Microbial parameters	F 4,64 = 15.3	<0.0001 F 6,64 = 1.2	0.30	F 12,64 = 1.3 0.24	F 6,64 = 0.7	0.63
		measured on
		beech leaves
	M A N O V A M A N O V A	Microbial parameters	F 2,16 = 227.7 <0.0001 F 6,32 = 1.8	0.12	F 6,32 = 4.4	0.0024	F 6,32 = 3.2	0.0129
		measured on
		hazel leaves
	M A N O V A M A N O V A	Microbial parameters	F 2,16 = 55.5	<0.0001 F 6,28 = 0.6	0.71	F 2,14 = 1.3	0.30	F 6,28 = 1.1	0.39
		measured on
		ash leaves
	Bold values denote significance at P < 0.05.
	GLZ, generalised linear model.

Table 3

 3

	Relative occurrences (%) of shredder genera in single-and mixed-species leaf bags (all sampling dates and	Genus	Beech	Hazel	Ash	Hazel + ash	Beech + hazel	Beech + ash	All 3 species
	replicate bags combined)	Plecoptera
		Amphinemura	38.4	46.3	36.5	42.4	42.1	45.6	34.9
		Capnioneura	12.4	8.7	7.5	10.3	7.6	7.7	9.6
		Leuctra	9.5	7.2	5.6	5.6	10.4	8.5	7.4
		Nemoura	27.2	19.4	31.1	22.2	23.6	22.6	27.7
		Protonemura	2.9	2.1	6.8	3.8	2.4	2.7	4.4
		Trichoptera
		Notidobia		0.1		0.1	0.1		0.1
		Odontocerum						0.2
		Potamophylax	4.3	14.2	11.5	14.1	8.6	10.3	14.1
		Sericostoma	0.2		0.1		0.5	0.2	0.1
		Other genera
		Gammarus	5.0	1.7	0.9	1.6	4.3	2.2	1.6
		Elodes		0.1					0.1
		Tipula	0.2	0.1			0.3	0.1
		Abundance	581	1261	1022	1160	997	926	936
		Estimated	8.7	8.1	7.5	7.4	9.3	9.1	8.6
		richness

Acknowledgments

We are grateful to Didier Lambrigot and Sylvain Lamothe for help in field work and laboratory analyses, and to Marie-He ´le `ne O'Donoghue for support in literature research. Comments from John Richardson, Alan Hildrew and two anonymous reviewers improved the manuscript. This study was partly supported by the EU Commission (RivFunction: contract EVK1-CT-2001-00088).


Luca Padovani

Vasco Thudichum Vasconcelos

Hugo Torres Vieira

Typing Liveness in Multiparty Communicating Systems

Session type systems are an effective tool to prove that communicating programs do not go wrong, ensuring that the participants of a session follow the protocols described by the types. In previous work, we have introduced a typing discipline for the analysis of progress in binary sessions. In this paper, we generalize the approach to multiparty sessions following the conversation type discipline, while strengthening progress to liveness. Conversation types allow to discipline interaction in systems where a possibly unanticipated number of multiple participants interact using a single medium of communication. We combine the usual session-like fidelity analysis with the liveness analysis and devise an original treatment of recursive types allowing us to address challenging configurations that are out of the reach of existing approaches.

Introduction

The importance of error detection in the early cycles of software development, and the consequent savings arising from it, can never be overemphasized. The problem becomes even more acute when concurrency comes into play, for concurrency faults are notoriously hard to track down. This work concentrates on early error detection of concurrent, message passing systems, and addresses, apart from the usual communication safety and session fidelity, the static identification of states in which processes wait forever for messages that are never sent.

The setting in which we operate is that of (multi-party) sessions [START_REF] Baltazar | A type system for flexible role assignment in multiparty communicating systems[END_REF][START_REF] Bettini | Global progress in dynamically interleaved multiparty sessions[END_REF][START_REF] Caires | Conversation types[END_REF][START_REF] Dezani-Ciancaglini | On progress for structured communications[END_REF][START_REF] Honda | Types for dyadic interaction[END_REF][START_REF] Honda | Language primitives and type discipline for structured communication-based programming[END_REF][START_REF] Honda | Multiparty asynchronous session types[END_REF]. Sessions are private conversations occurring between two or more interacting participants. Each participant behaves according to a session type that describes the messages that the participant is supposed to send/receive and their relative order. One of the strengths of sessions is that they provide a structuring construct on top of which complex systems can be built in a modular way. The relatively simple typing discipline imposed by session types ensures strong properties such as liveness, that is the eventual completion of communication operations. This point in favor of sessions is also, somewhat paradoxically, a weakness: since session types describe only intra-session communications, but say nothing on inter -session dependencies, it may be the case that a well-typed participant simultaneously involved in two or more sessions finds itself in a deadlock because of mutual dependencies between sessions. We address this problem by capturing potentially dangerous dependencies between sessions, so that liveness is ensured also when communications on several different sessions are interleaved.

To illustrate the basic ingredients of our approach, consider the process (νs)( rec X .s? x.X | rec X .s? y.X | rec X .s! 5.s! true.X )

describing three participants (say A, B, and C, composed in parallel) that interact within the scope of a multiparty session s. The aim of C is to repeatedly send two messages (here exemplified as the constants 5 and true) respectively to A and B. Since all these participants interact within the same session s, however, the order of the synchronizations cannot be predicted and it may well be the case that 5 messages are received by B and true messages are received by A or, in fact, that one of A or B does not receive any message at all! In order to recover the linearity of communications (there is at most one possible synchronization in a session channel at a given moment) we tag messages with labels following the approach of [START_REF] Caires | Conversation types[END_REF]. In particular, we refine (1) to (νs)( rec X .s?l x.X | rec X .s?m y.X | rec X .s!l 5.s!m true.X ) [START_REF] Baltazar | A type system for flexible role assignment in multiparty communicating systems[END_REF] so that l-and m-tagged messages respectively and uniquely identify synchronizations with A and B. We are then able to characterize the overall protocol that takes place on session s as the type T s µα. τ l int. τ m bool.α saying that the conversation consists of an infinite exchange of alternated l-and m-tagged messages whose payload is described by the types int and bool, respectively. The occurrences of τ in the type denote synchronizations that are supposed to occur in a session typed by T s . To specify the behavior of the participants involved in the conversation, we split T s into "slices" which we distribute among the participants. First of all, we separate the behavior of C from the rest of the system, and obtain

T s = T C • T ′
where T C µα. ! l int. ! m bool.α and T ′ µα. ? l int. ? m bool.α

In particular, T C says that C repeatedly sends alternated l and m messages and T ′ says that the rest of the system should be ready to receive the very same messages, in this order. Then, we further split T ′ in the behaviors of A and B, thus:

T ′ = T A • T B
where T A µα. ? l int.α and T B µα. ? m bool.α

Note that this splitting is valid assuming that the environment in which A and B execute guarantees that the synchronization on each l message occurs before the synchronization on each m message. This is indeed guaranteed by the sequential structure C. Since T A , T B , and T C match the behaviors of A, B, and C with respect to s we can declare that process (2) is well typed and consequently that it enjoys communication safety (no message with wrong type is ever sent), session fidelity (the interactions follow the protocol described by T s ), and liveness (each interaction described in T s eventually occurs). Of all these properties, liveness is the most delicate one, in the sense that it may easily break up when two or more sessions are interleaved with each other. To illustrate the issue, consider the following refinement of (2)

(νs)( (νr)( rec X .r?m y.s?l x.X | rec X .s?m y.r!m y.X ) | rec X .s!l 5.s!m true.X ) (3)
in which A and B are engaged in another session r, different from s, while C behaves exactly as before. Now B forwards y in a m-tagged message to A, maybe so that A and B can double-check that they are given consistent information from C. Session s is still well typed according to T s and session r is well typed according to T r µα. τ m bool.α. Yet, (3) is stuck because A waits for the message from B before having received the message from C, but C sends its message to B only after it has successfully delivered the message to A. So, none of the synchronizations in T s and T r ever happens, although the structure of the participants in (3) agrees to these types.

One possibility for detecting the problem in (3) stems from the observation that the two sessions s and r are mutually dependent on each other. So, one may devise a static analysis technique that keeps track of inter-session dependencies and flags any system that gives rise to circularities as ill typed. This approach has been pursued, for instance, in [START_REF] Bettini | Global progress in dynamically interleaved multiparty sessions[END_REF][START_REF] Coppo | Inference of Global Progress Properties for Dynamically Interleaved Multiparty Sessions[END_REF][START_REF] Coppo | Global progress for dynamically interleaved multiparty sessions[END_REF]. The limit of this approach is that, by considering sessions as atomic units, it is quite coarse grained when it comes to analyzing dependencies. For instance, (νs)( (νr)( rec X .s?l x.r?m y.X | rec X .s?m y.r!m y.X ) | rec X .s!l 5.s!m true.X )

is a simple variation of (3) where A performs the same two inputs, but in the "correct" order. Also in (4) there are actions on session s interleaving with actions on session r and vice versa, so the approach based on session dependencies also flags (4) as ill typed, which is unfortunate because (4), contrarily to (3), enjoys liveness. The approach we pursue here is based on the idea of tracking the dependencies between actions instead of sessions. To this aim, we annotate each interaction in a type with an identifierwhich we call event-and we keep track of the dependencies between events by means of strict partial order ≺. To get the flavor of the technique at work, let us apply it to the sessions s and r discussed above. First of all, we annotate the types of s and r with three events e, f , and g: s : µα.e τ l int.f τ m bool.α r : µα.g τ m bool.α

Then, we analyze the dependencies between the actions in the participants of (3): it must be e ≺ f (read, e precedes f ) because C first sends the l-tagged message, and only then it sends the m-tagged message; it must be g ≺ e because A waits for the m-tagged message before waiting for the l-tagged one; finally, it must be f ≺ g by looking at the structure of B. Overall, ≺ is not a strict partial order because of the circularity in the relation g ≺ e ≺ f ≺ g between the two sessions s and r, hence (3) is ill typed.

Our approach builds on previous works [START_REF] Kobayashi | A type system for lock-free processes[END_REF][START_REF] Kobayashi | A new type system for deadlock-free processes[END_REF][START_REF] Padovani | From Lock Freedom to Progress Using Session Types[END_REF][START_REF] Vieira | Typing progress in communication-centred systems[END_REF] that use analogous annotations for reasoning on the dependencies between actions. With respect to these works, our contributions are along two major vectors. First of all, we show that the techniques can be applied to sessions/conversations with an arbitrary (and possibly variable) number of participants. Second, we support complex recursive process structures. The latter aspect requires a non-trivial extension of the technique described in [START_REF] Vieira | Typing progress in communication-centred systems[END_REF] because, in order to declare that a system like (4) is well typed, we must be able to distinguish occurrences of the same event that pertain to different iterations of a recursive process.

The next section formally describes our language. Section 3 introduces the type system and the main results. Section 4 concludes the paper including a more detailed comparison with related work and hints on future developments.

Process Model

We consider an infinite set of names ranged over by x, y, . . . representing communication channels, an infinite set of process variables ranged over by X , . . . , a set of message labels l, . . . . Processes, ranged over by P , Q, . . . , are the terms defined by the grammar in Fig. 1. The language is that of TyCO [START_REF] Vasconcelos | Typed concurrent objects[END_REF] that extends the π-calculus [START_REF] Milner | A calculus of mobile processes, part I and II[END_REF] by considering labelled communication. The terms 0, P | Q, and (νx)P respectively denote the inactive process, the parallel composition of P and Q, and the restriction of name x in P . Terms rec X .P and X are used to construct recursive processes. The term x!l y.P denotes a process that sends a message on channel x and then continues as P . A message is made of a label l and an argument y. The term x?{l i y i .P i } i∈I denotes a process that waits for a message from channel x and then continues as P i according to the label of the received message. The argument of the received message replaces the name y i in P i . To keep the setting as simple as possible, we have not included conditional or non-deterministic processes. These constructs can be easily added.

The binders of the language are name restriction (νx)P , which binds the name x in P , the input prefix x?l y.P , which binds the name y in P , and the recursion rec X .P , which binds the

P, Q ::= 0 (Inaction) | x!l y.P (Output) | P | Q (Parallel) | x?{l i y i .P i } i∈I (Input Summation) | (νx)P (Restriction) | rec X .P (Recursion) | X (Recursion Variable)
Figure 1: Syntax of processes

k ∈ I x?{l i y i .P i } i∈I | x!l k z.Q → P k {z/y k } | Q P → Q (νx)P → (νx)Q (R-Com,R-New) P → P ′ P | Q → P ′ | Q P ≡ P ′ P ′ → Q ′ Q ′ ≡ Q P → Q (R-Par,R-Cong)
Figure 2: Reduction relation recursion variable X in P . The notions of free and bound names (as well as free and bound process variables) are defined in the usual way. We identify processes modulo renaming of bound names and of bound process variables. The semantics of the language is defined via a structural congruence and a reduction relation. Structural congruence is standard, except that it includes the law rec X .P ≡ P {rec X .P/X } for unfolding recursive processes. Note that the unfolding of recursive processes is captured by structural congruence, where P {Q/X } denotes the capture-avoiding substitution of the free occurrences of X by process Q in P .

Reduction is defined by the rules in Fig. 2. Rule (R-Com) describes the synchronization of two processes exchanging a message: the sender emits a message with a label l k that is among those accepted by the receiver and the argument z of the message replaces the bound input parameter in the appropriate continuation P k of the receiver. The remaining rules close the relation under language contexts-name restriction and parallel composition-as well as under structural congruence.

Having presented our process model, which we consider to be the simplest possible setting that allows to discipline multiparty interaction, at least considering a session-type based approach, we are in a position to present our type system.

Type System

This section starts by introducing the notion of strict partial orders which allows to identify well-formed communication dependencies in processes. It then introduces types and operations on these, most notably type split which allows to separate a type in two disjoint "slices" of behavior. Processes are typed against a conventional typing context and an ordering for the events in the types. Finally it presents the main results of the paper, namely soundness of the type system (Theorem 1) and liveness (Theorem 2). Strict partial orders. We consider an infinite set of event identifiers E and the set of natural numbers N, and use a, b, . . . to range over E and n, m, . . . to range over N. We use a n to denote an element in set E × N. We further introduce a distinguished event, ⊤, use e, f, . . . to range over (E × N) ∪ {⊤}, and call this set the set of events. A strict (or irreflexive) partial order ≺ over the set of events is a binary relation that is asymmetric (hence irreflexive) and transitive. We write e ≺ f when the pair (e, f ) is in ≺, and supp(≺) for the support of ≺, namely the set of events that occur in ≺.

Next we define two partial operations over strict partial orders. We write e + ≺ for the strict partial order obtained by adding a least event e to ≺, provided that e does not occur in

p ::= ! | ? | τ (Polarity) T ::= a n p l T (Shared Type) | B ≺ (Linear Type) Γ ::= • | Γ, x : T (Context) ∆ ::= • | ∆, X : (Γ; ≺) (Recursion Context) B ::= end (Stop) | B 1 | B 2 (Parallel) | µα.B (Recursion) | α (Variable) | a n p{l i T i .B i } i∈I (Prefix Summation)
Figure 3: Syntax of types and typing contexts

supp(≺). Formally, e + ≺ ≺ ∪ {(e, f ) | f ∈ supp(≺)} ∪ {(e, ⊤
)}, where we explicitly add the pair (e, ⊤) since ≺ may be empty (in which case e + ∅ is defined as {(e, ⊤)}). We write ≺ 1 • ∪ ≺ 2 for the least strict partial order that includes both ≺ 1 and ≺ 2 , if it exists. We use • ∪ to gather the communication dependency structures of, e.g., two parallel processes. Types. The syntax of types is given in Fig. 3. Our types are based on conversation types [START_REF] Caires | Conversation types[END_REF] extended with event annotations following the approach introduced in [START_REF] Vieira | Typing progress in communication-centred systems[END_REF]. A polarity p describes a communication capability: ! specifies an output; ? specifies an input; and τ specifies a synchronization, i.e., a matched communication pair (cf., [START_REF] Caires | Conversation types[END_REF]). At the type level we distinguish two separate categories of channels: shared (or unrestricted) channels -described by a n p l Tare used for modeling (possibly persistent) services having a publicly known name, with which sessions can be established; linear channels -described by B ≺ -are used for modeling the private conversations within sessions. Note that the distinction between shared and linear channels appears at the type level only, while they are treated uniformly in the process model. For the sake of simplicity we omit non-channel types (e.g., Int) which could be easily added.

A type a n p l T describes the behavior of a shared channel via an event a n , a polarity p, a message label l and a type T describing the message argument. We associate shared types with events to temporally relate shared communications with others, in particular with the communications specified by the message type T . We include the exponent n for the sake of uniformity w.r.t. linear types (which exploit it) so as to simplify the presentation of the orderings, and omit them when specifying shared types. For example, the type a ?service T 1 describes a channel which offers an input on label service, receiving a channel which is then used according to T 1 , associated with event identifier a, while b !remoteservice T 2 describes a channel which outputs (with event b) on remoteservice a channel to be used accordingly to type T 2 .

A type B ≺ captures the linear usage of a channel: B specifies the behavior of a process w.r.t. the channel, whereas ≺ specifies the ordering of events expected from the external environment. Informally, ≺ is used in a type B ≺ to represent the sequentiality information that B admits but does not impose. For example, when typing a process that concurrently sends messages hello and bye the type may specify that the outputs on hello and bye actually take place one after the other if such order is imposed by the corresponding inputs (present in the external process environment).

Behavioral types B include inaction end, parallel composition B 1 | B 2 of two independent behaviors B 1 and B 2 , recursive types µα.B, recursion variables α, and (prefixed) summation a n p{l i T i .B i } i∈I . Sums capture communication capabilities associated with event a n , polarity p, and a menu of synchronization options. Each entry in the menu is identified by a distinct label l i , the type of the argument of the message T i , and the behavior B i that takes place after the synchronization. We say a linear type B ≺ is well-formed if supp(≺) does not include events associated with communication actions of polarity τ in B (since no further ordering information can be provided for such actions by the external environment). In the remainder whenever we write B ≺ we assume that B ≺ is well-formed. We also identify α-equivalent (recursive) types by convention.

Following the ideas presented in [START_REF] Vieira | Typing progress in communication-centred systems[END_REF], we associate with each linear communication an event a n so as to temporally relate the communication action described by the summation with respect to others, establishing an overall ordering of communications. In this work, we introduce the notion of iteration, by adding to events a natural number n, allowing to describe infinite chains of (related) events. Informally, the exponent allows to capture the several "stages" of a type by means of an increment, so, for example, µα.a 1 τ l T.b 1 τ m T ′ .α unfolds to a 1 τ l T.b 1 τ m T ′ .µα.a 2 τ l T.b 2 τ m T ′ .α so as to associate the first iteration (of l m synchronizations) with exponent 1 and the second iteration with exponent 2 and so on and so forth. Operations on types. We write labels(B) for the set of labels occurring in B. We say that B 1 and B 2 are behaviorally independent, notation B 1 #B 2 , if labels(B 1 ) ∩ labels(B 2 ) = ∅, so that non-interference is captured by disjoint message label sets. We also need an operation to remove part of the partial order in a type, defined as B ≺ ′ \ ≺ B ≺ ′ \≺ for linear types, and T \≺ T for shared types. Since linear types may contain sequentiality assumptions, we use this operation to clear hypotheses that are proved externally.

In order to capture the several iterations of a communication that may repeat itself in the context of recursion, we introduce an operator that increments the exponent associated with an event by a given factor, defined as inc(a n , m) a n+m and inc(⊤, m) ⊤. We then extend inc to strict partial orders, pointwise, and to behavior types so that inc(a

n p{l i T i .B i } i∈I , m) a n+m p{l i inc(T i , m).inc(B i , m)} i∈I .
The increment of a behavior is an homomorphism for all other constructs. The increment operation on types affects only linear types, inc(B ≺ , m) inc(B, m) inc(≺,m) , as events associated with shared communications (including the ones specified in the message type) are not considered to be repeated in different stages (and consequently ordered) but rather to be repeated always at the same stage, hence inc(a n p l T, m) a n p l T . Essentially, we model shared communication repetition using replication (via recursion), so shared replicated communication actions have the same temporal ordering, while we model linear recursive repetition (necessarily) using a sequential chain of events. The exponent is then used to capture repetition (without cycles) in the orderings.

To simplify the typing rules, we define a type equivalence relation ≡ that includes commutativity, associativity and neutral end for | , as well as iso-recursive equivalence for recursive types µα.B ≡ B{µα.inc(B, m)/α} for some m > 0, saying that the next iteration of the behavior is captured by the increment of the events (we use any positive m so as to support misalignment between processes and types, and otherwise use m = 1).

We now introduce operations that capture the temporal ordering prescribed by types. We write events(B) for the set of elements of E × N occurring in a behavior B, not including the events in message types. Formally:

events(B)        ∅ if B = end or B = α events(B 1 ) ∪ events(B 2 ) if B = B 1 | B 2 {e} ∪ i∈I events(B i ) if B = e p{l i T i .B i } i∈I {inc(e, k) | e ∈ events(B ′ ) and k ≥ 0} if B = µα.B ′
Notice that events(µα.B) includes all the events in the body of the recursion, incremented zero or more times so as to capture the first and the following iterations. We extend the operation to types, by defining events(B ≺ ) events(B), as we are only interested in linear types where supp(≺) ⊆ events(B), and by defining events(e p l T ) {e}. We write B↓ for the strict partial order over E × N induced by a type B. Notice that B↓ is a partial operator since it uses • ∪ and + . Formally:

B↓            ∅ if B = end or B = α B 1 ↓ • ∪ B 2 ↓ if B = B 1 | B 2 e + ( • ∪ i∈I B i ↓) if B = e p{l i T i .B i } i∈I {(inc(e, k), inc(f, k)) | (e, f ) ∈ B ′ ↓ and k ≥ 0} • ∪ {(inc(e, m), inc(f, n)) | e, f ∈ events(B ′ ) and m < n} if B = µα.B ′
Notice that the operation adds a least event in the case of the prefix summation, and for recursion adds all pairs obtained from the body of the recursion (incremented zero or more times) and all pairs that pertain to different iterations. We extend the definition to types by taking (e p l T )↓ (e, ⊤) and B ≺ ↓ B↓ \ ≺, where \ denotes set difference. The definition for linear types considers the order obtained from the behavioral type removing the ordering expected from the external environment, so B ≺ ↓ characterizes exclusively the ordering imposed by the type.

To identify types that characterize channels that do not depend on the external environment to evolve, and hence are "self-sustained" communication wise, we introduce a predicate that is true of types containing no unmatched communication actions. We say that a behavioral type B is matched if it contains no top-level (i.e., excluding message types) input or output polarities. We extend the definition to linear types by considering matched (B ≺ ) matched (B) (which, by well-formedness, implies ≺= ∅), and matched (e p l T ) p = ?. A message type of polarity ? says that a shared input is available. Since we are only interested in capturing continuously available shared inputs, ? shared types "absorb" (as will be clear from the definition of type splitting) ! shared types, so as to capture the fact that (replicated) shared inputs are still available after synchronization. Hence, the definition of matched () for shared types excludes solely (unmatched) shared outputs, and considers the (infinitely available) shared inputs to be matched (regardless whether they are used or not). Typing contexts. The syntax of typing contexts is given in Fig. 3. We assume by convention that, in a typing context Γ, x : T and in a recursion environment ∆, X : (Γ; ≺), the name x and the process variable X do not occur in Γ and in ∆, respectively, as usual. Also, we consider contexts up to permutations of their entries.

We let Γ un range over contexts that contain only outputs on shared channels and linear types with end behavior, that is, if x : T is in Γ un , then T is either e ! l T ′ or end ∅ . We use such contexts to describe systems that only use resources that may be used exponentially, namely to describe (the continuation of) processes that input on shared channels. We exclude shared inputs from Γ un in order to avoid "nested" shared inputs, so that inputs on shared channels are continuously active (cf. uniform receptiveness [START_REF] Amadio | On message deliverability and non-uniform receptivity[END_REF][START_REF] Sangiorgi | The name discipline of uniform receptiveness[END_REF]). Similarly, we let Γ lin range over contexts that contain only linear types, that is, types of the form B ≺ .

We are interested in systems where all communications are matched, i.e., typed in matched contexts, defined as the pointwise extension of the matched predicate on types. We also lift the notions of type increment, inc, type equivalence, ≡, and partial order difference, \, pointwise to contexts. Splitting and conformance. We now introduce two notions crucial to our development, namely splitting (inspired by [START_REF] Baltazar | A type system for flexible role assignment in multiparty communicating systems[END_REF] and by the merge operation of [START_REF] Caires | Conversation types[END_REF]) that explains how behaviors can be decomposed and safely distributed to distinct parts of a process (e.g., to the branches of a parallel composition), and conformance that captures the desired relation between typing contexts and strict partial orders.

We say type T conforms to order ≺, noted conforms(T, ≺), if T ↓ ⊆ ≺. Notice that since T ↓ excludes the ordering expected from the external environment, conformance focuses on

B ≺ = B ≺ • end ∅ B 1 #B 2 ∀ i∈{1,2} B i ≺ ′ i • ∪≺ ′′ i = B ′ i ≺ ′ i • B ′′ i ≺ ′′ i B 1 | B 2 • ∪ i∈{1,2} (≺ ′ i • ∪≺ ′′ i ) = B ′ 1 | B ′ 2 • ∪ i∈{1,2} ≺ ′ i • B ′′ 1 | B ′′ 2 • ∪ i∈{1,2} ≺ ′′ i (L-End,L-Par) ∀ j∈{1,2} T j = e p j {l i T i .B j i } i∈I • ∪ i∈I ≺ j i p 1 = ? p 2 = ! ∀ i∈I B i ≺ 1 i • ∪≺ 2 i = B 1 i ≺ 1 i • B 2 i ≺ 2 i e τ {l i T i .B i } i∈I • ∪ i∈I (≺ 1 i • ∪≺ 2 i )\(T 1 ↓ • ∪T 2 ↓) = T 1 • T 2 (L-Sync) T = e p{l i T i .B ′ i } i∈I • ∪ i∈I ≺i ∀ i∈I B i ≺i • ∪≺ = B ′ i ≺i • B ≺ e p{l i T i .end} i∈I #B e p{l i T i .B i } i∈I ( • ∪ i∈I ≺i) • ∪≺ • ∪((e+events(B))\(T ↓ • ∪B ≺ ↓)) = T • B ≺ (L-Break) B ≺1 • ∪≺2 = B 1 ≺1 • B 2 ≺2 µα.B ≺1 • ∪≺2 = µα.B 1 ≺1 • µα.B 2 ≺2 α ∅ = α ∅ • α ∅ (L-Rec,L-Var)
• = • • • (C-Empty) Γ = Γ 1 • Γ 2 Γ, x : T = Γ 1 , x : T • Γ 2 (C-Left) Γ = Γ 1 • Γ 2 T = T 1 • T 2 Γ, x : T = Γ 1 , x : T 1 • Γ 2 , x : T 2 (C-Split)
Figure 6: Context splitting the order imposed by the types (which is the focus of the overall ordering). The conforms predicate is defined on typing contexts as the pointwise extension of the predicate on types, so conforms(Γ, ≺) ensures that every communication action specified in Γ is ordered by ≺.

Splitting is defined both on types and on typing contexts. We write T = T 1 • T 2 to mean that type T is split in types T 1 and T 2 , and likewise for Γ = Γ 1 • Γ 2 . Linear type splitting, shared type splitting and context splitting are given by the rules in Figs. 456(where we omit symmetric rules).

We briefly describe the rules in Fig 4 . A behavioral type may be split in itself and in end, so as to allow, e.g., to give away the behavior completely to one branch of a parallel composition-rule (L-End). A parallel composition B 1 | B 2 (where B 1 and B 2 are apart #) may be split in two parallel compositions, the components of which are obtained by decomposing B 1 and B 2 together with the ordering assumptions-rule (L-Par). A synchronized (τ ) prefix summation may be split in prefix summations with dual polarities (? and !) whose continuations are obtained by splitting the synchronized prefix summation continuations-rule (L-Sync)where further ordering assumptions can be present in (each) one of the splitted types, just as long such assumptions are proved by the other splitted type. We also ensure that there are no assumptions left regarding the event associated with the prefix e as the type is matched and no further ordering information can be provided by the external context.

A prefix summation may be split in an independent (#) behavior, obtained by splitting (all) the continuations, and in the prefix summation whose continuations specify the remaining behavior-rule (L-Break)-where some extra care with the assumptions is required: since this rule may decompose a type in such a way that the overall ordering is not guaranteed by the splitted types (the split takes place at the level of the continuations), we ensure that such ordering assumptions are present in the overall type via a relation between the event of the prefix e with all events of the B type, where no assumption that is proved by the splitted

∆; Γ 1 ; ≺ 1 ⊢ P ∆; Γ 2 ; ≺ 2 ⊢ Q ∆; Γ 1 • Γ 2 ; ≺ 1 • ∪ ≺ 2 ⊢ P | Q ∆; Γ, x : T ; ≺ ⊢ P matched (T ) ∆; Γ; ≺ ⊢ (νx)P (T-Par,T-New) ∆; Γ un ; ∅ ⊢ 0 ∆, X : (inc(Γ lin , n); inc(≺, n)); Γ lin ; ≺ ⊢ P n ∈ N ∆; Γ lin ; ≺ ⊢ rec X .P (T-Inact,T-LRec) ∆, X : (Γ; ≺); Γ; ≺ ⊢ P Γ = Γ un , x : e ? l T ≺= (e + ≺ ′′ ) • ∪ ≺ ′ e ∈ supp(≺ ′ ) ∆; Γ; ≺ ⊢ rec X .P (T-URec) ∆(X ) = (Γ; ≺) conforms(Γ, ≺) ∆; Γ; ≺ ⊢ X ∆, Γ 2 ; ≺ ⊢ P Γ 1 ≡ Γ 2 ∆; Γ 1 ; ≺ ⊢ P (T-Var,T-Equiv) ∀ i∈I ∆; Γ, x : B i ≺ ′ i , y i : T i ; ≺ i ⊢ P i ∆; Γ, x : e ?{l i T i .B i } i∈I • ∪ i∈I ≺ ′ i ; e + ( • ∪ i∈I ≺ i ) ⊢ x?{l i y i .P i } i∈I (T-LinIn) ∆; Γ, x : B k ≺ ′ ; ≺ ⊢ P k ∈ I ∆; (Γ, x : e !{l i T i .B i } i∈I ≺ ′ ) • y : T k ; e + (≺ • ∪ T k ↓) ⊢ x!
types is present (T ↓ • ∪ B ≺ ↓).
A recursive type is split in two recursive types, the bodies of which are obtained by splitting the body of the incoming recursive type, as well as the ordering assumptions-rule (L-Rec). Also, a recursion variable (without assumptions) may be split in itself-rule (L-Var).

Shared type splitting (Fig. 5) decomposes shared communication capabilities in two distinct ways, depending on whether the polarity of the incoming type is ? or !. A shared input is split in a shared input and either in an output or another input, via rule (S-In-L). Essentially, the latter allows for typing processes that separately offer the input capability (e.g., a service that is provided by two distinct sites), and the former allows for typing processes that offer the dual communication capabilities (e.g., a service provider and a service client). A shared output is split in two shared outputs-rule (S-Out)-which allows for typing processes that offer the output capability separately (e.g., two clients of some service). Notice type splitting preserves the message types and event association so as to guarantee the dual communication actions agree on the type of what is communicated and on the ordering.

Context splitting (Fig. 6) allows to divide a context in two distinct ways: context entries either go into the left or the right outgoing contexts-(C-Left) and the omitted symmetric-or they go in both contexts-(C-Split). The latter form lifts the (type) behavior distribution to the context level, while the former allows to delegate the entire behavior to a part of the process, leaving no usage at all to the other part. To lighten notation we use Γ 1 • Γ 2 to represent any Γ such that Γ = Γ 1 • Γ 2 (if such Γ exists). Notice that, given Γ 1 and Γ 2 , there may be more than one Γ such that Γ = Γ 1 • Γ 2 . Typing system. We may now present our type system which characterizes processes according to typing assumptions for the free process variables (in ∆), for the names (in Γ), and an overall ordering of events ≺. We say process P is well-typed if ∆; Γ; ≺ ⊢ P is derivable using the rules in Fig. 7.

We briefly comment on the rules in Fig 7 . In rule (T-Par) the parallel composition is typed if the branches are typed in splittings ( • ) of the context and a decomposition of the order (which is ensured to be sound via • ∪). In rule (T-New) the name restriction is typed if the process in the scope of the restriction is typed in the same contexts together with the typing assumption for the usage of the restricted name which must be a matched type (all communication prefixes are matched). Notice that the overall ordering ≺ is preserved, hence the ordering prescribed by name x is still present in the conclusion, even though the type T of x is not.

In rule (T-Inact) the inaction process is typed with any usage of recursion variables (∆), and with only outputs on shared labels and end linear types (Γ un ) as these are the only resources that may be used exponentially, and an empty overall ordering (∅). In rule (T-LRec) a recursive process is well typed if so is the body of the recursion in the same typing context Γ lin (which only includes linear usages) and overall ordering ≺, and in the recursion environment augmented with an assumption for the recursion variable: the variable is assumed to have exactly the same usage and overall ordering up to an increment (for some n) of the natural exponent of the events. Rule (T-LRec) therefore captures, in a fairly intuitive way, subsequent iterations of a (linear) recursion: the point of the next iteration is characterized by an increment of the typing and ordering.

Rule (T-URec) addresses a recursive process that uses only shared resources where no increment is involved since shared communications do not have iterations (their repetition is considered to happen at the level of a single iteration). So the recursion environment is augmented with the same typing and ordering that types the body of the recursion. The typing mentions only shared exponential resources (Γ un ) together with a shared input (on x), as we intend to capture replicated shared inputs (a recursive process specifying only shared outputs can be typed separately in expected lines). In order to ensure that the shared input is an immediate action of the body of the recursion, the ordering makes e a minimal event. Given the above explanation, rule (T-Var) is straightforward: the assumption for the variable provides the context and ordering for the process. In rule (T-Equiv) we embed the notion of context equivalence in the type system, since we need to unfold recursive types when typing the body of a recursion.

Communication prefixes are also typed in separate rules, depending on the type of the subject of the communication. In rule (T-LinIn) the input on a channel x with linear usage is typed if the continuation processes are typed with the usages for x prescribed in the prefix summation type, together with a (sound) separation of the ordering assumptions; also, by adding a typing assumption for the usage of the received name (according to the corresponding message type), and a (sound) separation of the events greater than e in the overall ordering. The e is the event associated with the prefix summation (notice that we pick fresh events since + is undefined otherwise). The fact that events in the continuation are of greater order ensures that the communications in the continuation are in fact prescribed to take place after the prefix itself. Notice that the overall ordering registered in the conclusion is a tree rooted in e. Further notice that the communication dependency structure of the received name is transparently kept in the conclusion (the ordering prescribed by the channel usages is invariantly registered in the overall ordering). This allows us to type systems where communications on received channels are interleaved with others, configurations out of reach of related approaches.

The reasoning is similar in rule (T-LinOut). The continuation is typed by considering the continuations of the prefix summation (any prefix summation containing the only label mentioned by the process) which is uniquely associated with event e, together with the same ordering assumptions ≺ ′ (as we are only interested that the environment guarantees the order of one branch). The typing context Γ is actually the result of a split of the context registered in the conclusion, which also mentions the usage delegated in the communication for the sent name. Finally, the overall ordering in the conclusion also registers the ordering (of events greater than e) prescribed by the message type.

Rules (T-UIn) and (T-UOut) explain the typing for communications on shared channels. In rule (T-UIn) the input with shared usage is typed if the continuation process is typed adding the usage for the received name to the context. Notice that the fact that we type the continuation with the shared input usage implies that the continuation must offer again the shared input behavior (so shared inputs can be typed only in the context of a recursion). Notice also that the overall ordering in the conclusion is that of the premise, as expected in a replicated process, and specifies that the event associated with the shared input is minimal (so as to ensure it is immediately available). Furthermore, we require that the remaining context mentions exclusively shared outputs (Γ un ) so that no other shared inputs are defined in the continuation. This would be a problem for liveness since shared inputs on free names defined in the continuation might leave a matching output dangling. However, we may freely type processes in the continuation that specify shared inputs in restricted names (or even in the received name).

In rule (T-UOut) we type the output on a shared channel if the continuation is typed in the empty context and empty ordering. This means that our model for shared channel communications is an asynchronous one. There are (at least) two approaches to guarantee that shared inputs (that have matching outputs) are always active (uniform receptiveness): one is to exclude usage of the shared name in the continuations of both input and output prefixes [START_REF] Sangiorgi | The name discipline of uniform receptiveness[END_REF] (we followed a similar approach in [START_REF] Vieira | Typing progress in communication-centred systems[END_REF] excluding the corresponding event in the continuations); the other relies on an asynchronous model of communication [START_REF] Amadio | On message deliverability and non-uniform receptivity[END_REF]-which we adopt here for shared channels. The advantage of this approach is that it supports processes that specify in the continuation of a shared input a matching output (intuitively, think of a recursive "service" call). Also, looking at (T-UOut) and (T-Par) we argue that every process P that we have used in examples in the continuation of a shared output x!l y.P can be specified (and typed) using the parallel composition P | x!l y.0, essentially since the type delegated in the communication is obtained via a split of the context nonetheless. Notice that rule (T-UOut) says that the event associated with the output is minimal w.r.t. the message type in the conclusion. Notice also that the rules for communication prefixes make no distinction whatsoever on the type of the channel communicated.

We can now show that process (4) is well typed. We take

T s µα.e 1 τ l int.f 1 τ m bool.α T r µα.g 1 τ m bool.α
where we have added to each event an index denoting the iteration in the recursive behavior of the processes that implements these interactions. Each unfolding of a type increments the indexes of the events. The splitting of these behaviors produces

T As µα.e 1 ? l int.α T Bs µα.f 1 ? m bool.α T Cs µα.e 1 ! l int.f 1 ! m bool.α T Ar µα.g 1 ? m bool.α T Br µα.f 1 ! m bool.α
regarding sessions s and r. Now, looking at the structure of the participants in (4), we realize that the following relations must hold: the structure of A requires e 1 ≺ g 1 ≺ e 2 ; the structure of B requires f 1 ≺ g 1 ≺ f 2 ; finally, the structure of C requires e 1 ≺ f 1 ≺ e 2 . Overall, the whole process is well typed by considering the strict partial order Results. We are now in a position to present our results, namely that typing is preserved under reduction (Theorem 1) and that a class of well-typed processes (those with matched communications) enjoys a liveness property (Theorem 2). We start by mentioning some auxiliary results, in particular that conformance between the typing context and the overall ordering is ensured for all derivations. This result may be viewed as a sanity check that says the conditions imposed by our rules are enough to keep conformance invariant in a derivation. We may also show that split is an associative relation, in particular for behavioral types. This result in particular ensures that the derivation (sub-)trees may be moved around, used in the proof of the following (standard) results.

≺ T s ↓ • ∪ T r ↓ • ∪ {(f i , g i ), (g i , e i+1 ) | i ∈ N} k ∈ I e τ {l i T i .B i } i∈I → B k B 1 → B ′ 1 B 1 | B 2 → B ′ 1 | B 2 B 1 ≡ B ′ 1 → B ′ 2 ≡ B 2 B 1 → B 2 • → • B 1 → B 2 Γ, x : B 1 ≺ → Γ, x : B 2 ≺ Γ 1 → Γ 2 Γ 1 , x : T → Γ 2 , x : T
≺ → ≺ e ∈ supp(≺) ≺ → ≺\ e Γ 1 → Γ 2 ≺ 1 →≺ 2 Γ 1 ; ≺ 1 → Γ 2 ; ≺ 2
Lemma 1 (Subject Congruence). If ∆; Γ; ≺ ⊢ P and P ≡ Q then ∆; Γ; ≺ ⊢ Q.

Lemma 2 (Substitution). If ∆; Γ 1 , x : T ; ≺ ⊢ P and Γ 2 = Γ 1 • y : T then ∆; Γ 2 ; ≺ ⊢ P {x/y}.

The proofs follow by induction on the structure of the process and on the length of the typing derivation (respectively) along non-surprising lines. Notice that substitution uses context splitting to characterize the context that types the resulting process, since name y may already be used by P and the soundness of the substitution is guaranteed by the split. Before presenting our first main result we need to introduce two auxiliary notions that characterize reduction of contexts and of strict partial orders. As expected from a behavioral type system, as processes evolve so must the types that characterize the processes. The reduction relations for behavioral types and contexts are given in Fig. 8. Hence, τ prefix summations (in "active contexts") may reduce and a context reduces if it has an entry on a linear type prefix that reduces. In such way contexts may mimic the corresponding behavior in processes. Also, the empty context reduces so as to mimic synchronizations on restricted channels and on shared channels (embedding context reduction with reflexivity) since no change in the types is required to capture such synchronizations.

Fig. 9 shows the reduction for orders and context/order pair. Strict partial order reduction is also reflexive to capture both shared synchronizations and communications that depend on shared communications (as they take place repeatedly for each of the continuation of the shared input). Reduction is also defined by removing an event of the ordering, so as to capture one shot synchronizations (which includes infinite chains of synchronizations). We may now present our first main result.

Theorem 1 (Preservation). If ∆; Γ 1 ; ≺ 1 ⊢ P 1 and P 1 → P 2 then Γ 1 ; ≺ 1 → Γ 2 ; ≺ 2 and ∆; Γ 2 ; ≺ 2 ⊢ P 2 .

The proof follows by induction on the length of the derivation of P 1 → P 2 . The theorem says that typing is preserved under process reduction, up to a reduction in the context and ordering. Fidelity is an immediate consequence of Theorem 1, as usual (cf. [START_REF] Baltazar | A type system for flexible role assignment in multiparty communicating systems[END_REF]), thanks to the precise correspondence between reduction in processes and in typing contexts. We now turn our attention to the liveness result, where we use → n to denote a sequence of n reductions.

Theorem 2 (Liveness). Let ∆; Γ 1 ; ≺ 1 ⊢ P 1 with matched (Γ 1 ), and let x :

B 1 ≺ ′ 1 in Γ 1 . If e ∈ events(B 1 ≺ ′ 1 ) then P 1 → n P 2 and (Γ 1 ; ≺ 1 ) → n (Γ 2 ; ≺ 2 ) and ∆; Γ 2 ; ≺ 2 ⊢ P 2 with x : B 2 ≺ ′ 2 in Γ 2 and e ∈ events(B 2 ≺ ′
2 ), for some n > 0.

In words, every event e occurring in the type of a linear channel used by a well-typed process can eventually disappear from the type environment. This means that either e is associated with an (inter)action that can eventually be performed by the process, or that e occurs in a branch of a choice which is not selected. This property is akin to lock freedom [START_REF] Kobayashi | A type system for lock-free processes[END_REF] or progress [START_REF] Bettini | Global progress in dynamically interleaved multiparty sessions[END_REF][START_REF] Coppo | Inference of Global Progress Properties for Dynamically Interleaved Multiparty Sessions[END_REF][START_REF] Honda | Multiparty asynchronous session types[END_REF] except that e in Theorem 2 can be associated with an action that is arbitrarily deep within the process structure, whereas lock freedom and progress are usually formulated for top-level actions only. The proof follows by induction on ≺. The invariant is that for each linear synchronization prescribed by the types there is either an immediate corresponding synchronization in the process or there are preceding actions which necessarily are of "lesser" order. The fact that behaviors described by linear types have a correspondence with the communication capabilities of processes is a standard property of linear type theories.

Notice that we are not able to characterize shared usages in the same way, as the events associated with them are persistent. However, we may immediately conclude that since any linear synchronization that depends on a shared synchronization takes place then so does the shared synchronization (in fact, our proof relies on the fact that also shared synchronizations are live, along with communications in restricted channels with matched typings). Notice also that our type-based approach addresses processes with "unmatched" typing, just as long as we consider them up to the composition with any other processes for which the resulting typing is matched -in particular via rule (T-Par) of Fig. 7. An immediate consequence of Theorem 1 and Theorem 2 combined is that any reachable configuration also has the liveness property.

Concluding Remarks

We present a type system for multiparty session-based communication-centred systems that guarantees liveness in addition to session fidelity even when multiple sessions are interleaved. Compared to other models for multiparty session communication, our approach strives to achieve minimality of both language and type features. Regarding language features, we rely on message labels for preventing communication races on linear channels, whereas other approaches make use of channel polarities [START_REF] Gay | Subtyping for session types in the pi calculus[END_REF], of distinct channel endpoints [START_REF] Vasconcelos | Fundamentals of session types[END_REF], or roles [START_REF] Bettini | Global progress in dynamically interleaved multiparty sessions[END_REF][START_REF] Coppo | Inference of Global Progress Properties for Dynamically Interleaved Multiparty Sessions[END_REF]. Moreover, we do not make use of dedicated session initialization primitives. Regarding type features, our work exploits notions introduced in [2, 4] (e.g., the τ and the splitting), allowing us to use the same type language for specifying both global and local types. This is in contrast with common multiparty session type theories such as [START_REF] Bettini | Global progress in dynamically interleaved multiparty sessions[END_REF][START_REF] Coppo | Inference of Global Progress Properties for Dynamically Interleaved Multiparty Sessions[END_REF][START_REF] Honda | Multiparty asynchronous session types[END_REF], which introduce distinct languages for global and local types connected by a projection of the former into the latter.

A number of type-based techniques guaranteeing deadlock freedom, progress, or liveness properties have been proposed. Kobayashi [START_REF] Kobayashi | A type system for lock-free processes[END_REF][START_REF] Kobayashi | A new type system for deadlock-free processes[END_REF] presents type systems for lock-free and deadlock-free processes written in the pure π-calculus. Roughly, every top-level input/output prefix in a lock-free process is guaranteed to be eventually consumed, whereas a deadlock-free process is one that is always able to reduce, unless it has terminated. The type systems rely on channel usages, which are behavioral types resembling session types where actions are annotated with pairs of obligation/capability levels, roughly denoting the time at which actions begin/are supposed to end. Top-level actions with a finite capability level are guaranteed to succeed in a finite amount of time (and possibly under some fairness assumption). For session-based languages, the relevant works on binary sessions are [START_REF] Dezani-Ciancaglini | On progress for structured communications[END_REF][START_REF] Padovani | From Lock Freedom to Progress Using Session Types[END_REF], while [START_REF] Bettini | Global progress in dynamically interleaved multiparty sessions[END_REF][START_REF] Coppo | Inference of Global Progress Properties for Dynamically Interleaved Multiparty Sessions[END_REF] deal with multiparty sessions. The basic idea of [START_REF] Bettini | Global progress in dynamically interleaved multiparty sessions[END_REF][START_REF] Coppo | Inference of Global Progress Properties for Dynamically Interleaved Multiparty Sessions[END_REF][START_REF] Dezani-Ciancaglini | On progress for structured communications[END_REF] is to devise a type system that detects the dependency graph between different sessions, where a dependency arises if a (blocking) action in one session guards an action pertaining a different session. Liveness is guaranteed if the dependency graph is acyclic. [START_REF] Padovani | From Lock Freedom to Progress Using Session Types[END_REF] leverages Kobayashi's technique described in [START_REF] Kobayashi | A type system for lock-free processes[END_REF] from channel usages to session types showing that such technique can achieve a greater accuracy, when compared to [START_REF] Bettini | Global progress in dynamically interleaved multiparty sessions[END_REF][START_REF] Coppo | Inference of Global Progress Properties for Dynamically Interleaved Multiparty Sessions[END_REF][START_REF] Dezani-Ciancaglini | On progress for structured communications[END_REF]. The present work differs from these in several minor and major ways. In particular, our process model is synchronous, while the ones in [START_REF] Bettini | Global progress in dynamically interleaved multiparty sessions[END_REF][START_REF] Coppo | Inference of Global Progress Properties for Dynamically Interleaved Multiparty Sessions[END_REF][START_REF] Padovani | From Lock Freedom to Progress Using Session Types[END_REF] is asynchronous. Asynchrony has a non-trivial impact in the type system for progress, mainly because output actions are non-blocking. The progress property considered in [START_REF] Bettini | Global progress in dynamically interleaved multiparty sessions[END_REF][START_REF] Coppo | Inference of Global Progress Properties for Dynamically Interleaved Multiparty Sessions[END_REF] assumes that missing session participants can eventually join the system at any time. In practice, this assumption implies that any action on shared channels is considered non-blocking, because it is always possible to add some (well-typed) processes that provide for the missing messages. Also, [START_REF] Coppo | Inference of Global Progress Properties for Dynamically Interleaved Multiparty Sessions[END_REF] defines a syntax-directed type system and automatic inferences are known for the systems described in [START_REF] Kobayashi | A type system for lock-free processes[END_REF][START_REF] Kobayashi | A new type system for deadlock-free processes[END_REF]. In our case, the definition of a syntax-directed type system and of an inference algorithm remain open problems.

One major difference between our work and the aforementioned ones, which constitutes the main technical contribution, regards the treatment of recursive types. In all previous works, annotations such as obligation/capability levels in [START_REF] Kobayashi | A type system for lock-free processes[END_REF][START_REF] Kobayashi | A new type system for deadlock-free processes[END_REF], dependency graphs [START_REF] Bettini | Global progress in dynamically interleaved multiparty sessions[END_REF][START_REF] Coppo | Inference of Global Progress Properties for Dynamically Interleaved Multiparty Sessions[END_REF], timestamps [START_REF] Padovani | From Lock Freedom to Progress Using Session Types[END_REF] are statically associated with types, regardless of their recursive structure. In our case, unfolding a recursive type has the effect to "freshen" the events occurring therein. This significantly increases the range of well-typed processes. In particular, none of the aforementioned works is able to prove progress for non-trivial recursive processes interleaving (blocking) actions on different channels. For example, the (appropriate encoding of the) (4) is ill typed according to all previous type systems. More recently, the first author has studied a type system for deadlock and lock freedom which is capable of addressing non-trivial recursive process configurations, albeit in the context of the linear π-calculus [START_REF] Padovani | Deadlock and lock freedom in the linear π-calculus[END_REF]. The type system in [START_REF] Padovani | Deadlock and lock freedom in the linear π-calculus[END_REF] can prove that a configuration such as ( 4) is (dead)lock free, but only encoding the multiparty session s in terms of several binary sessions which, in turn, can be encoded using linear channels. In the present work instead we consider a calculus with a primitive notion of multiparty session, addressing scenarios that cannot be compiled down to binary sessions. Naturally a type-based approach is only relevant if it can be taken into practice, so decidability is a fundamental property. We may argue that we can extract a decidable type-checking procedure from our type system, if we annotate restricted names with their types (as usual) and process recursion variables with the increment factor (together with confining unfoldings to a "just-in-time" setting). Inference is also an important issue as it allows to save the programmer's effort to specify the types and increase the probability that such advanced type system can actually be used in practice. Although we believe these are very important questions to address, we decided to leave them to future clarification and concentrate on the principles of our approach for now, so as to make further efforts worthwhile. Furthermore, observing that types are becoming very rich characterizations of process behavior (in our case how and when channels are used), one may ask if it is possible to deduce processes from types (e.g., [START_REF] Carbone | Structured communication-centered programming for web services[END_REF]) and spare the "programmer" the effort of writing programs and just ask him to write the types.

Figure 4 :Figure 5 :

 45 Figure 4: Linear type splitting p ∈ {?, !} e ? l T = e ? l T • e p l T (S-In-L) e ! l T = e ! l T • e ! l T (S-Out) Figure 5: Shared type splitting

Figure 7 :

 7 Figure 7: Typing rules

Figure 8 :

 8 Figure 8: Type and context reduction

Figure 9 :

 9 Figure 9: Order and typing reduction