1.Introduction and motivation

This workshop was originally proposed by the STELLAR theme team NTEL (Neuroscience and Technology Enhanced Education). The NTEL theme team comprised Paul Howard-Jones (University of Bristol, coordinating), Bert de Smedt (Katholieke Universiteit Leuven, Belgium), Michela Ott (CNRNational Research Council, Italy) and Theo van Leeuwen (Twente University, Netherlands). From May 2010 to May 2011, NTEL was funded by STELLAR to explore the issues and opportunities that may be generated by combining what we know about the brain with the affordances of modern learning technology. This workshop aimed to bring together TEL researchers and specialists in neuroscience to:

-To identify areas of understanding where technology enhanced learning may benefit from neuroscience and -To discuss how interdisciplinary research capacity in this area can be developed.

The workshop was by invitation-only, with priority given to active researchers in the TEL field who expressed interest in using findings from neuroscience to inform their research. Additionally, workshop attendance was appropriately balanced to provide sufficient expert opinion from neuroscience, psychology and education.

Programme:

Monday March 28th Summing up some of the issues/barriers etc 9.00 -10. 30 Presentations by NTEL team on a "Levels of Analysis" approach 10.30 -11.00 Coffee break 11.00 -12.15 Small group discussion on: Q3: "How can we develop interdisciplinary research capacity in this area?" Discussion groups report back on question; Plenary Discussion 12.30 -1. 30 Lunch 13. 30 -15.30 Snow activities 15.30 -16.00 Theme Team sum up some key opportunities identified 16.00 -17.00 Where do we from here?

Mutual interests, common goals, collaboration between participants

Workshop Description

As can be seen from the programme above, the structure of workshop avoided an emphasis on individual presentation, in order to maximise opportunities for interdisciplinary dialogue between members of the diverse communities of neuroscience and TEL. In order to support discussion, a detailed 10,000 word review was circulated 3 weeks prior to the meeting that had been prepared by the NTEL theme team. This review reported on recent neuroscience findings that might be considered relevant to research within TEL. This document, together with additional reviews by members of the NTEL theme team on literacy and numeracy, was also posted on the NTEL web-site (www.neuro-tel.net). Additionaly, a presentation was provided by Prof Dan Schwartz on his personal U.S. perspective on possibilities in this emergent area, and 2 individual presentations were provided by Paul Howard-Jones (University of Bristol) and Theo van Leeuwen (Twente University, Netherlands) that summarised the discussion document and allowed for clarification of its concepts.

In this way, the workshop was able to focus on generating a set of key issues to overcome, and a set of opportunities for progress that took the form of new grand challenges for STELLAR. They point out that digital implementation can be practice-oriented (providing easily-accessed and unsupervised repeated practice), can be age-independent, needs-oriented (e.g. providing alternative input/output modes for learner also suffering from slight dyspraxia or reading difficulties), meaningful (e.g. they can link the physical to the abstract in ways not possible in the physical world, such as when a learner 'zooms into' a 1-10 number line to discover decimal numbers) and they can offer private, unthreatening interaction and feedback in an endlessly patient fashion. These potential advantages of integrating our scientific understanding with technology are relevant in attempts to remediate a broader range of developmental disorders. Although claims about the general effectiveness of commercial programmes must be carefully scrutinised 2 , neuroimaging can also provide insights in cases where successful results are reported. For example, a dyslexia intervention using commercially available language training software reported partial remediation and improved reading, with ameliorated disrupted function in brain regions associated with phonological processing and additional compensatory activation in other regions [START_REF] Temple | Neural deficits in children with dyslexia ameliorated by behavioral remediation: Evidence from functional fMRI[END_REF] . When the cognitive and neural data converges in this way, we can be more confident in the underlying theoretical models and the effectiveness of the intervention.

Historically, neuroscientists have focused more upon abnormal than normal development and this helps explain why the first examples of neuroscience in TEL have been aimed at ameliorating developmental disorders. However, understanding from neuroscience has increasingly wider implications for TEL, with relevance to a range of mainstream TEL concepts. Although a preference for a particular learning style does not appear helpful in educational terms, we have seen (in Box 3) how some types of digital personalization can influence emotional engagement. Neuroscientific techniques may also provide insights into individual differences on a range of factors that can inform how technology might be tailored to suit particular types of learner. These factors may include ability, but also gender and age. One study has highlighted gender differences in how individuals respond to video games [START_REF] Hoeft | Gender differences in the mesocorticolimbic system during computer game-play[END_REF] , which have been cited as an informative and engaging context that educators may wish to understand learn from [START_REF] Gee | Learning and Games[END_REF] . In another example, the type of feedback which is optimal for our brain to learn appears dependent upon our maturity. Here, in a study of a computer-based rule search and application task, brain imaging data suggested a qualitative difference in how children and adults use performance feedback, with a transition around 11-13 years old towards an increased influence of negative feedback on performance adjustment [START_REF] Van Duijvenvoorde | Evaluating the negative or valuing the positive? Neural mechanisms supporting feedbackbased learning across development[END_REF] . Understanding how our ability to self-regulate develops through to adulthood may also provide insights and reasonable expectations (rather than constraints) about the self-regulated learning of children at different ages. Recent research shows how a range of factors that are critical to successful self-regulated learning (processing speed, voluntary response suppression, and working memory) mature across different age groups [START_REF] Luna | Maturation of cognitive processes from late childhood to adulthood[END_REF] , and this development is linked to an understanding of structural changes that occur in the brain until early adulthood [START_REF] Luna | The Maturation of Cognitive Control and the Adolescent Brain[END_REF] .

However, perhaps of greater value is the ability of technology to adapt dynamically to the changing needs of the learner, based on an automatic assessment of their responses. Indeed, the potential of combining TEL and neuroscience in adaptive educational systems has been highlighted in the UK as an area of research deserving future investment. An example of where scientific research has been integrated with an adaptive educational system is "Graphogame"a non-commercial system developed at the University of Jyväskylä (Finland) which introduces the association of graphemes and phonemes to young children according to the frequency and consistency of a grapheme in a given language [START_REF] Lyytinen | Early identification of dyslexia and the use of computer game-based practice to support reading acquisition[END_REF] . In this game, online algorithms analyze a child's performance and rewrite the lesson plans "on the fly" depending on which specific confusions the learner shows [START_REF] Mccandliss | Educational neuroscience: The early years[END_REF] . The difficulty of the content is also adjusted so that the challenge matches the learner's ability. Using fMRI and EEG together (allowing both good spatial and temporal resolution in measurements), it has been shown that the practise with the game could initiate print-sensitive activation in a critical component of the mature reading network located in the left occipitotemporal cortex, termed the "visual word-form system" [START_REF] Brem | Brain sensitivity to print emerges when children learn letter-speech sound correspondences[END_REF] . Knowing that this occipito-temporal print sensitivity is established during the earliest phase of reading acquisition in childhood, suggests that a crucial part of the later reading network first adopts a role in mapping print and sound. Such results provide insight into how the software succeeds in supporting literacy, how/when it should be implemented and how neuroscience can be used to inform TEL design. McCandliss 10 , reflecting on this and other studies, suggests "Given that adaptive educational computer programs are being developed in tandem with imaging studies of how such innovations drive changes in brain activity, new possibilities may emerge for educational and neuroscience research efforts to inform one another in increasingly rapid cycles."

It has been known for some time that illustrating text can enhance memory [START_REF] Paivio | Picture superiority in free recall: imagery or dual coding?[END_REF] , with pictures of objects appearing more memorable than their names. This effect has provided an important justification for the type of multimodality that can be provided by technology. Such approaches might be further informed by evidence that additional brain activity is produced by multimodal stimulus over and above that produced by experiencing each mode separately [START_REF] Beauchamp | Integration of auditory and visual information about objects in superior temporal sulcus[END_REF] . In this study, participants were scanned while exposed to auditory and visual characteristics of tools (hair-dryer, hammer etc) and the additional activities related to simultaneous exposure to both types of sensory cue were associated with making links between visual and auditory features. This automatic recruitment of additional processing might suggest we should necessarily observe improved memory for multimodally presented stimuli. However, this is not always the case. Simply presenting cues in two modes does not guarantee improved long-term memory (although it can decrease the load on working memory). The effectiveness of multimodal presentation as a memory/learning strategy appears to rely on whether it encourages in-depth processing of the type related to educational objectives [START_REF] Dubois | Multimedia design: the effects of relating multimodal information[END_REF] . Andreano et al. recently studied the effects of increasing the immersive nature of a virtual reality environment, with the hypothesis that this should increase activity in regions associated with learning [START_REF] Andreano | Auditory Cues Increase the Hippocampal Response to Unimodal Virtual Reality[END_REF] . This study showed that adding auditory cues to a virtual reality environment (comparing unimodal with multimodal) increases activation in the hippocampus, a region strongly associated with memory formation and having no sensory function, thus supporting the notion that multimodality is an important aspect of virtual reality that can support learning. The educational use of tangibles may also be informed by fresh understanding from neuroscience. For example, topics involving shape have been principally taught through the medium of vision, but there is increasing evidence for shape information being easily transferable between vision and haptics. A recent imaging study suggests that the relationship between audio and visual processes, which may be considered complimentary in their differences, may not resemble the relationship between haptic and visual processes, which may be considered more similar. Indeed, object recognition by touch and vision activate several overlapping and closely-related brain regions (see Fig. 1). In this study, the researchers observed "enhanced effectiveness", in neural terms, of combining haptic and visual stimulus 16 . That is, the multisensory gain with a combination stimulus was greater when its unisensory components were themselves associated with greater neural activity. Advances in fMRI techniques are now allowing the neural substrates of social processes to be imaged. This is providing insights into the subtleties of how we engage with others in simple co-operative tasks, which can contribute to our understanding of collaborative learning. A recent study identified the right pSTS as a key region for both social interaction and joint attention. By considering activations of this region in this and other studies [START_REF] Williams | An fMRI study of joint attention experience[END_REF][START_REF] Materna | Dissociable roles of the superior temporal sulcus and the intraparietal sulcus in joint attention: A functional magnetic resonance Imaging study[END_REF] , the authors suggest that full joint attention requires more than just simultaneously gazing at the same object. Instead, two people must deliberately coordinate attention on the object, usually with the expectation that the object will be rewarding (for cooperative exchanges) and/or relevant (for communicative exchanging), and it is this behaviour that activates the pSTS. In other research, it has been found that several aspects of social interaction that may support collaborative learning, such as interactional synchrony, anticipation of other's actions and co-regulation of turn-taking, are associated with neural synchronisation between collaborators' brains as measured by EEG [START_REF] Dumas | Inter-Brain Synchronization during Social Interaction[END_REF] . Brain research has also helped establish a better understanding of how trust between potential collaborators develops through reciprocity [START_REF] King-Casas | Getting to know you: Reputation and trust in a two-person economic exchange[END_REF][START_REF] Miller | Neuroscience -Economic game shows how the brain builds trust[END_REF] and insights into such trust differs from that engendered through institutions [START_REF] Boudreau | Knowing when to trust others: An ERP study of decision making after receiving information from unknown people[END_REF] .

