AlTiS (Altimetry Time Series) is a radar altimetry data processing and visualization software, tailored for fine-grained analysis of small scale water bodies.

Its goal is the obtaining water-level time-series derived from the altimetry measurements, but it can also be used to generate time series of any altimetrybased parameters (e.g., corrections applied to the range, backscattering coefficients, or brightness temperatures).

AlTiS software is used to compute Water Surface Elevation from nadir altimeters within the ESA-CCI River Discharge precursor project.

CTOH Altimetric products available for AlTiS processing

Data requests

AlTiS can process altimetric data products from the missions : Jason-1/2/3, ERS-2, ENVISAT, SARAL, Sentinel-3A/B, Sentinel-6/Jason-CS and soon the nadir altimeter onboard SWOT. They are supplied for free through a web request form on the CTOH website.

AlTiS is mainly employed for hydrological applications and can be used for training courses on radar altimetry at bachelor or master levels. It is also a very convenient tool to analyse the radar altimetry data contained in the GDR over any type of land surfaces.

AlTiS is free software developed by CTOH as part of its activities as a National Observation Service. AlTiS is released as open source under the CeCill License and target GNU/Linux and, Windows 10/11 operating systems under python3 environment. AlTiS is available on GitLab.

Hydrological applications

Graphical User Interface

* Product supplied to expert users only.

Open source software

AlTiS users

Screenshot of AlTiS GUI : 4 displays windows in order to edit altimeter measurement graphically Today, more than 70 users of over 21 countries have processed altimetric data to generate water level time series with AlTiS software. It is used for research and training activities.

The CTOH holds its own AlTiS teaching courses for students, engineers and researchers in the Midi-Pyrénées Observatory in Toulouse, France. In addition, it has created an AlTiS user network to provide information about software updates and new altimetric products.

On the current year, the CTOH has already answered more than 220 data requests.

An example of a time series of water level at Lambaréné (Ogooué River Basin in Gabon in Equatorial Africa) from the in-situ gauge record (black continuous line), the multi-mission altimetry-based record (ERS-2 data are represented with diamonds, ENVISAT with blue crosses on its nominal orbit and with green triangles on its second orbit, Cryosat-2 with green-blue stars, SARAL with red circles, Sentinel-3 with purple dots) [Bogning, Sakaros, et al., Remote Sensing, 2018].

An example of the altimetry data editing in the case of a river in the Inner Niger Delta area :

• First, a rough selection of the altimetry data is performed: (a) all altimetry data located a few kilometers away from the center of the river are selected (left panel), the major topographic features, such hills, river banks, tributaries, etc. can be identified (central panel), temporal variations of the altimetry signal cannot be related to any hydrological signal (right panel).

  Sylvain Biancamaria; Damien Allain; Florence Birol; Sakaros Bogning; Robin Chevrier; Jean-François Crétaux; Lucrèce Djeumeni; Julien Lefebve; Lancelot Leclercq; Fabien Léger; Rosemary Morrow; Fernando Niño LEGOS, Université de Toulouse, CNES, CNRS, IRD, UPS: https://www.legos.omp.eu/ctoh

  Using a Graphical User Interface (GUI), without requiring any particular skills in data processing, the user can handle altimetry data in order to :•Plot several parameters of altimetric measurement like surface height, altimetric range, atmospheric corrections applied to the range (ionospheric correction and wet and dry tropospheric corrections) as a function of latitude/longitude. • Display along-track characteristic parameters of the waveform like the backscatter coefficient, and peakiness. • Using a (Landsat) background map, easily select altimetric measurements to remove outliers. • Generate water height time series from the valid altimetry data previously selected • Export the time series into various files format as CSV and HydroWeb AlTiS accepts CTOH GDR altimetry products (Level 2 high frequency 10/20/40Hz data supplied by the CTOH). These data have been specifically conditioned to optimize the data size by making a geographical selection and includes the right altimetry parameters for hydrological studies.

  • Then, a more accurate selection is made; (b) the number of data is decreasing and outliers are removed (left panel), the shape of the river and its temporal variations in width (central panel) and height (left panel) becomes clearer. • This process is repeated until the final selection is achieved; (c) for its research and validation studies. Time series can be exported to the HydroWeb web site. Here we show an example of the Ossa lake (Cameroon).


Philippe Lory

The good company of T-type calcium channels

Corresponding author : Philippe Lory

Email : philippe.lory@igf.cnrs.fr Declaration (ethical approval, funding, availability of data and materials) : "not applicable"

Commentary on : 'T-type calcium channelosome', a review by N. Weiss and G.W. Zamponi (no abstract) 'You'll never walk alone' is the title of a popular song that now sounds well for ion channels.

In recent years, the word 'channelosome' has been coined to better capture the way in which some ion channels intimately involve protein partners to properly drive their functional signaling. In their 'T-type calcium channelosome' review, Weiss & Zamponi [10] provide for the first time a channelosome view of T-type Cav3 voltage-gated calcium channels (Cav) by gathering and merging a wealth of recent evidence showing that these channels are functionally determined by a wide range of protein-dependent modulations. As a rational definition, the 'channelosome' may be presented as the collection of all the proteins involved in intrinsic channel support and anchoring, as well as the proteins involved in posttranslational modulations, e.g. phosphorylation. In the Cav channel family this corresponds perfectly to the L-types (Cav1) and neuronal P/Q-, N-and R-types (Cav2) channels, whose native activities depends on a tight association of the 1 pore subunit with the auxiliary  and 2/ subunits, and possibly also the  subunit [START_REF] Catterall | Voltage gated sodium and calcium channels: Discovery, structure, function, and Pharmacology[END_REF]. Some studies have now consistently expanded our knowledge of the Cav1 and Cav2 channelosomes by employing proteomics approaches [START_REF] Muller | Quantitative proteomics of the Cav2 channel nano-environments in the mammalian brain[END_REF] [1] [START_REF] Liu | Mechanism of adrenergic Ca(V)1.2 stimulation revealed by proximity proteomics[END_REF]. Apart from the Cav channel landscape, there are many ion channels that depend critically on their channelosome structure to be functionally active. One recently described situation in the 4-domain channel family relates to sodium-leak channel NALCN, which must be co-expressed with three subunits UNC-79, UNC-80 and FAM155/NLF1 [START_REF] Monteil | New insights into the physiology and pathophysiology of the atypical sodium leak channel NALCN[END_REF] to exhibit channel activity.

The great interest of the Weiss & Zamponi review [10] is to scheme the appearance of the Ttype Cav3 channelosome as illustrated in Figure 1, although to date very few proteomics studies have been reported for these channels. The lack of available selective-or specificallydesigned tools, such as Cav3 antibodies or epitope-tagged Cav3 channels, has hampered investigations of the Cav3 channelosome. We can expect these approaches to be developed soon for any of the Cav3.1, Cav3.2 or Cav3.3 channels, enabling better resolution of the 'primary' Cav3 channelosome. A more complex level of the channelosome is linked to the socalled 'regulators'. In this review, it appears that Cav3 channels are subject to a variety of protein-dependent modulations that can significantly tune their functional activity. Up to eigtheen such regulators are described here, including syntaxin1A, 22 G-protein, calmodulin, USP5, STAC1 … So far, it is not clear whether any of these regulations are exclusive for one of the three Cav3 channel isoforms (Cav3.1, Cav3.2 or Cav3.3), although the published data nicely compiled here show there are selective features for some of these modulations, with Cav3.2 channels being by far the most prone to modulation. Some findings remain puzzling, such as how Cav3 channels might autoregulate themselves, possibly through selfassembly, to promote an auto-inhibitory phenotype [6 ,7]. In addition, Cav3 channels can also interact with other ion channels, including calcium-activated potassium channels (e.g. KCa1.1 and KCa3.1), based on a Cav3-KCa colocalization that delimit a calcium microdomain responsible for functional modulation of KCa channels. This modulation ultimately regulates the resting membrane potential and cellular excitability.

