Dissertations / Theses on the topic 'Algorithmique Distribué'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 dissertations / theses for your research on the topic 'Algorithmique Distribué.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
Nace, Dritan. "Contribution au réroutage distribué dans les réseaux de télécommunication." Compiègne, 1997. http://www.theses.fr/1997COMP997S.
Poitou, Olivier. "Une algorithmique adaptée à la distribution pour la résolution de problèmes irréguliers." Toulouse, ENSAE, 2003. http://www.theses.fr/2003ESAE0008.
Lefevre, Jonas. "Protocoles de population : une hiérarchie des variantes. Calcul de couplages autostabilisants." Palaiseau, Ecole polytechnique, 2014. http://www.theses.fr/2014EPXX0068.
Hinge, Antoine. "Dessin de graphe distribué par modèle de force : application au Big Data." Thesis, Bordeaux, 2018. http://www.theses.fr/2018BORD0092/document.
Graphs, usually used to model relations between entities, are continually growing mainly because of the internet (social networks for example). Graph visualization (also called drawing) is a fast way of collecting data about a graph. Internet graphs are often stored in a distributed manner, split between several machines interconnected. This thesis aims to develop drawing algorithms to draw very large graphs using the MapReduce paradigm, used for cluster computing. Among graph drawing algorithms, those which rely on a physical model to compute the node placement are generally considered to draw graphs well regardless of the type of graph. We developped two force-directed graph drawing algorithms in the MapReduce paradigm. GDAD, the fist distributed force-directed graph drawing algorithm ever, uses pivots to simplify computations of node interactions. MuGDAD, following GDAD, uses a recursive simplification to draw the original graph, keeping the pivots. We compare these two algorithms with the state of the art to assess their performances
Bournez, Olivier. "Modèles Continus. Calculs. Algorithmique Distribuée." Habilitation à diriger des recherches, Institut National Polytechnique de Lorraine - INPL, 2006. http://tel.archives-ouvertes.fr/tel-00123104.
systèmes physiques, biologiques, ou issus de l'informatique
distribuée. Nous nous intéressons à leur pouvoir de modélisation, et à
leurs propriétés en tant que systèmes de calculs, et plus généralement
aux propriétés calculatoires des modèles continus.
Les deux premiers chapitres ne visent pas à produire des résultats
nouveaux, mais à motiver ce travail, et à le mettre en
perspectives. Le chapitre 3 constitue un survol. Les chapitres 4, 5 et
l'annexe A présentent un panorama de quelques-uns de nos résultats
personnels en relations avec cette problématique.
Plus précisément, le chapitre 1 présente les systèmes dynamiques, avec
un point de vue classique et mathématique. Il vise d'une part à
souligner la richesse, et la subtilité des comportements possibles des
systèmes dynamiques continus, et d'autre part à mettre en évidence que
différents dispositifs sont intrinsèquement continus, et utilisables
comme tels pour réaliser des calculs. En outre nous insistons sur la
puissance de modélisation d'une classe de systèmes dynamiques, que
nous nommons les problèmes de Cauchy polynomiaux.
Les exemples du chapitre 2, issus de la bioinformatique, des modèles
de la biologie des populations, de la virologie biologique et de la
virologie informatique, et de l'algorithmique distribuée, se
distinguent de ceux du chapitre 1 par le fait qu'ils mettent
explicitement en jeu une certaine notion de concurrence entre agents.
Nous présentons la théorie des jeux, et ses modèles, en nous
focalisant sur certains de ses modèles du dynamisme. Ces modèles
continus deviennent naturels pour parler d'algorithmique distribuée,
en particulier dès que l'on a affaire à des systèmes de grandes
tailles, ou dont on ne contrôle pas les interactions. Nous pointons
quelques modèles de l'algorithmique distribuée qui intègrent ces
considérations, et le potentiel de l'utilisation des systèmes continus
pour l'algorithmique distribuée.
Le chapitre 3 constitue un survol de la théorie des calculs pour les
modèles à temps continu. La puissance des modèles de calculs à temps
et espace discrets est relativement bien comprise grâce à la thèse de
Church, qui postule que tous les modèles raisonnables et suffisamment
puissants ont la même puissance, celle des machines de Turing. On peut
aussi considérer des modèles où le temps est continu. Certaines
grandes classes de modèles ont été considérées dans la
littérature. Nous les reprenons dans ce chapitre, en présentant un
panorama de ce qui est connu sur leurs propriétés calculatoires.
Le chapitre 4 présente un résumé de quelques-uns de nos résultats
personnels à propos de la comparaison de la puissance de plusieurs
modèles à temps continu, en relations avec la thèse de Emmanuel
Hainry. Claude Shannon a introduit en 1941 le GPAC comme un modèle des
dispositifs de calculs analogiques. Les résultats de Shannon ont
longtemps été utilisés pour argumenter que ce modèle était plus faible
que l'analyse récursive, et donc que les machines analogiques sont
prouvablement plus faibles que les machines digitales. Avec Manuel
Campagnolo, Daniel Graça, et Emmanuel Hainry, nous avons prouvé
récemment que le GPAC et l'analyse récursive calculent en fait les
mêmes fonctions. Ce résultat prend toute sa perspective si l'on
comprend que les fonctions calculées par le GPAC correspondent aux
problèmes de Cauchy polynomiaux, dont le pouvoir de modélisation est
discuté dans le chapitre 1.
D'autre part, nous avons montré qu'il était possible de caractériser
algébriquement les fonctions élémentairement calculables et
calculables au sens de l'analyse récursive. Cela signifie d'une part
qu'il est possible de les caractériser en termes d'une sous-classe des
fonctions R-récursives à la Moore, ce qui étend les résultats de
Campagnolo, Costa, Moore, de la calculabilité discrète à l'analyse
récursive, mais aussi d'autre part, qu'il est possible de caractériser
ces fonctions de façon purement continue, par l'analyse, sans
référence à de la calculabilité.
Dans le chapitre 5, nous reprenons certains de nos résultats à propos
de caractérisations logiques de classes de complexité dans le modèle
de Blum Shub et Smale, en relations avec la thèse de Paulin Jacobé de
Naurois. Le modèle de Blum Shub et Smale constitue un modèle de calcul
à temps discret et à espace continu. Le modèle, défini initialement
pour parler de complexité algébrique de problèmes sur le corps des
réels, ou plus généralement sur un anneau, a été par la suite été
étendu par Poizat en un modèle de calculs sur une structure logique
arbitraire. Avec Paulin Jacobé de Naurois, Felipe Cucker et Jean-Yves
Marion, nous avons caractérisé syntaxiquement les classes de
complexité majeures dans ce modèle sur une structure arbitraire, à la
Bellantoni et Cook 1992.
Le chapitre 6 est consacré à une conclusion, dans laquelle nous
reprenons plusieurs questions et perspectives qui nous semblent
intéressantes.
Dans l'annexe A, nous discutons un point de vue sur les
hypercalculs. La question de l'existence de systèmes capables de
réaliser des hypercalculs, c'est-à-dire d'effectuer des calculs
exploitables qui ne seraient pas réalisables par aucune machine de
Turing, fait encore couler de l'encre et des controverses. Nous avons
été invité à exprimer notre point de vue dans un numéro spécial sur le
sujet, que nous reprenons en annexe A. Nous y rappelons plusieurs
mauvaises compréhensions fréquentes de la thèse de Church, et nous
présentons un panorama de plusieurs classes de systèmes mathématiques,
avec la caractérisation de leur puissance.
David, Vincent. "Algorithmique parallèle sur les arbres de décision et raisonnement en temps contraint : étude et application au minimax." Toulouse, ENSAE, 1993. http://www.theses.fr/1993ESAE0008.
Godard, Emmanuel. "Réécritures de graphes et algorithmique distribuée." Bordeaux 1, 2002. http://www.theses.fr/2002BOR12518.
Clément, Julien. "Algorithmique probabiliste pour systèmes distribués émergents." Paris 11, 2009. http://www.theses.fr/2009PA112231.
Mobile sensor networks have appeared in computer science several years ago. Some of these networks’ characteristics are new: sensors are small, with few memory; they can be corrupted easily and are mobile. Moreover, they may contain thousands of entities. For computer science, the stake is huge. All these new properties are a challenge for us, algorithm creators. It is necessary to adapt our methods and to make sure that from an algorithmic point of view, these new systems will function correctly in the years to come. The theoretical difficulty and the stake of these issues transform them into an interesting and exciting research subject. The goal this thesis is to reconsider some of the algorithms created for classical networks in order to make them performing on these new networks. We did not restrain ourselves to mobile sensor networks and also considered other recent systems. Also, we always introduced probability in order to unblock impossibilities or to improve the performance of the algorithms. We obtained different results on several kinds of new networks as peer to peer networks, robots networks or mobile sensor networks in which we extend the population protocol model. Finally, we introduced a formal model in order to prove that at some level of abstraction, there are very strong connections between the various types of networks, or at least between the models describing them
Lavault, Christian. "Algorithmique et complexité distribuées : applications à quelques problèmes fondamentaux de complexité, protocoles distribués à consensus, information globale, problèmes distribués d'élection et de routage." Paris 11, 1987. http://www.theses.fr/1987PA112392.
Bonnin, David. "Algorithmique distribuée asynchrone avec une majorité de pannes." Thesis, Bordeaux, 2015. http://www.theses.fr/2015BORD0264/document.
In distributed computing, asynchronous message-passing model with crashes is well-known and considered in many articles, because of its realism and it issimple enough to be used and complex enough to represent many real problems.In this model, n processes communicate by exchanging messages, but withoutany bound on communication delays, i.e. a message may take an arbitrarilylong time to reach its destination. Moreover, up to f among the n processesmay crash, and thus definitely stop working. Those crashes are undetectablebecause of the system asynchronism, and restrict the potential results in thismodel.In many cases, known results in those systems must verify the propertyof a strict minority of crashes. For example, this applies to implementationof atomic registers and solving of renaming. This barrier of a majority ofcrashes, explained by the CAP theorem, restricts numerous problems, and theasynchronous message-passing model with a majority of crashes is thus notwell-studied and rather unknown. Hence, studying what can be done in thiscase of a majority of crashes is interesting.This thesis tries to analyse this model, through two main problems. The first part studies the implementation of shared objects, similar to usual registers,by defining x-colored register banks, and α-registers. The second partextends the renaming problem into k-redundant renaming, for both one-shotand long-lived versions, and similarly for the shared objects called splitters intok-splitters
Chalopin, Jérémie. "Algorithmique distribuée, calculs locaux et homomorphismes de graphes." Bordeaux 1, 2006. http://www.theses.fr/2006BOR13257.
Lejeune, Jonathan. "Algorithmique distribuée d'exclusion mutuelle : vers une gestion efficace des ressources." Thesis, Paris 6, 2014. http://www.theses.fr/2014PA066174/document.
Distributed large-scale systems such as Grids or Clouds provide large amounts of heterogeneous computing resources. Clouds manage ressource access by contracts that allow to define a quality of service (response time, availability, ...) that the provider has to respect. My thesis focuses on designing new distributed locking algorithms for large scale systems that integrate notions of quality of service. At first, my thesis targets distributed locking algorithms with constraints in terms of priorities and response time. Two mutual exclusion algorithms are proposed: a first algorithm takes into account client-defined priorities and a second one associates requests with deadlines. I then move on to a generalized mutual exclusion problem in order to allocate several types of heterogeneous resources in a exclusive way. I propose a new algorithm that reduces the cost of synchronization by limiting communication between non-conflicting processes.All algorithms have been implemented and evaluated over the national platform Grid 5000. Evaluations show that our algorithms satisfy applicative constraints while improving performance significatively in terms of resources use rate and response time
Lejeune, Jonathan. "Algorithmique distribuée d'exclusion mutuelle : vers une gestion efficace des ressources." Electronic Thesis or Diss., Paris 6, 2014. http://www.theses.fr/2014PA066174.
Distributed large-scale systems such as Grids or Clouds provide large amounts of heterogeneous computing resources. Clouds manage ressource access by contracts that allow to define a quality of service (response time, availability, ...) that the provider has to respect. My thesis focuses on designing new distributed locking algorithms for large scale systems that integrate notions of quality of service. At first, my thesis targets distributed locking algorithms with constraints in terms of priorities and response time. Two mutual exclusion algorithms are proposed: a first algorithm takes into account client-defined priorities and a second one associates requests with deadlines. I then move on to a generalized mutual exclusion problem in order to allocate several types of heterogeneous resources in a exclusive way. I propose a new algorithm that reduces the cost of synchronization by limiting communication between non-conflicting processes.All algorithms have been implemented and evaluated over the national platform Grid 5000. Evaluations show that our algorithms satisfy applicative constraints while improving performance significatively in terms of resources use rate and response time
Maignan, Luidnel. "Points, distances, et automates cellulaires : algorithmique géométrique et spatiale." Paris 11, 2010. http://www.theses.fr/2010PA112325.
Spatial computing aims at providing a scalable framework where computation is distributed on a uniform computing medium and communication happen locally between nearest neighbors. We study the particular framework of cellular automata, using a regular grid and synchronous update. We propose to develop primitives allowing to structure the medium around a set of particles. We consider three problems of geometrical nature: moving the particles on the grid in order to uniformize the density, constructing their convex hull, constructing a connected proximity graph establishing connection between nearest particles. The last two problems are considered for multidimensional grid while uniformization is solved specifically for the one dimensional grid. The work approach is to consider the metric space underlying the cellular automata topology and construct generic mathematical object based solely on this metric. As a result, the algorithms derived from the properties of those objects, generalize over arbitrary regular grid. We implemented the usual ones, including hexagonal, 4 neighbors, and 8 neighbors square grid. All the solutions are based on the same basic component: the distance field, which associates to each site of the space its distance to the nearest particle. While the distance values are not bounded, it is shown that the difference between the values of neighboring sites is bounded, enabling encoding of the gradient into a finite state field. Our algorithms are expressed in terms of movements according to such gradient, and also detecting patterns in the gradient, and can thus be encoded in finite state of automata, using only a dozen of state
Naz, André. "Algorithmique distribuée pour grands ensembles de robots : centralité, synchronisation et auto-reconfiguration." Thesis, Bourgogne Franche-Comté, 2017. http://www.theses.fr/2017UBFCD027/document.
Technological advances especially in the miniaturization of robotic devices foreshadow the emergence of large-scale ensembles of small-size resource-constrained robots that distributively cooperate to achieve complex tasks (e.g., modular self-reconfigurable robots, swarm robotic systems, distributed microelectromechanical systems, etc.). These ensembles are formed from independent, intelligent and communicating units which act as a whole ensemble. These units cooperatively self-organize themselves to achieve common goals. These systems are tought to be more versatile and more robust than conventional robotic systems while having at the same time a lower cost.These ensembles form complex asynchronous distributed systems in which every unit is an embedded system with its own but limited capabilities. Coordination of such large-scale distributed embedded systems poses significant algorithmic issues and open for new opportunities in distributed algorithms. In my thesis, I defend the idea that distributed algorithmic primitives suitable for the coordination of these ensembles should be both identified and designed.In this work, we focus on a specific class of modular robotics systems, namely large-scale distributed modular robotic ensembles composed of resource-constrained modules that are organized in a lattice structure and which can only communicate with neighboring modules. We identified and implemented three building blocks, namely centrality-based leader election, time synchronization and self-reconfiguration.We propose a collection of distributed algorithms to realize these primitives. We evaluate them using both hardware experiments and simulations on systems ranging from a dozen of modules to more than a dozen of thousands of modules. We show that our algorithms scale well and are suitable for large-scale embedded distributed systems with scarce memory and computing resources
Tourancheau, Bernard. "Algorithmique parallèle pour les machines à mémoire distribuée : application aux algorithmes matriciels." Grenoble INPG, 1989. http://tel.archives-ouvertes.fr/tel-00332663/.
Farhat, Ayman. "Techniques algorithmiques pour la fiabilité et la sûreté des systèmes distribués." Thesis, National Library of Canada = Bibliothèque nationale du Canada, 1998. http://www.collectionscanada.ca/obj/s4/f2/dsk1/tape10/PQDD_0004/MQ40581.pdf.
Pérez, Garcia Julio César. "Contribution to security and privacy in the Blockchain-based Internet of Things : Robustness, Reliability, and Scalability." Electronic Thesis or Diss., Avignon, 2023. http://www.theses.fr/2023AVIG0120.
The Internet of Things (IoT) is a diverse network of objects typically interconnected via the Internet. Given the sensitivity of the information exchanged in IoT applications, it is essential to guarantee security and privacy. This problem is aggravated by the open nature of wireless communications, and the power and computing resource limitations of most IoT devices. Existing IoT security solutions are based on centralized architectures, which raises scalability issues and the single point of failure problem, making them susceptible to denial-of-service attacks and technical failures. Blockchain has emerged as an attractive solution to IoT security and centralization issues. Blockchains replicate a permanent, append-only record of all transactions occurring on a network across multiple devices, keeping them synchronized through a consensus protocol. Blockchain implementation may involve high computational and energy costs for devices. Consequently, solutions based on Fog/Edge computing have been considered in the integration with IoT. However, the cost of Blockchain utilization must be optimized, especially in the consensus protocol, which significantly influences the overall system performance. Permissioned Blockchains align better with the requirements of IoT applications than Permissionless Blockchains, due to their high transaction processing rate and scalability. This is because the consensus nodes, i.e., Validators, are known and predetermined. In existing consensus protocols used in Permissioned Blockchains, the Validators are usually a predefined or randomly selected set of nodes, which affects both system performance and fairness among users. The objective of this work is to propose solutions to improve security and privacy within IoT by integrating Blockchain technology, as well as to maximize fairness levels during consensus. The study is organized into two distinct parts: one addresses critical aspects of IoT security and proposes Blockchain-based solutions, while the other part focuses on optimizing fairness among users during the execution of the consensus algorithm on the Blockchain. We present an authentication mechanism inspired by the µTesla authentication protocol, which uses symmetric keys that form a hashchain and achieves asymmetric properties by unveiling the key used a while later. With this mechanism and the use of the Blockchain to store the keys and facilitate authentication, our proposal ensures robust and efficient authentication of devices, without the need for a trusted third party. In addition, we introduce a Blockchain-based key management system for group communications adapted to IoT contexts. The use of Elliptic Curve Cryptography ensures a low computational cost while enabling secure distribution of group keys. In both security solutions, we provide formal and informal proofs of security under the defined attack model. A performance impact analysis and a comparison with existing solutions are also conducted, showing that the proposed solutions are secure and efficient and can be used in multiple IoT applications. The second part of the work proposes an algorithm to select Validator nodes in Permissioned Blockchains maximizing Social Welfare, using α-Fairness as the objective function. A mathematical model of the problem is developed, and a method for finding the solution in a distributed manner is proposed, employing metaheuristic Evolutionary algorithms and a Searchspace partitioning strategy. The security of the proposed algorithm and the quality of the solutions obtained are analyzed. As a result of this work, two security protocols for IoT based on Blockchain are introduced, along with a distributed algorithm for maximizing Social Welfare among users in a Permissioned Blockchain network
Akhtar, Sabina. "Vérification formelle d'algorithmes distribués en PlusCal-2." Electronic Thesis or Diss., Université de Lorraine, 2012. http://www.theses.fr/2012LORR0014.
Designing sound algorithms for concurrent and distributed systems is subtle and challenging. These systems are prone to deadlocks and race conditions, and are therefore hard to reproduce. Formal verification is a key technique to model the system and its properties and then perform verification by means of model checking. Formal languages like TLA+ have the ability to describe complicated algorithms quite concisely, but algorithm designers often find it difficult to model an algorithm in the form of formulas. In this thesis, we present PlusCal-2 that aims at being similar to pseudo-code while being formally verifiable. PlusCal-2 improves upon Lamport?s PlusCal algorithm language by lifting some of its restrictions and adding new constructs. Our language is intended for describing algorithms at a high level of abstraction. Finite instances of algorithms described in PlusCal-2 can be verified through the TLC model checker. The second contribution presented in this thesis is a study of partial-order reduction methods using conditional and constant dependency relation. To compute conditional dependency for PlusCal-2 algorithms, we exploit their locality information and present them in the form of independence predicates. We also propose an adaptation of a dynamic partial-order reduction algorithm for a variant of the tlc model checker. As an alternative to partial order reduction based on conditional dependency, we also describe a variant of a static partial-order reduction algorithm for the tlc model checker that relies on constant dependency relation. We also present our results for the experiments along with the proof of correctness
Akhtar, Sabina. "Vérification Formelle d'Algorithmes Distribués en PlusCal-2." Phd thesis, Université de Lorraine, 2012. http://tel.archives-ouvertes.fr/tel-00815570.
Civit, Pierre. "Spécification des systèmes distribués dynamiques probabilistes sécurisés." Electronic Thesis or Diss., Sorbonne université, 2022. http://www.theses.fr/2022SORUS396.
This thesis proposes a natural hierarchical model for dynamic probabilistic distributed systems. The model extends in an intuitive way the labeled transition systems that best capture the intuition of an object moving from one state to another. The model consists of 3 essential ingredients: (1) a parallel composition operation, noted ||, allowing to represent a new object A||B resulting from the interaction between two objects A and B, (2) a pre-order relation <=, where A <= B means that the object A implements the object B in the sense of an observational semantics, (3) the composability property for <=, that is A <= B implies C||A <= C||B, (4) a hierarchical structure, i.e. a system X, composed of objects interacting with each other and able to join and leave the system dynamically, is also an object of the model. Furthermore, the thesis discusses the conditions to obtain (5) the monotonicity (with <=) of dynamic creation/destruction of objects, i.e., if (i) A <= B and (ii) X_A and X_B differ only by the fact that X_A dynamically creates and destroys the object A instead of dynamically creating and destroying the object B as X_B does, then (iii) X_A <= X_B. The model is declined in several variants: asynchronous, timed, bounded and allows a modular design and a refinement methodology based only on the notion of externally observable behavior
Bui, Marc. "Étude comportementale d'algorithmes distribués de contrôle." Paris 11, 1989. http://www.theses.fr/1989PA112242.
Sidi, Bah Aladé Habib. "Algorithmes distribués dans les réseaux hétérogènes et autonomes." Phd thesis, Université d'Avignon, 2012. http://tel.archives-ouvertes.fr/tel-00879973.
Debrat, Henri. "Certification formelle de la correction d'algorithmes distribués avec erreurs de transmission." Thesis, Université de Lorraine, 2013. http://www.theses.fr/2013LORR0268.
Computer systems fail. Whatever the reason of these failures, it has been a widespread approach to try and increase the faults-tolerance of a computer system through its replication. The resulting system is said to be a distributed one, in which replicas have to be kept consistent with each others. Hence, reaching agreement, and Consensus in particular, becomes the problem to solve - indeed, the paradigm. Solving Consensus (under various assumptions) is a hard task : algorithms designed on this purpose are subtle and proving their being correct is error-prone - whenever they are, which occasionally appears not to be the case. For more that thirty years, researchers interested in what is called Formal Methods have been working on mechanizing the verification process, in order to increase confidence in the correctness of (distributed) algorithms. The work we present here is at the intersection of distributed algorithms and formal methods. We use the Isabelle/HOL software to certify the correctness proof of various Consensus algorithms expressed in a uniform framework based on the Heard-Of Model, introduced by Charron-Bost and Schiper in 2009. Expressed in a common model, these algorithms, which, depending on the case, share some common mecanisms (number of steps, intermediate votes, ...), some elements of syntax, or types of assumptions (partial synchronism...), can be proved using some common arguments. As a consequence, the certification effort can be reduced by copying some intermediate lemmas from one proof to another and let the computer automatically parse them until some manual adaptation is required. This lead to the idea of certifying the correctness of multiple algorithms all together, instead of proving them one after the other, as one would do on paper in a traditional way. The effort of translation in the formal language of the proof assistant is then possibly reduced. Of course, each proof will also contain specific arguments, which will have to be isolated and translated into the software. Here, we illustrate this proposition through the presentation of formal certificates of correctness for six Consensus algorithms. As a consequence, on should not expect to find here a comprehensive linear presentation of each proof : we first show the arguments shared by multiple proofs, followed by those which are specific to each o them
Thomé, Emmanuel. "Algorithmes de calcul de logarithmes discrets dans les corps finis." Phd thesis, Ecole Polytechnique X, 2003. http://tel.archives-ouvertes.fr/tel-00007532.
Dans une première partie, nous exposons les différentes améliorations que nous avons apportées à l'algorithme de Coppersmith pour le calcul de logarithmes discrets en caractéristique 2. Ces améliorations ont rendu possible le record que nous avons atteint. La portée de ce calcul dépasse
le simple cadre des corps finis, à cause de l'existence de la réduction MOV d'une part, et de la récente introduction des cryptosystèmes fondés sur l'identité.
On s'intéresse plus en détail, dans une seconde partie du mémoire, au problème classique de la résolution d'un système linéaire creux défini sur un corps fini, porté aux limites de ce que la technologie (théorique et pratique) permet. Nous montrons comment une amélioration substantielle de l'algorithme de Wiedemann par blocs a rendu celui-ci compétitif pour la résolution d'un grand système linéaire creux sur \GF p.
Une partie de ce mémoire est consacrée au point de vue de l'expérimentateur, grand utilisateur de moyens de calcul, de la surcharge de travail humain que cela impose, et des constatations que cette position amène.
Lambein, Patrick. "Consensus de moyenne dans les réseaux dynamiques anonymes : Une approche algorithmique." Thesis, Institut polytechnique de Paris, 2020. http://www.theses.fr/2020IPPAX103.
Compact and cheap electronic components announce the near-future development of applications in which networked systems of autonomous agents are made to carry over complex tasks. These, in turn, depend on a small number of coordination primitives, which need to be programmatically implemented into potentially low-powered, and computationally limited, agents.Such applications include for example the coordination of the collective motion of mobile and vehicular networks, the distributed aggregation and processing of data measured locally in sensor networks, and the on-line repartition of processing load in the computer farms powering wide-scale services. As they address constraints that are not specific to the digital nature of the network such primitives also serve to model complex behavior of natural systems, such as flocks and neural networks.This monograph focuses on providing distributed algorithms that asymptotically compute the average of initial values, initially present at each agent of a networked system with time-varying communication links and in the absence of centralized control. Additionally, we consider the weaker problem of getting the agents to asymptotically agree on any value within the initial bounds. We focus on locally implementable algorithms, which leverage no information beyond what the agents can acquire by themselves, and which need no bootstrapping mechanism like a global start signal or a leader agent.We provide distributed average consensus algorithms that operate over dynamic networks given different local assumptions. These algorithms are computationally simple and operate in polynomial time in the number of agents.For bidirectional communications, we give a deterministic algorithm which asymptotically computes the average as long as the network never becomes permanently disconnected. For the general case of asymmetric communications, we provide a stabilizing Monte Carlo algorithm that is efficient in bandwidth and memory and operates in linear time, along with an extension by which the algorithm can be made to uniformly terminate over any connected network in which agents may start asynchronously.This contrasts with a plethora of results and techniques in which agents are provided external information – the size of the system, a bound over their degree, – helped with exogenous symmetry breaking – a leader agent, unique identifiers, – or where the network is expected to conform to a specific shape – a ring, a a complete network, a regular graph. Indeed, because very different networks may look alike to the agents, they are limited in what they can learn locally, and many functions are impossible to compute in a fully distributed manner without assuming some structure in the network or additional symmetry-breaking device. Given these stringent constraints, our contribution is to offer algorithms whose validity depends uniquely on local and instantaneous conditions. In the bidirectional model, we show that anonymous deterministic agents can asymptotically compute the average in polynomial time. For the general model of directed interactions, we allow agents to consult random oracles. Under those conditions, full information protocols are capable of solving any problem, and so we focus on the spatial complexity and tolerance to a lack of initial coordination in the agents, while offering stronger termination guarantees than in the bidirectional case. Beyond the fact that locally implementable algorithms are eminently desirable, our study contributes to mapping the limits that local interactions impose on networks
Debrat, Henri. "Certification formelle de la correction d'algorithmes distribués avec erreurs de transmission." Electronic Thesis or Diss., Université de Lorraine, 2013. http://www.theses.fr/2013LORR0268.
Computer systems fail. Whatever the reason of these failures, it has been a widespread approach to try and increase the faults-tolerance of a computer system through its replication. The resulting system is said to be a distributed one, in which replicas have to be kept consistent with each others. Hence, reaching agreement, and Consensus in particular, becomes the problem to solve - indeed, the paradigm. Solving Consensus (under various assumptions) is a hard task : algorithms designed on this purpose are subtle and proving their being correct is error-prone - whenever they are, which occasionally appears not to be the case. For more that thirty years, researchers interested in what is called Formal Methods have been working on mechanizing the verification process, in order to increase confidence in the correctness of (distributed) algorithms. The work we present here is at the intersection of distributed algorithms and formal methods. We use the Isabelle/HOL software to certify the correctness proof of various Consensus algorithms expressed in a uniform framework based on the Heard-Of Model, introduced by Charron-Bost and Schiper in 2009. Expressed in a common model, these algorithms, which, depending on the case, share some common mecanisms (number of steps, intermediate votes, ...), some elements of syntax, or types of assumptions (partial synchronism...), can be proved using some common arguments. As a consequence, the certification effort can be reduced by copying some intermediate lemmas from one proof to another and let the computer automatically parse them until some manual adaptation is required. This lead to the idea of certifying the correctness of multiple algorithms all together, instead of proving them one after the other, as one would do on paper in a traditional way. The effort of translation in the formal language of the proof assistant is then possibly reduced. Of course, each proof will also contain specific arguments, which will have to be isolated and translated into the software. Here, we illustrate this proposition through the presentation of formal certificates of correctness for six Consensus algorithms. As a consequence, on should not expect to find here a comprehensive linear presentation of each proof : we first show the arguments shared by multiple proofs, followed by those which are specific to each o them
Boussaton, Octave. "Application de la théorie des jeux à l'optimisation du routage réseau - solutions algorithmiques." Phd thesis, Université Henri Poincaré - Nancy I, 2010. http://tel.archives-ouvertes.fr/tel-00605791.
Malvault, Willy. "Vers une architecture pair-à-pair pour l'informatique dans le nuage." Phd thesis, Université de Grenoble, 2011. http://tel.archives-ouvertes.fr/tel-00633787.
Maviel, Pierre. "Definition de classes d'environnements reseaux pour la simulation d'algorithmes distribues." Paris 6, 1987. http://www.theses.fr/1987PA066519.
Casteigts, Arnaud. "Contribution à l'algorithmique distribuée dans les réseaux mobiles ad hoc - Calculs locaux et réétiquetages de graphes dynamiques." Phd thesis, Université Sciences et Technologies - Bordeaux I, 2007. http://tel.archives-ouvertes.fr/tel-00193181.
Lebhar, Emmanuelle. "Algorithmes de routage et modèles aléatoires pour les graphes petits mondes." Phd thesis, Ecole normale supérieure de lyon - ENS LYON, 2005. http://tel.archives-ouvertes.fr/tel-00011646.
Fortin, Pierre. "Algorithmique hiérarchique parallèle haute performance pour les problèmes à N-corps." Phd thesis, Université Sciences et Technologies - Bordeaux I, 2006. http://tel.archives-ouvertes.fr/tel-00135843.
Nous étudions tout d'abord deux expressions distinctes du principal opérateur (« multipôle-to-local ») ainsi que les bornes d'erreur associées. Pour ces deux expressions, nous présentons une formulation matricielle dont l'implémentation avec des routines BLAS (Basic Linear Algebra Subprograms) permet d'améliorer fortement l'efficacité de calcul. Dans la gamme de précisions qui nous intéresse, cette approche se révèle plus performante que les améliorations existantes (FFT, rotations et ondes planes), pour des distributions uniformes ou non.
Outre une nouvelle structure de données pour l'octree sous-jacent et des contributions algorithmiques à la version adaptative, nous avons aussi efficacement parallélisé notre méthode en mémoire partagée et en mémoire distribuée. Enfin, des comparaisons avec des codes dédiés justifient l'intérêt de notre code pour des simulations en astrophysique.
Blin, Lélia. "Algorithmes auto-stabilisants pour la construction d'arbres couvrants et la gestion d'entités autonomes." Habilitation à diriger des recherches, Université Pierre et Marie Curie - Paris VI, 2011. http://tel.archives-ouvertes.fr/tel-00847179.
Bernard, Thibault. "Marches aléatoires et mot circulant, adaptativité et tolérance aux pannes dans les environnements distribués." Phd thesis, Université de Reims - Champagne Ardenne, 2006. http://tel.archives-ouvertes.fr/tel-00143600.
algorithmes reposent principalement sur les trois propriétés fondamentales des marches aléatoires (Percussion, Couverture, Rencontre). Nous fournissons une méthode qui évalue
le temps ́ecoulé avant que ces trois propriétés soient vérifiées. Cela nous permet d'évaluer de la complexité de nos algorithmes. Dans un second temps, nous proposons l'utilisation d'un jeton circulant aléatoirement sous forme de mot circulant afin de collecter sur ce jeton des informations topologiques. Ces informations permettent la construction et la maintenance d'une structure couvrante du réseau de communication. Ensuite, nous
avons utilisé cette structure pour concevoir un algorithme de circulation de jeton tolérant aux pannes pour les environnements dynamiques. Cet algorithme a la particularité d'être complètement décentralisé. Nous proposons dans un dernier temps d'adapter notre circulation de jeton pour proposer une solution au problème d'allocation de ressources dans les réseaux ad-hoc.
Simon, Gwendal. "Conception et réalisation d'un système pour environnement virtuel massivement partagé." Rennes 1, 2004. http://www.theses.fr/2004REN10158.
Pigné, Yoann. "Modélisation et traitement décentralisé des graphes dynamiquesApplication aux réseaux mobiles ad hoc." Phd thesis, Université du Havre, 2008. http://tel.archives-ouvertes.fr/tel-00371962.
Nous étudions la résolution de problèmes dans ces graphes à l'aide de méthodes inspirées de mécanismes d'intelligence collective.
Les modèles proposés sont validés dans le contexte applicatif des réseaux mobiles ad hoc. Une approche originale de construction et de maintien de chemins de communication sous plusieurs contraintes est proposée. Le problème de la construction et du maintien d'une forêt couvrante dans un réseau mobile ad hoc est également étudié.
Maamra, Khaled. "Algorithmes auto-stabilisants efficaces pour les graphes." Thesis, Université Paris-Saclay (ComUE), 2017. http://www.theses.fr/2017SACLV065/document.
The main focus of my thesis is the design of an efficient kind of distributed algorithms, known as: Self-stabilizing. These algorithms have the property to recover from faults in the environment they're executed in, and this without any human intervention. Recovering here, means converging toward a pre-defined, correct configuration. In this setting, I was mainly interested by the problems of matching in graphs, clique partitions and publication subscription paradigms. For the maximal version of the matching problem in anonymous graphs, we achieved a more efficient randomized, self-stabilizing algorithm. This work is published in a journal version in PPL. The maximum version of the same problem, but in an identified setting, led to the design of an efficient self-stabilizing algorithm that approximates the optimal solution up to the 2/3. This result was published at OPODIS. During a research visit at TUHH, Hamburg, Germany. Together with Pr. Volker Turau we tackled the problem of self-stabilizing publish/subscribe paradigms. This led to an algorithm introducing the new notion of short-cuts in this type of structures and was published under a brief announcement and a regular paper at SSS and NetSyS. In collaboration with Mr. Siegemund, then a visiting researcher at LIX, École Polytechnique, we worked on an efficient self-stabilizing algorithm for clique partitions. This work is still in progress and in preparation for an eventual publication
Hanusse, Nicolas. "Navigation dans les grands graphes." Habilitation à diriger des recherches, Université Sciences et Technologies - Bordeaux I, 2009. http://tel.archives-ouvertes.fr/tel-00717765.
Duboux, Thibault. "Régulation dynamique du partitionnement de données sur machines parallèles à mémoire distribuée." Lyon, École normale supérieure (sciences), 1996. http://www.theses.fr/1996ENSL0009.
Malvaut-Martiarena, Willy. "Vers une architecture pair-à-pair pour l'informatique dans le nuage." Thesis, Grenoble, 2011. http://www.theses.fr/2011GRENM044/document.
With the emergence of Cloud computing, a new trend is to externalize computing tasks in order to decrease costs and increase flexibility. Current Cloud infrastructures rely on the usage of large-scale centralized data centers, for computing resources provisioning. In this thesis, we study the possibility to provide a peer-to-peer based Cloud infrastructure, which is totally decentralized and can be deployed on any computing nodes federation. We focus on the nodes allocation problem and present Salute, a nodes allocation service that organizes nodes in unstructured overlay networks and relies on mechanisms to predict node availability in order to ensure, with high probability, that allocation requests will be satisfied over time, and this despite churn. Salute's implementation relies on the collaboration of several peer-to-peer protocols belonging to the category of epidemic protocols. To convey our claims, we evaluate Salute using real traces
Maurer, Alexandre. "Communication fiable dans les réseaux multi-sauts en présence de fautes byzantines." Thesis, Paris 6, 2014. http://www.theses.fr/2014PA066347/document.
As modern networks grow larger and larger, they become more likely to fail. Indeed, their nodes can be subject to attacks, failures, memory corruptions... In order to encompass all possible types of failures, we consider the most general model of failure: the Byzantine model, where the failing nodes have an arbitrary (and thus, potentially malicious) behavior. Such failures are extremely dangerous, as one single Byzantine node, if not neutralized, can potentially lie to the entire network. We consider the problem of reliably exchanging information in a multihop network despite such Byzantine failures. Solutions exist but require a dense network, where each node has a large number of neighbors. In this thesis, we propose solutions for sparse networks, such as the grid, where each node has at most 4 neighbors. In a first part, we accept that some correct nodes fail to communicate reliably. In exchange, we propose quantitative solutions that tolerate a large number of Byzantine failures, and significantly outperform previous solutions in sparse networks. In a second part, we propose algorithms that ensure reliable communication between all correct nodes, provided that the Byzantine nodes are sufficiently distant from each other. At last, we generalize existing results to new contexts: dynamic networks, and networks with an unbounded diameter
Nisse, Nicolas. "Complexité algorithmique: entre structure et connaissance. Comment les jeux de poursuite peuvent apporter des solutions." Habilitation à diriger des recherches, Université Nice Sophia Antipolis, 2014. http://tel.archives-ouvertes.fr/tel-00998854.
Tixeuil, Sébastien. "Vers l'auto-stabilisation des systèmes à grande échelle." Habilitation à diriger des recherches, Université Paris Sud - Paris XI, 2006. http://tel.archives-ouvertes.fr/tel-00124848.
Pelle, Robin. "Contribution à la modélisation formelle d'essaims de robots mobiles." Electronic Thesis or Diss., université Paris-Saclay, 2020. http://www.theses.fr/2020UPASG062.
Distributed Algorithm is among domains where informal reasoning is not an option, especially when Byzantine errors may occur. It is also characterized by a large variety of models whose subtle modulations imply radically different properties.We are interested in "robotic network": clouds of autonomous entities performing a cooperative task. The applications that these swarms of agents offer are extremely promising: exploration and search for survivors in devasted areas, patrols and drone flights in formation, etc. These few potentially critical exemples underline the high dynamicity of the model; they also indicate how failures of robots or errors in the distributed protocols that equip them can have distastrous consequences.To ensure the safety of the protocols and the security of tasks, we aim to optain, with the help of the Coq proof assistant, foraml mechanical validations of properties of certain distributed protocols. A prototype of Coq's formal model for robot network, Pactole, has recently shown the feasibility of an proof assistant verification in this framework. It captures quite naturally many variants of these networks, especially with regard to topology or the properties of demons. This model is of course in the higher order, and is based on coinductive types. It makes it possible to demonstrate in Coq both positive roperties: the embedded program makes it possible to carry out the task regardless of the initial configuration, as negative properties: there is no embedded program to complete the task.In the emerging framework of robot networks, the models are distinguished by the characteristics and capabilities of the robots, the topology of the space in which they evolve, the degree of synchronism (modelled by the properties of the activation demon), the error that can occure, etc. The prototype Pactole expresses only some of these variants. Thought in a theoretical framework (point robots, instantaneous movement, etc.), hypotheses remain out of reach, in particular realistic hypothesis such as totally asynchronous executions, or risk of collision. The absence of collision is fundamental in all applications relates to formation flights (drones) and critical safety condition as soon as one is interested in air transport. Formal validation of this property is therefore of great importance.The work consits of extending the formal model to take into account asynchronous evolutions of large robots. This modelling should allow easy formulation of protocols and the task they are supposed to perform. Particular attention will be given to ensuring the absence of collisions during potentially complex movements
Legaux, Joeffrey. "Squelettes algorithmiques pour la programmation et l'exécution efficaces de codes parallèles." Phd thesis, Université d'Orléans, 2013. http://tel.archives-ouvertes.fr/tel-00990852.
Filou, Vincent. "Une étude formelle de la théorie des calculs locaux à l'aide de l'assistant de preuve Coq." Thesis, Bordeaux 1, 2012. http://www.theses.fr/2012BOR14708/document.
The goal of this work is to build a framework allowing the study, in aformal setting, of the correctness of local computations systems aswell as the expressivity of this model. A local computation system isa set of graph relabelling rules with limited scope, corresponding to a class of distributed algorithms.Our first contribution is the formalisation, in the Coq proofassistant, of a relationnal semantic for local computation systems.This work is based on an original formal graph theory for Coq.Ambiguities inherent to a "pen and paper" definition of local computations are corrected, and we prove that our definition captures all sub-classes of relabelling relations studied in the remainder. We propose a draft of a proof methodology for local computation systems in Coq. Our second contribution is the study of the expressivity of classes of local computations inside our framework. We provide,for instance, a formal proof of D. Angluin results on election and graph coverings. We propose original "meta-theorems" concerningthe LC0 class of local computation, and use these theorem to produce formal impossibility proofs.Finally we study possible transformations of local computation systemsand of their proofs. To this end, we adapt the notion of ForwardSimulation, originally formulated by N. Lynch, to localcomputations. We use this notion to define certified transformationsof LC0 systems. We show how those certified transformation can be useto study the expressivity of certain class of algorithm in ourframework. We define, as certified transformation, two notions ofcomposition for LC0 systems.A Coq library of ~ 50000 lines of code, containing the formal proofs of the theorems presented in the thesis has been produced in collaboration with Pierre Castéran
Fuguet, Tortolero César. "Introduction de mécanismes de tolérance aux pannes franches dans les architectures de processeur « many-core » à mémoire partagée cohérente." Thesis, Paris 6, 2015. http://www.theses.fr/2015PA066462/document.
The always increasing performance demands of applications such as cryptography, scientific simulation, network packets dispatching, signal processing or even general-purpose computing has made of many-core architectures a necessary trend in the processor design. These architectures can have hundreds or thousands of processor cores, so as to provide important computational throughputs with a reasonable power consumption. However, their important transistor density makes many-core architectures more prone to hardware failures. There is an augmentation in the fabrication process variability, and in the stress factors of transistors, which impacts both the manufacturing yield and lifetime. A potential solution to this problem is the introduction of fault-tolerance mechanisms allowing the processor to function in a degraded mode despite the presence of defective internal components. We propose a complete in-the-field reconfiguration-based permanent failure recovery mechanism for shared-memory many-core processors. This mechanism is based on a firmware (stored in distributed on-chip read-only memories) executed at each hardware reset by the internal processor cores without any external intervention. It consists in distributed software procedures, which locate the faulty components (cores, memory banks, and network-on-chip routers), reconfigure the hardware architecture, and provide a description of the functional hardware infrastructure to the operating system. Our proposal is evaluated using a cycle-accurate SystemC virtual prototype of an existing many-core architecture. We evaluate both its latency, and its silicon cost
Marchand, Corine. "Mise au point d'algorithmes répartis dans un environnement fortement variable, et expérimentation dans le contexte des pico-réseaux." Phd thesis, Grenoble INPG, 2004. http://tel.archives-ouvertes.fr/tel-00008039.
Saad, Clément. "Quelques contributions dans les réseaux de capteurs sans fil : Localisation et Routage." Phd thesis, Université d'Avignon, 2008. http://tel.archives-ouvertes.fr/tel-00364914.