Guillaume Le Baut
email: lebaut.guillaume@gmail.com

Julien Kirchgesner
email: julien.kirchgesner@gmx.com

Aurélien Amiot

Jérémie H Lefevre

Najim Chafai

Cécilia Landman

Isabelle Nion

Anne Bourrier

Charlotte Delattre

Chloé Martineau

H Sokol

Y Nguyen

Y Marion

G Lebreton

F Carbonnel

S Viennot

L Beaugerie

Antoine Ibd Network

Arrive Lionel

BOURRIER Beaugerie Laurent

Anne Camus

Chafai Najim

Chaput Ulriikka

CHOLLEY Martineau Chloé

Monnier Laurence

Debove Clotilde

Fléjou Dray Xavier

L E Gall

Kirchgesner Julien

Landman Cecilia

Marteau Philippe

Nion- Larmurier Isabelle

Ozenne Violaine

Parc Yann

Seksik Philippe

Sokol Harry

Svrcek Magali

Emmanuel Tiret

A Scoring System to Determine Patients' Risk of Colectomy Within 1 Year After Hospital Admission for Acute Severe Ulcerative Colitis Short title: Predictors of colectomy in patients with ASUC

Keywords: UC, ASUC: Acute severe ulcerative colitis, tumor necrosis factor blockers: anti-TNFs, Inflammatory bowel disease: IBD, C-reactive protein: CRP, Clostridioides difficile infection: CDI, inflammatory bowel disease unclassified: IBDU, Cytomegalovirus: CMV, interquartile ranges: IQR, 95% confident interval: 95%CI, WCC: white cell count

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

Abstract

Background & Aims: There is consensus on the criteria used to define acute severe ulcerative colitis (ASUC) and on patient management, but it has been a challenge to identify patients at risk for colectomy based on data collected at hospital admission.

We aimed to develop a system to determine patients' risk of colectomy within 1 y of hospital admission for ASUC based on clinical, biomarker, and endoscopy data.

Methods: We performed a retrospective analysis of consecutive patients with ASUC treated with corticosteroids, ciclosporin, or tumor necrosis factor (TNF) antagonists and admitted to 2 hospitals in France from 2002 through 2017. Patients were followed until colectomy or loss of follow up. A total of 270 patients with ASUC were included in the final analysis, with a median follow-up time of 30 months (derivation cohort). Independent risk factors identified by Cox multivariate analysis were used to develop a system to identify patients at risk for colectomy 1 y after ASUC. We developed a scoring system based on these 4 factors (1 point for each item) identify high-risk (score 3 or 4) vs low-risk (score 0) patients. We validated this system using data from an independent cohort of 185 patients with ASUC treated from 2006 through 2017 at 2 centers in France.

Results: In the derivation cohort, the cumulative risk of colectomy was 12.3% (95% CI, 8. 6-16.8). Based on multivariate analysis, previous treatment with TNF antagonists or thiopurines (hazard ratio [HR], 3.86; 95% CI, 1.82-8.18), Clostridioides difficile infection (HR, 3.73; 95% CI, 1.11-12.55), serum level of Creactive protein above 30 mg/L (HR, 3.06; 95% CI, 1.11-8.43), and serum level of albumin below 30 g/L (HR, 2.67; 95% CI, 1.20-5.92) were associated with increased risk of colectomy. In the derivation cohort, the cumulative risks of colectomy within 1 y in patients with scores of 0, 1, 2, 3, or 4 were 0.0%, 9.4% (95% CI, 4.3%-16.7%), 10.6% (95% CI, 5.6%-17.4%), 51.2% (95% CI, 26.6%-71.3%), and 100%. Negative predictive values ranged from 87% (95% CI, 82%-91%) to 92% (95% CI, 88%-95.0%). Findings from the validation cohort were consistent with findings from the derivation cohort.

Conclusion:

We developed a scoring system to identify patients at low-risk vs highrisk for colectomy within 1 y of hospitalization for ASUC, based on previous treatment with TNF antagonists or thiopurines, C difficile infection, and serum levels of CRP and albumin. The system was validated in an external cohort.

Key words:

Ulcerative colitis, acute severe colitis, colectomy, predictors WHAT YOU NEED TO KNOW Background: It has been a challenge to identify patients with acute severe ulcerative colitis (ASUC) at risk for colectomy within the next year based on data collected at hospital admission.

Findings:

We identified 4 factors associated with increased risk of colectomy within 1 y after hospital admission (previous treatment with tumor necrosis factor antagonists or thiopurines, Clostridioides difficile infection, increased serum level of C-reactive protein, decreased serum level of albumin). We used this information to develop a scoring system that identified patients at high-risk vs low-risk for colectomy, and validated it in an external cohort.

Implications for patient care: This scoring system can be used to identify patients at low risk of colectomy at 1 year (score 0) who can make an early transition to oral therapy and be discharged from the hospital, and patients at high-risk (scores of 3 or 4) who should be carefully monitored.

Introduction

Acute severe ulcerative colitis (ASUC) affects approximately 25% of patients with ulcerative colitis (UC) [START_REF] Cesarini | Predicting the Individual Risk of Acute Severe Colitis at Diagnosis[END_REF] . This complication is well defined by Truelove and Witts criteria as well as the therapeutic management after hospital admission 2 . Medical treatment notably intravenous corticosteroids, ciclosporin, and tumor necrosis factor blockers (anti-TNFs) have changed the prognosis of ASUC. However, colectomy is still required in a substantial subgroup of patients. Predictors of colectomy are needed in clinical practice, since morbidity, mortality and costs increase with the duration of hospitalization before colectomy [START_REF] Kaplan | Impact of Hospital Volume on Postoperative Morbidity and Mortality Following a Colectomy for Ulcerative Colitis[END_REF][START_REF] Leeds | Early Surgical Intervention for Acute Ulcerative Colitis Is Associated with Improved Postoperative Outcomes[END_REF][START_REF] Saha | Early colectomy in steroid-refractory acute severe ulcerative colitis improves operative outcome[END_REF] . Several predictive scores of colectomy in patients with ASUC have been already described [START_REF] Ventham | Predicting outcomes in acute severe ulcerative colitis[END_REF] , and include clinical and/or biological parameters, notably albumin or C-reactive protein (CRP) level.

Although they are strongly associated with the response to corticosteroids [START_REF] Lynch | Predicting outcome in acute severe ulcerative colitis: comparison of the Travis and Ho scores using UK IBD audit data[END_REF] , several points limit their use in clinical practice. They were established before the era of biologics and are generally calculated on day 3 after admission. Moreover, some critical items, such as the presence of Clostridioides difficile infection (CDI) are not included [START_REF] Ananthakrishnan | Excess hospitalisation burden associated with Clostridium difficile in patients with inflammatory bowel disease[END_REF][START_REF] Law | Systematic review with meta-analysis: the impact of Clostridium difficile infection on the short-and long-term risks of colectomy in inflammatory bowel disease[END_REF] . Nevertheless, none was created to foresee patients with a low risk of colectomy to allow decreased monitoring. Two recent studies have identified CRP / albumin ratio as a good predictor of colectomy over the medium to long term [START_REF] Gibson | CRP/Albumin Ratio: An Early Predictor of Steroid Responsiveness in Acute Severe Ulcerative Colitis[END_REF][START_REF] Choy | Predicting response after infliximab salvage in acute severe ulcerative colitis[END_REF] .

One recent review concludes that new scoring systems are required to predict response to treatment and colectomy [START_REF] Ventham | Predicting outcomes in acute severe ulcerative colitis[END_REF] . The aims of our study were to identify predictive factors, among clinical, biological, endoscopic, and radiological criteria and to perform a new score assessing the probability of colectomy during the first year after ASUC. Date of cohort entry was the date of hospital admission for ASUC. Patients were followed until April 31th, 2018, or at last news including loss to follow-up, colectomy or death, whichever occurred first. Secondly, an independent cohort including all consecutive patients with an ASUC treated between 2006 and 2017 from two French centers, Kremlin Bicetre hospital and Henri Mondor hospital, was built for external validation. Inclusion criteria were similar between the two cohorts and data were independently collected in each cohort.

Methods

Therapeutic management

Patient hospitalized for ASUC were treated according to standard guidelines [START_REF] Harbord | Third European Evidence-based Consensus on Diagnosis and Management of Ulcerative Colitis. Part 2: Current Management[END_REF] . In case of absence of response after 3 to 5 days of corticosteroids, options for colectomy, ciclosporin or anti-TNFs as a salvage medical therapy were considered.

Cytomegalovirus (CMV) infection was confirmed by presence of inclusion body in histopathological examination and testing for CDI was systematic at admission in our centers.

Data collection

Variables were collected at Saint Antoine hospital from the SUVIMIC registry (a prospective clinical database of all patients with IBD evaluated by Saint-Antoine Hospital digestive disease medical staff), endoscopic and medical records, and collected at Caen University hospital from medical records.

The following variables were collected at cohort entry: age, gender, IBD type (UC or IBDU), comorbidities according to the Charlson's index [START_REF] Charlson | A new method of classifying prognostic comorbidity in longitudinal studies: development and validation[END_REF] , previous appendicectomy, date of IBD diagnosis, disease extent defined by Montreal classification [START_REF] Dignass | Second European evidence-based consensus on the diagnosis and management of ulcerative colitis Part 1: Definitions and diagnosis[END_REF] , and previous treatment exposure, including thiopurines and anti-TNFs. Clinical variables, such as Truelove and Witts criteria [START_REF] Truelove | Cortisone in ulcerative colitis[END_REF] or Clinical activity index [START_REF] Lichtiger | Cyclosporine in Severe Ulcerative Colitis Refractory to Steroid Therapy[END_REF] , the number of stools, extra-intestinal manifestations, date of the onset of symptoms and the used of oral corticosteroids before admission were analyzed. We recorded biological data (hemoglobin, albumin, C-reactive protein, white cells count, and platelet count) and microbiological data (CDI and histological signs of CMV infection), that were obtained during the first full day following admission.

Radiological (disease extent) and endoscopic (Mayo endoscopic score, mucosal damage) variables were collected from original reports at the start of hospitalization.

Then, treatment exposures during hospitalization were assessed: drug classes (aminosalicylates, corticosteroids, thiopurines, ciclosporin and anti-TNFs), date of introduction and withdrawal, and therapy at hospital discharge, including colectomy.

During follow-up, occurrences of treatment modifications for IBD, hospitalizations, and colectomy were assessed. In the validation cohort, collected data were: age, previous treatment exposure, including thiopurines and anti-TNFs, albumin and Creactive protein levels, CDI, occurrence of colectomy, and date of last visit.

Outcomes

The primary outcome was the occurrence of colectomy within one year after hospital admission. The secondary outcomes included response to corticosteroids, need for rescue therapy and occurrence of colectomy, and were assessed at hospital discharge and end of follow-up.