When considering this 'regulatory' channelosome (modulosome) of Cav3 channels, little is known about the post-translational regulation of the Cav3 proteins. But the first steps are taken, with reports on how glycosylation, ubiquitination or phosphorylation of the Cav3 proteins impact their activity. Deciphering further these direct protein-dependent regulations will open up new opportunities to develop innovative therapeutic strategies, as reported for the dynamic deubiquitinase USP5-Cav3.2 regulation in pain therapy [START_REF] Garcia-Caballero | The deubiquitinating enzyme USP5 modulates neuropathic and inflammatory pain by enhancing Cav3.2 channel activity[END_REF]. Mass spectrometry approaches will undoubtedly allow the identification of other active regulation sites in a near future, hopefully selective for a single Cav3 isoform or for a few splice variants of a given isoform. In the meantime, studies of mutations causing diseases (channelopathies), which are currently being identified for Cav3 channels [START_REF] Lory | Neuronal Cav3 channelopathies: recent progress and perspectives[END_REF], may also help further decipher how some of the reported Cav3 regulations can be specifically affected in some disease conditions. Taken together, this 'T-type calcium channelosome' review by Weiss & Zamponi digests decades of effort to decipher Cav3 modulations and, more importantly, points to future research needed to document both the generic" and the "isoform-selective" T-type calcium channelosomes. Clearly, the Cav3.1, Cav3.2, and Cav3.3 subunits of T-type channels "never walk (work) alone" in the panorama of cellular excitability.

Figure 1 .

 1 Figure 1. An illustration symbolizing the many regulators decorating Cav3 T-type calcium channels


L'individuation humaine, une reproduction cosmique (postface)

Noémie Merleau-Ponty (CNRS-IRIS)

In La vie prénatale. Destin, identité, mémoire, Frédérique Ildefonse et Silvia D'Intino (eds), Jérôme Million, 2023 Saraswati veille à côté de moi, sous la figure d'une statue. Patronne des arts et des savoirs dans le panthéon hindou, ses accords à la veena font vibrer l'univers. Bienheureuse, bienheureux qui écoute, entend, murmure et prie, offre et honore. Réminiscences de l'Intelligible dans le platonisme, sacrifices pour accéder à un monde céleste à la vitalité permanente dans l'Inde hindoue, stratégie en rapport à un ensemble de forces en Chine ancienne, traduction de Boèce pour la bioéthique de l'embryon contemporain, il y a plusieurs manières pour l'individu de s'accorder avec un cosmos vivant de significations. Ce faisant, l'individu dessine, peut-être, une voie qui serait la sienne au sein d'un monde qui l'a façonné. Sa vie, il la doit en grande partie à une vie prénatale, préfiguration de son individualité ou champ qui détermine une individuation.

Etudier la vie, d'avant une vie née à l'existence, opère un déplacement heuristique fécond par rapport aux études anthropologiques sur la parenté. Certes, ces dernières ont toujours décrit la contribution de forces cosmiques au façonnage des personnes dans des réseaux sociaux structurés autour d'une famille. Mais, le geste ici proposé étudie le lien entre une individuation vivante et l'univers dans lequel elle prend vie. Il ne s'agirait pas d'entendre la vie prénatale dans une temporalité linéaire, un passé uniquement force du présent, mais bien une réalité dans laquelle une existence qui n'est pas née y est pourtant modelable. La vie prénatale est toujours accessible, si tant est que les efforts propres à chaque monde soient compris et réalisés par celles et ceux qui désirent s'y rendre, non en un lieu, mais en un Soi.

Dans chaque cas, un individu naît à l'humanité à partir d'une perte, celle de la mémoire des idées dans le platonisme, celle de l'union avec le principe vital dans la tradition hindoue, celle de sa liberté face au destin dans la Chine ancienne ou chez les Bassar du Togo. Philosophie, rituels et droiture des comportements sont autant de pratiques qui permettent à l'individu de trouver un chemin vers le monde qui l'a créé, et par là-même retrouver ce qui a été perdu pour générer un pouvoir de transformation. Les êtres humains sont en capacité d'apprendre et relater, à travers des textes et des traditions orales, que son existence peut reconfigurer ce dont elle est tributaire.

