Search

International audience; FIFO broadcast provides application ordering semantics of messages broadcast by the same sender and have been mostly implemented on top of unreliable static networks. In this article, we propose a round-based FIFO broadcast algorithm with both termination detection and bounded message size for dynamic networks with recurrent connectivity (Class TC^R of Time-varying Graph formalism). Initially, processes only know the number of processes N in the system and their identifier. Due to the dynamics of the network links, messages can be lost. Since no unbounded timestamp is used to identify a message, its size is bounded to 2N + O(log(N)) + msgSize bits where msgSize is the bound size in bits of the broadcast data. We also present an FIFO atomic broadcast algorithm in Class TC^R that uses the proposed FIFO broadcast and deliver primitives.

International audience; We initiate research on self-stabilization in highly dynamic identified message-passing systems where dynamics is modeled using time-varying graphs (TVGs). More precisely, we address the self-stabilizing leader election problem in three wide classes of TVGs: the class $TC^B(∆)$ of TVGs with temporal diameter bounded by $∆$, the class $TC^Q(∆)$ of TVGs with temporal diameter quasi-bounded by $∆$, and the class $TC^R$ of TVGs with recurrent connectivity only, where TC^B(∆) ⊆ $TC^Q(∆) ⊆ TC^R$. We first study conditions under which our problem can be solved. Precisely, we introduce the notion of size-ambiguity to show that the assumption on the knowledge of the number n of processes is central. Our results reveal that, despite the existence of unique process identifiers, any deterministic self-stabilizing leader election algorithm working in the TVG class $TC^Q(∆)$ or $TC^R$ cannot be size-ambiguous, justifying why our solutions for those classes assume the exact knowledge of n. We then present three self-stabilizing leader election algorithms for the TVG classes $TC^B(∆)$, $TC^Q(∆)$, and $TC^R$, respectively.

We present preliminary results on the last topic we collaborate with our late friend, Professor Ajoy Kumar Datta (1958–2019), who prematurely left us a few months ago. In this work, we shed new light on a self-stabilizing wave algorithm proposed by Colette Johnen in 1997 [12]. This algorithm constructs a BFS spanning tree in any connected rooted network. Nowadays, it is still the best existing self-stabilizing BFS spanning tree construction in terms of memory requirement, i.e., it only requires \(\varTheta (1)\) bits per edge. However, it has been proven assuming a weakly fair daemon. Moreover, its stabilization time was unknown. Here, we study the slightly modified version of this algorithm, still keeping the same memory requirement. We prove the self-stabilization of this variant under the distributed unfair daemon and show a stabilization time in \(O({\mathcal {D}}\cdot n^2)\) rounds, where \({\mathcal {D}}\) is the network diameter and n the number of processes.

International audience; In this paper, we propose a general scheme, called Algorithm $\mathsf{STlC}$, to compute spanning-tree-like data structures on arbitrary networks. $\mathsf{STlC}$ is self-stabilizing and silent and, despite its generality, is also efficient. It is written in the locally shared memory model with composite atomicity assuming the distributed unfair daemon, the weakest scheduling assumption of the model.Its stabilization time is in $n_{\texttt{maxCC}}$ rounds, where $n_{\texttt{maxCC}}$ is the maximum number of processes in a connected component. We also exhibit polynomial upper bounds on its stabilization time in steps and process moves holding for large classes of instantiations of Algorithm $\mathsf{STlC}$.We illustrate the versatility of our approach by proposing several such instantiations that efficiently solve classical problems such as leader election, as well as, unconstrained and shortest-path spanning tree constructions.

Consensus is one of the central distributed abstractions. By enabling a collection of processes to agree on one of the values they propose, consensus can be used to implement any generic replicated service in a consistent and fault-tolerant way. Therefore, complexity of consensus implementations has become one of the most important topics in the theory of distributed computing. Several concurrent objects have been proposed as building blocks to implement obstruction-free consensus or wait-free consensus in distributed systems augmented with failure detectors or strong synchronization primitives. In this paper we study an important subset of these objects: adopt-commit [1] , conflict-detector [2] , value-splitter [3] and grafarius [4] . We show that while some of these objects (adopt-commits and conflict-detectors) ensure a superset of the properties ensured by the others (value-splitter and grafarius), their space and individual step complexity is the same if implemented anonymously (the algorithm does not use process IDs). On the other hand, adopt-commit and conflict-detector objects have a larger complexity if we consider non anonymous implementations.