Statistical analyses

Continuous data are presented as medians and interquartile ranges (IQR) and were compared with a Wilcoxon-Mann-Whitney test. Categorical variables were summarized as frequencies with percentages and compared with a Chi-square or Fisher's test. Cumulative risk of colectomy was assessed in the whole cohort. Cox regression was used to assess the relationship between clinical, biological and endoscopic variables with the risk of colectomy within one year. Variables with a P values below than 0.10 at univariate analysis were included in multivariate analysis.

Sensitivity analysis was performed by excluding patients with IBDU.

According to the coefficient estimates in the multivariate Cox regression analysis, we built a prognostic score. To assess the quality of the prognostic score, patients were classified as having a low, intermediate or high probability of colectomy. Percentages (95% confident interval [95%CI]) of colectomy depending on the calculated score were estimated from 1000 bootstrapped samples of 270 patients (uniform selection with replacement) [START_REF] Efron | An Introduction to the Bootstrap[END_REF] . In the validation cohort, cumulative risk of colectomy at one year was assessed according to the developed score. P values <0.05 were considered statistically significant. The study was approved by the Saint-Antoine Hospital ethics committee for the both centers (N°2014-A01788-39). Statistical analyses were performed using SAS (version 9.4, Inc, Cary, NC, USA) and R (version 3.4.2, R Foundation for Statistical Computing, Vienna, Austria).

Results

Derivation cohort

Baseline characteristics

In the derivation cohort, 421 patients with UC or IBDU were hospitalized and screened. Of these, 270 patients were included in the analysis (Figure 1). Baseline characteristics are presented in Table 1. Thirty percent (81/270) of the patients were previously exposed to thiopurines. Among the 34 patients exposed to anti-TNFs before cohort entry, 7 had discontinued anti-TNFs before admission index, due to severe skin side effects (1), allergic reactions (2), serious infections (1), primary failure (1), remission (1), and nonadherence (1). Among patients with no missing data to assess the clinical activity index (Lichtiger index) and Truelove and Witts criteria (n=215, 80% of the total cohort), 83.2% had a clinical activity index above 10 and 75.2% had an ASUC defined by Truelove and Witts criteria. CRP level above 30mg/L, and albumin level below 30g/L were observed in 64.8% (175/270) and 44.4% (120/270) of patients, respectively. Endoscopy was performed in 241 patients (89.2%) and an abdominal CT scan in 70 patients (25.9%) (Supplementary table 1).

Therapeutic Management

Before admission index, 121 patients (45%) were treated with oral corticosteroids. Among them, 71 had no response to corticosteroids and 40 had a recurrence of symptoms during the decrease of corticosteroids. The first line treatment after hospital admission was intravenous corticosteroids in 94.1% (n=254) of patients, infliximab in 3.7% (n=10), ciclosporin in 1.5% (n=4), and adalimumab in 0.7% (2 patients, who failed to response to oral corticosteroids and infliximab during the last year prior to admission). Thirty-nine percent of patient treated with corticosteroids (n=98) needed a 2 nd line therapy. Among non-responders to the first line (38%, 102 patients, in any treatment group), 7%, 65%, 25%, and 3% were treated with colectomy, infliximab, ciclosporin, or other treatments (adalimumab or golimumab), respectively. The rate of response to infliximab and ciclosporin was 91% and 85%, respectively. Only 4 patients had a third medical line of treatment.

Colectomy was performed in 4.8% (n=13) of patients during the hospitalization after a median duration of 15 days (IQR: 8-19). No patients died during hospitalization.

Long term follow-up

Median time of follow-up was 30 months (IQR: 7-66). One patient died during the follow-up related to a cholangiocarcinoma. Forty-three percent of patients (n=83) were hospitalized for flare during the first year following ASUC. The cumulative risk of colectomy according to the time since the index hospitalization is shown in the figure 2. Colectomy was performed in 30 (12.3%), 43 (20.1%) and 47 (33.3%) at 1, 5, and 10 years after the index hospitalization, respectively. Among patients with missing data at admission about Lichtiger Index and Truelove and Witts criteria, no difference was observed on the rate of colectomy at one year (9% versus 11,6% in patients with available data, p=0.77).

Predictors of colectomy at one year By univariate analysis, patients with colectomy at one year were significantly older at diagnosis of IBD (Table 2). Previous treatment with thiopurines or anti-TNFs were associated with an increased risk of colectomy (Table 2). Considering previous treatment with thiopurines or anti-TNFs, hazard ratio was 2.4 (95%CI 1.19-5.00, p=0.01). Among patients with no missing data, clinical activity index was not associated with an increased risk of colectomy (HR: 1.07, 95%CI 0.93-1.22, p=0.36).

Regarding biological parameters, presence of CDI, CRP level above 30 mg/L and serum albumin level below 30 g/L measured during the first day following admission were predictors (Table 2). By multivariate analysis, four criteria were significantly associated with an increased risk of colectomy within one year after admission: previous treatment with anti-TNFs or thiopurines (HR: 3.86; 95%CI, 1.82-8.18), presence of CDI (HR: 3.73; 95%CI, 1.11-12.55), CRP level above 30 mg/L (HR: 3.06; 95%CI, 1.11-8.43), and albumin level below 30 g/L (HR: 2.67; 95%CI, 1.20-5.92). Results were consistent after exclusion of patients with IBDU. Results were consistent across centers.

We developed a prognostic score based on these four predictors. Since the coefficients of the Cox multivariate regression analysis varied around 1.19 between 0.98 and 1.35, the same weight for all variables was chosen to simplify: 1 point for each item, from 0 to 4. Forty-one patients (15.2%) had no criteria, 91 patients (33.7%) had one criteria, 113 (41.8%) patients had 2 criteria, 24 patients (8.9%) had 3 criteria and one patient (0.4%) had 4 criteria. The cumulative risk of colectomy within one year in patients with a score of 0, 1, 2, 3 and 4 items at admission was respectively 0.0%, 9.4% (95%CI 4.3-16.7), 10.6% (95%CI 5.6-17.4), 51.2% (95%CI 26.6-71.3), and 100% (Figure 3 and4). Colectomy was performed during hospitalization in the patient with 4 criteria. Characteristics of the score are presented in table 3. The negative predictive value varied between 87% (95%CI 82-91) and 92% (95%CI 88-95). The positive predictive value (PPV) increased gradually according to the score 1, 2, 3, 4 (respectively 9%, 10%, 42% and 100%). As estimated with the 95%CI from the bootstrap method, the percentage of patient with a low (score=0; n=41 (IQR: 30-53)), intermediate (score=1 or 2; n=204 (IQR: 192-217)) and high score (score=3 or 4; n=25 (IQR: 16-34)) was respectively 0.0 (0.0-0.0), 9.9 (5.7-14.2) and 53.3 (30.7-74.9).

Validation cohort