Luc Brisson rappelle ainsi que l'âme, principe d'animation d'un corps, migre là où elle peut être reçue. Il évoque : « Pour un platonicien comme Porphyre, tel embryon, et donc tel corps, présente telle aptitude à recevoir une âme pourvue de telles ou telles dispositions. C'est ce qu'explique Porphyre dans son traité Sur la manière dont l'embryon reçoit l'âme : « [...] en fait, que l'on suppose que l'âme, parce qu'elle se trouve dans le monde, traîne avec elle un corps fait d'éther, de souffle, d'air ou d'un mélange de ces éléments, ou qu'on la suppose capable, même sans ces véhicules, de venir s'établir dans les vivants aptes à accueillir sa présence, c'est d'un coup qu'elle produit l'animation du sujet dans son ensemble [...] » (11,(45)(46)(47)(48)(49)(50). C'est donc enveloppée de son pneûma qu'une âme vient de l'extérieur s'établir dans un corps apte à la recevoir, à la naissance. Par la suite, elle va mouvoir ce corps terrestre et le régir. » Frédérique Ildefonse s'intéresse quant à elle à une autre étape de la vie prénatale dans le platonisme, non pas conception de l'embryon, mais espace intermédiaire entre différentes existences. D'une vie à l'autre, l'Intelligible et ses âmes sont en harmonie, là où ce qui est juste, est accord aussi bien que justice. Cet équilibre entre l'objet des contemplations et le sujet contemplateur est perdu à la conception. La philosophie relève d'un effort pour retrouver cette harmonie métaphysique, en s'attachant à la pratiquer. On lit ainsi en conclusion du chapitre que « redresser les révolutions qui dans notre tête ont été dérangées lors de notre naissance, rendre celui qui contemple ces révolutions semblable à ce qui est contemplé en le faisant revenir à son état naturel antérieur : voici donc la tâche à laquelle nous devons être inlassablement attachés. » Dans la tradition hindoue, cette dynamique est profondément explicite, écrit Silvia d'Intino. Le rite sacrificiel est à la fois l'occasion du passage d'un monde mortel à un monde céleste béni de permanence et la réalisation de la divinité : « Cette conception du sacrifice en tant que passage dans un monde qui est à la fois le rite lui-même (en tant qu'oeuvre, monde créé) et le monde céleste qu'il préfigure -les brahmanes ne sont-ils pas assis comme les dieux autour du feu ? En fait, pendant le rite, ils sont des dieux. » En Chine ancienne, Catherine Despeux évoque comment le moment de la gestation donne à voir le façonnage du destin par un champ de force d'une précision remarquable, ainsi que les interstices à travers lesquels des parents peuvent s'emparer des logiques déterministes. La rectitude d'une femme enceinte, dans un espace-temps, de ses comportements, d'une alimentation particulière, peut remodeler le destin de son enfant pourtant décidé avant sa naissance. De manière frappante, la prédisposition dominante ne peut se réaliser sans l'individuation, dotée d'une capacité à jouer des forces en présence. On lit : « Le destin alloué par le Ciel pourrait être, du point de vue de l'humanité, normatif ou destructeur ; le but serait de le corriger autant que faire se peut, et en dernier ressort de l'accepter, dans la perspective d'un ciel plus fort que l'individu. Mais le mandat céleste reste plus une prédisposition, qu'il faut actualiser, qu'un déterminisme, d'autant que le destin d'une personne s'inscrit dans tout un réseau de corrélations et peut, de ce fait, par un jeu sur ces corrélations, être déjoué et modifié » Comprendre et transmettre la vivacité du cosmos sont des tâches ardues qui nécessitent d'apprendre, sans penser tout savoir. Les Bassar du Togo ne s'y trompent, selon Stéphan Dugast. La rigueur est de mise, afin d'embrasser la complexité des forces vitales, tout comme la modestie, afin d'accéder à l'homologie entre divination et représentations du monde prénatal. On lit : « Les commentaires des exégètes les plus savants de la société bassar se distinguent par leur rigueur, identifiable notamment à travers une franche réticence à céder aux charmes des constructions lisses et régulières et par un refus ferme de combler certaines lacunes par la mise en oeuvre d'un raisonnement de substitution, élaboré pour la circonstance. (…) Cette fidélité à un savoir éprouvé qui les dépasse leur permet souvent de remettre en cause tel ou tel point précis d'une synthèse audacieuse, proposée par de moindres connaisseurs, et les arguments qu'ils avancent alors révèlent toute la richesse d'un savoir dont ils ne maîtrisent peut-être pas toujours tous les arcanes, mais dont ils savent faire entendre qu'il provient de profondes réflexions sur un sujet grave portées par plusieurs générations d'experts. » Cette rigueur, opposée à la commodité de circonstances qui effacent la transmission d'une dialectique, toujours contextuelle, entre général et particulier, a de profondes implications pour les existences contemporaines. S'arrimer rapidement à une formule, par convenance plutôt que de manière convenable, inscrit une autorité heuristique dont la portée peut être fort pernicieuse. Le dernier chapitre insiste particulièrement sur ce point. Les mots de Boèce, assimilant l'être humain à une « substance individuelle d'une nature raisonnable » et appliqués par certains philosophes de la bioéthique à un propos concernant l'humanisation des embryons humains conçus en laboratoire, s'avèrent dommageables du point de vue de la justice reproductive. En effet, Alain Galonnier défend : « Fonder, comme Boèce y invite à notre sens, la constitution de la personne humaine sur le critère de la rationalité et le transposer tel quel dans le domaine de l'éthique biologique est d'abord susceptible de compliquer la législation française actuelle sur l'interruption volontaire de grossesse (IVG), et de participer à son inapplicabilité. (…) La seconde conséquence majeure de l'exportation de la détermination de la personne par la rationalité, conformément au jugement boécien, dans un contexte bioéthique, est d'être amené à ne plus considérer comme une personne tout sujet atteint d'affection dégénérative du système nerveux central, qui altère ses facultés mentales jusqu'à le priver de l'usage de la « raison ». » L'individuation humaine, en sa plus qualitative expression, constitue un enchevêtrement complexe entre détermination et liberté avec comme pierre de touche une éthique de vie. La perte inhérente à toute naissance est incorporée, selon les différentes traditions ici considérées, dans l'oubli, la chair et la finitude du corps, la détermination sévère ou le choix prénatal qui ferment certaines opportunités.

Prenons garde. Cette perte n'est pas qu'un défaut. Elle est aussi l'occasion d'un désir porté vers la capacité à refaçonner une existence. Ce désir nécessite un positionnement dans le monde, des actes précis, des choix qui font sens, en accord avec des connaissances. Accéder aux savoirs cosmiques -embryogenèse, métaphysique, astrologie ou encore capacité à interagir avec un dieu ou un esprit -accompagne un élan existentiel qui du manque génère un accord. S'accorder au savoir-faire de la vie prénatale n'est pas tant une réintégration, fantasme de complétude, que l'appropriation d'une capacité d'action créatrice. A travers l'individu, à travers celui qui agit en connaissance de cause, à travers sa responsabilisation, c'est le cosmos qui se reproduit. La vie prénatale n'est pas un champ de déterminations cosmiques dont il faudrait se libérer ou qu'il faudrait réembrasser totalement, mais l'espace même de la créativité vitale. Or, il semble que cette créativité, afin d'être vivante, poursuive sa création en lui donnant les moyens de s'y atteler. En ce sens, la reproduction cosmique peut être proprement donnée à la vie par la découverte que celles et ceux qui sont en vie peuvent la mobiliser.

La responsabilisation est puissance d'agir en conscience. La responsabilité est immense, et l'évocation de l'éthique comme de la justice n'étonne en ce sens point. Quel monde reproduisons-nous aujourd'hui à travers nos existences humaines ? Il est évident que les enjeux sont immenses, mais le champ des possibles également ouvert, si l'on en croit les enseignements de La vie prénatale. Chaque individu peut prendre ses responsabilités et faire des choix porteurs de vie, pour celles et ceux qui ne sont pas nés.


Mathieu Besson
email: mathieu.besson@inrae.fr

Julien Roche

Pierre Patrice

François Pierrick Haffray

François Allal

Marc Vandeputte

Florence Phocas

AN R-BASED PIPELINE FOR GENOTYPE CALLING AND PARENTAGE ASSIGNMENT OF TRIPLOID OFFSPRING TO THEIR DIPLOID PARENTS

HAL is

Introduction

Triploids, which are individuals bearing three sets of chromosomes, are commonly used in fish breeding. Triploids are sterile which allow (1) higher growth after maturity and feed efficiency, (2) better flesh quality and (3) lower risk of genetic introgression into wild populations. In rainbow trout where triploids account for a significant proportion of production, selective breeding programs are all performed on diploid lines expecting transfert of the genetic progress to their triploid progenies.

. However, evaluating only diploid performance is suboptimal as genetic correlations for the same trait between diploids and triploids may differ from unity. Hence, maximizing genetic gain in diploid lines requires the evaluation of breeding values on triploid sibs of the diploid candidates. In mixed-family designs of breeding programs, this implies correctly genotyping triploids and recovering their pedigree, which is not currently possible with open source tools. Here, we present a pipeline to genotype and assign triploids in fish obtained by second polar body retention after fertilization (the technique applied in salmonids) to their diploid parents based on a newly developed R package, GenoTriplo and an adaptation of APIS [START_REF] Griot | APIS: An auto-adaptive parentage inference software that tolerates missing parents[END_REF] software.

Material and Methods

We genotyped 1,232 triploid offspring obtained from 190 diploid dams and 98 diploid sires of rainbow trout on a Thermo Fisher SNP chip array with 57501 SNPs, from which we kept the 38,033 highest quality markers. Allele signals were obtained via Axiom Analysis Suite software as the luminescence of probesets A and B (SA and SB) for each marker and individual. GenoTriplo was designed in two steps, clustering and genotype calling. For the clustering, each individual was represented by a couple of coordinates (x the contrast and y the signal strength) for each marker.

x = Contrast = log2 ( S A S B ) y = Signal Strength = log2(S A ) + log2(S B )
2 Rmixmod R package was used to find clusters of individuals sharing the same genotype for a given marker. In the iterative algorithm, the initial number of clusters was set to 8, i.e. twice to the maximum number of possible genotypes. Clusters with close contrast values were merged to keep only four or less clusters. Five iterations were realized and we kept the iteration with the highest likelihood value. For the genotype calling, we identified the more extreme cluster based on its contrast (x) mean value and set it as homozygous (AAA if mean(x)>0 or BBB if mean(x)<0). Then, the remaining clusters were ordered by contrasts. Three main criteria were involved to improve cluster precision and to discriminate low-quality markers. (1) Genotype was declared as missing if the probability of the individual to belong to the cluster was below 0.85. (2) Genotype was also set missing if the distance between the cluster center and the individual exceeds 2.8*SDcluster. (3)

Genotypes of all individuals of the same cluster were all set missing if the standard deviation of the cluster exceed 0.28*(1+0.5*abs(Meancluster)). There were three categories of markers: PolyHighRes markers with 3 alleles observed and 4 genotypes, NoMinorHom markers with one homozygous genotype missing and CRbelowThreshold markers with call rate below 90%. Finally, we adapted APIS to enable parentage assignment of triploids.

To do so, we created three new likelihood tables, one for each possible offspring genotype (AAA, ABB, ABCthis latter being relevant only for microsatellite markers). Similar tables were produced to perform assignment by exclusion. To test whether this pipeline was efficient, we used APIS to assign the 1,232 triploid offspring genotyped with GenoTriplo. The assignment was done using the exclusion method with the 1,000 best markers selected on the highest values for minor allele frequency and call rate.

Results

Thanks to the 8 clusters initially targeted, most of the rare genotypes were detected. This resulted in minimizing the proportion of CRbelowThreshold markers and maximizing the proportion of informative NoMinorHom and PolyHighRes markers (Table 1) in comparison to [START_REF] Grashei | Genotype calling of triploid offspring from diploid parents[END_REF]' method. Furthermore, all offspring were assigned to their parents. The best couple category had a maximum 19 mismatches for 1,000 markers and a mean number of mismatches of 6.9 which is low (<1% of mismatch). The second-best couple had a minimum of 47 mismatches for a mean of 85.6 (Figure 1).

Discussion

Initially targeting eight clusters instead of four ones is a major difference between GenoTriplo and the method proposed by [START_REF] Grashei | Genotype calling of triploid offspring from diploid parents[END_REF]. It enabled the algorithm to identify clusters with few individuals that would have been included in a bigger cluster and which would have then been discarded due their distance to the cluster's center. Consequently, GenoTriplo maximizes the number of informative PolyHighRes markers found. Meanwhile, we showed that the accuracy of GenoTriplo allowed to assign all our triploid offspring to their diploids parents. Even though the true parents were unknown the difference in the numbers of mismatches between the best and the second-best couple was large enough to confirm the success of the assignment. Hence, this pipeline is a major breakthrough towards the selection of diploid lines based on performances of their triploid sibs.

Figure 1 .

 1 Figure 1. Number of offspring as a function of mismatches for the best parental couple (blue) and the second-best parental couple (red).

Table 1 .

 1 Number of markers per category in diploid parents and triploid offspring datasets.

	Population and method	PolyHighRes	NoMinorHom	CRbelowThreshold
	Diploid parents using Axas	31,096	2,855	3,485
	Triploid offspring using GenoTriplo	21,715	6,233	4,734

Acknowledgements

The HYPOTEMP project ( n°PFEA470019FA1000016) was funded by the French Government and the European Union (EMFF, European Maritime and Fisheries Fund) at the "Appels à projets Innovants" managed by the France Agrimer Office.


Pietro Abate
email: abate@pps.jussieu.fr

Jaap Boender
email: jaap.boender@pps.jussieu.fr

Roberto Di Cosmo
email: roberto@dicosmo.org

Stefano Zacchiroli

Strong Dependencies between Software Components

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

Introduction

Component-based software architectures [START_REF] Szyperski | Component Software: Beyond Object-Oriented Programming[END_REF] have the property of being upgradeable piece-wise, without necessarily touching all the pieces at the same time. The more pieces are affected by a single upgrade, the higher the impact of the upgrade can be on the usual operations performed by the overall system; this impact can either be beneficial (if the upgrade works as planned) or disastrous (if not). Package-based FOSS (Free and Open Source Software) distributions are possibly the largest-scale examples of component-based architectures, their upgrade effects are experienced daily by million of users world-wide, and the historical data concerning their evolution is publicly available.

Within FOSS distributions, software components are managed as packages [START_REF] Di Cosmo | Package upgrades in FOSS distributions: Details and challenges[END_REF].

Packages are described with meta-information, which include complex interrelationships describing the static requirements to run properly on a target system. Requirements are expressed in terms of other packages, possibly with restrictions on the desired versions. Both positive requirements (dependencies) and negative requirements (conflicts) are usually allowed.

Example 1.1. An excerpt of the inter-package relationships of the postfix Internet mail transport agent in Debian GNU/Linux1 currently reads:

1 Package: postfix 2 V e r s i o n : 2.5.5-1.1 3 Depends: libc6 (>= 2.7), libdb4.6, ssl-cert, 4 libsasl2-2, libssl0.9.8 (>= 0.9.8f-5), 5

debconf (>= 0.5) | debconf-2.0, 6 netbase, adduser (>= 3.48), dpkg (>= 1.8), 7

lsb-base (>= 3.0-6) 8 C o n f l i c t s : libnss-db (<< 2.2-3), smail, 9 mail-transport-agent, postfix-tls 10 P r o v i d e s : mail-transport-agent, postfix-tls As this short example shows, inter-package relationships can get quite complex, and there are plenty of more complex examples to be found in distributions like Debian. In particular, the language to express package relationships is not as simple as flat lists of component predicates, but rather a structured language whose syntax and semantics is expressed by conjunctive normal form (CNF) formulae [START_REF] Mancinelli | Managing the complexity of large free and open source package-based software distributions[END_REF]. In Example 1.1, commas represent logical conjunctions among predicates, whereas bars ("|") represent logical disjunctions. Also, indirections by the mean of so-called virtual packages can be used to declare feature names over which other packages can declare relationships; in the example (see line 10: "Provides") the package declares to provide the features called postfix-tls and mail-transport-agent.

Within this setting, it is interesting to analyse the dependency graph of all packages shipped by a mainstream FOSS distribution. This graph is potentially very large as distributions like Debian are composed of several tens of thousands packages, but it is surely smaller than widely studied graphs such as the World Wide Web graph [START_REF] Albert | The diameter of the world wide web[END_REF]. It is also more expressive though, in the sense that it contains different types of edges (dependencies and conflicts for example) and allows the use of disjunctions to express alternative paths. Simple encodings of the package universe have been proposed in the past [START_REF] Labelle | Inter-package dependency networks in open-source software[END_REF][START_REF] Maillart | Empirical tests of zipf's law mechanism in open source linux distribution[END_REF], to study the adherence of the dependency graph to small-world network laws. In such encodings, inter-package relationships were approximated by a simple binary relation of direct dependency, which is noted p → q in this paper. Formally, p → q holds whenever package q occurs syntactically in the dependency formula of p. This notion of direct dependency does not distinguish between q occurring in conjunctive or disjunctive position, ignoring the semantic difference between conjunctive and disjunctive dependencies, as well as the presence of conflicts among components.

In this paper we argue that there is a different dependency graph to be studied to grasp meaningful relationships among software components: a graph that represents the semantics of inter-component relationships, in which an edge between two components is drawn only if the first cannot be installed without installing the second. We call such a graph the strong dependency graph, argue that it is better suited to study package universes in component-based architectures, and study its network properties. Finally, we argue that the strong dependency graph can be used to establish a measure of package "sensitivity" which has several uses, from distribution wide quality assurance to establishing the potential risks of package upgrades. As a relevant, yet empirical, case study we build and analyse the strong dependency graph of present and past FOSS distributions, as well as the corresponding package sensitivity.

The rest of the paper is structured as follows: Section 2 introduces the notion of strong dependency, highlights the differences with plain dependencies and proposes related sensitivity metrics. Section 3 computes dependencies and sensitivity of components of a large and popular FOSS distribution. Section 4 gives an efficient algorithm to compute strong dependencies for large software repositories. Section 5 discusses applications of the proposed metrics for quality assurance and upgrade risk evaluation. Before concluding, Section 6 discusses related research.

Strong dependencies

Component dependencies can be used to compute relevant quality measures of software repositories, for instance to identify particularly fragile components [START_REF] Dick | Data mining in software metrics databases[END_REF][START_REF] Khoshgoftaar | Data mining for predictors of software quality[END_REF][START_REF] Livshits | Dynamine: Finding common error patterns by mining software revision histories[END_REF]. It is well known that small-world networks are resilient to random failures but particularly weak in the presence of attacks, due to the existence of highly connected hub nodes [START_REF] Albert | Error and attack tolerance of complex networks[END_REF]. To identify the components whose modification (e.g., removal or upgrade) can have a high potential impact on the stability of a complex software system, it is natural to look for hubs on which a lot of other components depend.

In FOSS distributions, not unlike other component-based systems [START_REF]Maven project[END_REF][START_REF] Clayberg | Eclipse Plug-ins[END_REF], the language used to encode inter-package relationships is expressive enough to cover propositional logic. As a consequence, considering only plain connectivity-i.e., the possibility of going from one package to another following dependency arcs-is no longer meaningful to identify hubs. For example, if p is to be installed and there exists a dependency path from p to q, it is not true that q is always needed for p, and in some cases q may even be incompatible with p.

In other terms, the syntactic connectivity notion does not tell much about the real structure of dependencies: we need to go further and analyse the semantic connectivity among software components induced by the explicit dependencies in the graph. That has led us to the following definition. Definition 2.1 (Strong dependency). Given a repository R, we say that a package p in R strongly depends on a package q in R, written p ⇒ R q, if there exists a healthy installation of R containing p, and every healthy installation of R containing p also contains q. We write Spreds(p) R for the set {q|q ⇒ R p} of strong predecessors of a package p in R, and Scons(p) R for the set {q | p ⇒ R q} of strong successors of p in R.

In the following, we will drop the R subscript when the repository is clear from the context.

The above notions of repository and healthy installation come from [START_REF] Mancinelli | Managing the complexity of large free and open source package-based software distributions[END_REF]; the underlying intuitions are as follows. A repository is a set of packages, together with dependencies and conflicts encoded as propositional logic predicates over other packages contained therein; an installation is a subset of the repository; an installation is said to be healthy when all its packages have their dependencies satisfied within the installation and dually their conflicts unsatisfied.

Intuitively, p strongly depends on q with respect to R if it is not possible to install p without also installing q. Notice that the definition requires p to be installable in R as otherwise it would vacuously depend on all the packages q in the repository. Due to the complex nature of dependencies, there can be a huge gap with the syntactic dependency graph as naively extracted from the metadata.

Example 2.2 (Direct vs strong dependencies). In simple cases, conjunctive direct dependencies translate to identical strong dependencies whereas disjunctive ones vanish, as for the packages of the following repository: We have that p → q, p → r and p ⇒ q, p ⇒ r (because p cannot be installed without either q or r), and that a → b, a → c whereas a ⇒ b, a ⇒ c (because a does not forcibly require neither b nor c). In general however, the situation is much more complex, like in the following repository:

Package: p Depends: q | r Package: r C o n f l i c t s : p Package: q p W Õ Õ % % 3 3 3 3 3 3 q r #
Notice that p ⇒ q in spite of q not being a conjunctive dependency of p, and r is incompatible with p, despite the fact that p → r.

Proposition 2.3 (Transitivity). If p ⇒ R q and q ⇒ R r then p ⇒ R r.

Proof. Trivial from Definition 2.1.

On top of the strong and direct dependency notions, we can define the corresponding dependency graphs. Definition 2.4 (Dependency graphs). The strong dependency graph SG(R) of a repository R is the directed graph having as vertices the packages in R and as edges all pairs p, q such that p ⇒ q. Note that the SG(R) is transitively closed as direct consequence as the transitivity of the strong dependency relation.

Similarly, the direct dependency graph DG(R) is the directed graph having as vertices the packages in R and as edges all pairs p, q such that p → q.

The dependency graphs can be used to formalise, via the notion of impact set, the intuitive notion of the set of packages which are potentially affected by changes in a given package.

Definition 2.5 (Impact set of a component). Given a repository R and a package p in R, the impact set of p in R is the set Is(p, R) = {q ∈ R | q ⇒ p}.

Similarly, the direct impact set of p is the set

DirIs(p, R) = {q ∈ R | q → p}.
While the impact set gives a sound lower bound to the set of packages which can be potentially affected by a change in a package, the direct impact set offers no similar guarantees. Note that by Definition 2.1, for all package p, p ∈ Is(p, R). Package sensitivity-a measure of how sensitive is a package, in terms of how many other packages can be affected by a change in it-can now be defined as follows.

Definition 2.6 (Sensitivity). The strong sensitivity, or simply sensitivity, of a package p ∈ R is |Is(p, R)| -1, i.e., the cardinality of the impact set minus 1. 2Similarly, the direct sensitivity is the cardinality of the direct impact set.

The higher the sensitivity of a package p, the higher the minimum number of packages which will be potentially affected by a change, such as a new bug, introduced in p. We write |p| and ||p|| to denote the direct and strong sensitivity of package p, respectively. The following basic property of impact sets and sensitivity follows easily from the definitions.

Proposition 2.7 (Inclusion of impact sets). If p ⇒ R q then Is(p, R) ⊆ Is(q, R). As a consequence, the sensitivity of p in R is smaller than the sensitivity of q in R.

When analysing a large component base, like Debian's, which contains about 22,000 components, it is important to be able to identify some measure that can be used to easily pinpoint "interesting" packages. Sensitivity can be (and actually is, in our tools) used to order packages, bringing the most sensitive to the forefront. To this end is important to note that (strong) sensitivity can be computed automatically (and efficiently, see Section 4) from dependencies; that is an important feature: given the sheer size of systems like Debian, it would be unreasonable to try mix sensitivity with hand-maintained classifications such as "core" packages, "end-user" packages, etc. But sensitivity alone is not enough: we do not want to spend time going through hundreds of packages with similar sensitivity to find the one which is really important, so we need to keep some of the structure of the strong dependency graph.

A first step is to group together only those packages that are related by strong dependencies, but our analysis of the Debian distribution led us to discover that we really need to go further and distinguish the cases of related components in the strong dependency graph from the cases of unrelated ones: in the picture in Figure 1, 3 configuration 1c shows q that clearly dominates r, as the impact set of r really comes from that of q, in configuration 1d, q and r are clearly equivalent, while in configuration 1a, q and r are totally unrelated, and in configuration 1b, q strong depends on r but q does not generate all the impact set of r.

p 1 3 3 D D D D D D D D D D D D D D D D D D _ _ _ p i % % 2 2 2 2 2 2 2 2 2 2 2 2 2 Ö Ö _ _ _ p n } } z z z z z z z z z z z z z z z z z z q r (a) Coincidence p 1 2 2 A A A A A A A A _ _ _ p i _ _ _ p n || | | | | | | s 1 } } | | | | | | | | | | | | | | | | | | | _ _ _ s k
y y r r r r r r r r r r r r r r r r r r r r r r r r r q r (b) General case of strong dependency Yet, the packages q and r all have essentially the same sensitivity values (n or n + 1) in all the first three cases (and n + k in the fourth, which can also contribute to the mass of packages of sensitivity similar to n). To distinguish these different configurations in strong dependency graphs, we introduce one last notion. Definition 2.8 (Strong dominance). Given two packages p and q in a repository R, we say that p strongly dominates q (p Is q) iff • Is(p, R) ⊇ (Is(q, R) \ Scons(p)), and