We present a silent self-stabilizing distributed algorithm computing a maximal $\ p$-star decomposition of the underlying communication network. Under the unfair distributed scheduler, the most general scheduler model, the algorithm converges in at most $12\Delta m + \mathcal{O}(m+n)$ moves, where $m$ is the number of edges, $n$ is the number of nodes and $\Delta $ is the maximum node degree. Regarding the time complexity, we obtain the following results: our algorithm outperforms the previously known best algorithm by a factor of $\Delta $ with respect to the move complexity. While the round complexity for the previous algorithm was unknown, we show a $5\big \lfloor \frac{n}{p+1} \big \rfloor +5$ bound for our algorithm.

International audience; In this paper, we revisit two fundamental results of the self-stabilizing literature about silent BFS spanning tree constructions: the Dolev etźal. algorithm and the Huang and Chen's algorithm. More precisely, we propose in the composite atomicity model three straightforward adaptations inspired from those algorithms. We then present a deep study of these three algorithms. Our results are related to both correctness (convergence and closure, assuming a distributed unfair daemon) and complexity (analysis of the stabilization time in terms of rounds and steps). We show that the bounded-memory version of the Dolev et al's BFS is round-optimal.We show that the stabilization time of the Huang and Chen's BFS is Omega(n) rounds.We show that these two algorithms have exponential stabilization times in steps.

Highly dynamic networks are characterized by frequent changes in the availability of communication links. These networks are often partitioned into several components, which split and merge unpredictably. We present a distributed algorithm that maintains a forest of (as few as possible) spanning trees in such a network, with no restriction on the rate of change. Our algorithm is inspired by high-level graph transformations, which we adapt here in a (synchronous) message passing model for dynamic networks. The resulting algorithm has the following properties: First, every decision is purely local---in each round, a node only considers its role and that of its neighbors in the tree, with no further information propagation (in particular, no wave mechanisms). Second, whatever the rate and scale of the changes, the algorithm guarantees that, by the end of every round, the network is covered by a forest of spanning trees in which 1) no cycle occur, 2) every node belongs to exactly one tree, and 3) every tree contains exactly one root (or token). We primarily focus on the correctness of this algorithm, which is established rigorously. While performance is not the main focus, we suggest new complexity metrics for such problems, and report on preliminary experimentation results validating our algorithm in a practical scenario., Long version of an OPODIS'14 paper. This version offers 40% more material, including the proofs and new content on the algorithm performance

We propose a fast, silent self-stabilizing protocol building a distance-k independent dominating set, named FID. The convergence of the protocol FID is established for any computation under the unfair distributed scheduler. The protocol FID reaches a terminal (also legitimate) configuration in at most 4n+k rounds, where n is the network size; it requires (k+1)log(n+1) bits per node.

In this paper we study efficient implementations for deterministic abortable objects. Deterministic abortable objects behave like ordinary objects when accessed sequentially, but they may return a special response abort to indicate that the operation failed (and did not take effect) when there is contention.

This paper makes contributions in two areas. First, we introduce an extended approach of self-stabilization, called self-stabilization with service guarantee. A self-stabilizing system tolerates transient faults: it automatically recovers to a correct behavior after a stabilization period. However, during stabilization periods, no property on the system behavior is guaranteed. A self-stabilizing protocol with service guarantee quickly provides a useful minimal service, and it maintains the minimal service during stabilization despite the occurrence of some disruptions. To illustrate our approach, we propose a clustering protocol (called SG-BSC), that builds 1-hop, bounded size and weight based clusters. SG-BSC protocol is self-stabilizing with service guarantee: it quickly reaches, in 4 rounds, a safe configuration from any arbitrary one. In a safe configuration, the following useful minimal service is provided: "each node belongs to a cluster, and each cluster has a leader and at most S i z e B o u n d ordinary nodes that are at most at distance 1 from their cluster-head". The convergence to a legitimate configuration (optimum service) is done in at most 7 ? N 2 + 4 rounds, where N is the number of nodes. We prove that any self-stabilizing protocol building weight-based clusters requires O ( N ) rounds to stabilize. Once the optimum service is reached, any cluster-head has the highest weight in its cluster, and the number of clusters is locally optimal. During the stabilization period, the minimal service is preserved; so, the hierarchical organization stays available throughout the entire network. Simulation results show the interest of self-stabilization with service guarantee compared to self-stabilization. We propose an extension of self-stabilization providing a service guarantee.We present a self-stabilization with service guarantee protocol (SG-BSC).SG-BSC protocol builds 1-hop, bounded size and weight based clusters.We prove the SG-BSC protocol properties: convergence, safety and service guarantee, and its time complexity.The interest of self-stabilization with service guarantee is established by simulations.