In the validation cohort, 185 patients were included (100 and 85 from Kremlin Bicetre hospital and Henri Mondor hospital, respectively), with a median age at admission of 38.0 (IQR: 25-51) and 35.6% (66/185) were previously exposed to anti-TNFs or thiopurines. Median CRP and albumin levels were respectively 48.5mg/L (IQR: 20.2-117.0) and 29.9g/L (IQR: 25.0-35.0). CRP above 30mg/L, albumin below 30g/L and CDI were observed in 65.9% (122/185), 49.7% (92/185) and 5.4% (10/185) of patients, respectively. Seven patients were lost to follow-up before one year. The cumulative risk of colectomy within one year was 21.6% (95%CI:15.9-27.9). In this cohort, cumulative probability of colectomy according to the score 0, 1, 2, 3, 4 at admission were respectively 6.2% (95%CI:0.4-25.

Discussion

Among data on hospital admission of 270 unselected patients with ASUC, 4 predictors of colectomy within one year have been identified: previous treatment with anti-TNFs or thiopurines, presence of CDI, CRP level above 30 mg/L and albumin level below 30 g/L. We combined the variables into a score, which is highly predictive of having a colectomy or not within one year after admission. Results were consistent in the validation cohort for low-and high-risk profile patients.

Our population is similar to others studies, notably regarding clinical and biological characteristics [START_REF] Parian | Appendectomy does not decrease the risk of future colectomy in UC: results from a large cohort and meta-analysis[END_REF][START_REF] Jain | Predictors of long-term outcomes in patients with acute severe colitis: A northern Indian cohort study: Acute severe colitis: Longterm outcome[END_REF][START_REF] Williams | Infliximab versus ciclosporin for steroid-resistant acute severe ulcerative colitis (CONSTRUCT): a mixed methods, open-label, pragmatic randomised trial[END_REF] . The rate of CDI (4.3%) is homogenous with recent studies [START_REF] Regnault | Prevalence and risk factors of Clostridium difficile infection in patients hospitalized for flare of inflammatory bowel disease: A retrospective assessment[END_REF] . Corticosteroid therapy for ASUC was the cornerstone of first-line treatment in our study (94.0%) as previous studies [START_REF] Lynch | Outcomes of rescue therapy in acute severe ulcerative colitis: data from the United Kingdom inflammatory bowel disease audit[END_REF] , and the overall response rate to corticosteroids in our cohort (61%) was similar with the literature [START_REF] Turner | Response to Corticosteroids in Severe Ulcerative Colitis: A Systematic Review of the Literature and a Meta-Regression[END_REF] . Despite no difference was reported regarding efficacy and short-term safety between infliximab and ciclosporin in the two randomized controlled trials [START_REF] Williams | Infliximab versus ciclosporin for steroid-resistant acute severe ulcerative colitis (CONSTRUCT): a mixed methods, open-label, pragmatic randomised trial[END_REF][START_REF] Laharie | Ciclosporin versus infliximab in patients with severe ulcerative colitis refractory to intravenous steroids: a parallel, open-label randomised controlled trial[END_REF] , a higher proportion of patient were treated with infliximab (65%) compared to ciclosporin (25%) in our study.

This may be related to the substantial proportion of patients previously exposed to thiopurines and thus not eligible for ciclosporin, and also related to physician preferences, as reported in previous studies [START_REF] Harbord | Third European Evidence-based Consensus on Diagnosis and Management of Ulcerative Colitis. Part 2: Current Management[END_REF][START_REF] Narula | Systematic Review and Meta-Analysis: Infliximab or Cyclosporine as Rescue Therapy in Patients With Severe Ulcerative Colitis Refractory to Steroids[END_REF] . We observed a high response to infliximab (91%) and ciclosporin (85%), compared to a meta-analysis of nonrandomized studies (respectively, 74.8% and 55.4%) [START_REF] Narula | Systematic Review and Meta-Analysis: Infliximab or Cyclosporine as Rescue Therapy in Patients With Severe Ulcerative Colitis Refractory to Steroids[END_REF] . However, these rates of response are similar to the CySIF study, which observe at day 7 86% of response to ciclosporin and 84% to infliximab [START_REF] Laharie | Ciclosporin versus infliximab in patients with severe ulcerative colitis refractory to intravenous steroids: a parallel, open-label randomised controlled trial[END_REF] . Since the response rate of the second line therapy was higher, the percentage of colectomy during hospitalization (4.8%) was lower compared to that of literature, which is usually ranging from 11% to 25% [START_REF] Jain | Predictors of long-term outcomes in patients with acute severe colitis: A northern Indian cohort study: Acute severe colitis: Longterm outcome[END_REF][START_REF] Deiana | Outcome of acute severe ulcerative colitis in patients previously exposed to immunosuppressive therapy[END_REF][START_REF] Mokhele | Predictors of emergency colectomy in patients admitted with acute severe ulcerative colitis[END_REF] .

After one year of follow-up, probability of colectomy (12.3%) was nevertheless close to recent studies (12%) [START_REF] Jain | Predictors of long-term outcomes in patients with acute severe colitis: A northern Indian cohort study: Acute severe colitis: Longterm outcome[END_REF] .

Four criteria at admission were associated with colectomy within one year after ASUC in multivariate analysis. First, previous exposure to anti-TNFs or thiopurines was predictive of colectomy. Two studies have already reported a strong association between colectomy and previous exposure to immunosuppressants [START_REF] Deiana | Outcome of acute severe ulcerative colitis in patients previously exposed to immunosuppressive therapy[END_REF][START_REF] Patrick | The effect of pre-admission immunosuppression on colectomy rates in acute severe ulcerative colitis[END_REF] . None reported an association with anti-TNFs, which may be related to the period of inclusion. Second, CDI is a well-known predictor, especially for the long term risk (OR: 2.96; 95% CI: 1.19-7.34) but not for the short term risk [START_REF] Ananthakrishnan | Excess hospitalisation burden associated with Clostridium difficile in patients with inflammatory bowel disease[END_REF][START_REF] Law | Systematic review with meta-analysis: the impact of Clostridium difficile infection on the short-and long-term risks of colectomy in inflammatory bowel disease[END_REF] . Third, a level of albumin below 30 g/L was already included in previous scores [START_REF] Gibson | CRP/Albumin Ratio: An Early Predictor of Steroid Responsiveness in Acute Severe Ulcerative Colitis[END_REF][START_REF] Ho | Predicting the outcome of severe ulcerative colitis: development of a novel risk score to aid early selection of patients for second-line medical therapy or surgery[END_REF] . Lastly, CRP level, which is also a marker of inflammation, was associated with colectomy in historical cohorts [START_REF] Lindgren | Early predictors of glucocorticosteroid treatment failure in severe and moderately severe attacks of ulcerative colitis[END_REF][START_REF] Travis | Predicting outcome in severe ulcerative colitis[END_REF] .

From these 4 items, a predictive score of colectomy has been developed.

Firstly, an internal validation was performed with bootstrapping technique. Secondly, a validation cohort was built to assess external validation. Results were consistent in the validation cohort for low-and high-risk profile patients. When no criterion is present, the risk of colectomy at one year is minimal (0% to 6%), allowing an early transition to oral and discharge from hospital. When one or two criteria are identified, 10 to 30% of patients will be operated within one year. Among patients with a score of 2, discrepancies were observed between derivation and validation cohorts was observed about the score 2 (10.6% (95%CI: 5.6-17.4) versus 29.4% (95%CI: 19.3-40.3)). A potential residual confounding cannot be excluded, but this difference may be also related to the physician preference. Indeed, patients with this score range are at intermediate risk, among whom physicians preference may have the highest impact on colectomy occurrence in this area of uncertainty. Further studies are required to assess the impact of referent physician preference on the decision of colectomy. Among patients with a score greater than three, the risk is higher and colectomy may be discussed earlier, decreasing the morbi-mortality of surgery. PPV is similar with those observed in an English cohort published by Lynch et al. [START_REF] Lynch | Predicting outcome in acute severe ulcerative colitis: comparison of the Travis and Ho scores using UK IBD audit data[END_REF] .

The score developed in this study has several strengths: it is easy to use because only four items are included, with one point for each, improving the reproducibility between physicians and could be widely used. Since it is assessed at the first day of hospitalization, it can help physicians early in the therapeutic management. Previous treatments with anti-TNFs or thiopurines and CDI have been included for the first time in a predictive score of colectomy after ASUC. Some limitations need to be discussed. Radiological and endoscopic criteria were too often lacking to be included in the analysis. Xie et al. have shown a higher performance of the UCEIS to predict colectomy after a median follow -up of 73 months than the mayo endoscopic score [START_REF] Xie | Ulcerative Colitis Endoscopic Index of Severity (UCEIS) versus Mayo Endoscopic Score (MES) in guiding the need for colectomy in patients with acute severe colitis[END_REF] . The number of Truelove and Witts criteria and the clinical activity index were not available for all patients. The later was nevertheless not predictive of colectomy in several studies [START_REF] Kohn | Infliximab in severe ulcerative colitis: short-term results of different infusion regimens and long-term follow-up: INFLIXIMAB IN SEVERE REFRACTORY ULCERATIVE COLITIS[END_REF][START_REF] Monterubbianesi | Infliximab three-dose induction regimen in severe corticosteroid-refractory ulcerative colitis: Early and late outcome and predictors of colectomy[END_REF] and Lindgren et al.

had also included patients with moderately severe flare according to Truelove and Witts criteria [START_REF] Lindgren | Early predictors of glucocorticosteroid treatment failure in severe and moderately severe attacks of ulcerative colitis[END_REF] . Fecal calprotectin seems to have a predictive value in ASUC, but it was not routinely measured in our centers [START_REF] Ventham | Predicting outcomes in acute severe ulcerative colitis[END_REF][START_REF] Xie | Fecal calprotectin as an alternative to ulcerative colitis endoscopic index of severity to predict the response to corticosteroids of acute severe ulcerative colitis: A prospective observational study[END_REF] . Moreover, we focused on colectomy after ASUC, but, nowadays, it would be interesting to have predictors of others issues such as mucosal healing, or success of specific biologics or small molecules [START_REF] Motobayashi | Predictors of mucosal healing during induction therapy in patients with acute moderate-to-severe ulcerative colitis[END_REF] .

Further studies are required to identify these predictors.

To conclude, in this exploratory cohort of consecutive patients with ASUC, four independent predictors of colectomy within one year were identified: previous treatment with anti-TNFs or thiopurines, presence of CDI, CRP level above 30 mg/L, and albumin level below 30 g/L. A score combining these predictors is highly predictive of the occurrence and risk magnitude of colectomy within one year after admission and a replicative cohort confirmed these results.

PatientsA

  derivation cohort was created by reviewing medical files of consecutive patients with UC, defined by European consensus criteria 2 , or inflammatory bowel disease unclassified (IBDU) (whose diagnosis remained unclassified at the end of follow-up), hospitalized in emergency for IBD flare between 2002 and 2017 at Saint-Antoine Hospital, Paris and between 2008 and 2017 at Caen University hospital, and treated with intravenous corticosteroids, ciclosporin, or anti-TNFs. In case of recurrence of ASUC during follow-up, only the first episode was considered. Patients with Crohn's disease at the time of hospital admission or during follow-up, and patients without information on albumin and CRP levels at admission were excluded.

  5) (1/17), 8.4% (95%CI:3.4-16.4) (6/71), 29.4% (95%CI:19.3-40.3) (21/74), 50% (95%CI:26.3-69.8) (10/21), and 50% (95%CI:0.0-96.0) (1/2) (Figure4and Supplementary data 2), which is consistent with findings from the derivation cohort among patients with a score of 0 (low-risk profile) and score 3-4 (high-risk profile). The patient with a score of 0 and who underwent colectomy during hospitalization was 68 years old and had, besides no response to intravenous CS, a known low grade colonic dysplasia and a latent Mycobacterium tuberculosis infection.

Figure 1 :

 1 Figure 1: Flow chart of study (Derivation cohort) IBD: Inflammatory bowel disease; CRP: C-reactive protein

Figure 2 :Figure 3 :Figure 4 :

 234 Figure 2: Rate of colectomy according to the time since admission for ASUC (Derivation cohort)

Table 1 :

 1 Characteristic at admission (Derivation cohort)

	Characteristic	N total=270
	Demographic parameters
	Male	134 (49.6)
	Age at admission, year	32.0 (24.0-47.0)
	At least one item in Charlson's score	41 (15.2)
	Duration of disease, year	2.0 (0.0-7.0)
	ASUC within 6 months after diagnosis	80 (29.6)
	Disease
	Ulcerative colitis	260 (96.3)
	IBDU	10 (3.7)
	Extension of disease
	Extensive colitis	162 (60)
	Left sided colitis	101 (37.4)
	Proctitis	7 (2.6)
	Previously exposed to anti-TNFs or	88 (32.6)
	thiopurines (past and current users)
	Clinical parameters
	Number of stools per day	10.0 (7.0-15.0)
	Lichtiger index*	12.0 (10.0-14.0)
	Extra-intestinal manifestation	31 (11.9)
	Biological parameters
	CRP, mg/L	53.0 (18.6-110)
	Albumin, g/L	30.7 (26.3-35.5)
	Hemoglobin, g/dL	11.6 (10.1-13.2)
	WCC (x 10 9 per L)	9.9 (7.56-13.0)
	Platelet (x 10 9 per L)	388 (305 -479)
	CMV colitis	5 (5.8)
	CDI, n (%)	10 (4.3)
	Results are expressed as median (interquartile range) for continuous variables and
	as N (%) for categorical variables.
	* Among 215 patients with no missing data to assess the clinical activity index
	(Lichtiger index)
	ASUC: Acute severe ulcerative colitis; IBDU: Inflammatory bowel disease unclassified; CRP: C-
	reactive protein; WCC: white cell count; CMV: cytomegalovirus; CDI: Clostridioides difficile infection