p 1 2 2 A A A A A A A A _ _ _ p i _ _ _ p n || | | | | | | q r (c) Ordered p 1 2 2 A A A A A A A A _ _ _ p i _ _ _ p n || | | | | | | q × × r r r (d) Equivalent

• p strongly depends on q

The intuition of strong dominance, is that a package p dominates q if the strong dependency of p on q "explains" the impact set of q: the packages that q has an impact on are really those that p has an impact on, plus p. This notion has some similarity in spirit with the standard notion of dominance used in control flow graphs, but is technically quite different, as strong dependency graphs are transitive, and have no single start node.

Using the transitivity of strong dependencies, the following can be established.

Proposition 2.9. The strong domination relation is a partial pre-order.

Proof. Reflexivity is trivial to check. For transitivity, suppose we have p Is q and q Is r: first of all, p strongly depends on r is a direct consequence of the fact that the strong dependency relation is transitive, so the second condition for p Is r is established. For the first condition, we know that Is(p, R) ⊇ (Is(q, R) \ Scons(p)) and Is(q, R) ⊇ (Is(r, R) \ Scons(q)). By transitivity of strong dependencies, since p ⇒ q ⇒ r, we also have that Scons(p) ⊇ Scons(q) ⊇ Scons(r). Then we have easily that Is(p, R)