Chapter 3; The vehicular Ad Hoc network (VANET) could be considered as an ad hoc extension of a cellular mobile network. Thus communications are then possible either between vehicles or from vehicle to infrastructure based-network. However, the VANET suffers from a lack of connectivity and a limited capacity. One solution is to use clustering-based protocols to communicate between vehicles. The Clustering approach is well suited for vehicular networks because the dynamics of vehicular traffic result in the formation of natural groups of vehicles. In VANET, clustering criteria have to take into account the time and spatial dynamics of vehicular traffic. In this study, we review the effective clustering criteria used for VANET self-organization to exhibit such properties as scalability and stability of the structure. Finally, we introduce and develop a new clustering-based protocol for vehicular networks, called CONVOI. We show within simulation experiments that our proposal allows to build stable convoys with limited size.

We propose a transformer building a silent self-stabilizing with service guarantee 1-hop clustering protocol $\mathcal{TP}$ of an input silent self-stabilizing 1-hop clustering protocol $\mathcal{P}$. From an arbitrary configuration, $\mathcal{TP}$ reaches a safe configuration in at most 3 rounds, where the following useful minimal service is provided: "each node belongs to a 1-hop cluster having an effective leader". During stabilization of $\mathcal{TP}$, the minimal service is preserved, so the clustering structure is available throughout the entire network. The minimal service is also maintained despite the occurrences of some external disruptions, called highly tolerated disruptions, denoted $\mathcal{HTD}$. $\mathcal{TP}$ reaches a terminal (also legitimate) configuration in at most $4*S_\mathcal{P}$ rounds where $S_\mathcal{P}$ is the stabilization time of $\mathcal{P}$ protocol. Moreover, $\mathcal{TP}$ requires only 2 bits per node more than $\mathcal{P}$.

The area of self-stabilization in large scale networks has been received increasing attention among researchers, since self-stabilization provides a foundation for self-properties, including self-healing, self-organizing and self-adaptive. This paper makes contributions in two areas. First, we describe a new extended approach of self-stabilization, called self-stabilization with service guarantee. Second, we propose a self-stabilizing protocol computing and preserving the knowledge of neighbor clusters, called CNK. A cluster-head maintains about each neighbor cluster: the identity of its head, paths leading to it, and the list of members. The most interesting property of CNK is the service guarantee during the stabilization phase. CNK quickly provides, in at most 4 rounds, the following minimal useful service: "each cluster-head knows valid paths leading to heads of all its neighbor clusters". CNK protocol preserves the minimal service despite changes in the clustering structure (creation of new clusters, restructuring or crumbling of existing clusters). The knowledge of neighbor clusters is thus highly available. This knowledge is enough to allow the continuity functioning of hierarchical protocols as hierarchical routing protocols.

In this paper, we compare the two fault tolerant approaches: self-stabilization and robust self-stabilization, and we investigate their performances in dynamic networks. We study the behavior of four clustering protocols; two self-stabilizing GDMAC and BSC, and their robust self-stabilizing version R-GDMAC and R-BSC. The performances of protocols are compared in terms of their cluster-heads number, availability of both minimal and optimum services and the stabilization time.

In a distributed system, the environment is described by the scheduler (also called adversary or demon). Through an example related to stabilization, we show that a formal proof that does not use a formal definition of a scheduler is pointless. As a matter of fact, we show that the same algorithm, according to the scheduler, can be either correct or incorrect and in the cases where it is correct, can have different complexities. The paper is an attempt to better understand the meaning of proving a probabilistic algorithm in a indeterministic environment.

Clustering means partitioning nodes into groups called clusters, providing the network with a hierarchical organization. A self-stabilizing protocol, regardless of the initial system state, automatically converges to a set of states that satisfy the problem specification without external intervention. Due to this property, self-stabilizing protocols are adapted to highly dynamic networks as ad hoc or sensors networks. In this paper, we propose a self-stabilizing clustering protocol. Our protocol guarantees a threshold (size bound) on the number of nodes that a clusterhead handle. Therefore, none of the clusterheads are overloaded at anytime. The criterion of the clusterheads election is based on their weight value, a general parameter that can be computed according to several node parameters as transmission power, battery power, ... .