Table 2 :

 2 Clinical and biochemical variables of 270 patients admitted with ASUC (Derivation cohort)

		Colectomy at one	No colectomy	Hazard ratio	p
		year	at one year	(95%CI)
		(n=30)	(n=240)
	Clinical variables
	Male	16 (53.3)	118 (49.2)	0.86 (0.42-1.76)	0.68
	Charlson's index	0 (0-1)	0 (0-0)	1.18 (0.93-1.52)	0.18
	Previous appendectomy	3 (10)	9 (3.8)	2.70 (0.82-8.89)	0.10
	Age at diagnosis (years)	37.0 (25.0-47.0)	26.0 (21.0-40.0)	1.03 (1.01-1.05)	<0.01
	Age at admission above 50 (years)	10 (33. 3)	49 (20.4)	1.90 (0.89-4.06)	0.10
	Disease duration (years)	2 (0.0-7.0)	2 (0.0-7.0)	0.99 (0.94-1.04)	0.75
	ASUC onset within 6 months after	4 (13.3)	76 (31.7)	0.35 (0.12-0.99)	0.048
	diagnosis
	Extensive colitis (E3) (vs E2 + E1)	23 (77)	139 (58)	2.21 (0.9-5.2)	0.07
	Medication before admission:
	Thiopurines	14 (46.7)	67 (27.9)	2.09 (1.02-4.27)	0.04
	Anti-TNFs	9 (30)	34 (12.6)	3.17 (1.45-6.93)	<0.01
	Time of flare-up before admission	33.0 (20.0-75.0)	31.0 (16.0-56.0)	1.00 (0.99-1.00)	0.55
	Oral steroids before admission to	17 (56.7)	104 (43.5)	1.57 (0.76-3.23)	0.22
	treat flare-up
	Number of stools	10.0 (7.0-15.0)	10.0 (6.0-15.0)	1.03 (0.99-1.08)	0.15
	Extra-intestinal manifestation	2 (6.9)	29 (12.5) (29)	0.54 (0.13-2.28)	0.40
	Biochemical variables
	CRP above 30 mg/L	25 (83.3)	150 (62.5)	2.84 (1.09-7.43)	0.03
	Albumin below 30 g/L	20 (66.7)	100 (41.7)	2.60 (1.22-5.56)	<0.01
	Hemoglobin (g/dL) *	10.8 (9.80-12.2)	11.8 (10.2-13.3)	0.88 (0.75-1.03)	0.12
	WCC (x 10 9 per L) **	9.32 (7.1-13.0)	9.9 (7.6-13.0)	1.00 (1.0-1.0)	0.44
	Platelet (x 10 9 per L) ***	395 (328-495)	388 (299-479)	1.00 (0.99-1.00)	0.52
	Presence of C. difficile infection	3 (13.0)	7 (3.4)	3.83 (1.16-12.62)	0.03
	CMV colitis	2 (18.2)	3 (4.0)	4.32 (0.93-20.07)	0.06
	ASUC: Acute severe ulcerative colitis; WCC: white cell count; CRP: C-reactive protein; CMV:
	Cytomegalovirus; Risk corresponding to an increase of one unit (*), 1000 WCC/mm 3 (**) and 10 000
	platelet (***)

Table 3 :

 3 Characteristics of score one year after admission for ASUC from derivation cohort

		Negative	Positive
		predictive value	predictive value	Sensitivity (%)	Specificity (%)
		(NPV) (%)	(PPV) (%)	(95%CI)	(95%CI)
		(95%CI)	(95%CI)
	Score=0	87 (82-91)	-	-	83 (78-87)

Supplementary data 1: Endoscopic and radiological criteria at admission

35.1 (20) 64.9 (37) * Among 241 patients with no missing data about endoscopic criteria ** Among 70 patients with no missing data about radiological criteria Supplementary data 2: Cumulative probability of colectomy according to the time since admission for ASUC and to the score in the validation cohort


Davide Frey

Rachid Guerraoui

Anne-Marie Kermarrec

Martin Mogensen

Maxime Monod

Vivien Quéma

Gossiping Capabilities

Gossip-based protocols are now acknowledged as a sound basis to implement collaborative high-bandwidth content dissemination: content location is disseminated through gossip, the actual contents being subsequently pulled.

In this paper, we present HEAP, HEterogeneity-Aware Gossip Protocol, where nodes dynamically adjust their contribution to gossip dissemination according to their capabilities. Using a continuous, itself gossip-based, approximation of relative capabilities, HEAP dynamically leverages the most capable nodes by (a) increasing their fanouts (while decreasing by the same proportion those of less capable nodes) and (b) employing them early in the dissemination chain. These, on the other hand, have an incentive to take on additional load as being first in the chain improves their perceived quality. A lightweight accountability mechanism is used to track selfish nodes that might declare a high capability in order to augment their perceived quality without contributing accordingly.

We evaluate HEAP in the context of a video streaming application on a 236 PlanetLab nodes testbed. Our results shows that HEAP improves the quality of the streaming by 25% over a standard gossip protocol without impacting the average load or availability of the system.

Introduction

Gossip-based dissemination. Gossip-based protocols provide a reliable way to disseminate information in large-scale dynamic systems [START_REF]Gossip-based computer networking[END_REF][START_REF] Birman | Bimodal multicast[END_REF][START_REF] Eugster | Lightweight probabilistic broadcast[END_REF]. For this reason, they have recently been acknowledged as a sound basis to locate content in peer-to-peer streaming applications [START_REF] Li | BAR gossip[END_REF][START_REF] Zhang | Coolstreaming/donet: A data-driven overlay network for efficient live media streaming[END_REF]. 1In a gossip protocol, each node periodically forwards every stream-packet identifier it receives to a subset of nodes picked uniformly at random. These nodes may subsequently pull the content whenever necessary.

In most gossip-based protocols we are aware of, the dissemination load is evenly spread among all participating nodes. Specifically, all nodes usually have the same number of gossip targets (fanout) and the same dissemination period, and therefore send exactly the same number of messages. However, this uniform distribution of load ignores the heterogeneous nature of large-scale distributed systems where nodes may exhibit significant differences in their capabilities.

Such heterogeneity in capabilities may be the result of heterogeneity in computational power, i.e., small devices versus powerful machines, in network connections, parts of the network might be lossy and alter the communication between certain peers, or in actual host applications with some nodes running network-greedy applications while others have full bandwidth available. As an example, while the penetration of the Internet into homes has greatly favored the deployment of p2p collaborative systems, bandwidth capability of edge nodes connected through ADSL links remains extremely heterogeneous. This is particularly true for the upload capacity which is of utmost importance for collaborative systems. For instance, the average upload capacity of ADSL connections in Europe is 1077kbps, while it is 899kbps in North America and only 170kbps in Africa [1]. As we confirm later in the paper, a load-balancing strategy oblivious to such discrepencies may significantly hamper the reliability of the dissemination of, say, a South-American soccer game to Asia, Europe, and Africa.

As in [START_REF] Castro | SplitStream: high-bandwidth multicast in cooperative environments[END_REF][START_REF] Zhang | Coolstreaming/donet: A data-driven overlay network for efficient live media streaming[END_REF][START_REF] Sung | Enabling contribution awareness in an overlay broadcasting system[END_REF][START_REF] Kyasanur | Smart gossip: An adaptive gossip-based broadcasting service for sensor networks[END_REF][START_REF] Venkataraman | Chunkyspread: Heterogeneous unstructured treebased peer to peer multicast[END_REF][START_REF] Vishnumurthy | On heterogeneous overlay construction and random node selection in unstructured p2p networks[END_REF][START_REF] Bishop | Considering priority in overlay multicast protocols under heterogeneous environments[END_REF], we recognize the need to account for the discrepencies between peers and we leverage them to achieve a more effective dissemination process. Doing this in the context of a gossip protocol presents important technical challenges. First, capabilities can clearly change over time and an effective dissemination protocol needs to dynamically track and reflect their changes. Second, the reliability of gossip protocols heavily relies on the uniformly random selection of target peers: biasing this selection and hurting uniformity could impact the average quality of gossip dissemination.

In short, we address these challenges using two observations about the behavior of gossip dissemination protocols. First, mathematical results on epidemics and empirical evaluations of gossip protocols [START_REF] Eugster | Epidemic information dissemination in distributed systems[END_REF][START_REF] Pittel | On spreading a rumor[END_REF] convey the fact that the reliability of dissemination is ensured as long as the average of all fanouts is approximatively ln(n) (in a system of size n). This is crucial because the size of the fanout is an obvious knob to adapt the contribution of a node. A node with an increased (resp. decreased) fanout will send more (resp. less) information about the packets it can provide and in turn will be pulled from more (resp. less) often. Hence, the observation about the ideal fanout being of size ln(n) on average opens a clear opportunity for adaptation. Second, and this is a general characteristic of large-scale dissemination protocols, the utility of messages is higher in the first gossip rounds. Basically, the capability of a node intervening in the first gossip rounds can have a dramatic impact on the overal reliability of dissemination [START_REF] Karp | Randomized rumour spreading[END_REF]. This is particularly crucial because such a node is likely to frequently be pulled for new packets. Usually, the latter rounds simply impose more redundancy to ensure that all nodes are eventually covered.

Based on these observations, we propose a new gossip protocol, which we call HEAP (HEterogeneity-Aware Gossip Protocol ). HEAP is specifically aimed for collaborative, highbandwidth content distribution. It relies on a gossip-based aggregation protocol [START_REF] Jelasity | Gossip-based aggregation in large dynamic networks[END_REF][START_REF] Van Renesse | Astrolabe: A robust and scalable technology for distributed system monitoring, management, and data mining[END_REF] to have each node continously assess its relative capability in order to implement the following mechanisms.

1. Fanout adaptation: each node updates its fanout to match its relative capability. We perform this adaptation in such a way that, whenever some node decreases (resp. increases) its fanout by a proportion x, d nodes increase (resp. decrease) their fanout by a proportion x/d. This strategy is precisely devised to ensure the average fanout value persists over time without decreasing under the fatal ln(n) threshold and without unnecessarily increasing and impacting the overall load on the system.

2. Biased gossip target selection: each node biases the selection of gossip targets so that the position of nodes in the dissemination process matches their capabilities. This is achieved by taking into account the hopcount of any given message so that the early stages of the dissemination process involve the most capable nodes. These nodes have an incentive to take on the resulting additional load as being first in the dissemination chain improves their perceived quality (as we show through our experiments in Section 5). To preserve enough uniformity in the random selection and ensure global reliability, we apply a sliding window technique where less capable nodes have better chances to be selected in subsequent rounds.

A companion sub-protocol, which we call LIFT (LIghtweight Freerider Tracking), is also provided to track selfish nodes that might declare a high capability in order to augment their perceived quality, without contributing accordingly. While interesting in its own right, LIFT is particularly useful in the context of HEAP. A node that declares a high capability will, in fact, end up among the first in the dissemination chain and thus benefit from a higher gossip reliability (Section 5). However, such a node is also expected to contribute more (larger fanout) and it may negatively impact the overall reliability if it decides not to do so (Section 5). Our LIFT protocol (a) requires nodes to record the history of the nodes they sent packets to and (b) involves an audit procedure in which a node can potentially be confronted with others in order to check if it behaves as it is supposed to. These characteristics allow LIFT to achieve particularly effective results with only negligible overhead.

We evaluated HEAP in the context of a video streaming application on a 236-PlanetLabnode testbed. We used upload capacity as a capability metric. Specifically, we considered nodes with asymmetric bandwidth and heterogeneous upload capacities. Upload bandwidth is in fact a crucial parameter for collaborative applications and may vary not only as a result of the limits imposed by the provider but also depending on the overall bandwidth consumption in a given geographical area.