⊇ (Is(q, R) \ Scons(p)) ⊇ (Is(r, R) \ Scons(q)) \ Scons(p) = Is(r, R) \ Scons(p).
This pre-order is now able to distinguish among the cases of Figure 1. In Figure 1c we have that q Is r, but not the converse; in 1d both q Is r and r Is q hold, i.e., q and r are equivalent according to strong domination; in 1a and 1b no dominance relationship can be established between q and r.

It is possible, and actually quite useful, to generalise the strong dominance relation to cover also the case shown in 1b, where a part of the impact set of the package r is not covered by the impact set of q, as follows.

Definition 2.10 (Relative strong dominance). Given two packages p and q in a repository R, we say that p strongly dominates q up to z (p z Is q) iff

• |(Is(q,R)\Scons(p))\Is(p,R)| |Is(p,R)| * 100 = z, and
• p strongly depends on q

It is easy to see that p Is q iff p 0 Is q, and one can compute in a single pass on the repository the values z for each pair of packages such that p ⇒ q, leaving for later the choice of a threshold value for z. In the case of figure 1b, we have that q dominates r up to k/n * 100.

Strong dependencies in Debian

Due to the different properties of direct and strong dependencies, the two measures of package sensitivity can differ substantially. To verify that, as well as other properties of the underlying dependency graphs, we have chosen Debian GNU/Linux as a case study. 4 The choice is not casual: Debian is the largest FOSS distribution in terms of number of packages (about 22, 000 in the latest stable release) and, to the best of our knowledge, the largest component-based system freely available for study.