A distributed network can be modelled by a communication graph G = (V;E) where V is a set of processors and an edge hpqi 2 E if and only if processors p and q can communicate directly. Several variants have been de ned depending on the precise meaning of \communicate directly". In the state network models, each processor owns a singlewriter/multi-reader shared register, writable by the owner and readable by each neighbour. In the link network models, for each pair of processors joined by an edge, there are two single-writer/single-reader registers, each writable by one and readable by the other. Lamport [5] de ned three kinds of registers depending on the semantics when read and write operations overlap: safe, regular and atomic. Thus, six di erent network models arise by specifying two parameter for the shared registers: strength in fatomic, regular, safeg and location in flink, stateg. Our goal has been to determine possibilities and impossibilities for transforming an algorithmic solution designed for one variant into a solution for a weaker variant while retaining one or both of the fault tolerance properties wait-freedom and self-stabilization. In all six models the registers are single-writer, and so this descriptor is omitted in the following summary. We previously reported the following algorithms and impossibilities for transforming between some of these models: 1. From atomic-state to atomic-link{ a self-stabilizing compiler, and a proof that a wait-free one is impossible [1]. 2. From atomic-state to regular-state{ a self-stabilizing compiler that wait-free implements each write operation and obstruction-free implements each read operation, and a proof that it is impossible for both to be wait-free [2]. 3. From regular-state to regular-link{ there is a straightforward compiler that is wait-free and self-stabilizing [2,3]. 4. From atomic-link to regular-link{ there is a straightforward interpretation of Lamport's work [5] that constitutes a compiler that is wait-free and self-stabilizing [2,3].

A goal of peer-to-peer applications is to share files between users themselves rather than downloading files from file servers. Self-downloading protocols have the property that, eventually, every user downloads only from other users. Self-downloading is problematic if users disconnect from the system upon completing file downloading, because they only share with other users while connected. Yet, if users continue to arrive at a sufficient rate, self-downloading protocols are possible. One vulnerability of file sharing between users is the possibility that files or segments could be counterfeit or corrupt. Protocols that are d -safe tolerate some number of instances of faulty segments in a file being downloaded, because each segment is downloaded d times before being shared. This article shows that d -safe self-downloading is possible for a sufficiently large arrival rate of users to the system. Upper and lower connectivity and sharing bounds are given for d = 2, and simulation results show effects of relaxing assumptions about arrival rates and bandwidth.

There is a proliferation of models for distributed computing, consisting of both shared memory and message passing paradigms. Different communities adopt different variants as the “standard” model for their research setting. Since subtle changes in the communication model can result in significant changes to the solvability/unsolvability or to the complexity of various problems, it becomes imperative to understand the relationships between the many models. The situation becomes even more complicated when additional requirements such as fault-tolerance are added to the mix. This motivates us to determine exactly under what circumstances a program designed for one model and delivering some set of additional guarantees can be converted into an “equivalent” programs for a different model while delivering comparable guarantees. Once these relationships are understood, they can be exploited in system design.

We present a randomized self-stabilizing leader election protocol and a randomized self-stabilizing token circulation protocol under an arbitrary scheduler on anonymous and unidirectional rings of any size. These protocols are space optimal. We also give a formal and complete proof of these protocols. To this end, we develop a complete model for probabilistic self-stabilizing distributed systems which clearly separates the non deterministic behavior of the scheduler from the randomized behavior of the protocol. This framework includes all the necessary tools for proving the self- stabilization of a randomized distributed system: definition of a probabilistic space and definition of the self-stabilization of a randomized protocol. We also propose a new technique of scheduler management through a self-stabilizing protocol composition (cross-over composition). Roughly speaking, we force all computations to have a fairness property under any scheduler, even under an unfair one.

http://www.springer.com/; International audience; Ad hoc networks consist of wireless hosts that communicate with each other in the absence of a fixed infrastructure. Such networks cannot rely on centralized and organized network management. The clustering problem consists in partitioning network nodes into groups called clusters, giving a hierarchical organization of the network. A self-stabilizing algorithm, regardless of the initial system configuration, converges to legitimates configurations without external intervention. Due to this property, self-stabilizing algorithms tolerate transient faults. In this paper we present a robust self-stabilizing clustering algorithm for ad hoc network. The robustness property guarantees that, starting from an arbitrary configuration, in one round, network is partitioned into clusters. After that, the network stays partitioned during the convergence phase toward a legitimate configuration where the clusters partition ensures that any neighborhood has at most k clusterheads (k is a given parameter).