Our results show that, HEAP improves stream quality by 25% with respect to standard homogeneous gossip, while generating a very similar load. 2 We also show that HEAP ensures a dynamic adaptation of the contribution of nodes that matches the distribution of capabilities across the system; we report on the negligible overhead of its underlying capability aggregation protocol; and we measure the impact of the capability of a node on the stream quality it obtains through HEAP as well as the amount of its contribution. Finally, we report on the negligible overhead of LIFT and measure the impact of a selfish node based on its degree of freeriding, as well as the relation between the number of LIFT audits performed, the degree of freeriding and the probability of detecting selfish nodes.

Roadmap. The rest of the paper is organized as follows. Section 2 gives some background on traditional gossip-based dissemination and provides an overview of HEAP. Sections 3 and 4 describe HEAP and LIFT in details. We present our streaming application and reports on the results of our experiments on PlanetLab in Section 5. Related work is covered in Section 6. Some concluding remarks are given in Section 7.

HEAP design overview

In this section, we present an overview of HEAP, our gossip-based protocol for collaborative high-bandwidth content distribution. We first provide some background on standard gossipbased protocols, then we discuss the rationale behind our approach. Finally, we present an overview of the components of the HEAP and companion LIFT protocols. Section 3 elaborates on the details.

Background on gossip-based protocols

Gossip-based dissemination protocols. Most such protocols follow some variant of the skeleton illustrated in Algorithm 1, which HEAP itself extends. In the context of collaborative high-bandwidth content distribution, typically content location is pushed using a gossip protocol and the content is subsequently pulled. This reduces redundancy on large messages.

Consider a set of n nodes Π = {p 1 , . . . , p n }, and an event e to be disseminated in the system: e typically contains a series of application blocks (e.g., stream packets in a streaming application) as well as control information and additional data for error correction.

The gossip protocol works as follows. Nodes periodically contact a fixed number f of nodes chosen according to the selectNodes() function and propose to them a set of event identifiers (ids) with a [Propose] message (lines 6-7 & 26-28 in Algorithm 1).

The selectNodes(f ) function is typically returning a set of f nodes, chosen uniformly at random in Π. The fixed number f is called the fanout and is a key parameter of gossipbased dissemination protocols. It can be tuned to trade reliability against overhead. Typically, the larger the fanout, the more reliable the dissemination [START_REF] Bailey | The Mathematical Theory of Infectious Diseases and its Applications[END_REF][START_REF] Karp | Randomized rumor spreading[END_REF][START_REF] Koldehofe | Simple gossiping with balls and bins[END_REF][START_REF] Pittel | On spreading a rumor[END_REF]. As discussed in the introduction, a large fanout may impose a large overhead over the system and introduce unnecessary redundancy. A value of the fanout of ln(n) is typically considered ideal to ensure reliable dissemination with small resource consumption [START_REF] Eugster | Epidemic information dissemination in distributed systems[END_REF].