All stable releases of Debian have been considered, from 1994 to February 2009. For each release the archive section main and in particular the i386 architecture has been considered; the choices are justified by the fact that they identify both the most used parts of Debian, 5 and that they are the only parts which have been part of all Debian releases and hence can be better compared over time. The obtained archive parts have been analysed by building both the direct and strong dependency graphs; while the construction of the former is a trivial exercise, the implemented efficient way of constructing the latter is discussed in Section 4. To build the direct dependency graph the Depends and Pre-Depends inter-package relationships have been considered [START_REF] Jackson | Debian policy manual[END_REF].

Figure 2 shows the resulting evolution of the number of graph nodes and edges across all Debian releases. The size of the distribution has grown steadily, yet super-linearly, across most releases [START_REF] Robles | Mining large software compilations over time: another perspective of software evolution[END_REF][START_REF] Herraiz | Managing libre software distributions under a product line approach[END_REF], but the growth rate has decreased in the past two releases. As expected, strong and direct sensitivity are not entirely unrelated, given that the former is the semantic view of the latter, hence they tend to grow together.

More precisely the total number of strong dependencies is higher, in all releases, than the total number of direct dependencies. A partial explanation comes from the fact that the strong dependency graph is a transitive closed graph-property inherited by the underlying strong dependency relationship-whereas the direct dependency graph is not. Performing the transitive closure of the direct dependency graph however would be meaningless, because the propagation rules of disjunctive and conjunctive dependencies are not expressible simply in terms of transitive arcs.

We have studied the apparent correlation between strong and direct dependencies analysing the respective sensitivity measures for each release. Table 1 confirms the correlation and gives some statistical data about package sensitivity. The first column is the Spearman ρ correlation index, 6a commonly used non-parametric correlation index that is not sensible to exceptional values [START_REF] Fenton | Software Metrics: A Rigorous and Practical Approach[END_REF]. An index between 0.5 and 1.0-in all the releases we have ρ ∈ [0.91, 0.94]is commonly interpreted as a strong correlation between the two variables. The more common correlation index r for the same set of data (not shown in the table) gives consistently a value of 0.55: the huge difference among ρ and r indicates that the few exceptional values in the data series have really high weight; when analyzing some of these exceptional values, we will see how this is indeed the case.

The remaining columns show mean and standard deviation for, respectively, direct sensitivity, strong sensitivity, and ∆ = ||p|| -|p|. In particular we note an increasingly high standard deviation in latest Debian releases, which hints that there is an increasing number of peaks.

Figure 3 shows in more detail the correlation phenomenon for Debian 5.0 "Lenny", the latest (and largest) Debian release. The figure plots strong vs direct sensitivity for each package in the release. In most cases, strong sensitivity is higher than direct sensitivity, yet close: 82.9% of the packages fall in a standard deviation interval from the mean of ∆; the next percentile ranks are 97.4% for two standard deviations, and 99.8% for three. The remaining cases allow for important exceptions of packages with very high strong sensitivity and very low direct sensitivity. Such exceptions are extremely relevant: metrics built on direct sensitivity only would totally overlook packages with a huge potential impact. libc6 is the package shipping the C standard library which is required, directly or not, by almost all applications written or otherwise linked to the C programming language. About a half of all the packages in the distribution depends directly on libc6, as can be seen in row 13 of the table, but almost all packages in the archive cannot be installed without it, as the strong sensitivity of libc6 is 20'126, on a total of 22'311 packages. In this case direct sensitivity does not inhibit identifying the package as a sensitive one, though, even if it underestimates widely its importance. Now consider row 1 of Table 2: gcc-4.3-base, which is a package without which libc6 cannot be installed. It is the package with the largest ∆, having direct sensitivity of only 43 and strong sensitivity of 20'128. Ranking its sensitivity with the direct metric would have led to completely miss its importance: a bug into it can potentially affect all packages in the distribution. Note however that gcc-4.3-base is not a direct dependency of libc6, showing once more that to grasp this kind of interpackage relationships the semantics, rather than the syntax, of dependencies must be put into play.

In the second row, libgcc1 shows a similar pattern, being this time a direct dependency of libc6. The third row and many others in the table show more complex patterns. Ordering packages only according to sensitivity might lead to oversee other important characteristic. Possibly the most extreme cases are those of ncurses-bin and libx11-data, which are mentioned just once in all We believe this is sufficiently conclusive evidence to totally dismiss, from now on, any analysis based on the syntactic direct dependency graph, when considering component based systems with expressive dependency languages.

Using strong dominance to cluster data

Now we turn to the problem of presenting the sensitiveness information in a relevant way to a Quality Assurance team: we could simply print a list of package names, ordered by their sensitiveness; this would give a result quite similar to that of table 2 above, just dropping the first and fourth column. A smart Debian developer will surely spot the fact that gcc-4.3-base, libgcc1 and libc6 are Here is where our definition of relative strong dominance comes into play, allowing to build meaningful clusters that provide sensible information to the maintainers: Figure 4 shows the graph of relative strong domination between the first 20 packages of Table 2. Bold edges show strong domination as defined in Definition 2.8. Normal edges show relative domination, where the install sets of the two packages almost fully overlap, apart from a few packages (edges are labelled with the percentage z of Definition 2.10).

This figure shows clearly that it is possible to isolate five clusters of related packages with similar sensitivity values; some of them may look surprising at first sight to a Debian developer, and evident after a little time spent exploring the package metadata: this actually confirms the real value of this way of presenting data.

Debian is a small world

We expected the strong dependency graph to retain the small world characteristics previously established for the direct dependency graph [START_REF] Labelle | Inter-package dependency networks in open-source software[END_REF], but this required some extra effort to get sensible results: indeed, computing clustering coefficients and other similar measures on the strong dependency graph will yield very different values (as the strong dependency graph is transitive), so we first built a non-transitive version of the strong dependency graph, and computed the usual small world measures on it.

Note that, since the strong dependency graph contains some cycles, the obtained non-transitive graph is not unique. The differences are however minor enough to not alter the overall results.

The clustering coefficient and average path length of the non-transitive graph are, though slightly smaller, well within the range of small-world networks. More than half the edges of the direct graph have disappeared, but this has not significantly affected either the graph clustering or the path length. The relevant statistics are summarised in Table 3.3.

Some additional notes about obtained small-world statistics. First, both graphs contain one enormous (weakly connected) component, next to which all other components are of insignificant size (for the direct graph, there are 1'480 remaining packages in 1'424 components, which would make their average size just above 1; the ratio is similar for the strong graph). Second, when we look at the density of both graphs (the number of edges in the graph divided by the maximum possible number of edges), we see that both graphs are extremely sparse.

Efficient computation

It is not evident that strong dependencies as defined in Section 2 are actually tractable in practise: from previous results [START_REF] Mancinelli | Managing the complexity of large free and open source package-based software distributions[END_REF][START_REF] Di Cosmo | Maintaining large software distributions: new challenges from the FOSS era[END_REF] it is known that checking installability of a package (or co-installability of a set of packages) is an NPcomplete problem. Even if in practise checking installability turns out to be tractable on real-world problem instances, the sheer number of instances that computing strong dependencies may require in the general case makes the problem much harder. We start by observing that the problem of determining strong dependencies is decidable. Proof. Since R is finite, the set of all installations is also finite. Among these installations, finding the healthy one is just a matter of verifying locally the dependency relations. Then, for each p and q, it is enough to check all healthy installations to see whether q is present whenever p is.

If we want to know if a particular packages p strongly depends on q in a repository R however, the argument used in the proof of decidability leads to an algorithm that has exponential worst-case complexity in the size n of a repository R. One possible algorithm to find all strong dependencies in a repository R is as follows. Require: R = ∅ strongdeps ← ∅ for all p, q ∈ R do if strong dependency(p, q, R) then strongdeps ← strongdeps ∪ {p, q} end if end for return strongdeps Where the function strong dependency uses a SAT solver to check whether it is possible to install p without installing q (in repository R). This algorithm requires checking n 2 SAT instances, which is unfeasible with n ≅ 22, 000. We need to look for an optimised approach; the following remark is the key observation.

Remark 4.2 (Reducing the search space). All packages q on which a given package p strongly depends are included in any installation of p. Furthermore, if a package p conjunctively depends on a package q, then q is a strong dependency of p.

This leads to the following improved algorithm that strongly relies on the notion of installation sets and the property of transitivity of strong dependencies.