Understanding how our brain responds to other humans can also shed light on our response to artificial agents (tutors, competitors, collaborators), which may form an increasingly important part of the new learning technologies. New learning technologies that embody key elements of individual human tutoring while avoiding its extraordinary financial cost are likely to exploit what we understand about human processes of imitation, shared attention and empathy [START_REF] Meltzoff | Foundations for a New Science of Learning[END_REF] . When we 'communicate' with non-human technology we may recruit brain regions usually involved with communicating with each other, particularly if this technology appears moderately human-like. A question tackled in a recent fMRI study was how human-like an artificial agent needs to be before we start attributing human intentions to them, i.e. a theory of mind. Although we have already seen that visual appearance is not a prerequisite (see Box 3) using networks usually associated with biological action, it does seem that visual appearance can play an important role. In a recent fMRI study, participants were asked to play a game against different type of opponent who, unbeknown to them, were all playing randomly [START_REF] Krach | Can machines think? Interaction and perspective taking with robots investigated via fMRI[END_REF] . Brain regions associated with theory of mind were activated in order of increasing human-like features (computer<functional robot<anthropomorphic robot<human). This suggests that cosmetic attempts to make technology more human-like may seriously influence our tendency to attribute human intentions and engage with it (Fig. 2).

Fig. 2 Regions associated with 'theory of mind' grow more active as the appearance of a technological opponent beomes more human-like, even when it is clearly not human (Krach et al 2008).

Through technology, we are now able to experience mobile, ubiquitous and pervasive learning, but biological contexts play an important role in understanding why such 24/7 experiences appear to be effective or not. Sleep plays an important role in memory, so when we learn influences how well we learn, with better recall following a period asleep than after the same period awake. Since technology now makes it easier for us search out, learn, communicate and apply knowledge all day and all night, this access can impact negatively on our sleep. For example, hormonal developmental influences produce a phase delay in the circadian timing mechanism of teenagers, but the use of mobile technology has also been shown to contribute to their sleep loss [START_REF] Van Den Bulck | Television viewing, computer game playing, internet use and self-reported time to bed and time out of bed in secondary-school children[END_REF] . A recent study in the U.S., a recent study showed the average teenager indulging in around 4 activities involving technology after 9.00 pm, spending over an hour on each [START_REF] Calamaro | Adolescents Living the 24/7 Lifestyle: Effects of Caffeine and Technology on Sleep Duration and Daytime Functioning[END_REF] . When we sleep after learning, the hippocampus in our brain rapidly integrates this information within distributed regions of the cortex [START_REF] Walker | Year in Cognitive Neuroscience[END_REF] . Successive sleep-dependent reactivation of this hippocampal-cortical network leads to progressive strengthening of connections across the cortex, which over time, allowing these memories to become independent of the hippocampus and gradually integrated with other, preexisting cortical memories. Therefore, not only does sleep support our recall of these memories but it also supports our ability to make links between these memories and older ones, which is important for our creative functioning. So, when access to technology impacts on our sleep habits, it can be detrimental to both our learning and our creativity. Moreover, activities involving close bright screens are able to delay the brain's production of the hormone melatonin and so interrupt sleepcycles in ways that a TV screen does not [START_REF] Higuchi | Effects of VDT tasks with a bright display at night on melatonin, core temperature, heart rate, and sleepiness[END_REF][START_REF] Higuchi | Effects of playing a computer game using a bright display on presleep physiological variables, sleep latency, slow wave sleep and REM sleep[END_REF] .

Evidence that our learning has biological substrates is sometimes mistakenly used to support theories of biologically determined outcomes. Yet a core concept of modern neuroscience is the brain's plasticity. Our educational experience influences the connectivity, function and structure of our brains. Even in old age, the brain remains plastic [START_REF] Boyke | Training-induced brain structure changes in the elderly[END_REF][START_REF] Lovden | Experience-dependent plasticity of white-matter microstructure extends into old age[END_REF] and use of cognitive training by the elderly has been shown to improve and protect cognitive function. These successful attempts at technology enhanced lifelong learning include research that has focused on sufferers of Alzheimer's, who have used training derived directly from our understanding of how different regions of the brain are affected at the various stages of the disease (AD). This study showed maintenance of cognitive function for sufferers with severe symptoms compared with controls, and improvements in related behaviours (anxiety, depression, apathy, sleep disturbances) for those with mild to moderate symptoms (Yuanguas 2006). Many of the training programmes tested have been technology-based and it has been pointed out that technology offers particular advantages in these applications Faucounau(2010) et al.

Computer-based cognitive training (so called "brain training") amongst the healthy has chiefly been found to improve performance on the training itself, rather than transferring to everyday application [START_REF] Owen | Putting brain training to the test[END_REF] . Once very important exception, however, is the training of working memory, which is a major constraint on our ability to learn new concepts. When young adults undertook a 19-day computer-based training program that focused on developing working memory for 30 minutes a day, it was found that not only their working memory, but also their fluid intelligence improved (i.e. their ability to solve problems in new situations). A convincing range of such results (including associated neural changes -see Fig 3) have led scientists to conclude that working memory can be trained [START_REF] Klingberg | Training and plasticity of working memory[END_REF] , and changes to prefrontal activations associated with working memory have been identified [START_REF] Olesen | Increased prefrontal and parietal activity after training of working memory[END_REF] . This bodes well for those wishing to develop more effective "brain training" games -but so far the commercial response to these exciting developments has been slow.

Interdisciplinary Discussions

It was noted that links existed between a range of concepts in TEL and neuroscience. The diagram below highlights some of these(fig. 4) Fig. 4 Some potential links between concepts in neuroscience and TEL. The table is intended to highlight where interdisciplinary discussion might be fruitful in interrelating concepts, and is not intended to imply equivalence or any simple correspondence of ideas.

Discussions identified a number of barriers to progress that would need tackling in efforts to integrate understanding from neuroscience TEL research, arising from differences in:

• language, terms and concepts in the two fields • professional aims (neuroscience is interested in determining new fundamental facts about neural processes, TEL seeks to generate practical demonstrations of benefit) • methods and epistemology, and the types of validity that are sought • research contexts (i.e. moving from controllable lab experiments to more ecologically valid but complex and less controllable "real world" scenarios)

Emerging Research Questions

In response to the discussion document, some participants had already noted a number of areas where neuroscience and TEL might inform each other, and they demonstrated these in the following (potential) research questions:

Charles Fadel:

How might neuroscience help refute "learning styles" and other techniques for accelerated learning -or help confirm them?

Tamara van Gog:

1. Would mirror neurons really play a role in learning from video-based or animation-based modeling examples in which tasks involving human movement are demonstrated to learners (which we hypothesized in a 2009, Educational Psychology Review article, might be a potential explanation for the fact that many animations about mechanical or natural phenomena are NOT more effective than a series of static pictures, while those involving human movement are) 2. Self-regulated learning: Adults are quite effective at monitoring their learning under certain instructional conditions; the findings regarding young children are mixed, an interesting question in my opinion would be whether this process relies on the same neural mechanisms in children and adults and how it develops?

And two more general questions:

3. Cognitive load measurement: EEG seems very promising, but what about fMRI for example?

4. I often get the impression that many people in the TEL community believe that technology makes kids effective multitaskers (doing homework with the television on while chatting on Facebook and following tweets), even though studies in cognitive psychology show that when it comes to learning, this is not effective at all; potentially, neuroscience research on attention and memory could make an important contribution (and one that might be more convincing for some) in this area as well Tony Fisher:

1.How might neuroscience inform our pedagogical and technological choices when we look to exploit ICT tools, social networks etc as part of learning and teaching? To what extent are we able to remember old solutions or strategies whilst generating new ones while using new technologies? Lisa Friedrich 1. What games are suitable to be combined with neurophysiological measurements (e.g. can be modified to send appropriate trigger for EEG analyses)? 2. What approaches are there/ should be made for adaptive educational systems (e.g. what kind of measurements (EEG, ECG, skin conductance,...), criteria/threshold for adaptation, which games, impact/consequences/improvement) Further discussion was focused on developing further Grand Challenges, as a means of demonstrating how opportunities at the confluence of neuroscience and TEL might arise.

Grand Challenge 1

• Substantially improving motivation and learning of students in European schools by systematically using game-based environments informed by our emerging understanding of the brain's reward system Activities necessary:

• Basic research on understanding how the brains reward system responds to different types of feedback -and how that influences learning • Use the neuro-computational algorithm, implement them into the game software to maximise engagement • Design-experimentation on improving an exemplary game; including varying the content • Bridging studies that study the game in the laboratory but also in the classroom with teachers included in this process.

• Scaling studies • Involve industry, technologists, educators, neuroscientists to explore the interdisciplinary processes to build future research capacity A Time frame of ~4 years would be necessary for this project. Measurable outcomes could be:

• improved engagement and achievement amongst targeted students

The generation of neurocomputational algorithms accurately predicting behaviour in a variety of game contexts, with their neural correlates

Grand Challenge 2

• Designing TEL environments to systematically inform all European teachers on main advances in Neuroscience and possible conclusions for teaching and learning in school.