In this paper, we reduce the problem of computing the convergence time for a randomized self-stabilizing algorithm to an instance of the stochastic shortest path problem (SSP). The solution gives us a way to compute automatically the stabilization time against the worst and the best policy. Moreover, a corollary of this reduction ensures that the best and the worst policy for this kind of algorithms are memoryless and deterministic. We apply these results here in a toy example. We just present here the main results, to more details, see [1].

http://www.springer.com/; International audience; Ad hoc sensor networks consist of large number of wireless sensors that communicate with each other in the absence of a fixed infrastructure. Fast self-reconfiguration and power efficiency are very important property on any sensor network management. The clustering problem consists in partitioning network nodes into groups called clusters, thus giving at the network a hierarchical organization. Clustering increase the scalability and the energy efficiency of communication among the sensors. A self-stabilizing algorithm, regardless of the initial system state, converges to a set of states that satisfy the problem specification without external intervention. Due to this property, self-stabilizing algorithms are adapted highly dynamic networks. In this paper we present a Self-stabilizing Clustering Algorithm for Ad hoc sensor network. Our algorithm adapts faster than other algorithms to topology changes.

International audience; An advantage of peer-to-peer applications is that files can be shared without concentrated load on file servers. This note proposes deterministic techniques for splitting a files into segments so that, for certain restricted cases of arrival and server rates, users may copy files from one another without fetching the data from file servers.

International audience; We initiate research on self-stabilization in highly dynamic identified message-passing systems where dynamics is modeled using time-varying graphs (TVGs). More precisely, we address the self-stabilizing leader election problem in three wide classes of TVGs: the class TCB(Δ) of TVGs with temporal diameter bounded by Δ, the class TCQ(Δ) of TVGs with temporal diameter quasi-bounded by Δ, and the class TCR of TVGs with recurrent connectivity only, where TCB(Δ)⊆TCQ(Δ)⊆TCR. We first study conditions under which our problem can be solved. We introduce the notion of size-ambiguity to show that the assumption on the knowledge of the number n of processes is central. Our results reveal that, despite the existence of unique process identifiers, any deterministic self-stabilizing leader election algorithm working on the class TCQ(Δ) or TCR cannot be size-ambiguous, justifying why our solutions for those classes assume the exact knowledge of n. We then present three self-stabilizing leader election algorithms for Classes TCB(Δ), TCQ(Δ), and TCR, respectively. Our algorithm for TCB(Δ) stabilizes in at most 3Δ rounds. However, we show that stabilization time cannot be bounded for the leader election problem in TCQ(Δ) and TCR. Nevertheless, we circumvent this issue by showing that our solutions are speculative in the sense that their stabilization time in TCB(Δ) (⊆TCQ(Δ)⊆TCR) is O(Δ) rounds.

International audience; We define the mod k-synchronization problem as a weakening of the Firing Squad problem, where all nodes fire not at the same round, but at rounds that are all equal modulo k. We propose an algorithm that achieves mod k-synchronization in any dynamic network where there exist – possibly several – fixed spanning stars within each period of Delta consecutive rounds. In other words, we require that there always exists a temporal path of length at most Delta between some fixed node gamma and every other node. As opposed to the perfect synchronization achieved in the Firing Squad problem, mod k-synchronization thus does not require any strong connectivity property in the network. In our algorithm, all the nodes "know'' Delta, but they ignore what nodes are the centers of the spanning stars. We also prove that if the bound Delta for guaranteeing fixed spanning stars exists but is unknown to the agents, then mod k-synchronization is impossible.All nodes in our algorithm fire in less that 6kn + 4k rounds after all nodes become active, but unfortunately use unbounded counters. We then propose a refinement of this algorithm so that it becomes finite state while maintaining the same time complexity. The correctness of our first algorithm has been formally established in the proof assistant Isabelle.