for all p ∈ R do strongdeps ← strongdeps ∪ conj deps(p, R) end for for all p ∈ R do S ← install(p, R) for all q ∈ S do if (p, q) ∈ strongdeps ∧ strong dep(p, q, R) then strongdeps ← strongdeps ∪ {p, q} end if end for end for return strongdeps The function conj deps(q, R) returns all packages in R that are connected to q, considering only conjunctive paths. We add to the strongdeps set all couples (p, q) such that there exists a conjunctive path between p and q, and then for all remaining packages in the install set of p, we check if there is a strong dependency using the SAT solver.

On one hand, the analysis of the structure of the repositories shows that it is in practise possible to find installation sets that are quite small. Considering only the installation set for a given package drastically reduces the number of calls to the SAT solver. On the other hand, since the large majority of strong dependencies can be derived directly from conjunctive dependencies, building the graph of conjunctive dependencies beforehand can further reduce the computation time.

In our experiments, calculating the strong dependency graph and sensitivity index for about 22, 000 packages takes about 5 minutes on a modern commodity Unix workstation. 7

Perspective applications

The given notions of strong dependency, impact set, sensitivity, and strong dominance can be used to address issues showing up in the maintenance of large component repositories. In particular, we have identified two areas of application: repository-wide Quality Assurance (QA) and upgrade risk evaluation for user machines.

Quality Assurance FOSS distribution the size of Debian are not easily inspectable by hand, without specific tools. The work of release managers in such scenario is about maintaining a coherent package repository, i.e., in which each package is installable in at least one healthy installation. Such repositories are usually not built from scratch, but rather evolve from an unstable state to a stable one which is periodically released as the new major release of the distribution. Day to day maintenance of the repository includes actions such as adding packages to the repository (e.g., newly packaged software, or new releases) as well as removing them (e.g., superseded softwares or sub-standard quality packages which are not considered suitable for releasing). Quality assurance is meant to spot repository-wide incompatibilities or sub-standard quality packages, according to various criteria.

In such ecosystems, removing a package can have nonlocal effects which are not evident by just looking at the direct dependencies of the involved packages. For instance, removing a package p such that several packages depends on p | q might be appropriate only if q is installable in the archive. The strong dependency graph can be used to detect similar cases efficiently. Once the graph has been computed-and Section 4 showed that the cost is affordable even for large distributions-detecting if a package is removable in isolation reduces to check whether its node has inbound edges or not. If really needed, following inbound edges can help building sets of packages removable as a whole.

In the same context, sensitivity can be used to decide when to freeze packages during the release process (decision currently delegated to folklore): the higher the sensitivity, the sooner a package should be frozen. Sensitivity can also be used to activate heuristic warnings in archive management tools when apparently innocuous packages are acted upon: attempting to remove or otherwise alter gcc-4.3-base at the end of the Lenny release process (see Table 2) would have surely been an error, in spite of the few packages mentioning it directly in their dependencies.

Upgrade risk evaluation System administrators of machines running FOSS distributions would like to be able to judge the risks of a certain upgrade. Risk evaluation not necessarily in the sense of deciding whether or not to perform an upgrade-not performing one is often not an option, due to the frequent case of upgrades that fix security vulnerability. Upgrade risk evaluation is nevertheless important to allocate suitable time slots to deploy upgrade plans proposed by package managers: the riskier the upgrade, the longer the time slot that should be planned for it.

The general principle we propose is that a package that is not strongly depended upon by other packages is relatively safe to upgrade; conversely, a package that is needed by many packages on the system might need some safety measures in case of problems (backup servers, . . . ). However this measure should be computed in relation to the actual user installation and not as an absolute value with respect to the distribution such as plain impact sets. Once the strong dependency graph of a user installation has been computed, the legacy package manager can be used to find upgrade plans as usual. On that plan the overall upgrade sensitivity can then be computed by summing up the size of the installation impact sets of all packages touched by the proposed plan; where the installation impact set of a package p is defined as the intersection of the strong impact set with the local installation.

The strong dependency graph used for risk evaluation must be the one corresponding to the distribution snapshot which was known before planning the upgrade. This is because we want to evaluate the risks with respect to the current installation, not to a future potential one in which package sensitivity can have changed. The maintenance of such graph on user machines is straightforward and can be postponed to after upgrade runs have been completed, in order to be ready for future upgrades.

Note that in this way, what is computed is an under approximation of the upgrade risk measure. For example consider the following scenario: a package p having Depends: q | r, and a healthy installation I = {p, q}. The direct dependencies of p entail no strong dependency, but in the given installation q has been "chosen" to solve p dependencies. Even if p ∈ Is(q, R) ∩ I, an upgrade of q in that specific installation has potentially an impact on p. The under approximation is nevertheless sound-i.e., all packages in the installation impact set are installed.

Release upgrades A particular case of upgrade are the so called release upgrades (or distribution upgrades) which are performed periodically to switch from an older stable release of a given distribution to a newer one. The relevance of such upgrades is that they usually affect almost all of the packages present in user installation. Such kind of upgrades are usually already performed wisely by system administrators devoting to them large time slots.

During release upgrades system administrators can be faced with the choice of whether to switch to a new major version of some available software or to stay with an older, legacy one. For instance, one can have the choice to switch to the Apache Web server 2.x series, or to stay with Apache 1.x. The upgrade is not forced by strict package versioning by either offering packages with different names (e.g. apache1 vs apache2 in Debian and its derivatives) or by avoiding explicit conflicts among the two set of versions (as it happens in RPM-based distributions). The choice is currently not technically well assisted: if apache2 is tentatively chosen, the package manager will propose to upgrade all involved packages to the most recent version without highlighting which upgrades are mandatory to fulfil dependencies and which are not.

While this is a deficiency of state of the art solving algorithms [START_REF] Treinen | Solving package dependencies: from EDOS to Mancoosi[END_REF], strong dependencies offer a cheap technical device to work around the problem with current solvers. It is enough to compute the strong dependency graph of both distributions and, in particular, the strong dependencies of the two (or more) involved packages. Then, by taking the difference of the strong dependencies in the new and in the old graph, the list of package which must be forcibly upgraded to do the switch is obtained. All such forced upgrades can then be presented to the administrator to better guide her or his choice.

Related works

Several interesting works have dealt with issues related to the topics touched by this paper. In the area of complex networks, [START_REF] Labelle | Inter-package dependency networks in open-source software[END_REF][START_REF] Maillart | Empirical tests of zipf's law mechanism in open source linux distribution[END_REF] used FOSS distributions as case studies. The former is the closest to our focus, as it studies the network structure obtained from Debian inter-package relationships, showing that it is small-world, as the node connectivity follows a near power-law distribution. However, the analysis is performed on the direct dependency graph which, as discussed, misses the semantics of dependencies.

We could not get more information on how the data of [START_REF] Labelle | Inter-package dependency networks in open-source software[END_REF] has been computed, as the snapshot of Debian used there comes from late 2004, and is no longer available in the Debian archives; based on the figures presented in the paper, and our analysis of the closest Debian stable distribution, we conclude that their analysis dropped all information about Conflicts and Pre-Depends. As a consequence, the figures produced for what is called in the paper "the 20 most highly depended upon packages" falls extremely short of reality: libc6 is crucial for 3 times more packages than what is reported, and other critical packages such as gcc-4.3-base are entirely missed.

In the area of quality assurance for large software projects, many authors correlate component dependencies and past failure rates in order to predict future failures [START_REF] Zimmermann | Predicting defects using network analysis on dependency graphs[END_REF][START_REF] Nagappan | Using software dependencies and churn metrics to predict field failures: An empirical case study[END_REF][START_REF] Neuhaus | Predicting vulnerable software components[END_REF]. The underlying hypothesis is that software "faultproneness" of a component is correlated to changes in components that are tightly related to it. In particular if a component A has many dependencies on a component B and the latter changes a lot between versions, one might expect that errors propagates through the network reducing the reliability of A. A related interesting statistical model to predict failures over time is the "weighted time damp model" that correlates most recent changes to software fault-proneness [START_REF] Graves | Predicting fault incidence using software change history[END_REF]. Social network methods [START_REF] Hanneman | Introduction to social network methods[END_REF] were also used to validate and predict the list of sensitive components in the Windows platform [START_REF] Zimmermann | Predicting defects using network analysis on dependency graphs[END_REF].