Each node maintains a list (eventsToPropose) containing the identifiers of the events it has delivered since its last gossip. A node may deliver an event either when publishing a new one (line 4 in Alogirthm 1), or when retrieving it (i.e., receiving a [Brief] message, lines [START_REF] Eugster | ∆-reliable broadcast: A probabilistic measure of broadcast reliability[END_REF][START_REF] Ganesh | Peer-to-peer membership management for gossipbased protocols[END_REF][START_REF] Garbinato | An adaptive algorithm for efficient message diffusion in unreliable environments[END_REF][START_REF] Gupta | Scalable fault-tolerant aggregation in large process groups[END_REF].

There are basically two ways to gossip events: (i) when a new event e is produced, it is gossiped asynchronously, i.e., immediately sending a [Propose] message, which contains only a single event e, to f nodes (line 5 in Algorithm 1), and (ii) periodically whenever the GossipTimer triggers (line 6 in Algorithm 1), which period is given by the gossipPeriod parameter.

Upon reception of a gossip message containing event ids, a node pulls the content it has not yet retrieved by sending a [Request] message to the sending peer. A peer being pulled then sends back the actual content in a [Brief] message that contains the events which ids were requested in the received [Request] message.

Gossip-based membership protocol. Gossip protocols typically assume that each node is able to sample uniformly the system when renewing the f gossip targets. This is key to the reliability of the dissemination (function selectNodes() in Algorithm 1). In large scale infrastructures, where nodes maintain only a partial view of the system, this can be achieved through a peer-sampling protocol [START_REF] Allavena | Correctness of a gossip based membership protocol[END_REF][START_REF] Eugster | Lightweight probabilistic broadcast[END_REF][START_REF] Jelasity | Gossip-based peer sampling[END_REF][START_REF] Voulgaris | Cyclon: Inexpensive membership management for unstructured p2p overlays[END_REF]. Many variants exist which mostly differ in (i) the selection of the gossip target (ii) the data exchanged over gossip and (iii) the processing of this data. 3

HEAP design rationale

The design of HEAP stems from two observations on gossip protocols. First, most gossip dissemination protocols assume a homogeneous fanout [START_REF]Gossip-based computer networking[END_REF] even though theory reveals that the reliability of gossip dissemination is actually preserved as long as an O(ln(n)) fanout value is ensured on average [START_REF] Kermarrec | Probabilistic reliable dissemination in large-scale systems[END_REF], regardless of the actual fanout distribution across nodes. 4 HEAP leverages this property to adjust the fanout distribution so that (i) the average fanout remains close to ln(n), and (ii) the fanout values match the capability distribution. In other words, starting from a homogeneous initial fanout, we thus heterogeneize the fanout among nodes. We call this the fanout adaptation protocol.

The second key observation relates to the importance of nodes which are involved early in the dissemination chain. 5 In (push-based) protocols, the number of nodes that receive the message grows exponentially during the first rounds of gossiping. Afterwards, the set of uninformed processes only shrinks by a constant factor. This conveys the fact that the utility of a message decreases with the number of hops it travels. This has been leveraged in [START_REF] Karp | Randomized rumour spreading[END_REF], where the authors propose a push-based dissemination until n/ log n nodes have the message with high probability (exponential growth phase). The protocol then switches to a pull (quadratic shrinking) phase as the probability to reach uninformed nodes dramatically decreases. This shows that the nodes gossiping messages early are of the utmost importance for an early spreading. In addition, in the context of high-bandwidth content distribution where nodes pull the actual content, such nodes are the first to advertise new data and will be pulled proportionally more often. This suggests that to achieve efficient content dissemination, such nodes should be capable of sustaining high load. HEAP leverages these observations and biases the selection of the gossip targets toward the most capable nodes at early stages: we call this component of HEAP the biased gossip target selection.

In short, a HEAP node (i) takes into account its own capability (and its variations over time) by dynamically adjusting its own fanout, and thus directly impacting its own contribution, and (ii) accounts for capabilities of other peers by biasing the target peer selection for gossip dissemination, directly impacting the contribution of other peers.

Both these operations must be carried out with care so as not to hurt the reliability of the protocol. In the following, we describe how this is achieved in the HEAP protocol.

HEAP fanout adaptation. To get a sense of the underlying challenge, consider upload bandwidth as a measure of capability. A naive approach would simply consist for each node to periodically measure its capability and increase (resp. decrease) its fanout proportionally to the increase (resp. decrease) of its bandwidth -since the last measure. This approach has two major limitations. First, it could easily lead to a significant drop in the reliability of the system if all nodes see their upload capacity progressively diminish, even by a small proportion in each period. Eventually, all fanouts will end up significantly lower than the theoretical ln(n) threshold, impacting the reliability of the dissemination. Second, the unilateral decision of how to increase or decrease the fanout can lead to extreme situations of unfairness.

Instead in HEAP, nodes dynamically adjust their fanout according to the capability distribution of the nodes. To ensure that the contribution of a node matches it capability, each node needs to have an idea of its own position across nodes, capability-wise. To this end, we introduce a gossip-based capability aggregation protocol in which nodes periodically send their capability values to their neighbors. Periodically, each p i measures its capability, it normalizes it according to its local approximation of the global capacity, and it computes and then adopts a new target fanout. A major challenge towards achieving this goal is to prevent these adaptations from jeopardizing the overall reliability of a gossip dissemination. Effectively, a homogeneous fanout across nodes obviously limits the impact of the failure of a subset of the nodes on the reliability of the dissemination. HEAP ensures that (i) the fanout average remains close to ln(n), (ii) the fanout distribution matches the capability distribution, while the average fanout is kept accross nodes.

HEAP biased gossip target selection. It is clear that nodes involved early in the dissemination chain are of the utmost importance. One of the originality of HEAP is to place the most capable nodes in the beginning of the gossip dissemination. This ensures both that capable nodes be prevalent in the gossip phase and that they be proportionally more requested to provide the content. Achieving such an adaptation is challenging for two reasons. First, biasing the gossip target selection is somewhat antagonist with the uniform random selection of gossip targets, which is key to the reliability of traditional gossip approaches. Second, placing such nodes early in the dissemination chain, not only improves the overall efficiency of the system but also provides those nodes with an improved streaming quality. This gives an incentive to collaborate, but might as well give rise to freerider vocations. This latter issue is actually both more probable to happen and more harmful than in a standard gossip protocol.

To tackle this challenge, we propose a companion collaborative LIghtweight Freerider Tracking protocol, called LIFT. LIFT periodically audits randomly chosen nodes to verify if their behavior matches the expectations based on their capabilities. Basically, LIFT tracks down selfish nodes, that announce themselves as capable nodes by declaring a high capability to take advantage from the biased gossip target selection mechanism of HEAP. Such nodes clearly benefit from being placed early in the chain, but they significantly harm the whole system if they do not contribute as they should, that is by participating in the dissemination process according to their capabilities.

HEAP description

In this section, we provide the details of HEAP. As already explained, HEAP can be seen as the combination of (i) a standard gossip protocol as the one depicted in Algorithm 1, (ii) a fanout adaptation mechanism, (iii) a biased gossip-target selection, and (iv) a gossip-based capability-aggregation mechanism. In this section, we detail the three latter ones, the standard gossip protocol having been already presented in the previous section.

System model. We assume an unstructured overlay network of n nodes, built using a gossipbased peer sampling protocol; such protocols are known to achieve topologies close to those of random graphs. As this is not the purpose of the paper, we do not detail them here; the interested reader can refer to [START_REF] Jelasity | Gossip-based peer sampling[END_REF]. Each node in a peer-sampling protocol maintains a view of c nodes which represent a random sample of the network. The gossip partners are selected from this view. Nodes gossip their capability along with their IP addresses, so that each node knows the capability of its partners. We assume that each node has a large enough sample to make statistical inference on the population of the network.

Capability aggregation mechanism. The pseudocode of the capability aggregation protocol is depicted in Algorithm 2. Each node periodically (i.e., every capPeriod time units) gossips the latest capabilities it has received (including its own) to capFanout communication partners. Upon receipt of such information, the capability values are aggregated into nodesCap local to provide each node with information about the capabilities of other nodes.

Algorithm 2 The capability aggregation gossip protocol.

f target = cap local capavg • f init .
This allows each node to match its fanout with its capability ratio. There is however one exception. Nodes may also specify a maximum fanout value, f max , chosen so that it is always possible, in the worst case (in terms of bandwidth and latency) to exchange information with every set of f max nodes within less than the duration of a round (i.e., gossipPeriod). A node that has f target > f max does not increase its fanout further than f max but sends compensation messages to the poorest nodes it is aware of.

It is important to observe that we recompute a new target fanout periodically, at every adaption phase, based on the collected capability values as well as on the initial fanout f init ≃ ln(n), and not based on the last computed target fanout. This prevents the average value of the fanout from eventually diverging from f init .

Algorithm 3

The fanout adaptation mechanism. Biased gossip target protocol. In standard gossip protocols, nodes are picked uniformly at random from the local membership view. On the other hand, HEAP selects gossip targets according to their capabilities. The objective is to favor the nodes with the highest capabilities during the first hops of the dissemination and to select nodes with lower and lower capabilities at later hops. HEAP also strives to maintain a reasonable level of uniformity in the selection of nodes to preserve the reliability property of gossip dissemination. Instead of ensuring uniformity at each hop, HEAP aims at ensuring it across all hops, while introducing a bias toward specific hops for each node depending on its capability value. Nodes may also be selected with a low probability at other hops. In order to know at which hops each node should benefit from a bias in the peer selection, we divide the set of nodes into slices according to their capability values. To achieve this, we consider a message being disseminated in an ideal tree, with fanout f init , built by adding nodes in a breadth-first fashion in descending order of their capability values. In such a tree, the f init nodes with highest capability values receive the message at the first hop, the second f 2 init receive it at the second, the subsequent f 3 init at the third and so on: dissemination terminates in h tree hops.

In principle, each node should slice its view according to the expected number of hops in this ideal tree. The first slice should therefore contain the top f init nodes, the second should contain the second f 2 init nodes, and so on. In practice, however, each node only has a partial view of the network that is smaller than the size of the system. For this reason, it scales down the size of each slice according to the ratio between the size of the system and the size of its view, 6 while guaranteeing that each slice contains at least f target nodes.

Nodes use slices during gossip-based dissemination to select their gossip targets based on the hop count of the messages they need to disseminate. Because, in general, each gossip message is a collection of event ids with different hop counts, the hopcount of a message is determined as the average hop count over all the events ids it contains.

The publisher of the stream initiates the dissemination by selecting its targets from slice 0 , that is the slice containing the f target nodes with the highest capability values. In subsequent hops, a node at hop i in the dissemination selects its gossip targets from the set of slices between slice 0 and slice i . As shown in Section 5, this simple protocol biases the peer target selection whithout hampering too significantly the uniformity of the protocol, and thus without hurting the reliability of gossip-based dissemination.

LIFT

LIFT is a protocol aimed at tracking selfish nodes in a collaborative high-bandwidth content dissemination system. Although LIFT could be used in other settings, it is particularly interesting in the context of HEAP. Purely selfish nodes do not want to harm the system deliberately but only to take the most out of it while contributing as little as possible. However, as we explained previously, HEAP may both favor and be harmed by nodes with such selfish behaviors. Focusing on selfish behavior only, as opposed to BAR Gossip [START_REF] Li | BAR gossip[END_REF] or PeerReview [START_REF] Haeberlen | PeerReview: Practical accountability for distributed systems[END_REF] which deal with Byzantine behavior and provide strong guarantees, allows LIFT to operate without using any expensive key-based mechanism.

The LIFT protocol allows a node -the audit node -to periodically suspect other nodes and check if they are operating as they are supposed to, or if they exhibit selfish behaviors. Nodes having a high capability and lying about it punish themselves without impacting the performance in HEAP. Therefore, we focus on nodes declaring a high capability to be placed early in the dissemination chain. Such nodes may for instance be either complete freeriders and contribute nothing at all or liars (about their capability). Liars may contribute as much as they can, yet the discrepency with their expected contributions (based on their declared capabilities) may impact the overall efficiency of the system.

As pointed out, we focus here on the detection of selfish nodes. Properly punishing them requires further investigation and is left for future work. Each node logs when it sent a [Brief], which events were in the [Brief] and to whom it sent it. Additionally, each node must be able to confirm if it did receive a brief from a given node. This is done by keeping track of the requests sent. For presentation simplicity, we only consider one audit node and one audited (suspected) node. The algorithm for the audit node is shown in Algorithm 4 while the one for the audited nodes is in Algorithm 5.

The audit node suspects another node by requiring its short-term gossip history ([GMYH] message in Algorithm 4). The audited node replies with a history containing the identifiers of both the events it sent over the last period and of their recipients. The size of the reply message ([HIMH] message in Algorithm 4) is constrained to contain at most 10KB of data and at most 10s of past history to bound the associated overhead.

It may happen that the audited node does not seem to reply to an audit if: (a) one of the messages got lost ([GMYH] or [HIMH]) or (b) the audited node fakes message losses by not replying to the audit. Therefore, if the audit node does not receive any reply within a reasonable delay (e.g., dNoResp, typically 5s), it keeps sending up to nbOfNoResp other audit requests. After nbOfNoResp attempts, the audited node is considered non-responsive and its suspicion is confirmed.

Algorithm 4 LIFT -Audit node

Initialization: When the audit node receives a [HIMH], it randomly picks nbAckAsked supposedly sent [Brief] messages from the received history and selects their recipients as witnesses for the audited node. The audit node, then contacts the witnesses with a [AckRqst] to verify that they indeed received the [Brief] messages as declared, and then waits for them to respond with [Ack] or [NoAck].

1: suspectSet = Π 2:
Based on these replies, the audit node produces a verdict on the selfishness of the audited node. If the audit node receives nbAckNeeded [Ack] messages, it decides that the audited node is correct and reschedules it for suspicion in dResuspect seconds. On the other hand, if the audit node receives nbNoAckNeeded [NoAck] messages, it detects the audited node as a freerider. As pointed out earlier, punishing detected freeriders requires further investigation.

As [AckRqst], [Ack] and/or [NoAck] messages may get lost, the audit node, after a delay dAck, attempts again to give a verdict based on the [HIMH] received. After nbOfTriesWithSameHIMH attempts, it asks the audited node again for another [HIMH] and keeps running the above procedure until a decision can be reached. Note that the verification is done in priority with the same briefHistory to lower the traffic overhead and also to prevent the audited node from suddenly behaving perfectly correctly.

Evaluation

We evaluated HEAP on a streaming application with a single source and up to 236 PlanetLab nodes subscribed to the stream.

In this section, we first describe the experimental setting as well as the considered applica- tion. We then provide a detailed evaluation of the behavior of HEAP as well as a comparison with standard (homogeneous) gossip protocols with different fanouts. Unless stated otherwise, HEAP runs with an initial fanout of 6. We run homogeneous gossip with a fanout of 6, 8 and 10. We evaluated HEAP on a streaming application with a single source and up to 236 Plan-etLab nodes subscribed to the stream. We also report on the accuracy of the LIFT protocol. We finally show that the capability aggregation and the fanout adaptation protocols provide accurate results in dynamic environments.

In short, we demonstrate that HEAP matches the distribution of the node dissemination load and the distribution of the node's perceived quality to the distribution of their capability, without impacting the reliability and without any noticeable overhead.

Experimental setting

Video streaming application. We evaluated HEAP in the context of a video streaming application. We based the experiments on the parameters given in [START_REF] Li | BAR gossip[END_REF]. We stream video at the rate of 234 Kbps so that a source initiates a broadcast of 30 events per second. Each event has a size of 1Kbyte and a brief contains a maximum of 10 of those events. The events have an associated time to live value (TTL) of 10 seconds during which they are valid. Once a TTL expires, the event is simply dropped and no longer gossiped. We use 5 streams in each experiment.

Experimental testbeds. We deployed the video streaming application on over 750 Planet-Lab machines located all over the world on which we were able to run our streaming application on up to 236 nodes at the same time. The Planetlab deployment provides us with a real wide-area challenging environment.

PlanetLab and network capabilities. Because the PlanetLab nodes are situated mostly in research and education places, they benefit from a very good network quality, namely incoming and outgoing bandwidth (not to mention latency). As such, PlanetLab is not representative of a typical collaborative p2p system [START_REF] Spring | Using planetlab for network research: myths, realities, and best practices[END_REF], in which most nodes would be end user typically behind ADSL connection, with an asymetric bandwidth and limited upload/download capacities. For mapping a scaled-down approximation of internet nodes onto the PlanetLab network, we decided to artificially limit the upload and download capacity of nodes so that they match the bandwidth usually available for home users, namely 56K, ISDN, (A)DSL and cable. To this end, we used internet usage statistics per continent [2] to have a realistic distribution of nodes across different continents and then limited the bandwidth according to the distribution of bandwidth in each of the different continents [1].

HEAP configuration. As previously mentioned, HEAP requires each node to be provided with a sufficiently large sample to be able to bias the target selection for instance. Given the limited scale provided by Planetlab testbed, we assumed a global membership. Also, we considered a static distribution of capabilities. Note that the accuracy of the aggregation protocol is provided through another experiment, with dynamically changing capabilities.

Evaluation metrics. We compare HEAP against an homogeneous gossip with various fanout along the following metrics: (i) the overall streaming quality of the system, (ii) the distribution of the streaming quality according to node capability, reflecting the ability of HEAP to optimize the dissemination by exploiting the capability of the most capable node, and (iii) the traffic generated for the dissemination of the stream. This shows that HEAP does not generate overhead over homogeneous and a better utilization of bandwidth among nodes.

We also report on the impact of selfish nodes in HEAP and show the ability of LIFT to detect such nodes. We provide figures on the precision and speed of selfish node detection, the percentage of false positives and the overhed of the protocol.

HEAP versus homogeneous gossip

Streaming quality. The streaming quality is computed as follows: we consider a sliding window, corresponding to 1s of streaming. For each position of the window over the whole stream, we compute the number of nodes that received at least 92% of the streamed packets. This value is assumed to be the lower bound to be able to watch a stream [START_REF] Li | BAR gossip[END_REF]. The values represented are the average over all windows.

Figure 1 depicts the distribution of the values of this metric over the nodes. The nodes are sorted by increasing capability and grouped in chunks of 10% nodes. Each value represents the percentage of nodes (averaged in the set of 10% nodes) that received at least 92% of the streamed packet using a sliding window size of 1s.

Several observations can be made on this figure. First, HEAP outperforms all homogeneous gossip configurations, including those with a higher average fanout than HEAP. The figure reveals that HEAP provides a better streaming quality for all nodes regardless of the capability. Many nodes with the highest capability get a good stream quality with HEAP. (This actually shows that HEAP provides an incentive for selfish nodes to be placed early in the dissemination, for instance.) In addition, HEAP dramatically improves the quality of low capability nodes. While only a few percent of such nodes get a good streaming quality with homogeneous gossip and a fanout of 6, HEAP achieves approximatively 55%. We also provide the quality achieved by the biased gossip target selection only and the fanout adaptation only. Even though the results are better than homogeneous gossip, they are not as performant as HEAP. This conveys the fact that HEAP exploits the most capable nodes to significantly improve the quality of both the most capable nodes and the low-capability nodes. Finally, we observe that the streaming quality metric matches the capability distribution.

Figure 2 shows the total traffic generated by the three configurations of homogeneous gossip (fanout of 6, 8 and 10), HEAP, and each of biased target selection and fanout adaptation only. We observe that HEAP outperforms all other configurations and provides 77% of nodes with a good stream quality, while any configuration of homogeneous gossip is lower than 60%. While we observe a significant improvement, the percentages remain lower than with HEAP. This illustrates the fact that the strength of HEAP resides in combining the fanout adaptation and the biased gossip target selection. Contribution versus capability. Figure 3 shows the traffic according to the capability. We observe that in all homogeneous gossip configurations, the traffic is fairly homogeneous across all nodes except for the very low capability nodes. In biased gossip target configurations, we observe that the traffic matches the distribution of capability. This reflects a better bandwidth usage using HEAP. Again we observe that HEAP outperforms any of its two sub mechanisms used in isolation.

Figure 4 shows the overall traffic generated by all the protocols. Note that most of the traffic is not represented on the figure. We observe that the protocol generated with the biased gossip target selection performs best. What is clear from the plot is that increasing the fanout in homogeneous gossip significantly increases the total traffic. The total traffic is increased in HEAP which is consistent with the fact that HEAP provides a better availability.

LIFT performance

We first expose the key parameters of LIFT and the inheritent limitations to the simplicity of the protocol. False positives. A false positive is when a node is detected freeriding when in fact it was behaving correctly. This can happen in two cases:

1. The suspected node tried to send all its payload ([Brief] message) and logged them as being sent correctly but x ≥ nbAckNeeded of them got lost in the communication channels. These x messages are thus sent with the history of briefs ([HIMH] messa ge) sent to the audit node. If the audit node asks for confirmation for those exact x briefs, the node will be detected freeriding and in fact was not.

2. Assume the suspected node s sent a brief b to a node r and the delay between the time it was sent (thus logged) and the reception is given as d s,r . If the time taken for the audit node to ask for a briefHistory ([GMYH] message), receive it and contact r is smaller than d s,r then r will reply it did not receive b (which is on the way). The probability that this happens once is very small and the probability that this happens nbAckNeeded times is even smaller.

Non detection. A case of non detection is when a freerider can continue misbehaving without being detected by the audit node. This can happen when the freerider nodes sends x ≥ nbAckNeeded briefs but obviously not to all those it was supposed to in its past history. If the history is sent to the audit node and the audit node gets nbAckNeeded or more confirmations from the witnesses, the freerider has done enough work not to be detected. The probability of detection trivially increases as x decreases.

Detection Quality

We have experimented LIFT with nbAckAsked=3, nbAckNeeded=2 and nbNoAckAsked=3, meaning that for 3 [Ack]/[NoAck] replies, if 2 of them are positive, the audited node is disculped, if 3 replies are negative, the audited node is detected as a freerider.

Detection Precision. The number of false positives we have detected with these parameters is 15 out of 3777 different node verifications (each node getting verified 45 times on average), thus accounting for a false positive detection percentage as low as 0.397%.

The number of freeriders that we could not detect is 16, thus accounting for a non detection percentage as low as 0.424%.

Detection Speed. We have experienced different kinds of freerider, spanning from the very selfish one that never sends a brief to the very mild freerider that sends 95% of the time what it should. We thus define the percentage of freeriding of a node as the ratio between the number of briefs the node did not send over the number of briefs the node was supposed to send. With the given parameters Figure 5 shows that LIFT has no problem detecting fully freeriding nodes. The number ith of verifications needed to detect nodes grows as the freeriding percentage decreases, and even nodes with a freeriding percentage of 5% (i.e., that behave honestly 95% of the time) get detected, but with 24 verifications on average.

Overhead

For one verification, that is sending a [GMYH], receiving its corresponding to the [Brief] that was supposedly sent. The reason to return the [Request] is that even in case s sent a given brief to r, we want to make sure s did not intentionally only send a subset of the events requested by r -instead of sending only a limited number of briefs, a selfish node could send all briefs, but containing only a limited amount of the events they should really contain. Table 1: Average size of the different LIFT messages (bytes).

Structural Properties

Accuracy of the capability aggregation protocol. Although we used a static capability distribution to evaluate HEAP, we provide below the accuracy of the capacity aggregation protocol that we run separately. The capability aggregation protocol provides each node with the ability to estimate the gloabl capability of the system. Figure 6 depicts the output of the capability aggregation protocol on one of the 236 PlanetLab nodes. Capability data is gossiped every second. The capability estimate and the real capability wealth are depicted respectively by the plain and dashed lines. Error bars are also plotted and represent the range of errors among node estimations. The absolute error is represented by the light plain line and is computed as the difference between the real capability and the average of the estimated values. The maximum and average error are respectively 14.39% and 3.27% (Figure 6). We thus observe that the estimation on each node is quite accurate. Accuracy of the fanout adaptation. Likewise, we run an experiment with capability changing over time. Figure 7 shows that the average fanout value over time is maintained. Error bars are represented on the graph and show that the average value remains within reasonable bounds compared to the mean fanout set to 4 in this experiment. The figure shows that the maximum fanout remains within the bounds set by the compensation protocol (set to 10 in this experiment). We observe that the fanout adaptation protocol suceeds to keep the average fanout value close to the initial fanout. This section discusses related work both in the area of gossip-based protocols and peer to peer streaming systems. We focus more specifically on approaches that account for heterogeneity.

Gossip-based protocols. Gossip based protocols are scalable and they exhibit high resilience to failures and good probabilistic reliability guarantees [START_REF] Eugster | ∆-reliable broadcast: A probabilistic measure of broadcast reliability[END_REF]. They provide a general-purpose appealing solution for a wide range of distributed applications [START_REF] Birman | Bimodal multicast[END_REF] such as replicated databases [START_REF] Demers | Epidemic algorithms for replicated database maintenance[END_REF], aggregation (cf. [START_REF] Jelasity | Gossip-based aggregation in large dynamic networks[END_REF][START_REF] Gupta | Scalable fault-tolerant aggregation in large process groups[END_REF][START_REF] Kempe | Gossip-based computation of aggregate information[END_REF]), failure detection [START_REF] Van Renesse | Astrolabe: A robust and scalable technology for distributed system monitoring, management, and data mining[END_REF][START_REF] Van Renesse | A gossip-style failure detection service[END_REF], mobile event notification [START_REF] Haas | Gossip-based ad hoc routing[END_REF][START_REF] Luo | Route driven gossip: Probabilistic reliable multicast in ad hoc networks[END_REF], and overlay construction [START_REF] Jelasity | T-man: Gossip-based overlay topology management[END_REF][START_REF] Montresor | Chord on demand[END_REF][START_REF] Bonnet | Small world networks: From theoretical bounds to practical systems[END_REF]. In addition, specific gossip protocols were devised to support random peer selection [START_REF] Allavena | Correctness of a gossip based membership protocol[END_REF][START_REF] Eugster | Lightweight probabilistic broadcast[END_REF][START_REF] Jelasity | Gossip-based peer sampling[END_REF][START_REF] Ganesh | Peer-to-peer membership management for gossipbased protocols[END_REF][START_REF] Voulgaris | Cyclon: Inexpensive membership management for unstructured p2p overlays[END_REF], or to cope with severe types of failures and attacks [START_REF] Haridasan | Defense against intrusion in a live streaming multicast system[END_REF][START_REF] Li | BAR gossip[END_REF][START_REF] Malkhi | Optimal unconditional information diffusion[END_REF][START_REF] Minsky | Tolerating malicious gossip[END_REF][START_REF] Bortnikov | Brahms: Byzantine resilient random membership sampling[END_REF]. As we pointed out in the introduction, these protocols involve all nodes evenly in the dissemination task [START_REF] Melamed | Araneola: A scalable reliable multicast system for dynamic environments[END_REF], which is often undesirable in highly heterogeneous systems such as the Internet. Our objective is thus to tackle this limitation and have nodes contribute to the system according to their capabilities.

Some amount of heterogeneity is present in gossip protocols that do not assume a prior knowledge of the size of the system, e.g., [START_REF] Ganesh | Peer-to-peer membership management for gossipbased protocols[END_REF], and where nodes may start with different fanouts. However, these protocols consider such heterogeneity as a temporary situation and typically seek to converge towards a stable state where all nodes have the same fanout of ln(n). In contrast, HEAP seeks to assign different fanouts to different nodes in order to achieve better resource utilization.

Certain gossip-based dissemination protocols do have adaptive features. Some propose ideas that resemble our fanout adaptation scheme, while others exploit techniques similar to our biased gossip-target selection scheme. However, to the best of our knowledge, none of them combines both.

The gossip protocol proposed in [START_REF] Rodrigues | Adaptive gossip-based broadcast[END_REF] adapts the emission rate for a known buffer size depending on the number of participating nodes. In Smart Gossip [START_REF] Kyasanur | Smart gossip: An adaptive gossip-based broadcasting service for sensor networks[END_REF], nodes of a wireless network gossip with different probabilities to account for the heterogeneity of the topology. The goal, however, is to reduce the overall number of messages sent, rather than adapt to individual capabilities. The protocol of [START_REF] Garbinato | An adaptive algorithm for efficient message diffusion in unreliable environments[END_REF] aims at probabilistically maximizing reliability in a spanning tree depending on the characteristics of the network. This approach is related to ours as nodes exchange messages to gather a knowledge of the topology. The aim of providing an optimized tree is fairly different though. In Gravitational Gossip [START_REF] Jenkins | A gossip protocol for subgroup multicast[END_REF], the fanin of nodes may be adjusted based on the quality of reception they expect. This is achieved by biasing the node selection such that certain nodes have better chances to be selected for gossip than others. While somehow similar in spirit to our gossip-target selection, the technique is static and focuses on the fanin. SwapLinks [START_REF] Vishnumurthy | On heterogeneous overlay construction and random node selection in unstructured p2p networks[END_REF] builds a peer-to-peer unstructured overlay network by statistically controlling the degree of each node depending on its capacity. This approach is related to our fanout adaptation mechanism as nodes with higher degree are selected more often and contribute more to the algorithm. Yet, non uniform peer-selection may hurt the reliability of gossip-based dissemination. In addition, this approach does not rely on the aggregated capacity of nodes across the system.

Heterogeneous-aware p2p streaming. Following the wide penetration of Internet access into homes, peer-to-peer streaming systems have received an increasing interest as ways to leverage the computing power available at the edge of the network. While single-tree approaches have dominated at first, they turn out to be highly vulnerable to failures as a failed node harms its entire subtree. Multi-tree schemes have been proposed such as Splitstream [START_REF] Castro | SplitStream: high-bandwidth multicast in cooperative environments[END_REF], Chunkyspread [START_REF] Venkataraman | Chunkyspread: Heterogeneous unstructured treebased peer to peer multicast[END_REF] and Coolstreaming [START_REF] Li | Inside the new coolstreaming: Principles, measurements and performance implications[END_REF][START_REF] Zhang | Coolstreaming/donet: A data-driven overlay network for efficient live media streaming[END_REF]. They enhance reliability by ensuring that part of the stream is disseminated through diverse paths, a characteristic that comes for free in gossip-based protocols where the neighbors of each node keep changing over time [START_REF] Jelasity | Gossip-based peer sampling[END_REF].

Splitstream accounts for heterogeneous capacities by enabling nodes to limit the number of their descendants in a tree. Yet, heterogeneity is not taken into account dynamically and each node takes local decisions without any normalization over the distribution of capacities across nodes. The work in [START_REF] Bishop | Considering priority in overlay multicast protocols under heterogeneous environments[END_REF] and [START_REF] Sung | Enabling contribution awareness in an overlay broadcasting system[END_REF] proposes a set of heuristics that account for bandwidth heterogeneity and node uptimes in tree-based multicast protocols. This leads to significant improvements in bandwidth usage and ultimately in the system's performance, particularly in that experienced by high contributors. In addition the protocols aggregates global information about the implication of nodes across trees by exchanging messages along tree branches in a way that relates to our capacity aggregation protocol.

Chunkyspread [START_REF] Venkataraman | Chunkyspread: Heterogeneous unstructured treebased peer to peer multicast[END_REF] is a multi-tree Splitstream-like system accounting for heterogeneity using the SwapLinks protocol [START_REF] Vishnumurthy | On heterogeneous overlay construction and random node selection in unstructured p2p networks[END_REF]. Nodes contribute in proportion to their capacity and/or willingness to collaborate. This is reflected by heterogeneous degrees across nodes. Yet there is no specific scheme to discover and aggregate information about node capacities which is simply assumed to be known by the application. A follow-up protocol [START_REF] Steele | A parameter-free load balancing mechanism for p2p networks[END_REF] uses a gossip-based aggregation mechanism to compute some global knowledge of the system through gossiping in order to set the parameters of the Swaplinks protocol. This again plays a similar role as our capacity aggregation protocol. While improving upon single tree approaches, the fairly static nature and the lack of redundancy of these tree-based approaches makes them still vulnerable to churn.

As opposed to tree-based systems, Coolstreaming [START_REF] Zhang | Coolstreaming/donet: A data-driven overlay network for efficient live media streaming[END_REF] is data-driven. Content location information is gossiped between neighbors (based on a membership protocol providing each node with a random sample of the network), while the actual content is pulled as in swarming systems. However, dissemination paths in Coolstreaming are static: nodes explicitly choose their partners and do not change them until they have to be replaced, while our approach exhibits a more dynamic nature. The analysis of real Coolstreaming traces [START_REF] Li | Inside the new coolstreaming: Principles, measurements and performance implications[END_REF] has revealed huge heterogeneity in terms of contribution as a result of its partner selection mechanism. Yet nodes have no information available about the load distribution across nodes. The similarity with HEAP is thus limited to the selection of targets based on capability.

Concluding Remarks

We propose HEAP, a new gossip-based protocol for collaborative high-bandwidth content distribution. HEAP adapts the dissemination load of the nodes to account for their heterogeneity. Experimental results on a video streaming application demonstrate the significant improvement of HEAP over a standard homogeneous gossip protocol.

We considered upload capacity as the main factor for heterogeneity, which is crucial in the context of streaming. Other factors could reveal important in other applications. We believe HEAP could easily be adapted to such factors encapsulated within the underlying aggregation protocol. Also, we considered the choice of the fanout and the gossip targets as the way to adjust the load of the nodes. One might also explore adapting the frequency of the dissemination or the memory of the nodes devoted to the dissemination.

Figure 1 :Figure 2 :

 12 Figure 1: Quality vs capability: percentage of nodes receiving at least 92% of the stream for each segment of 10 capability percentiles.

Figure 3 :Figure 4 :

 34 Figure 3: Bandwidth usage vs capabilities: average bandwidth utilization for each capability value

Figure 5 :

 5 Figure 5: Freeriding percentage of a node vs the average number of verification for detection.

Figure 6 :

 6 Figure 6: PlanetLab: Accuracy of the capability aggregation protocol

Figure 7 :

 7 Figure 7: PlanetLab: Evolution of the average fanout value

  Algorithm 1 Basic gossip protocol

	Initialization:
	1: f := ln(n) + c + O(1)	{f is the fanout}
	2: eventsToPropose := eventsDelivered := requestedEvents := ∅
	3: trigger start(GossipTimer(gossipPeriod))
	upon event publish | e do	{The application layer uses this primitive every time a new event e is produced
		and needs to be broadcast}
	4: deliverEvent(e)
	5: gossip({e.id}, f )
	upon event fire | GossipTimer do
	6: gossip(eventsToPropose, f )
	7: eventsToPropose := ∅	{Infect and die}
	upon event receive | [Propose, eventsProposed] do
	8: wantedEvents := ∅
	9: for all e.id ∈ eventsProposed do
	10:	if (e.id / ∈ requestedEvents) then
	11:	wantedEvents := wantedEvents ∪ e.id
	12: requestedEvents := requestedEvents ∪ wantedEvents
	13: trigger reply | [Request, wantedEvents
	upon event receive | [Request, wantedEvents] do
	14: askedEvents := ∅
	15: for all e.id ∈ wantedEvents do
	16:	askedEvents := askedEvents ∪ getEvent(e.id)
	17: trigger reply | [Brief, askedEvents
	upon event receive | [Brief, events] do
	18: for all e ∈ events do
	19:	if (e / ∈ eventsDelivered) then
	20:	eventsToPropose := eventsToPropose ∪ e.id
	21:	deliverEvent(e)
	function selectNodes(f ) returns set of nodes is
	22: return f uniformly random chosen nodes in Π
	function getEvent(event id) returns event is
	23: return the event corresponding to the id
	procedure deliverEvent(e) is
	24: deliveredEvents := deliveredEvents ∪ e
	25: trigger deliver | e	{The event e is given to the application layer}
	procedure gossip(event ids, fanout) is
	26: communicationPartners := selectNodes(fanout)
	27: for all p ∈ communicationPartners do
	28:

trigger send | p, [Propose, event ids]

  The pseudocode of the fanout adaptation mechanism is instead depicted in Algorithm 3. Nodes use the capability values collected in nodesCap local to compute their fanouts for gossip dissemination, f target , as follows:

	Initialization:
	1: capFanout :≃ ln(n)
	2: cap

local := local node's capability 3: nodesCap local := set of w capabilities 4: trigger start(CapGossipTimer(capPeriod)) upon event fire | CapGossipTimer do 5: values := cap local ∪ k most recently received capability values 6: communicationPartners := selectNodes(capFanout) 7: for all p ∈ communicationPartners do 8: trigger send | p, [CapAgg, values] upon event receive | [CapAgg, values] do 9: nodesCap local := nodesCap local ∪ values Fanout adaptation mechanism.

  trigger start(AuditTimer(auditPeriod)) upon event fire | AuditTimer do 3: nodes := pick numberOfConcurrentAudits nodes in suspectSet 4: for all p in nodes do trigger send | b.dest, [AckRqst, b.header] upon event receive | [Ack, header] do 13: suspect := header.src 14: if (number of [Ack] received for suspect ≥ nbOfAckNeeded) then 15: trigger trust suspect and resuspect in dResuspect seconds 16: else if (number of [NoAck] received for suspect ≥ nbOfNoAckNeeded) then trigger resuspect suspect x times with same briefHistory if no decision can be made 20: trigger send | header.src [GMYH] if no decision can be made after x tries with the same briefHistory

	5:	trigger send | p, [GMYH]
	6:	resuspect p in dNoResp seconds if no [HIMH] answer from p
	upon event receive | [HIMH, briefHistory] do
	7: if (briefHistory < 5s) then
	8:	resuspect in dSmallNoLog seconds
	9: else
	10:	pick nbAckAsked random briefs b in briefHistory
	11:	for all b do
	12:
	17:	trigger punish | suspect	{The suspect is detected as a freerider and must thus be punished}
	18: else
	19:

  Algorithm 5 LIFT -node. upon event receive | [GMYH] do {Give Me Your History} 1: briefHistory := the last historySize briefs sent {historySize is chosen such that the history = min(10s, 10KB)} 2: trigger reply | [HIMH, briefHistory] {Here Is My History} upon event receive | [AckRqst, header] do 3: if self received a brief corresponding to header then

	4:	trigger reply | [Ack, header]
	5: else
	6:	trigger reply | [NoAck, header]

  [HIMH] response, sending nbAck-Asked [AckRqst] and receiving nbAckAsked [Ack]/[NoAck], the total traffic usage is bounded by 12269+nbACKasked • max(1166, 767) bytes. The sizes of each individual LIFT messages are given in Table 1. The [Ack] messages are significantly larger than the [NoAck] ones, because they additionally contain the [Request]

In contrast, even though trees are often seen as the ultimate efficient way of dissemination, they are not very robust in large-scale dynamic settings. For instance, a perfectly structured tree for disseminating a stream, over 30 runs on PlanetLab, in all runs, a significant number of nodes were not able to view the stream due to the static nature of trees exacerbating the loss rate of UDP packets.

Homogeneous means that all nodes contribute the same amount.

Note that gossip-based dissemination protocols also follow this canvas[START_REF]Gossip-based computer networking[END_REF].

Obviously, in an uneven distribution of fanout values, the failure of a node having a large fanout may have a larger impact on dissemination.

Note that this observation is also valid for tree-based approaches.

We assume that each node has a large enough view to make this scaling possible.

Acknowledgements

The authors would like to thank Ken Birman, Pascal Felber, Dahlia Malkhi and Jean-Philippe Martin for useful comments, Fabian Kaelin and Song Pak, undergraduates students at EPFL for early work on the gossip simulations and on the PlanetLab implementation. Special thanks to Boris Koldehofe for many fruitful discussions about this project. Maxime Monod has been partially funded by the Swiss National Science Foundation with grant 20021-113825.