Activities necessary

• Define a curriculum with respect to concepts, methods, and findings of neuroscience with respect to learning and instruction (including the definition of a process to revise the curriculum in the light of advances in research). We need a working group comprising educ. Researchers, practicing teachers, teacher educators, and neuroscience researchers. • Develop and evaluate a platform for bi-directional exchange (collecting and urging relevant areas of investigation -target group being neuroscientists ad educational researcherneuroscience in a nutshell /minimum level of knowledge not to fall under the influence of neuromyths / strong method focus. Need for a technical team in addition. • Support the systematic implementation (including finding ways to engage the different groups, evaluation of these TEL environments; tap into funding; use ECER network; ministries of education. • Empirical research: studies on scientific reasoning; change of perspective of use of rewards, interest, motivation This Grand Challenge could be later generalised to include parents and policy makers as target groups. A suitable timeframe would be 2-3 years in order to meet the following measurable success criteria:

• vibrant community;

• development of research agendas;

• change in (neuro)scientific reasoning of teachers • scale of participation(5000 teachers)

5.Researchers and Communities

Clearly, such projects as outlined above would require interdisciplinary teams for their successful promulgation:

Educational expertsable to identify content and participants, to help problematize research questions, guide issues of ecological validity, participate in evaluations

Cognitive neuroscientists -able to provide existing neural concepts and help theorize their application

Fig 1

 1 Fig 1 Regions of the brain that activate for visual and haptic object recognition overlap. Tangibles both types of information about shapes and these appear to enhance each other's neural effectiveness

Fig 3

 3 Fig 3 Increases in frontal and parietal regions after WM training (Olesen et al. 2004)

  2. How does neuroscience help us to understand and foster attention, engagement and flow in learning?3. What can we usefully say in ITE and teacher CPD about the intersection of TEL and findings from neuroscience?

	Niklas Ravaja:
	How do emotion-and cognition-related psychophysiological responses predict learning during a
	learning game?
	Diane Levine:
	1.	Can technology help us to learn what to remember?
	2.	What can the neuroscientific evidence on 'rewards' tell us about the ways in which young
		people develop relationships with others online?
	3.	Is there a difference between cultural and biological evolution? And how much do
		culturally learned thinking skills explain human creativity in a globalised TEL context?
	4.	What sorts of metaphors are good for helping children and young people understand
		what we know about how brains worK? And how can they use those working models to keep
		safe and happy online?
	5.

Psychologists -able to provide existing psychological concepts linking brain and learning behaviour, able to provide essential data specifying participants TEL experts (including commercial software providers) -able to theorise learner-technology interaction, help devise and construct prototypes and support exploitation of outcomes.


Search for Turbulent Gas through Interstellar Scintillation

Keywords: Galaxy:structure, dark matter, ISM 1 What is interstellar scintillation?

Stars twinkle because their light propagates through the atmosphere. The same phenomenon is expected when the light of remote stars crosses a Galacticdisk or halo -refractive medium such as a molecular cloud. We present the promising results of a test performed with the ESO-NTT and the perspectives.

• The diffusion radius R di f f (λ ) of the screen, defined as the transverse separation for which the root mean square of the phase difference at wavelength λ is 1 radian. • The refraction radius

R re f (λ ) = λ z 0 R di f f (λ ) ∼ 30860 km λ 1 µm z 0 1 kpc R di f f (λ ) 1000 km -1 (1)
where z 0 is the distance to the screen. This is the size, in the observer's plane, of the diffraction spot from a patch of R di f f (λ ) in the screen's plane. The illumination pattern from a stellar source of radius r s is the convolution of the point-like intensity pattern with the projected intensity profile of the source (Fig. 2, up-right). The cloud, moving with transverse velocity V T relative to the line of sight, will induce stochastic intensity fluctuations of the light received from the star at the characteristic time scale

t re f (λ ) = R re f (λ ) V T ∼ 5.2 minutes λ 1µm z 0 1 kpc R di f f (λ ) 1000 km -1 V T 100 km/s -1 .
(2) with modulation index m scint. = σ I / Ī given by m scint. = 0.12 λ 1µm

z 0 10pc -1/6 R di f f (λ ) 1000km -5/6 r s /z 1 R ⊙ /10kpc -7/6 . (3)
This modulation index decreases when the apparent stellar radius increases.

Signature of the scintillation signal: The first two signatures point to a propagation effect, which is incompatible with any type of intrinsic source variability.

• Chromaticity: Since R re f varies with λ -1/5 , one expects a small variation of the characteristic time scale t re f (λ ) between the red side of the optical spectrum and the blue side. • Spatial decorrelation: We expect a decorrelation between the light-curves observed at different telescope sites, increasing with their distance. • Correlation between the stellar radius and the modulation index: Big stars scintillate less than small stars through the same gaseous structure. • Location: The probability for scintillation is correlated with the foreground gas column-density. Therefore, extended structures may induce scintillation of apparently neighboring stars looking like clusters.

Foreground effects, background to the signal: Atmospheric intensity scintillation is negligible through a large telescope [Dravins et al. (1998)]. Any other atmospheric effect should be easy to recognize as it affects all stars. Asterosismology, granularity of the stellar surface, spots or eruptions produce variations of very different amplitudes and time scales. A rare type of recurrent variable stars exhibit emission variations at the minute scale, but such objects could be identified from their spectrum.

Preliminary studies with the NTT

During two nights of June 2006, 4749 consecutive exposures of T exp = 10 s have been taken with the infra-red SOFI detector in K s and J through nebulae B68, cb131, Circinus and towards SMC [Habibi et al. (2011)]. A candidate has been found towards B68 (Fig. 3), but the poor photometric precision in K s and other limitations prevent us from definitive conclusions. Nevertheless, we can conclude from the rarity of stochastically fluctuating objects that there is no significant population of stars that can mimic scintillation effects, and future searches should not be overwhelmed by background of fakes.

From the observed SMC light-curves we also established upper limits on invisible gaseous structures as a function of their diffusion radius (Fig. 4). This limit, although not really competitive, already excludes a major contribution of strongly turbulent gas to the hidden Galactic matter. These constaints are at the moment limited by the statistics and by the photometric precision. [Pfenniger & Combes (1994)].

3 Perspectives LSST will be an ideal setup to search for this signature of gas thanks to the fast readout and to the wide and deep field. Scintillation signal would provide a new tool to measure the inhomogeneities and the dynamics of nebulae, and to probe the molecular hydrogen contribution to the Milky-Way baryonic hidden matter.

Moniez

  Laboratoire de l'Accélérateur Linéaire, IN2P3-CNRS, Université de Paris-Sud, B.P. 34, 91898 Orsay Cedex, France, e-mail: moniez@lal.in2p3.fr 1 After crossing a fractal cloud described by the Kolmogorov turbulence law (Fig. 1, left), the light from a monochromatic point source produces an illumination pattern on Earth made of speckles of size R di f f (λ ) within larger structures of size R re f (λ ) (Fig. 1, right).

Fig. 1

 1 Fig. 1 Left: a 2D stochastic phase screen (grey scale), from a simulation of gas affected by Kolmogorov-type turbulence. Right: the illumination pattern from a point source (left) after crossing such a phase screen. The distorted wavefront produces structures at scales ∼ R di f f (λ ) and R re f (λ ) on the observer's plane.

Fig. 2

 2 Fig. 2 Simulated illumination map at λ = 2.16µm on Earth from a point source (up-left)-and from a K0V star (r s = 0.85R ⊙ , M V = 5.9) at z 1 = 8 kpc (right). The refracting cloud is assumed to be at z 0 = 160 pc with a turbulence parameter R di f f (2.16µm) = 150 km. The circle shows the projection of the stellar disk (r s × z 0 /z 1 ). The bottom maps are illuminations in the K s wide band (λ central = 2.162µm, ∆ λ = 0.275µm).

Fig. 3

 3 Fig. 3 Light-curves for the two nights of observation (above) and images of the candidate found toward B68 during a low-luminosity phase (up-right) and a highluminosity phase (bottom); North is up, East is left.

Fig. 4

 4 Fig.4The 95%CL maximum optical depth of structures with R di f f (1.25µm) < R d toward the SMC. The right scale gives the maximum contribution of structures with R di f f (1.25µm) < R d to the Galactic halo (in fraction); the gray zone shows the possible region for the hidden gas clumpuscules expected from the model of[Pfenniger & Combes (1994)].


Florent Marchand De Kerchove

Relabeling Algorithms On Dynamic Graphs

Invaluable thanks go to my supervisor, Frédéric Guinand, for his guidance and insight stemming from expertise. Your honest advice was always the most helpful; I'll be sure to take heed of it.

Then I would like to sincerely thank my lab mates. Alexis, for our many philosophical, somewhat metaphysical, and mostly fruitful discussions. Guillaume, for bringing your distinctive opinions to the table. Thibaut, for coping with my frequent, ludicrous teasing

Context 1.Dynamic graphs

Dynamic graphs arose from a need to include time into graph-based models. Graphs are powerful mathematical structures, suited to numerous theoretical and real-world applications. Indeed, if one wants to study a set of things and the relationships between these things, a graph is probably the most suited abstraction for that end. As far as we know, the concept of graph was first used by Euler to solve the "Seven Bridges of Könisberg" problem, where one must find a circuit crossing each of the seven bridges once and only once [START_REF] Euler | Solutio problematis ad geometriam situs pertinentis[END_REF]. Although the first recorded use of the term "graph" appeared 150 years later in [START_REF] Sylvester | Chemistry and algebra[END_REF].

However, for all their usefulness in a static context, graphs are not sufficient when it comes to modeling dynamic relationships between things. Consider, and we will refer to this example countless times in this report, the relationships in an ad-hoc network of mobile devices. A mobile device is capable of establishing a communication link with another device in the network when they are within range of each other's sensors. We consider networks of homogeneous devices of identical sensors, thus communication between mobile devices is assumed to be bidirectional1 . We can use a graph to abstract this mobile network: the mobile devices will be our graph's nodes, and the communication links between the devices will be our graph's edges. This abstraction is perfectly valid when we look at only a snapshot of the mobile network, an instantaneous capture of the devices and their communication links. However, these devices are mobile, i.e. they move freely in the environment in which they are situated. When two mobile devices move out of range of each other, they are suddenly unable to communicate, breaking the link between them. If we want to fully study this mobile network using graphs, we need to account for the disappearance (and appearance) of edges. In other words, we now must work with a dynamic set of edges.

That is precisely the notion introduced by Harary and Gupta [START_REF] Harary | Dynamic Graph Models[END_REF]. In this paper, the authors define four basic kinds of dynamic graphs, depending on where the dynamic lies:

• If the set of nodes is dynamic, i.e. nodes may be added or removed, we have a node-dynamic graph. When a node disappears, its incident edges are removed from the graph as well.

• If the set of edges is dynamic, we have an edge-dynamic graph.

• If the weights on nodes are dynamic, i.e. they change with time, we have a node weighted dynamic graph.

• If the weights on edges are dynamic, we have an edge weighted dynamic graph.

The authors note that all combinations of the above basic types can occur. In our mobile network example, if we assume that mobile devices can appear and disappear, then we need a graph that has a dynamic set of nodes as well as a dynamic set of edges.

Once we have properly defined the dynamic of our network, we still need a framework with which to study this dynamic. Harary and Gupta, still in the same article, suggest two approaches to study dynamic graphs. The first one is to model dynamic graphs as a logic program, arguing that this is a natural model, on the basis that logic programming is a relational programming paradigm, and graphs are relations. In addition, the ability of logic programs to handle nondeterminism is ideal to deal with combinatorial searches and algorithms. To our knowledge, this model did not garner a strong following, despite its legitimacy.

The second model, however, had more impact in the field. Straightforwardly, a dynamic graph can be decomposed as a discrete sequence of static graphs. Each static graph is a snapshot of the dynamic graph at a given time. These static graphs can then be studied by all the mathematical tools already at our disposal. This is precisely the view adopted by Ferreira and his "evolving graph" model [START_REF] Ferreira | Building a Reference Combinatorial Model for MANETs[END_REF].

Born in the context of mobile ad-hoc networks, the formalism of evolving graphs is a mathematical tool to analyze a sequence of static graphs captured from the same dynamic network. It introduces new concepts required by the incorporation of time, like the one of a path over time, called a journey. Our contribution is deeply rooted in this formalism, and as a matter of fact we will make use of the definitions presented in this seminal article [START_REF] Ferreira | Building a Reference Combinatorial Model for MANETs[END_REF].

Distributed algorithms and local computation

Armed with a sound mathematical basis for modeling mobile networks, we must now turn to characterizing distributed algorithms on these networks.

Distributed algorithm are designed to work on a heterogeneous set of hardware devices, without requiring a central entity to control them. The algorithm is shared by all nodes in a network, but each will execute it independently and concurrently. Typically, there is no synchronization between nodes, and information is only shared via messages. Since nodes can only send messages directly to adjacent nodes, communication with distant nodes is always indirect. Thus, nodes can never be sure of the algorithmic state of a non-adjacent node. This is a first cause of difficulty in designing distributed algorithms, in contrast to algorithms driven by a central entity. A centralized algorithm has information on the whole graph, and can act on any node without delay. A second difficulty arises from the fact that nodes do not have access to information on the network as a whole, such as topological information (network size, diameter, . . . ). Distributed algorithms are thus constrained by both local computation and local knowledge.

Fundamental problems of distributed programming include:

Counting Finding out the number of nodes of a network. We will focus mainly on this problem in this report.

Leader election

It is often desirable in a network to elect a leading node, in order to reestablish a central authority. The network leader can then command the other nodes to execute some computation, and to return their results back to the leader. In turn, the leader is polled for results by a user, abstracting the distributed aspect of the computation. By using a leader, one can take advantage of the wealth of knowledge concerning algorithms for centralized networks.

Spanning tree Spanning trees are a practical structure for distributed networks. Communication can be achieved without redundancy, and some problems, like leader election, can be reduced to finding a spanning tree (the root of the tree can be chosen as the leader).

Termination detection

Discovering when all nodes have completed their execution of an algorithm, without the help of a central authority. Detecting termination is essential in order to exploit the computation results, and to start another algorithm.

While these problems have been studied thoroughly for static networks, the combination of distributed algorithms and dynamic graphs is still a nascent research area. We focused our efforts on these problems because they are well-defined, abstract, though practically relevant, all the while being still open for improvement when applied to dynamic networks.

Related work

Distributed algorithms have been extensively studied in the past [CR79; Ang80; GHS83; NS93], and still are an active research area [START_REF] Dell | Information Dissemination in Highly Dynamic Graphs[END_REF][START_REF] Kuhn | Distributed Computation in Dynamic Networks[END_REF]. This interest resulted in a large number of models to characterize distributed algorithms, and the communication networks they are usually executed on. These models are seldom compatible in their assumptions on synchronizations protocols and mobility models for example. As a consequence, algorithms that are elaborated for distinct, specific models are not easily comparable to each other. This diversity called for higher-order theoretical frameworks, where the intrinsic properties of distributed algorithms can be analyzed without getting dragged into implementation details.

We focus on the model introduced by Casteigts [START_REF] Casteigts | Contribution à l'algorithmique distribuée dans les réseaux mobiles ad hoc -Calculs locaux et réétiquetages de graphes dynamiques[END_REF], where graph relabeling systems [START_REF] Litovsky | Graph relabelling systems and distributed algorithms[END_REF] are coupled with evolving graphs [START_REF] Ferreira | Building a Reference Combinatorial Model for MANETs[END_REF]. Though alternatives do exist [START_REF] Angluin | Computation in Networks of Passively Mobile Finite-State Sensors[END_REF], we felt they were still too restrictive in their approach, whereas the model we consider is more general. This framework was later extended by Casteigts et al. [START_REF] Casteigts | Characterizing Topological Assumptions of Distributed Algorithms in Dynamic Networks[END_REF][START_REF] Casteigts | Distributed Computing in Dynamic Networks: Towards a Framework for Automated Analysis of Algorithms[END_REF]. While these works are fairly recent, there have already been a couple follow-ups [Pig+10; FGA11]; this report can be inscribed along those.

Preliminaries

Our contributions build upon the work established by Casteigts et al. [START_REF] Casteigts | Distributed Computing in Dynamic Networks: Towards a Framework for Automated Analysis of Algorithms[END_REF]. Therefore, the concepts of local computation, graph relabelings and evolving graphs are required to fully understand the next section.

For the sake of clarity and completeness, we reproduce here the definitions by Casteigts et al. [START_REF] Casteigts | Distributed Computing in Dynamic Networks: Towards a Framework for Automated Analysis of Algorithms[END_REF] needed to express our results. Readers already familiar with these concepts may skip this section and refer to it when the need arises.

Graph relabelings

Graph relabelings [START_REF] Litovsky | Graph relabelling systems and distributed algorithms[END_REF] are a formalism where distributed algorithms are represented as a set of local interaction rules. These rules are independent from any communication protocol. Abstracting the effective communication allows us to specify and reason about important properties of distributed algorithms, such as correctness and termination, without limiting these results to a specific implementation.

As the name implies, a graph relabeling system is first and foremost a graph with labels on its vertices and edges. These labels are used by the interaction rules of the relabeling algorithm. An interaction rule is defined as a transition from one pattern of vertices and edges and their associated labels (preconditions), to another such pattern (actions). Since graph relabeling systems were introduced to characterize properties of local computation, interaction rules are local: they involve a limited set of connected vertices and edges. In this paper, we only consider interaction rules between pairs of vertices; see Figure 1 for the commonly-used scopes of computation.

We now give a formal definition of graph relabeling systems in the context of mobile networks. Let G = (V G , E G ) be a finite undirected loopless graph, with V G as the set of nodes in our network, and E G representing the set of communication links between them. Two vertices u and v are neighbors if and only if they share a common edge (u, v) in E G . Let λ : V G ∪ E G → L * be a mapping that associates every vertex and edge from G with one or several labels from an alphabet L. The label of a given vertex or edge u, at a given time t is denoted by λ t (u). The pair (G, λ) is the labeled graph, written G.

A complete algorithm is defined by the triplet {L, I, P}, where I is the set of initial states, and P is a set of relabeling rules. Since we are interested in distributed algorithms, where every node in the network will execute the same identical algorithm, the set of rules P is the same for all vertices.

Algorithm 1 (or A 1 for short) is an example of a complete algorithm expressed in the formalism of graph relabelings. Each vertex can be in one of two states: I and N , standing for informed and non-informed respectively. Initially, only the emitter vertex has the I state. Then, repeated application of the rule diffuses the information in the network. This is a simple and general information propagation algorithm.

Algorithm 1: Information propagation

Initial states: I for the emitter, N for every other node

I N I I r 1 :
The algorithm works in the following way. Since rules are patterns, each node looks for another node in order to match the rule's preconditions (the left-hand side of the rule). When a pair matches, both nodes modify their labels in the way described by the right-hand side of the rule. Figure 2 gives a step-by-step example of executing Algorithm 1 on a static graph. Here, all nodes are informed at the end. Note that this is only one possible execution sequence of the algorithm for this graph; others appear when matching pairs of nodes are selected in a different order.

Note that, from a node's perspective, when two or more neighbor nodes match a rule's preconditions, only one rule can be applied at a time. Depending on the order the rules are applied to these matching pairs, the algorithm may have different outcomes.

Evolving graphs

Definition

Evolving graphs were introduced by Ferreira [Fer04] as a model for dynamic networks. In this model, the evolution of the network topology is simply recorded as a sequence of static graphs, where each static graph can be seen as a snapshot of the network at a given time.

a b c G 1 a b c G 2 a b c G 3 a b c G 4 a b c 1,4 2 2,3 {G 1 , G 2 , G 3 , G 4 }
Figure 3: An evolving graph is a sequence of static graphs. On the lower hand-side is a compact representation of an evolving graph. Edges are labeled with the date of their presence.

Formally, an evolving graph is a triplet (G, S G , S ) = G, where:

• S is the sequence of dates used to capture the static graphs. can be anything meaningful to the network: discrete ( ⊂ ) and continuous ( ⊂ ) time systems are common.

• S G is the sequence of undirected static graphs G i = (V i , E i ), where G i is a snapshot of the network topology during an interval [t i , t i+1 ).

• G is the union of all G i in S G , called the underlying graph of G.

We will use the simple notations V and E to denote the sets of vertices and edges of the underlying graph G. A vertex (resp. edge) u is in V (resp. E) if and only if it belongs to at least one static graph in S G . In addition, we will use the notation

G [t a ,t b ) when taking a temporal subgraph G = (G , S G , S ) of G = (G, S G , S ), where G ⊆ G, S G = {G i ∈ S G : t i ∈ [t a , t b )}, and S = {t i ∈ S ∩ [t a , t b )}.

Basic concepts

First, we consider a presence function ρ : E × → {0, 1} that indicates whether a given edge is present at a given date. For e ∈ E and t ∈ [t i , t i+1 ), with t i and t i+1 being two consecutive dates in S , ρ(e, t) = 1 ⇐⇒ e ∈ E i .

A journey is a path over time between two vertices. Formally, a journey in G is a sequence of couples J = {(e 1 , σ 1 ), (e 2 , σ 2 ), . . . , (e k , σ k )} where {e 1 , e 2 , . . . , e k } is a walk in G, {σ 1 , σ 2 , . . . , σ k } is a non-decreasing sequence of dates from , and ρ(e i , σ i ) = 1 for all i ≤ k. A strict journey only contains couples (e i , σ i ) taken from distinct graphs of the sequence S G .

For any u, v in V , if a journey from u to v exists in G, we write u v, or u st v in the case of a strict journey. We assume that u u for all u in V . Note that a journey is not necessarily symmetrical, even if edges are undirected, because time intervals create a new level of direction. The horizon of a node u is the set {v ∈ V : u v}, thus u is included in its own horizon.

A network is connected over time if and

only if ∀u, v ∈ V , u v ∧ v u.
In other words, there is a round-trip journey between any two nodes. This property is especially useful for algorithms where acknowledgments of sent data are needed.

Relabelings over evolving graphs

Now we combine graph relabelings and evolving graphs to create an analysis framework for distributed algorithms on dynamic networks.

Let G = (G, S G , S ) be an evolving graph. The static graph in S G that covers the time interval

[t i , t i+1 ) is written G i ; we have G i ∈ S G and t i , t i+1 ∈ S . The labeled graph (G i , λ t i +ε ), denoted G i ,
represents the state of the network just after the topological event of date t i , and G i[ denotes the labeled graph (G i-1 , λ t i -ε ) representing the network state just before that event. Thus,

G i = Event t i (G i[ ).
Between two consecutive topological events, any number of relabelings may take place. For a given algorithm A and two consecutive dates t i , t i+1 ∈ S , we denote by R A [t i ,t i+1 ) one of the possible relabeling sequence induced by A on the graph G i during the period [t i , t i+1 ). We have

G i+1[ = R A [t i ,t i+1 ) (G i ).
Let us call t k the date of the last static graph in S G . A complete execution sequence from t 0 to t k is then given by an alternated sequence of relabeling steps and topological events:

X = R A [t k-1 ,t k ) • Event t k-1 • • • • • Event t i • R A [t i-1 ,t i ) • • • • • Event t 1 • R A [t 0 ,t 1 ) (G 0 )
We already mentioned that the order of execution of the rules is not deterministic, since it depends on implementation details concerning the selection of pairs of nodes matching a rule's preconditions. We denote by χ A/G the set of all possible execution sequences of an algorithm A over an evolving graph G. An example execution of a relabeling algorithm over an evolving graph is given in Figure 4.

Distributed algorithm analysis

A distributed algorithm can have multiple outcomes for the same graph. We usually want the algorithm to be complete: it should achieve its goal in all cases. For example, the propagation algorithm (Algorithm 1) should inform all nodes in the network. Unfortunately, all networks will not necessarily allow the algorithm to complete. If the network contains at least two connected components, then only one of them will have all of its nodes informed, since there is only one informed node initially, and information is propagated along edges.

Hence, we find a first way of analyzing distributed algorithm: by characterizing graphs on which they are complete, and graphs on which they can not reach their goal This time, the execution is a sequence of intertwined relabeling steps and topological events. In future diagrams, we will combine relabeling steps and topological events for the sake of brevity; thus we will only show the sequence of labeled graphs. at all. A condition on graphs ensuring the completeness of algorithm A will be called a sufficient condition for A. Conversely, a necessary condition for A defines the class of graphs on which A will always fail. Formal definitions of these concepts follow.

Objectives of an algorithm

Given an algorithm A and a labeled graph G, the state one wishes to reach can be given by a logic formula P on the labels of vertices (and edges, if appropriate). In the case of the propagation algorithm, such a terminal state could be that all nodes are informed,

P 1 (G) = ∀v ∈ V, λ(v) = I
The objective O A is then defined as the fact of verifying the desired property by the end of the execution, that is, on the final labeled graph, after the last relabeling step.

O A 1 = P 1 (G k[ )

Necessary conditions

Given an algorithm A, its objective O A and an evolving graph property C N , the property C N is a (topology-related) necessary condition for O A if and only if:

∀G, ¬C N (G) =⇒ ¬O A Proving this result comes to prove that ∀G, ¬C N (G) =⇒ X ∈ χ A/G |P(G k[ ).
(The desired state is not reachable by the end of the execution (time k), unless the condition is verified).

Sufficient conditions

Symmetrically, an evolving graph property C S is a (topology-related) sufficient condition for A if and only if:

∀G, C S (G) =⇒ O A Proving this result comes to prove that ∀G, C S (G) =⇒ ∀X ∈ χ A/G |P(G k[ ).
Because we have not made any assumptions on the synchronization between nodes, we have no way of ensuring that a rule will effectively be applied. Therefore, we must formulate a progression hypothesis that will allow us to characterize sufficient conditions.

Progression Hypothesis 1. In every time interval [t i , t i+1 ), with t i in S , each vertex is able to apply at least one relabeling rule with each of its neighbors, provided the rule preconditions are already satisfied at time t i (and still satisfied at the time the rule is applied).

Analysis of the propagation algorithm

Casteigts et al. show [CCF12]

that the information propagation algorithm has the following necessary and sufficient conditions.

Condition 1. ∃u ∈ V : ∀v ∈ V, u v.
(There is a node that can reach all the others by a journey.)

Condition 2. ∃u ∈ V : ∀v ∈ V, u st v.

Scope of analysis

When dealing with mobile networks, it is often desirable to maintain a property or structure over time, instead of merely reaching it. For example, maintaining a spanning tree, or an elected leader, or an accurate estimation of the graph size. Although analyzing such maintenance algorithms with the framework of relabelings over evolving graph is possible [Pig+10], we will not do so in this report.

Another aspect of mobile networks we will not consider explicitly is the appearance and disappearance of nodes during algorithm execution. Actually, this aspect is implicitly handled by the formalism of evolving graphs. Recall that evolving graphs are a postmortem view of the mobile network; in a given evolving graph, all the nodes that can appear or disappear belong to V . As such, even if a node can be seen as "appearing" from another node's viewpoint, for us it was present all along.

Contributions

In this section, we present our core contributions to the analysis of distributed algorithms on dynamic graphs.

First, we provide a sufficient condition for the decentralized counting algorithm from Casteigts [START_REF] Casteigts | Contribution à l'algorithmique distribuée dans les réseaux mobiles ad hoc -Calculs locaux et réétiquetages de graphes dynamiques[END_REF]. A necessary condition for this algorithm was formulated in Casteigts et al. [START_REF] Casteigts | Distributed Computing in Dynamic Networks: Towards a Framework for Automated Analysis of Algorithms[END_REF], but a sufficient condition was left open. We then introduce the concept of tight conditions, to strengthen the guarantees offered by necessary and sufficient conditions. We review the conditions and algorithms introduced so far with respect to this tightness criterion. Then, we combine the counting and information propagation algorithms to obtain a distributed counting algorithm where all nodes are informed of the final count. Finally, we propose another counting algorithm for dynamic networks where nodes have unique identifiers and can locally infer termination.

Sufficient condition for the decentralized counting algorithm

Decentralized counting algorithm

This decentralized counting algorithm was first proposed in Casteigts' thesis [START_REF] Casteigts | Contribution à l'algorithmique distribuée dans les réseaux mobiles ad hoc -Calculs locaux et réétiquetages de graphes dynamiques[END_REF], along with other variants.

Algorithm 2: Decentralized counting Initial states: (C, 1) for every node

(C, i) (C, j) (C, i + j) F r 1 :
This is an example of a truly distributed algorithm: all nodes have the same initial state, and all nodes execute the same algorithm. Each node has two labels: a state indicator (C of F ), and a counter. Initially, a node starts in the "counting" state (C), with a counter of value 1. The counter indicates the number of counted nodes so far by its holder, hence they all begin at 1. When two nodes in the counting state meet and apply rule 1, one of them transitions to the "counted" state (F ), and the other updates the value of its counter by summing the counters of both nodes. Ultimately, the goal is to have the last node remaining in the counting state to hold the total number of nodes in the network as the value of its counter. Figure 5 gives an example execution sequence.

(C, 1) (C, 1) (C, 1) (C, 1) r 1 (C, 1) F (C, 2) (C, 1) r 1 (C, 3) F F (C, 1)
Figure 5: Example execution of the decentralized counting algorithm. If we consider this to be the whole execution sequence, then the counting was not successful: two nodes remain in the counting state. For these two nodes to apply rule 1 and merge, there must be an edge between them; this is the intuition behind a sufficient condition for this algorithm.

Casteigts showed [START_REF] Casteigts | Contribution à l'algorithmique distribuée dans les réseaux mobiles ad hoc -Calculs locaux et réétiquetages de graphes dynamiques[END_REF] that this algorithm has the following invariant. Let (resp. ) be the set of nodes in state "C" (resp. "F"), and V be the set of all nodes. Then We can express the objective of this algorithm as the property that only one counting node remains at the end of the computation. Formally:

P 2 = ∃u ∈ V : ∀v ∈ V \ {u}, λ(u) = C ∧ λ(v) = F O A 2 = P 2 (G k[ )
The necessary condition to this algorithm was then shown to be:

Condition 3. ∃v ∈ V : ∀u ∈ V, u
v. (There is a node reachable by all the others.)

Sufficient condition

Let us now prove that Condition 4 is a sufficient condition for Algorithm 2.

Condition 4. The underlying graph G is complete. Precisely

: ∀u, v ∈ V , u = v =⇒ (u, v) ∈ E.
First, note the following properties of Algorithm 2.

Lemma 1. ∀t i , t j ∈ S , j ≤ i, ∀u ∈ V , λ t i (u) = C =⇒ λ t j (u) = C.
("C" labels never change until they disappear.) Proof. Counters can only disappear from a vertex by application of r 1 . Any counter still present at t i ∈ S \ {t 0 } must have been there from the beginning.

Lemma 2. ∀t i , t j ∈ S , j ≥ i, ∀u ∈ V , λ t i (u) = F =⇒ λ t j (u) = F .
("F" labels never change once they appear.) Proof. No rule can apply to a vertex with a "F" label, thus its label can never change once it becomes "F". ({u, v}). (If two counters share an edge, at least one of them will disappear.) Proof. During the relabeling step R [t i ,t i+1 ) , either r 1 is applied to (u, v), or r 1 can not be applied because preconditions on the labels are not met anymore after an intermediary relabeling. In the first case, one counter disappears from one vertex of {u, v}; in the second case, one vertex of {u, v} already lost its counter. In both cases, F ∈ λ t i+1[ ({u, v}).

Lemma 3. Under Progression Hypothesis 1, ∀t

i ∈ S \ {t k }, ∀(u, v) ∈ E i , λ t i (u) = λ t i (v) = C =⇒ F ∈ λ t i+1[
We can now show that Condition 4 (C 2 ) is sufficient for Algorithm 2 to fulfill its objective.

Proposition 1. Condition 4 is sufficient on G to guarantee that Algorithm 2 will reach its objective O A 2 .

Proof. (By contradiction). Assume O A 2 is not satisfied: for some execution sequence X ∈ χ A 2 /G , there are at least two final counters in G k . Let u and v be two nodes with such counters:

u, v ∈ V , u = v, λ t k (u) = λ t k (v) = C. Since G is complete (by Condition 4), (u, v) ∈ E i , for some t i ∈ S . By Lemma 1, λ t i (u) = λ t i (v) = C. Then, by Lemma 3, either λ t i+1[ (u) = F or λ t i+1[ (v) = F , and in both cases we have F ∈ λ t k ({u, v}) by Lemma 2, leading to a contradiction. Hence, C 2 =⇒ O A 2 . (C, n) (C, m) Final step t k (C, i) (C, j) Some step t i r 1 (C, i + j) F Step t i[
Figure 6: Illustration of the sufficient condition proof. If the final step t k has two nodes in the counting state, and since the underlying graph is complete, there must have been an edge between these two nodes at some step t i . If two nodes share an edge at some step t i , then they inevitably apply rule 1. Thus only one counter remains, even though we assumed there were two.

F 1 : ∃u ∈ V : ∀v ∈ V, u v F 2 : ∀u, v ∈ V, u v F 3 : ∃u ∈ V : ∀v ∈ V, u st v F 4 : ∀u, v ∈ V, u st v F 5 : ∃u ∈ V : ∀v ∈ V \ {u}, (u, v) ∈ E F 6 : ∀u, v ∈ V, u = v, (u, v) ∈ E F 7 : ∃u ∈ V : ∀v ∈ V, v u F 6 F 4 F 2 F 7 F 5 F 3 F 1

Comparison of counting algorithms

In Casteigts et al. [START_REF] Casteigts | Distributed Computing in Dynamic Networks: Towards a Framework for Automated Analysis of Algorithms[END_REF], a classification of graphs is given. Each condition (necessary or sufficient) defines a class of graphs: all the graphs satisfying the condition are part of this class. Classes of graphs can then be compared to each other, via the partial order induced by inclusion. Figure 7 illustrates the relationships between seven conditions. Under this classification, Condition 4 gives class F 6 , one the of narrowest, whereas the necessary condition to the decentralized counting algorithm is represented by F 7 , one of the largest. Theses classes allow us to compare the decentralized counting to other counting algorithms, on the basis of their requirements. An algorithm with a looser sufficient condition (inducing a larger class of graphs) is less specific, i.e. applicable to more graphs.

We can thus compare the decentralized counting algorithm with its centralized variant, Algorithm 3.

Algorithm 3: Centralized counting

Initial states: (C, 1) for the counting node, N for every other node

(C, i) N (C, i + 1) F r 1 :
In this algorithm, counting is handled by a single node in the network. This node starts in the "counting" state (label C) and keeps a counter initialized to 1, whereas all the others start in the "neutral" state (label N ). When the counting node meets a neutral node, the counter is increased by one, and the neutral node becomes "counted" (label F ). This is not a distributed algorithm in the purest sense, since the initial states are not uniform: one node begins in the unique state of counting.

This algorithm can be shown to have Condition 5 as a necessary condition.

Condition 5. ∃u ∈ V, ∀v ∈ V \ {u}, (u, v) ∈ E.

(A node shares an edge with all the others.)

Condition 5 gives class F 5 , which is larger than F 6 . We can thus conclude that the centralized counting algorithm is less specific than the decentralized version.

However, Condition 5 is sufficient for the centralized counting algorithm only if we pick the node u that shares an edge with all the other nodes as the initial node with a counter. If we want to be able to pick any node arbitrarily at random to be the counting node, then all nodes must share an edge with all the others. This condition is none other than Condition 4. In that case, the decentralized counting algorithm is the less specific, because its necessary condition has a larger class of graph; it also holds the advantage of requiring no centralization caused by a node with a special initial state.

Combination of algorithms

In the decentralized counting algorithm, only one node has knowledge of the total number of nodes. We would like to let all nodes know of the final count. Specifically, we want an algorithm capable of reaching the following desired state.

P 3 = ∃u ∈ V : ∀v ∈ V \ {u}, λ(u) = (C, |V |) ∧ λ(v) = (F, |V |)
The straightforward way to reach this state is to execute the information propagation algorithm (Algorithm 1) just after the counting algorithm is over. Unfortunately, nodes have no way of knowing that the algorithm they are currently executing is over. This is a known limit of computation in anonymous network [START_REF] Tel | Introduction to Distributed Algorithms[END_REF]. So, unless we give nodes a way of breaking symmetry (by assigning unique identifiers for example), we will not be able to chain both algorithms this way.

One solution is to execute both algorithms in parallel instead of chaining them. We get the following relabeling algorithm: Algorithm 4: Counting combined to propagation Initial states: (C, 1) for every node

(C, i) (C, j) (C, i + j) (F, i + j) r 1 : (F, i) (F, j > i) (F, j) (F, j) r 2 :
In this new algorithm, a counted node also updates its counter when rule 1 is applied. And because of rule 2, counted nodes diffuse the value of the highest counter. Clearly, once we arrive at a sole counting node, repeated application of r 2 will propagate the final tally to all counted nodes. Until the correct total count is reached however, propagation still occurs but is only of practical interest; it has the side effect of updating a lower bound on the census. Figure 8 illustrates this scheme.

(F , i) (F , j) (C, |V |)
Counting nodes

(F , |V |) (F , |V |) (C, |V |)
Propagating the result Figure 8: Overview of the algorithm combining counting and information propagation.

The first phase is concerned with getting the total number of nodes; propagation can be seen as a side effect. In the second phase, only rule 2 can match nodes. It broadcasts the final count to every node.

Once the algorithm is defined, we want a necessary and a sufficient condition. We focus on the sufficient condition first. Intuitively, the sufficient conditions for the two algorithms from which Algorithm 4 is created will take part in elaborating the sufficient condition for the hybrid algorithm. The two rules correspond to the two phases of counting and propagation. The latter phase is only of interest once the former is over, even though the rules are applied concurrently; propagation of the final count is what matters for the algorithm. Hence, the counting phase needs to end, and this requires a complete underlying graph (Condition 4). For the second phase, a strict journey from the final counting node to all the other nodes should suffice, but since we can not know in advance which node will fill this role, we must ensure such a journey can begin from any node (Condition 6). Condition 6. ∀u, v ∈ V : u st v (There is a strict journey between any two nodes.) However, these journeys are unnecessary until the counting phase is over. Since the requirements for both phases are separate, the sufficient condition can be expressed from Condition 4 and Condition 6 using temporal subgraphs (see subsubsection 2.2.1), giving Condition 7.

Condition 7. ∃t p ∈ S such that G [0,t p ) has a complete underlying graph, and G [t p ,t k ) satisfies Condition 6.

Let us now turn over to the necessary condition. Symmetrically, the two necessary conditions from the counting algorithm and the propagation algorithm will be used to express the necessary condition for the combined algorithm. Let us call them respectively N 1 (Condition 3) and N 2 (Condition 1). Clearly, if N 1 does not hold, then the counting phase can not succeed, leading to the failure of the combined algorithm. Likewise for N 2 , regardless of whether N 1 is satisfied. Consequently, any of the two can serve as a necessary condition for Algorithm 4.

It is interesting to note that, even if N 1 holds for an evolving graph G, we have no guarantee that any relabeling sequence will reach the desired goal state. The next subsection elaborates on this issue.

Tight necessary and sufficient conditions

A necessary condition might be broader than required. We know that any graph not satisfying this condition will never fulfill the algorithm's objective, but it gives us no additional clue about graphs satisfying the condition. Indeed, for any graph satisfying the condition, some may never fulfill the objective, some may fulfill it in some cases, and some may fulfill it in all cases; we can not know without a stronger definition.

Besides, it is not difficult to find trivial necessary conditions that are overly broad. For any relabeling algorithm, any condition which encompass all graphs is a necessary condition. Take the condition that the graph should have nodes: |V | > 0. Then, let S be the set of graphs not satisfying this condition; trivially, S = . It follows that any graph in S will never fulfill the objective, since S is empty, hence (|V | > 0) is a necessary condition. It is trivial in the sense that it does not enlarge the set of graphs for which the algorithm will fail.

When finding necessary conditions, we preferably want them to be as tight as possible. A necessary condition should partition the set of dynamic graphs into two subsets: the set of all graphs for which the algorithm will systematically fail, and the set of all graphs for which the algorithm will succeed at least once. To this end, we define tight necessary conditions that generates such partitioning; Figure 9 illustrates their advantage.

No knowledge

Graphs satisfying C N Will never reach O A

All evolving graphs Will reach O A in at least one instance

Graphs satisfying C T N

Will never reach O A

All evolving graphs

Definition 1. Let A be an algorithm, O A be its objective, and C N be a necessary condition. C N is a tight necessary condition if and only if

∀G, C N (G) =⇒ ∃X ∈ χ A/G |P(G k )
In other words, if C N holds for an evolving graph G, then at least one execution sequence of A over G will reach the desired state.

Symmetrically, we define tight sufficient conditions.

Definition 2. Let A be an algorithm, O A be its objective, and C S be a sufficient condition. C S is a tight sufficient condition if and only if

∀G, ¬C S (G) =⇒ ∃X ∈ χ A/G |¬P(G k )
In other words, if C S does not hold for a graph G, then at least one execution sequence of A over G will fail to reach the desired state.

Note that a condition that is both necessary and sufficient is also a tight necessary and tight sufficient condition (like Condition 5 for the centralized counting algorithm).

Tightening known conditions

We now show that Condition 4 is a tight sufficient condition for Algorithm 2. We have two ways to do so:

• Show that an evolving graph lacking completeness of its underlying graph will fail to fulfill its objective in at least one outcome.

• Show that all graphs for which all outcomes succeed in fulfilling the objective have a complete underlying graph.

The following proof uses the former path.

Proof. Let G = (G, S G , S ) be an evolving graph. By hypothesis, G is not complete; i.e. there are two distinct nodes u, v ∈ V such that (u, v) / ∈ E. Since u and v are never in direct contact, they can not apply rule r 1 . If u and v are the only two counting nodes left, then it follows that ¬P(G k ), thus the objective O A 2 can not be fulfilled and Condition 4 is tight. We are left with exposing a relabeling sequence which leaves u and v with two C labels.

When applying r 1 , any of the two nodes can keep the C label, creating two possible outcomes. Every time r 1 is applied to u (resp. v) with another node, we choose the outcome where u (resp. v) keeps the C label. Ultimately, there are at least two nodes in the counting state at time t k : u and v. There may be more, but in all cases the algorithm fails to fulfill the objective.

It can also be shown that all necessary and sufficient conditions given for the algorithms in Casteigts et al. [START_REF] Casteigts | Distributed Computing in Dynamic Networks: Towards a Framework for Automated Analysis of Algorithms[END_REF] are tight. This is expected, because mathematical proofs have a tendency to follow Occam's razor; the smallest set of hypotheses needed by the proof is kept. Nonetheless, tight conditions ensure we narrowed down the right property required by the algorithm to fail (or succeed).

Counting with identifiers

Let us now present a novel distributed algorithm for counting in networks where nodes have identifiers. We already mentioned that local detection of global termination is not feasible in anonymous networks (as shown by Tel [Tel00]). Local detection of global termination is invaluable in practice: each node can determine on its own when to stop executing the algorithm, and when to exploit its result. That is the reason this counting algorithm will make use of unique identifiers for nodes.

The algorithm can be expressed using two relabeling rules (Algorithm 5). Each node has three labels: Algorithm 5: Counting with identifiers

Initial states: L = {i u }, T = {i u } for each node u I J I J L L = L L ∪ L L ∪ L T T {I, J} {I, J}
r 1 :

I J I J L L = L L L T T = T T ∪ T T ∪ T r 2 :
• A unique identifier. In the diagram, this identifier is inscribed in the node's inside. Note that identifiers can be in any domain. When we write I and J, we do not intend that only the nodes with the respective identifiers I and J will match the rule. These are variables intended to capture a node's identifier and use its value later. We write i u the identifier of node u.

• A set L of identifiers of known nodes. Here again, one should not confuse L for a static label, for it represents a dynamic set of labels. During the algorithm execution, if we expand L we may get L = {a, b, c, . . . , z}, or L = {1, 2, 3, . . . , n}, or anything, depending on the domain from which identifiers are taken. We denote by L u the set L of a node u.

• A set T of identifiers of nodes who shared the same list L at some point in time.

The previous remark holds for T as well; here again we write T u to denote the set T of a node u.

Initially, each node u has a unique identifier i u , and L u = T u = {i u }. The first rule will match two nodes, u and v, of distinct sets L u and L v , who proceed to merge them together. The set L is thus used to make a census of known nodes, by sharing knowledge with adjacent nodes. Conversely, the second rule matches two nodes with identical sets L, but with distinct sets T . This time, the sets L are left alone, and the sets T are merged together. Intuitively, the set T is a set of acknowledgments: two nodes agree on their set of known nodes L, and they assume that this set is stable. Hence, by transitivity, for any node v whose identifier is in the set T u of node u, we have L u ⊂ L v . If L u is updated after that, then the acknowledgment is obsolete, and that is why the set T is reset when rule 1 is applied. Figure 11 gives an example of a couple relabeling steps for this algorithm.

Ultimately, if the set L is complete (L = {i x |∀x ∈ V }) and all nodes agree (T = L), then counting is over. Every node has the result, and also the identifiers of each node in the network. However, our interest here is to give nodes the power to know when the algorithm is over. In other words, we want the property that, for any node u, L u = T u =⇒ L u = {i x |∀x ∈ V }. Unfortunately, that is not always the case; see the counter-example in Figure 12.

Nevertheless, there is a way for the implication to be true: when the graph is connected initially, i.e. in G 0 there is only one connected component containing all nodes of V . Under Progression Hypothesis 1, every node u will fill its set L u with the identifiers of its neighbors at this initial time t 0 . This is enough to guarantee that local detection of global termination will raise no false positive, as the following proof demonstrates. Proof. (By contradiction). Let G = (G, S G , S ) be an evolving graph. At t 0 , this first date in S , the labeled graph G 0 is connected. Furthermore, assume there is a node u ∈ V such that L u = T u but L u is not complete. That is, ∃x ∈ V : i x / ∈ L u . Since G 0 was connected, x had at least one neighbor in G 0 , call that neighbor node y. Now, since (x, y) ∈ E 0 , i x ∈ L y because x and y would have applied r 1 under Progression Hypothesis 1 and because identifiers never disappear from a set L. Then, either:

v L = {v} T = {v} w L = {w} T = {w} u L = {u} T = {u} x L = {x} T = {x} r 1 v L = {v} T = {v} w L = {u, w} T = {u, w} u L = {u, w} T = {u, w} x L = {x} T = {x} r 1 v L = {v} T = {v} w L = {u, w, x} T = {w, x} u L = {u, w} T = {u, w} x L = {u, w, x} T = {w, x}
• i y ∈ T u , which means that both y and u acknowledged their L sets. Since i x ∈ L y it follows that i x ∈ L u , leading to a contradiction;

• i y / ∈ T u , and since L u = T u we have i y / ∈ L u . We found another node, y, which is not in L u . By the same argument, we can find a neighbor node of y, call it z, and show that i z must not be in L u , and so on and so forth until we reach u, because the graph is finite, and show that i u / ∈ L u , which is absurd.

Thus, if L u = T u then L u = {i x |∀x ∈ V }.
We have not yet characterized necessary and sufficient conditions for this algorithm. The interactions between the two rules make the analysis more complex, but we think these conditions can be found nonetheless.

Algorithms for the naming problem

In this section we discuss another distributed computing problem we have worked on but not to the point of giving formal proofs. We share these preliminary findings in the hope they can serve as a basis for further research.

The naming problem is another classical problem of distributed computing. Consider a mobile network of anonymous nodes able to communicate with their neighbors. The naming problem consists in attributing a unique identifier to each node in the network.

Local resolution

A first, naive way of trying to solve the naming problem is to locally resolve collisions between identifiers. When two nodes with the same identifier meet, one of them must change to another identifier.

Algorithm 6: Local naming

Initial states: 0 for every node

i i i j = i r 1 :
This collision may be resolved in any number of ways. For example, if identifiers are in and two nodes have the same identifier value i = j, for i, j ∈ , then increasing i to i + 1 is enough to have i = j. Generally, if identifiers are taken from a set S, and if any two elements from S are either equal or distinct, then a collision can be resolved by randomly picking an element from S until the identifiers differ.

Clearly, S needs to contain at least two elements otherwise this procedure for resolving collisions would never end. Furthermore, S should be at least as large as

|V | if 1 1 1 1 1 1 r 1 1 2 2 1 2 2 r 1 1 3 2 1 2 2
Figure 13: Solving the naming problem with local resolution.

we hope to solve the naming problem. In practice, we can easily take an infinite set of distinct elements, like , or words constructed from an alphabet. By resolving all local collisions between pairs of nodes, we ensure each node will not have the same identifier as any of its neighbors. This is in fact a coloring of the nodes in the network. However, we can not guarantee that a node will not share its identifier with another non-adjacent node, unless the underlying graph is complete.

Centralized naming

A second method of solving the naming problem is to use a central counter. Initially, one node starts in a differentiated state: as a counter which holds the next identifier to hand out to neighbor nodes; we will call it the source node. Initially, the source node gives itself the identifier 0, and its counter is set to 1. When the source node encounters another node u, u receives the current value of the counter as its identifier, and the counter is increased. If all nodes in the network meet with the source node, then all will have distinct identifiers. The algorithm thus solves the naming problem.

Algorithm 7: Centralized naming

Initial states: (0, 1) for the naming node, N for every other node

(0, i) N (0, i + 1) i r 1 :
The algorithm is actually quite similar to the centralized counting algorithm from Casteigts [START_REF] Casteigts | Contribution à l'algorithmique distribuée dans les réseaux mobiles ad hoc -Calculs locaux et réétiquetages de graphes dynamiques[END_REF]. Although in this case, in addition to counting, the differentiated node identifies neighbors as well. Nevertheless, it follows that the necessary and sufficient conditions for both algorithms are the same, i.e. the source node has degree n -1 in the underlying graph (Condition 5).

Random walking counter

Instead of using a centralized counter, we could pass the counter from node to node, like in a relay race. The counter is initialized to zero once again, and each time it is relayed to an unnamed node, that node takes the counter's current value as its identifier, before increasing it.

Depending on the topology of the network, all nodes may receive the counter, and thus have a unique identifier. Like in centralized naming, this counter can obviously be used for counting the nodes in the network, as well as naming them.

Algorithm 8: Token naming

Initial states: (0, 1) for the node holding the token, (N , N ) otherwise

(i, j) (N , N ) (i, N ) ( j, j + 1) r 1 :
However, and contrarily to centralized naming, the circulation of the token induces a random walk in the network. Hence, the necessary and sufficient conditions which held for the centralized naming algorithm are inadequate in this case.

Note that the token can only pass from a named node to an unnamed one; it can never end up on a previously visited node. Since, to solve the naming problem, we need to name all nodes in the network, what we need then is a journey which starts from the source node and goes through every other node, until no node is left unnamed. We will call such a journey an Hamiltonian journey.

It can be shown that the token will only progress along an Hamiltonian journey. Consequently, we can express the necessary condition for this naming algorithm: the evolving graph needs to contain at least one Hamiltonian journey starting from the source node. In the absence of such a journey, the token can not name all nodes, and thus the algorithm fails.

The sufficient condition is harder to find. It is easy to see that a chain of nodes can always be named, as well as ring networks of any size. In these graphs, the token has always only one possible node with which to interact, until all nodes are named. Adding only one edge may create situations where the token can be trapped in a dead-end, but not necessarily. Hamiltonian journeys may be a piece of the puzzle, but as of now, a sufficient condition for this algorithm still eludes us.

Tree method

The token method is sequential, since there is only one token traversing the graph at all times. The random walk of a lone token in large graph can be impractical. If we want the algorithm to finish quickly, we should make use of parallel computation. The problem then is to ensure that two nodes never receive the same identifier, even though naming is done concurrently and nodes have no direct way to know which identifiers may have been already assigned.

One solution is to use a naming scheme that will prevent duplicate identifiers from appearing. Consider a tree where the root has ID 0. Now, any children of the root can be uniquely identified by its child index, starting at 0. But if we use this index as an identifier number, the root will share its identifier with its first child. However, any node in the tree, save the root, can be uniquely described by the ID of its parent and its child index. Thus, if the root has ID 0, its first child has ID (0,0), its second child (0,1), and its second child's first child has ID (0,1,0). Identifiers are defined recursively, using the identifier of the parent node.

First, consider a static network. The algorithm can be described as follows:

• Assign identifier 0 to a source node;

• A node which already has an ID send its own ID suffixed with i (ID:i) to its i-th neighbor, for every neighbor that is not its parent (its parent is the node that gave it its identifier). Alternatively, the node can broadcast to all its neighbors, and the parent will just ignore the new ID as it already has one.

For static graphs, this process is bounded in the number of vertices, and we have global termination, but at the cost of having to choose a source node. We can also notify the source node when all nodes have a name by using the Dijkstra-Scholten algorithm.

The algorithm needs some modifications to accommodate an evolving graph:

• Each node keeps an internal counter C, initially zero.

• When node a with an ID meets unnamed node b, b gets assigned an ID constructed from a's ID suffixed with the value of a's counter C, and this counter is increased by one.

Algorithm 9: Tree naming

Initial states: (0, 0) for the root node, (N , 0) otherwise (i, c) (N , 0) (i, c + 1) (i : c, 0)

r 1 :
This tree method is more similar to flooding algorithms: all nodes with an ID will assign IDs to encountered nodes; the naming of nodes is made parallel. The expected time to terminate the algorithm should be lower than for the single token method.

This method has one downside though: identifiers grow in length with each level in the tree. On the one hand, identifiers can be used to trace a path back to the root, but this path is only valid at the time the identifier is constructed; in a dynamic network, this information may quickly become obsolete. On the other hand, the memory required to hold an identifier grows with the tree.

We have not yet characterized necessary or sufficient conditions for this algorithm.

Analysis of maintenance algorithms

We mentioned in subsection 2.5 that there are two kinds of objectives for distributed algorithms: reaching a desired state, or maintaining it. This is an important distinction to make. Reaching a state where the graph contains a spanning tree is certainly not as useful in practice as maintaining the spanning tree over time. While there has been preliminary studies using simulations for maintenance algorithms expressed as relabeling systems [START_REF] Pigné | Construction et maintien d'une forêt couvrante dans un réseau dynamique[END_REF], they restricted their analysis to static graphs. Simulations over dynamic graphs are often tied to a particular mobility model (or several), each model bringing its bias to the results. The framework provided by relabeling algorithms over evolving graphs is free of these biases, by its higher level of concern. It would be interesting to see if this framework would still be as potent when analyzing maintenance algorithms.

Algorithmic complexity

In the literature, distributed algorithms are most often characterized by their algorithmic complexity. Whole articles are devoted to improving the worst-case complexity of one algorithm and bring it closer to the theoretical lower bound [START_REF] Awerbuch | Optimal Distributed Algorithms for Minimum Weight Spanning Tree, Counting, Leader Election, and related problems[END_REF].

While this is an area we barely touched in this report, the framework we used can help with the complexity analysis of relabeling algorithms. We could find, for example, how many relabeling steps it would take for the information propagation algorithm to inform all n nodes for an evolving graph satisfying the sufficient condition. Or we could find additional sufficient conditions under which the algorithm terminates in fewer relabeling steps. More guarantees can be given, while still basing the analysis on the same framework.

Mechanization

Finally, Casteigts et al. [START_REF] Casteigts | Distributed Computing in Dynamic Networks: Towards a Framework for Automated Analysis of Algorithms[END_REF] already alluded to the mechanization of their work. Precisely, they envision a software platform which would be used to define distributed relabeling algorithms and run a library of tests on them. This tool would help its user find necessary and sufficient conditions for a given algorithm, by testing known conditions and by giving him clues via exhaustive combinatorial search. Towards this end, this software could make an extensive use of formal proof systems, such as Coq (a goal shared with Castéran et al. [START_REF] Castéran | Certifying distributed algorithms by embedding local computation systems in the Coq proof assistant[END_REF]). Another possibility is to follow-up on the idea from Harary and Gupta [HG97] of using logic programming to model dynamic graphs and relabeling algorithms. The backtracking backbone of logic languages such as Prolog is particularly suited to handling combinatorial searches.

Even a modest simulation tool for looking at execution traces of relabeling algorithms over dynamic graphs could be useful for the analyst. Using a variety of mobility models mimicking the real world, simulations would validate or invalidate distributed algorithms for practical applications. This prospect has already been tackled [START_REF] Pigné | Modélisation et traitement décentralisé des graphes dynamiques -Application aux réseaux mobiles ad hoc[END_REF], but much remain to be uncovered still.

Conclusion

Throughout this report, we built upon the foundations provided by Casteigts et al. [START_REF] Casteigts | Distributed Computing in Dynamic Networks: Towards a Framework for Automated Analysis of Algorithms[END_REF] in the domain of distributed algorithms over dynamic graphs.

First, we showed that a complete underlying graph was sufficient for the decentralized counting algorithm to succeed. Then we created a hybrid counting algorithm which propagate its result to all nodes in the network, by combining two preexisting algorithms. We also presented a novel algorithm for counting in a network of named nodes; it gives nodes the power to detect the end of the execution by merely looking at their neighborhood.

To ensure the generality of necessary and sufficient conditions, we defined a tightness criterion, and demonstrated the tightness of the sufficient condition we gave for the decentralized counting algorithm.

Finally, while we had focused on counting algorithms so far, we still enunciated four methods of solving the naming problem. However, we presented these methods less formally, and did not provide a necessary or sufficient condition for all of them.

Figure 1 :

 1 Figure 1: Scopes of local computation. Nodes in the scope of preconditions are filled in white, while nodes affected by the actions are filled in black (reproduced from Casteigts et al. [CCF12]).

Figure 2 :

 2 Figure 2: Example execution of the information propagation relabeling algorithm on a static graph.Here, all nodes are informed at the end. Note that this is only one possible execution sequence of the algorithm for this graph; others appear when matching pairs of nodes are selected in a different order.

Figure 4 :

 4 Figure4: Execution of the information propagation relabeling algorithm on an evolving graph. This time, the execution is a sequence of intertwined relabeling steps and topological events. In future diagrams, we will combine relabeling steps and topological events for the sake of brevity; thus we will only show the sequence of labeled graphs.

  | | + | | = |V | holds at any time of the computation. It follows that if = {u} (only one counting node remains), then u's counter value is equal to |V |.

Figure 7 :

 7 Figure 7: Classification of graphs (reproduced from Casteigts et al. [CCF12]).

Figure 9 :

 9 Figure 9: Partitioning the set of all evolving graphs with a necessary condition C N (lefthand side), and a tight necessary condition C T N (right-hand side).

Figure 11 :Figure 12 :

 1112 Figure11: Counting with identifiers. The identifiers are set in each node's circle. Each set L grows with each application of r 1 , listing all known nodes. Two nodes acknowledge their identical lists by inscribing each other in the set T .

Figure 14 :

 14 Figure 14: Using a tree to solve the naming problem.

In practice, environmental hazards will affect the communicating range of the mobile devices (walls and other obstacles, weather, etc.), such that communication may become unidirectional.

PerspectivesWe did not provide a necessary or a sufficient condition for the counting algorithm with identifiers. Instead, we focused on finding a sufficient condition for ensuring local detection of termination. Similarly, the four methods we proposed to solve the naming problem would also benefit from further analysis, e.g. necessary and sufficient conditions, and formal proofs for these conditions when we provided them.

Acknowledgments