Our work differs for two main reasons. First, the source of dependency information is quite different. While dependency analysing for software components is inferred from the source code, the dependency information in software distributions are formally declared and can be assumed to be, on the average, trustworthy as reviewed by the package maintainer. Second, FOSS distributions still lack the needed data to correlate upgrade disasters with dependencies and hence to create statistical models that allow to predict future upgrade disasters. In more detail, the FOSS ecosystem is really fond of public bug tracker systems, but generally lacks explicit logging of upgrade attempts and a way to associate specific bugs to them. One of the goal of the Mancoosi8 project-in which the authors are involved-is to create a corpus of upgrade problems which will be a first step in this direction.

The key idea behind the notion of sensitivity can be seen as a direct application of the evaluation of "disease spread-ing speed" in small world networks [START_REF] Watts | Collective dynamics of smallworld networks[END_REF]: the higher the sensitivity, the larger the impact sets, the higher the (potential) bug spreading speed. The semantic definition of impact sets is crucial in this analysis: using the direct dependency graph would give no guarantee about which components will be effectively installed and therefore help bug spreading.

Conclusion and future work

This paper has introduced the novel notions of strong dependencies between software components, and of sensitivity as a measure of how many other components rely on the availability of a specific components; strong dominance has been introduced as well as a criterion to order and group components with similar sensitivity into meaningful clusters. We have shown concretely on a large scale real world example that such notions are better suited to describe true inter-component relationships than previous studies, which were solely based on the analysis of the syntactic (or direct) dependency graph. The main applications of these new notions are tools for quality assurance in large component ecosystems and upgrade risk evaluation.

The new notions have been tested on one of the largest known component-based system: Debian GNU/Linux, a popular FOSS distribution. Historical analysis of Debian strong and direct dependency graphs have been performed. Empirical evidence shows that, while the two notions are generally correlated, there are several components on which they give huge differences, with direct dependencies entirely missing key components that are correctly pinpointed by strong dependencies. We believe the case shown in this paper is strong enough to totally dismiss, in the future, measures built on direct dependencies as soon as the dependency language is expressive enough to encompass propositional logics.

We hence strongly advocate the evaluating of sensitivity on top of strong dependencies, and we have shown clearly how clustering components according to the notion of strong dominance allows to build a meaningful presentation of data, and uncover deep relationships among components in a repository.

Despite the theoretical complexity of the problem, and the sheer size of modern component repositories, we have succeeded in designing a simple optimised algorithm for computing strong dependencies that performs very well on real world instances, making all the measures proposed in this paper not only meaningful, but actually feasible.

Previous studies on network properties-such as small world characteristics-have been redone on the Debian strong dependency graph, showing that it stays small world.

Future works is planned in various directions. First of all the notion of installation impact set needs to be refined. While it is clear that the strong impact set is an under ap-proximation of it, it is less clear how to further refine it. On one hand we want to get closer to the actual set of potentially affected packages on a given machine. On the other it is not clear, for a package p depending on q | r to which extent both packages should be considered as potentially impacted by a bug in p. It appears to be a limitation in the expressiveness of the dependency language which does not state an order between q and r, but needs further investigation. Interestingly enough, the implicit syntactic order "p before q" is already taken into account by some distribution tools such as build daemons and is hence worth modelling.

Distributions like Debian use a staged release strategy, in which two repositories are maintained: an "unstable" and a "testing" one. Packages get uploaded to unstable and migrate to testing when they satisfy some quality assurance criteria, including the goal of maintaining testing devoid of uninstallable packages. Current modelling of the problem is scarce and implementations rely on empirical packageby-package, brute force migration attempts. We believe that the notion of strong dependency and the clusters entailed by strong dominance can help in identifying clusters of packages which should forcibly migrate together.

Figure 1 .

 1 Figure 1. Significant configurations in the strong dependency graph

Figure 2 .

 2 Figure 2. Evolution of packages, direct, and strong dependencies in Debian releases.

Figure 3 .

 3 Figure 3. Correlation between strong and direct sensitivity in Debian 5.0

Proposition 4 . 1 (

 41 Decidability). Strong dependencies for packages in a finite repository R are computable.

Figure 4 .

 4 Figure 4. Dominance relations among the topmost 20 sensitive packages

Table 1 . Direct and strong sensitivity in De- bian: correlation, mean, standard deviation.

 1 σ2.79 1.05, σ4.73 1.00, σ4.00 1.1 .93 1.70, σ13.9 2.90, σ25.9 1.88, σ18.5 1.2 .91 1.79, σ18.4 2.99, σ32.2 1.73, σ22.4 1.3 .91 1.92, σ21.9 3.06, σ38.2 1.69, σ25.8 2.0 .93 2.29, σ26.7 4.03, σ50.8 2.50, σ36.5 2.1 .94 2.60, σ34.9 4.93, σ64.5 2.93, σ46.6 2.2 .92 3.29, σ44.2 6.89, σ90.4 4.88, σ68.7 3.0 .92 3.99, σ59.2 10.4, σ131. 8.02, σ92.3 3.1 .92 5.29, σ91.4 22.3, σ282. 19.3 , σ246. 4.0 .92 5.55, σ85.1 28.2, σ352. 24.5 , σ313. 5.0 .93 5.07, σ86.1 36.0, σ480. 32.5 , σ440.

	Rel.	ρ	| • |	|| • ||	∆
	.93 .92 1.00,

Table 2 . Packages from Debian 5.0, sorted by gap between strong / direct impact set sizes.

 2

	#	Package	|p|	||p||	||p|| -|p|
	1 gcc-4.3-base	43 20128	20085
	2 libgcc1	3011 20126	17115
	3 libselinux1	50 14121	14071
	4 lzma	4 13534	13530
	5 coreutils	17 13454	13437
	6 dpkg	55 13450	13395
	7 libattr1	110 13489	13379
	8 libacl1	113 13467	13354
	9 perl-base	299 13310	13011
	10 libstdc++6	2786 14964	12178
	11 libncurses5	572 11017	10445
	12 debconf	1512 11387	9875
	13 libc6	10442 20126	9684
	14 libdb4.6	103	9640	9537
	15 zlib1g	1640 10945	9305
	16 debianutils	86	8204	8118
	17 libgdbm3	68	8148	8080
	18 sed		11	8008	7997
	19 ncurses-bin	1	7721	7720
	20 perl-modules	214	7898	7684
	21 lsb-base	211	7720	7509
	22 libxdmcp6	15	6782	6767
	23 libxau6	42	6795	6753
	24 libx11-data	1	6693	6692
	25 libxcb-xlib0	3	6695	6692
	26 libxcb1	87	6778	6691
	27 x11-common	137	6317	6180
	28 perl	2169	7898	5729
	29 libmagic1	28	5585	5557
	30 libpcre3	164	5668	5504
			. . .
	the explicit dependencies, and yet are really necessary for
	several thousand other packages.

Table 3 . Small-world figures for Debian 5.0.

 3

		Direct dep.	Strong dep.
		graph	graph
	Vertices	22,311	22,311
	Edges	107,796	40,074
	Average degree	4.83	1.80
	Clustering coeff.	0.41	0.39
	Average distance	3.18	2.86
	Components (WCCs)	1,425	2,809
	Largest WCC	20,831	19,200
	Density	0.00022	0.000081
	related and would look at them together, but it would be dif-
	ficult to see relationships among the other packages in the
	list, even if we can see that many packages have impact sets
	of similar size.

http://www.debian.org

The -1 accounts for the fact that the impact set of a package always contains itself. This way we ensure that sensitivity 0 preserves the intuitive meaning of "no package potentially affected".

Edges implied by transitivity are omitted from the diagrams for the sake of clarity.

The data presents in this section, as well as what was omitted due to space constraints, are available to download from http://www. mancoosi.org/data/strongdeps/. The tools used to compute the data are released under open source licenses and are available from the Subversion repository at https://gforge.info.ucl.ac.be/ svn/mancoosi/.

According to the Debian popularity contest, available at http:// popcon.debian.org

The statistical info for the first two rows are possibly not relevant, due to the small size of the two releases.

Intel Xeon 3 GHz processor, 3 Gb of memory

http://www.mancoosi.org

Acknowledgements The authors would like to thank Yacine Boufkhad, Ralf Treinen, and Jerôme Vouillon for many interesting discussions on these issues.