Dynamic networks consist of entities making contact over time with one another. A major challenge in dynamic networks is to predict mobility patterns and decide whether the evolution of the topology satisfies requirements for the successof a given algorithm. The types of dynamics resulting from these networks are varied in scale and nature. For instance, some of these networks remain connected at all times; others are always disconnected but still offer some kind of connectivity over time and space (temporal connectivity); others are recurrently connected,periodic, etc. All of these contexts can be represented as dynamic graph classes corresponding to necessary or sufficient conditions for given distributed problems or algorithms. Given a dynamic graph, a natural question to ask is to which of the classes this graph belongs. In this work we provide a contribution to the automation of dynamic graphs classification. We provide strategies for testing membership of a dynamic graph to a given class and a generic framework to test properties in dynamic graphs. We also attempt to understand what can still be done in a context where no property on the graph is guaranteed through the distributed problem of maintaining a spanning forest in highly dynamic graphs., Les réseaux dynamiques sont constitués d’entités établissant des contacts les unes avec les autres dans le temps. Un défi majeur dans les réseaux dynamiques est de prédire les modèles de mobilité et de décider si l’évolution de la topologie satisfait aux exigences du succès d’un algorithme donné. Les types de dynamique résultant de ces réseaux sont variés en échelle et en nature. Par exemple,certains de ces réseaux restent connexes tout le temps; d’autres sont toujours déconnectés mais offrent toujours une sorte de connexité dans le temps et dans l’espace(connexité temporelle); d’autres sont connexes de manière récurrente, périodique,etc. Tous ces contextes peuvent être représentés sous forme de classes de graphes dynamiques correspondant à des conditions nécessaires et/ou suffisantes pour des problèmes ou algorithmes distribués donnés. Étant donné un graphe dynamique,une question naturelle est de savoir à quelles classes appartient ce graphe. Dans ce travail, nous apportons une contribution à l’automatisation de la classification de graphes dynamiques. Nous proposons des stratégies pour tester l’appartenance d’un graphe dynamique à une classe donnée et nous définissons un cadre générique pour le test de propriétés dans les graphes dynamiques. Nous explorons également le cas où aucune propriété sur le graphe n’est garantie, à travers l’étude du problème de maintien d’une forêt d’arbres couvrants dans un graphe dynamique.

Dynamic networks consist of entities making contact over time with one another. A major challenge in dynamic networks is to predict mobility patterns and decide whether the evolution of the topology satisfies requirements for the successof a given algorithm. The types of dynamics resulting from these networks are varied in scale and nature. For instance, some of these networks remain connected at all times; others are always disconnected but still offer some kind of connectivity over time and space (temporal connectivity); others are recurrently connected,periodic, etc. All of these contexts can be represented as dynamic graph classes corresponding to necessary or sufficient conditions for given distributed problems or algorithms. Given a dynamic graph, a natural question to ask is to which of the classes this graph belongs. In this work we provide a contribution to the automation of dynamic graphs classification. We provide strategies for testing membership of a dynamic graph to a given class and a generic framework to test properties in dynamic graphs. We also attempt to understand what can still be done in a context where no property on the graph is guaranteed through the distributed problem of maintaining a spanning forest in highly dynamic graphs.; Les réseaux dynamiques sont constitués d’entités établissant des contacts les unes avec les autres dans le temps. Un défi majeur dans les réseaux dynamiques est de prédire les modèles de mobilité et de décider si l’évolution de la topologie satisfait aux exigences du succès d’un algorithme donné. Les types de dynamique résultant de ces réseaux sont variés en échelle et en nature. Par exemple,certains de ces réseaux restent connexes tout le temps; d’autres sont toujours déconnectés mais offrent toujours une sorte de connexité dans le temps et dans l’espace(connexité temporelle); d’autres sont connexes de manière récurrente, périodique,etc. Tous ces contextes peuvent être représentés sous forme de classes de graphes dynamiques correspondant à des conditions nécessaires et/ou suffisantes pour des problèmes ou algorithmes distribués donnés. Étant donné un graphe dynamique,une question naturelle est de savoir à quelles classes appartient ce graphe. Dans ce travail, nous apportons une contribution à l’automatisation de la classification de graphes dynamiques. Nous proposons des stratégies pour tester l’appartenance d’un graphe dynamique à une classe donnée et nous définissons un cadre générique pour le test de propriétés dans les graphes dynamiques. Nous explorons également le cas où aucune propriété sur le graphe n’est garantie, à travers l’étude du problème de maintien d’une forêt d’arbres couvrants dans un graphe dynamique.