Dissertations / Theses on the topic 'Algorithme du Consensus'
To see the other types of publications on this topic, follow the link: Algorithme du Consensus.
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 'Algorithme du Consensus.'
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.
1
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.
Full textAbstract:
Présentation d'un cadre général pour l'étude et l'analyse des algorithmes répartis et résolution de plusieurs problèmes de fond relatifs à la complexité dans les systèmes répartis. Développement de divers outils d'analyse en moyenne de la complexite en messages de protocoles généraux à consensus. Résolution par l'analyse mathématique d'un problème ouvert sur les performances comparées des anneaux uni et bidirectionnels pour la complexité en moyenne en messages d'algorithmes d'élection déterministes. Un algorithme probabiliste de construction d'un arbre couvrant sur un système distribué anonyme et quelconque est développé. Deux théorèmes sont proposés qui bornent la faille des messages en fonction de la complexite en messages des algorithmes distribués asynchrones du point de vue de la quantité d'information.
2
Hanna, Fouad. "Etude et développement du nouvel algorithme distribué de consensus FLC permfettant de maintenir la cohérence des données partagées et tolérant aux fautess." Thesis, Besançon, 2016. http://www.theses.fr/2016BESA2051.
Full textAbstract:
De nos jours, le travail collaboratif a pris une place très importante dans plusieurs domaines, et notamment dans le domaine du télédiagnostic médical. Et la cohérence des données partagées est un enjeu primordial dans ce type d'application. De plus, pour garantir la cohérence des données, l'utilisation d'un algorithme de consensus est un élément indispensable dans les plateformes collaboratives. Nous présentons ici un nouvel algorithme de consensus, nommé FLC, permettant de garantir la cohérence des données partagées dans les systèmes distribués collaboratifs complètement asynchrones. Notre algorithme est tolérant aux pannes et a pour objectif d'améliorer la performance de consensus et notamment lorsque les processus participants tombent en panne. Ce nouvel algorithme utilise l'oracle leader Omega pour contourner le résultat d'impossibilité du théorème FLP. L'algorithme est décentralisé et adopte le modèle de pannes crash-stop. L'algorithme FLC s'appuie sur deux idées principales. La première propose de réaliser, au début de chaque cycle d'exécution, une phase simple d'élection de processus leader garantissant l'existence d'un seul leader par cycle. La deuxième bénéficie de la stabilité du système et plus particulièrement du fait que le processus leader ne tombe pas en panne d'un consensus à l'autre. Les performances de notre algorithme ont été analysées et comparées à celles des algorithmes les plus connus dans le domaine. Les résultats obtenus par simulation en utilisant la plateforme Neko ont montré que notre algorithme donne les meilleures performances lorsque le réseau utilisé est un réseau multicast et qu'aucun processus ne tombent en panne ainsi que pour les situations dans lesquelles l'algorithme de consensus subit une ou plusieurs pannes de processus coordinateurs/leadersNowadays, collaborative work took a very important place in many fields and particularly in the medicaltelediagnosis field. The consistency of shared data is a key issue in this type of applications. Moreover, itis essential to use a consensus algorithm to ensure data consistency in collaborative platforms. We presenthere our new consensus algorithm FLC that helps to ensure data consistency in asynchronous collaborativedistributed systems. Our algorithm is fault tolerant and aims to improve the performance of consensus ingeneral and particularly in the case of process crashes. The new algorithm uses the leader oracle tocircumvent the impossibility result of the FLP theorem. It is decentralized and considers the crash-stop failuremodel. The FLC algorithm is based on two main ideas. The first is to perform, at the beginning of eachround, a simple election phase guaranteeing the existence of only one leader per round. The second is totake advantage of system stability and more particularly of the fact that the leader does not crash betweentwo consecutive consensus runs. The performance of our algorithm was analyzed and compared to the mostknown algorithms in the domain. The results obtained by simulation, using the Neko platform, demonstratedthat our algorithm gave the best performance when using a multicast network in the best case scenario and insituations where the algorithm undergoes one or more crashes of coordinators/leaders processes
3
Ouattara, Mory. "Développement et mise en place d'une méthode de classification multi-blocs : application aux données de l'OQAI." Phd thesis, Conservatoire national des arts et metiers - CNAM, 2014. http://tel.archives-ouvertes.fr/tel-01062782.
Full textAbstract:
La multiplication des sources d'information et le développement de nouvelles technologies ont engendré des bases données complexes, souvent caractérisées par un nombre de variables relativement élevé par rapport aux individus. En particulier, dans les études environnementales sur la pollution de l'air intérieur, la collecte des informations sur les individus se fait au regard de plusieurs thématiques, engendrant ainsi des données de grande dimension avec une structure multi-blocs définie par les thématiques. L'objectif de ce travail a été de développer des méthodes de classification adaptées à ces jeux de données de grande dimension et structurées en blocs de variables. La première partie de ce travail présente un état de l'art des méthodes de classification en général et dans le cas de la grande dimension. Dans la deuxième partie, trois nouvelles approches de classification d'individus décrits par des variables structurées en blocs ont été proposées. La méthode 2S-SOM (Soft Subspace-Self Organizing Map), une approche de type subspace clustering basée sur une modification de la fonction de coût de l'algorithme des cartes topologiques à travers un double système de poids adaptatifs défini sur les blocs et sur les variables. Nous proposons ensuite des approches CSOM (Consensus SOM) et Rv-CSOM de recherche de consensus de cartes auto-organisées basées sur un système de poids déterminés à partir des partitions initiales. Enfin, la troisième partie présente une application de ces méthodes sur le jeu de données réelles de la campagne nationale logement (CNL) menée par l'OQAI afin de définir une typologie des logements au regard des thématiques : qualité de l'air intérieur, structure du bâtiment, composition des ménages et habitudes des occupants.
4
Kyrgyzov, Ivan. "Recherche dans les bases de donnees satellitaires des paysages et application au milieu urbain: clustering, consensus et categorisation." Phd thesis, Télécom ParisTech, 2008. http://pastel.archives-ouvertes.fr/pastel-00004084.
Full textAbstract:
Les images satellitaires ont trouvées une large application pour l'analyse des ressources naturelles et des activités humaines. Les images à haute résolution, e.g., SPOT5, sont très nombreuses. Ceci donne un grand intérêt afin de développer de nouveaux aspects théoriques et des outils pour la fouille d'images. L'objectif de la thèse est la fouille non-supervisée d'images et inclut trois parties principales. Dans la première partie nous démontrons le contenu d'images à haute résolution. Nous décrivons les zones d'images par les caractéristiques texturelles et géométriques. Les algorithmes de clustering sont présentés dans la deuxième partie. Une étude de critères de validité et de mesures d'information est donnée pour estimer la qualité de clustering. Un nouveau critère basé sur la Longueur de Description Minimale (LDM) est proposé pour estimer le nombre optimal de clusters. Par ailleurs, nous proposons un nouveau algorithme hiérarchique basé sur le critère LDM à noyau. Une nouvelle méthode de ''combinaison de clustering'' est présentée dans la thèse pour profiter de différents algorithmes de clustering. Nous développons un algorithme hiérarchique pour optimiser la fonction objective basée sur une matrice de co-association. Une deuxième méthode est proposée qui converge à une solution globale. Nous prouvons que le minimum global peut être trouvé en utilisant l'algorithme de type ''mean shift''. Les avantages de cette méthode sont une convergence rapide et une complexité linéaire. Dans la troisième partie de la thèse un protocole complet de la fouille d'images est proposé. Différents clusterings sont représentés via les relations sémantiques entre les concepts.
5
Belkadi, Adel. "Conception de commande tolérante aux défauts pour les systèmes multi-agents : application au vol en formation d'une flotte de véhicules autonomes aériens." Thesis, Université de Lorraine, 2017. http://www.theses.fr/2017LORR0183/document.
Full textAbstract:
Ces dernières années, l’émergence des nouvelles technologies tels que la miniaturisation des composants, les dispositifs de communication sans fils, l’augmentation de la taille de stockage et les capacités de calcul, a permis la conception de systèmes multi-agents coopératifs de plus en plus complexes. L’un des plus grands axes de recherche dans cette thématique concerne la commande en formation de flottes de véhicules autonomes. Un grand nombre d’applications et de missions, civiles et militaires, telles que l’exploration, la surveillance, et la maintenance, ont alors été développées et réalisées dans des milieux variés (terre, air, eau). Durant l’exécution de ces tâches, les véhicules doivent interagir avec leur environnement et entre eux pour se coordonner. Les outils de communication disponibles disposent souvent d’une portée limitée. La préservation de la connexion au sein du groupe devient alors un des objectifs à satisfaire pour que la tâche puisse être accomplie avec succès. Une des possibilités pour garantir cette contrainte est le déplacement en formation permettant de préserver les distances et la structure géométrique du groupe. Il est toutefois nécessaire de disposer d’outils et de méthodes d’analyse et de commande de ces types de systèmes afin d’exploiter au maximum leurs potentiels. Cette thèse s’inscrit dans cette direction de recherche en présentant une synthèse et une analyse des systèmes dynamiques multi-agents et plus particulièrement la commande en formation de véhicules autonomes. Les lois de commande développées dans la littérature pour la commande en formation permettent d’accomplir un grand nombre de missions avec un niveau de performance élevé. Toutefois, si un défaut/défaillant apparaît dans la formation, ces lois de commandes peuvent s’avérer très limitées, engendrant un comportement instable du système. Le développement de commandes tolérantes aux défauts devient alors primordial pour maintenir les performances de commande en présence de défauts. Cette problématique sera traitée dans ce mémoire de thèse et concernera le développement et la conception de commandes en formation tolérantes au défaut dévolu à une flotte de véhicules autonomes suivant différente configuration/structurationIn recent years, the emergence of new technologies such as miniaturization of components, wireless communication devices, increased storage size and computing capabilities have allowed the design of increasingly complex cooperative multi-agent systems. One of the main research axes in this topic concerns the formation control of fleets of autonomous vehicles. Many applications and missions, civilian and military, such as exploration, surveillance, and maintenance, were developed and carried out in various environments. During the execution of these tasks, the vehicles must interact with their environment and among themselves to coordinate. The available communication tools are often limited in scope. The preservation of the connection within the group then becomes one of the objectives to be satisfied in order to carry out the task successfully. One of the possibilities to guarantee this constraint is the training displacement, which makes it possible to preserve the distances and the geometrical structure of the group. However, it is necessary to have tools and methods for analyzing and controlling these types of systems in order to make the most of their potential. This thesis is part of this research direction by presenting a synthesis and analysis of multi-agent dynamical systems and more particularly the formation control of autonomous vehicles. The control laws developed in the literature for formation control allow to carry out a large number of missions with a high level of performance. However, if a fault/failure occurs in the training, these control laws can be very limited, resulting in unstable system behavior. The development of fault tolerant controls becomes paramount to maintaining control performance in the presence of faults. This problem will be dealt with in more detail in this thesis and will concern the development and design of Fault tolerant controls devolved to a fleet of autonomous vehicles according to different configuration/structuring
6
Ouattara, Mory. "Développement et mise en place d'une méthode de classification multi-blocs : application aux données de l'OQAI." Electronic Thesis or Diss., Paris, CNAM, 2014. http://www.theses.fr/2014CNAM0914.
Full textAbstract:
La multiplication des sources d'information et le développement de nouvelles technologies ont engendré des bases données complexes, souvent caractérisées par un nombre de variables relativement élevé par rapport aux individus. En particulier, dans les études environnementales sur la pollution de l'air intérieur, la collecte des informations sur les individus se fait au regard de plusieurs thématiques, engendrant ainsi des données de grande dimension avec une structure multi-blocs définie par les thématiques. L'objectif de ce travail a été de développer des méthodes de classification adaptées à ces jeux de données de grande dimension et structurées en blocs de variables. La première partie de ce travail présente un état de l'art des méthodes de classification en général et dans le cas de la grande dimension. Dans la deuxième partie, trois nouvelles approches de classification d'individus décrits par des variables structurées en blocs ont été proposées. La méthode 2S-SOM (Soft Subspace-Self Organizing Map), une approche de type subspace clustering basée sur une modification de la fonction de coût de l'algorithme des cartes topologiques à travers un double système de poids adaptatifs défini sur les blocs et sur les variables. Nous proposons ensuite des approches CSOM (Consensus SOM) et Rv-CSOM de recherche de consensus de cartes auto-organisées basées sur un système de poids déterminés à partir des partitions initiales. Enfin, la troisième partie présente une application de ces méthodes sur le jeu de données réelles de la campagne nationale logement (CNL) menée par l'OQAI afin de définir une typologie des logements au regard des thématiques : qualité de l'air intérieur, structure du bâtiment, composition des ménages et habitudes des occupantsThe multiplication of information source and the development of news technologies generates complex databases, often characterized by relatively high number of variables compared to individuals. In particular, in the environmental studies on the indoor air quality, the information's collection is done according to several thematic, yielding column partitioned or multi-block data set. However, in case of high dimensional data, classical clustering algorithms are not efficient to find clusters which may exist in subspaces of the original space. The goal of this work is to develop clustering algorithms adapted to high dimensional data sets with multi-block structure. The first part of the work shows the state of art on clustering methods. In the second part, three new methods of clustering: the subspace clustering method 2S-SOM (Soft Subspace-Self Organizing Map)is based on a modified cost function of the Self Organizing Maps method across a double system of weights on the blocks and the variables. Then we propose two approaches to find the consensus of self-organized maps CSOM (Consensus SOM) and Rv-CSOM based on weights determined from initial partitions. The last part presents an application of these methods on the OQAI data to determine a typology of dwellings relatively to the following topics: indoor air quality, dwellings structure, household characteristics and habits of the inhabitants
7
van, de Hoef Sebastian. "Extended Consensus Algorithms." Thesis, KTH, Reglerteknik, 2013. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-125809.
Full textAbstract:
An extension of the linear consensus protocol for agents moving in the plane is considered. For single integrator agents the use of a vector perpendicular to the standard consensus feedback leads to a large family of trajectories. If the new perpendicular term is applied only sustained oscillations are facilitated. For special congurations the form of the system trajectories is given in form of eigenvalues and {vectors of the system matrix. A proof is given that this additional term does not eect stability. On the other hand it is motivated that robustness against discrete implementation and switching topologies can be decreased. The control strategy is also applied to agents with double integrator dynamics. Stability can be archived with suciently high velocity feedback and the eect of this feedback on the system performance is further discussed. Using the results for single integrators a self{triggered consensus control strategy is proposed based on the assumption of bounded input magnitude of the other agents. Additional communication of the actual input leads to asymptotic convergence. By applying similar reasoning it is shown how local controllers at the agents can avoid circular regions in state{space while moving towards consensus.
8
DANCKAERT, PERRUCHOT ANNE. "Traitement informatique des autoradiographies de gels de sequences : conception et mise en oeuvre d'un systeme automatique d'interpretation d'autoradiographies, elaboration d'un algorithme de construction de la sequence consensus a partir de fragments." Paris 7, 1988. http://www.theses.fr/1988PA077045.
Full text
9
Córdova, Morales David Alexis. "Blockchain Application for Mesh and Mobile Ad Hoc Networks." Electronic Thesis or Diss., Sorbonne université, 2022. https://theses.hal.science/tel-03922843.
Full textAbstract:
La blockchain est une technologie qui permet de maintenir un unique registre d’information de façon décentralisé et distribué tout en garantissant la sécurité des données. Cette technologie, qui est à l’origine de la cryptomonnaie la plus populaire, le Bitcoin, est en train de changer la façon dont nous concevons les registres d’informations dans les systèmes distribués. En effet, l’ensemble des fonctions cryptographiques ainsi que la nature distribuée de la technologie font de la blockchain, un des outils les plus sécurisés de nos jours pour maintenir un registre de l’information. Les premières applications à avoir adopté cette technologie se trouvent dans le domaine des finances, où il est désormais possible de réaliser des transactions directement entre les utilisateurs sans passer par une autorité centrale. Néanmoins, d’autres domaines ont aussi suscité leurs intérêts pour cette technologie, telle que la médecine, pour le partage sécurisé des données médicales ; l’art et la musique, pour le suivi des droits d’auteur et des redevances ; la gouvernance, pour le vote sécurisé, l’IoT, etc. Or, pour bénéficier d’une telle technologie il est nécessaire de compter avec une haute fiabilité et connectivité, telle que fourni par l’Internet. Dans les réseaux mesh et ad hoc mobile, il est souvent nécessaire de déployer sa propre infrastructure et ses propres services là où l’infrastructure des opérateurs ne sont pas disponibles dus à la géographie du site ou à une situation d’exception comme est le cas de désastres naturels, zone de guerre ou le monitorat des zones protégées pour réaliser des missions déterminées. La dynamiste de ces réseaux rend difficile l’utilisation d’une blockchain pour maintenir un registre d’information. En effet, la mobilité des nœuds peut causer des partitions dans le réseau qui peuvent ou pas être désirées ; des nœuds peuvent apparaitre et disparaitre, les partitions peuvent se séparer ou se réunir en fonction de la mobilité des nœuds. Cela pose un problème pour une blockchain traditionnelle, car les partitions dans le réseau entraînent des forks (des chaînes concurrentes) qui sont souvent résolu en choisissant la chaîne la plus longue et en ignorant les autres chaînes concurrentes. Pour les cas d’utilisation des réseaux mesh et ad hoc mobile que nous cherchons à résoudre, les chaînes concurrentes construites par effet des partitions réseaux peuvent être considérés comme des chaînes légitimes portant des informations relatives à une partition réseau déterminé. Il est donc important d’inclure ces chaînes dans le registre d’information. Dans ce manuscrit de thèse, nous proposons le Blockgraph, une technologie semblable à la blockchain capable de faire face aux partitions réseaux pour les réseaux mesh et ad hoc mobiles. Le Blockgraph, prend la forme d’un graph orienté acyclique en fonction de la mobilité de nœuds et hérite de toutes les propriétés de sécurité de la blockchain. De plus, nous proposons C4M, un algorithme de consensus inspiré en RAFT qui a été adapté au Blockgraph et qui également est tolérant aux partitions du réseau. Pour valider nos solutions, nous avons d’abord implémenté le Blockgraph et C4M dans le simulateur à événements discrets, NS-3. Nous avons réalisé une première étude des performances de chaque système, puis nous avons implémenté le Blockgraph dans des vrais routeurs mesh à mode de proof-of-concept pour valider l’efficacité de notre solution. Finalement nous avons réalisé une étude de performances et présenté nos conclusionsBlockchain is a technology that maintains a single record of information in a decentralized and distributed manner while ensuring data security. This technology, which is behind the most popular cryptocurrency, Bitcoin, is changing the way we think about information records in distributed systems. Indeed, the cryptographic feature set and the distributed nature of the technology make blockchain one of the most secure tools available today for maintaining a record of information. The first applications to have adopted this technology are in the field of finance, where it is now possible to carry out transactions directly between users without going through a central authority. However, other fields have also shown interest in this technology, such as medicine, for the secure sharing of medical records; art and music, for the tracking of copyrights and royalties; governance, for secure voting, IoT, etc. However, to benefit from such technology it is necessary to count with high reliability and connectivity, as provided by the Internet. In mesh and mobile ad hoc networks, it is often necessary to deploy its own infrastructure and services where the infrastructure of operators are not available due to the geography of the site or to an exceptional situation as is the case of natural disasters, war zones or monitoring of protected areas to achieve specific missions. The dynamism of these networks makes it difficult to use a blockchain to maintain a record of information. Indeed, the mobility of nodes can cause partitions in the network that may or may not be desired; nodes can appear and disappear, partitions can split or reunite depending on the mobility of the nodes. This poses a problem for a traditional blockchain, as partitions in the network lead to forks (competing chains) that are often resolved by choosing the longest chain and ignoring other competing chains. For the use cases of mesh and mobile ad hoc networks that we seek to solve, the concurrent chains constructed by the effect of network partitions can be considered as legitimate chains carrying information related to a given network partition. It is therefore important to include these chains in the information register. In this thesis manuscript, we propose the Blockgraph, a blockchain-like technology capable of dealing with network partitions for mobile mesh and ad hoc networks. The Blockgraph, takes the form of a direct acyclic graph based on node mobility and inherits all the security properties of the blockchain. In addition, we propose C4M, a RAFT-based consensus algorithm that has been adapted to work with the Blockgraph and is also tolerant to network partitions. To validate our solutions, we first implemented the Blockgraph and C4M in the discrete event simulator, NS-3. We performed a first performance study of each system, then we implemented the Blockgraph in real proof-of-concept mesh routers to validate the effectiveness of our solution. Finally, we performed a performance study and presented our conclusions
10
Bechihi, Adel. "Joint design of control algorithms and communication protocols for Connected and Automated Vehicles." Electronic Thesis or Diss., université Paris-Saclay, 2023. http://www.theses.fr/2023UPAST203.
Full textAbstract:
Dans cette thèse, nous nous adressons le problème du contrôle de systèmes multi-agents connectés via des modèles réalistes de systèmes de communication. Nous traitons principalement les systèmes de véhicules connectés et automatisés (CAVs) communiquant via des systèmes de communication 5G qui permettent deux types de communication : la communication directe entre les nœuds, connue sous le nom de communication véhicule-à-véhicule (V2V), et la communication à travers l'infrastructure réseau, qui est la manière traditionnelle de communiquer dans les réseaux cellulaires.La thèse traite de trois problèmes : premièrement, nous analysons les propriétés de stabilité et de convergence de l'algorithme du consensus pour agents d'intégrateurs du premier ordre en utilisant un schéma d'accès multiple par répartition temporelle (TDMA) pour partager les ressources du réseau d'un canal de communication partagé. La stabilité exponentielle du système considéré est démontrée, et une borne explicite dépendant des paramètres du système de communication est fournie pour estimer la vitesse de convergence. Ensuite, nous abordons le problème du contrôle de formation d'un groupe de véhicules connectés dans un contexte de communication 5G. Nous proposons un algorithme d'allocation de ressources pour sélectionner les utilisateurs émetteurs afin d'atteindre la formation souhaitée tout en respectant les contraintes imposées par le couche de communication. Enfin, nous étudions les propriétés de stabilité des filtres de Kalman pour les systèmes hybrides, précisément, des systèmes avec une dynamique en temps continu observée à travers des mesures en temps discret. La stabilité d'entrée-à-état (ISS) est démontrée pour de tels systèmes en utilisant une fonction de Lyapunov appropriée. Ce résultat peut être considéré comme une première étape dans l'analyse de la robustesse du système global, car il permet de prendre en compte les effets des erreurs de communication sur la stabilité du système contrôléIn this thesis, we address the problem of control of multi-agent systems connected over realistic models of communication systems. We mainly focus on systems of connected and automated vehicles (CAVs) that communicate through a 5G communication system, which allows two types of communication: direct communication between nodes, known as Vehicle-to-Vehicle (V2V) communications, and communication through the network infrastructure, which is the traditional way of communication in cellular networks.The thesis discusses three problems: first, we analyze the stability and convergence properties of the consensus algorithm of first-order integrator agents using a time-division multiple access (TDMA) scheme to share the network resources of a broadcast shared communication channel. Exponential stability of the considered system is proved, and an explicit bound depending on the communication system parameters is provided to estimate the convergence rate. Second, we treat the problem of formation control of a float of connected vehicles in a 5G communication context. We propose a resource allocation algorithm to select the transmitting users to achieve the desired formation while satisfying the constraints imposed by the communication system. Finally, we study the stability properties of Kalman filters for hybrid systems, i.e., systems with continuous-time dynamics observed through discrete-time measurements. Input-to-state stability (ISS) is proved for such systems relying on an appropriate Lyapunov function. This result can be considered as a first step in the robustness analysis of the overall system since it allows to treat the effects of communication errors on the controlled system stability
11
Lauzier, Matthieu. "Conception et validation de plateformes de communication autour du corps humain, à l'échelle de l'individu et du groupe." Thesis, Lyon, INSA, 2015. http://www.theses.fr/2015ISAL0027/document.
Full textAbstract:
Depuis plusieurs années, bénéficiant de nombreuses évolutions technologiques, le domaine de l'instrumentation sans fil a conquis de nouveaux champs d'application, comme le suivi de paramètres physiologiques des personnes, par le développement des réseaux de capteurs sans fil autour du corps humain (BAN, pour Body Area Networks). Majoritairement orienté vers le domaine médical et l'amélioration des conditions de vie des patients, ce type de plate-forme s'est plus récemment étendu à d'autres activités, notamment aux loisirs et au sport. Selon le contexte applicatif, les hypothèses et les contraintes liées à ces réseaux peuvent être très variées, c'est pourquoi le développement de mécanismes de communication adaptés est nécessaire. Au cours de mes travaux de thèse, je me suis intéressé à la réalisation de plate-formes de collecte de données pour des applications sportives en situation de mobilité. Dans une première partie est abordée la collecte d'informations individuelles, pour laquelle nous présentons une preuve de concept en contexte sportif, avant d'apporter des éléments complémentaires à la modélisation des canaux des BAN et aux stratégies de communication pour la collecte individuelle. Ensuite, nous abordons la réflexion sur la collecte d'informations dans les réseaux denses et mobiles, en proposant des algorithmes distribués basés sur le consensus permettant d'identifier des groupes de façon dynamique, à petite et large échelle. Des réalisations pratiques à chaque étape de mes travaux de thèse permettent la validation des plate-formes développées, grâce à un ensemble conséquent de données collectées sur le terrain. L'analyse des données fournit également des éléments pour mieux caractériser les communications, notamment à large échelle, ce qui ouvre de nombreuses pistes quant à de futurs travaux. De plus, si un fort contexte applicatif est présent dans ces travaux, les méthodes d'analyse et les algorithmes développés sont valorisables et extensibles à d'autres domainesThe technological evolutions which have taken place for the last decades allowed the emergence of new application fields, such as the wireless monitoring of physiological parameters collected on the human body, with the development of Wireless Body Area Networks (WBANs, or BANs). Mostly dedicated to the medical domain and the improvement of the patients' comfort and safety, this kind of platforms more recently extended to other kinds of activities, such as sports and leisures. According to the applicative context, the hypotheses and constraints associated to these networks can vary drastically, yielding the necessity of developing adapted communication mechanisms. The works presented in this thesis have focused on the realization of data collection platforms for mobile sports applications. In a first part, we concentrate on the individual data collection, for which we give a proof of concept in the context of a Marathon race, before aiming at a better understanding of individual channel models and cooperative mechanisms for on-body data centralization. In a second part, we are interested in dense and mobile networks consisting in an important number of coexisting BANs. Our aim is to propose distributed algorithms based on consensus to allow dynamic group detection, with a variable scale. The validation of the approaches developed in this document is performed by practical implementations and experiments at each step of this work, thanks to an important amount of real world collected data. Through extended analyzes, we provide elements allowing to characterize the communication within mobile BANs, and particularly large scale networks. Although guided by the strong applicative context of live TV broadcast, these works and analysis methods don't lose in generality, and this challenging and original context opens a lot of perspectives
12
Bénéteau, Laurine. "Médians de graphes : algorithmes, connexité et axiomatique." Electronic Thesis or Diss., Aix-Marseille, 2022. http://www.theses.fr/2022AIXM0512.
Full textAbstract:
Le problème du médian est un des problèmes les plus étudiés en théorie des espaces métriques. Nous l'étudions dans les graphes médians d'un point de vue algorithmique. Nous présentons un algorithme linéaire basé sur un calcul rapide des classes de parallélisme des arêtes (les Thêta-classes) via un parcours en largeur particulier (LexBFS). Nous donnons également un algorithme linéaire pour le problème du médian dans les l1-complexes cubiques des graphes médians et dans les structures d'évènements.Ensuite, nous présentons une caractérisation des graphes aux médians connexes dans la p-ième puissance Gp du graphe et donnons une méthode polynomiale pour vérifier si un graphe est un graphe aux médians Gp-connexes, étendant un résultat de Bandelt et Chepoi (cas p=1). Nous utilisons cette caractérisation pour montrer que certaines classes de graphes sont G2-connexes, comme les graphes de Helly bipartis et les graphes pontés. Nous travaillons également sur l'aspect axiomatique en étudiant l'ABC-problème, qui consiste à déterminer les graphes (nommés ABC-graphes) dans lesquels la fonction médian est l'unique fonction consensus respectant trois axiomes simples (A) Anonymat, (B) Intervalle (Betweeness) et (C) Cohérence. Nous montrons que les graphes modulaires aux médians G2-connexes sont des ABC-graphes et définissons de nouveaux axiomes pour caractériser la fonction médian dans d'autres classes de graphes, comme les graphes aux médians connexes. Nous prouvons également que les graphes respectant la propriété d'appariement (qui sont des ABC-graphes) est une sous-classe propre des graphes de Helly bipartis et étudions la complexité de la reconnaissance de ces graphesThe median problem is one of the most investigated problem in metric graph theory. We will start by studying this problem in median graphs. We present a linear time algorithm based on the majority rule which characterize the median in median graphs and on a fast computation of the parallelism classes of the edges (the \Theta-classes) via LexBFS which is a particular breadth first search algorithm.We also provide linear time algorithms to compute the median set in the l_1-cube complexes of median graphs and in event structures. Then, we provide a characterization of the graphs with connected medians in the pth power of the graph and provide a polynomial method to check if a graph is a G^p-connected median graph, extending a result of Bandelt and Chepoi (case p=1). We use this characterization to prove that some important graph classes in metric graph theory have G2-connected medians, such as bipartite Helly graphs and bridged graphs. We will also studied the axiomatic aspect of the median function by investigating the ABC-problem, which determine the graphs (named ABC-graphs) in which the median function is the only consensus function verifying three simples axioms (A) Anonymat, (B) Betweeness and (C) Consistency. We show that modular graphs with G2-connected medians are ABC-graphs and define new axioms allowing us to characterize the median function on some graph classes. For example the graphs with connected medians (including Helly graphs). We also show that a known class of ABC-graphs (graphs satisfying the pairing property) is a proper subclass of bipartite Helly graphs and we investigate their recognition
13
Mårtensson, Christopher, and Linus Sjövall. "Consensus Algorithms - Flocking and Swarms." Thesis, KTH, Optimeringslära och systemteori, 2011. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-105773.
Full textAbstract:
An interesting eld of mathematics is the study of swarming and ocking. By using graph theory, one can describe a system of agents that transfer information between each other. With the help of certain algorithms it is possible to update the agent's information in order to reach consensus between the agents. If the information relates to the position, the velocity, or the acceleration of each agent, a behaviour similar to that of animals ocks or insect swarms is observed. Several other applications also exist, for example in systems of multiple robots when no central coordination is possible or simply not desired. In this paper dierent algorithms used to change the agent's information state will be studied and researched in order to determine the requirements under which the entire set of agents achieve consensus. First the case where agents receive information from a non-changing set of agents will be studied. Specically a particular algorithm, where each agent's information is determined by a linear function depending on the information state of all other agents from which information is received, will be considered. A requirement for this particular algorithm to reach consensus is that every agent both receives information and also sends information to every other agent, directly or indirectly through other agents. If all information transfers are weighed equally, the consensus achieved will be the average of all initial information states. Consensus can also be reached under looser conditions where there exists an agent that sends information to every other agent, directly or indirectly. The changes of the system's behaviour when one uses dierent consensus algorithms will be discussed, and computer simulations of these will be provided. An interesting case is where the information (often referring to location, velocity or acceleration) is received only from agents within a given distance and thus the information is received from dierent agents at dierent times. This results in nonlinear algorithms and mostly simulations and interpretations will be given. An observation is that whether consensus is achieved or not depends partially on the initial information states of the agents and the maximum distance for information transfer.Ett intressant omrade inom matematiken ar att beskriva fenomenet med ockar och svarmar. Med hjalp av grafteori kan man beskriva ett system av agenter som skickar information mellan varandra och med hjalp av algoritmer som beskriver hur varje agents informationen ska uppdateras sa att konsensus nas. Om informationen beskriver en position eller foryttning i rummet kan man observera ett beteende som liknar det hos djurockar eller insektssv armar. Manga andra tillampningsomraden nns ocksa, till exempel i system av robotar nar det saknas central styrning och internt beslutstagande ar onskvart. I denna rapport kommer olika algoritmer for att uppdatera en agents status att undersokas for att bestamma vilka krav som nns for att konsensus skall nas. Forsta delen kommer att behandla ett enklare fall dar varje agent tar emot information fran en oforanderlig uppsattning agenter. Specikt sa kommer en algoritm, dar en agents status bestams av en linjar funktion som beror pa statusen hos de agenter fran vilka information mottages, att studeras. Ett krav for att denna algoritm ska na konsensus ar att varje agent bade skickar och tar emot information fran samtliga ovriga agenter, direkt eller indirekt via andra agenter. Om alla informations overforingar vags lika sa kommer alla agenter na medelvardet av agenternas initialvarden. Konsensus kan ocksa nas under mindre restriktiva villkor, om det nns en agent som skickar information till alla andra noder (direkt eller indirekt). Forandringar av systemets beteende vid olika uppdateringsalgoritmer kommer att studeras och datorsimuleringar av dessa fenomen kommer att ges. Ett intressant fall ar da informationen (ofta position, hastighet eller acceleration) endast kan tas emot fran de agenter som nns inom ett givet avstand. darmed forandras den uppsattning agenter med vilka information overfors med tiden. Detta resulterar i olinjara algoritmer och framforallt kommer simulationer och tolkningar av dessa att ges. En observation ar att om konsensus nas eller inte beror starkt pa densiteten bland agenterna i utgangslaget samt det maximala avstand vid vilket informationsoverforing kan ske.
14
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.
Full textAbstract:
L’avènement de composants électroniques compacts et bon marché présage d’une diversification rapide d’applications dans lesquelles des agents autonomes en réseau travaillent à réaliser un objectif commun. Ces tâches complexes, en dépit de leur diversité, dépendent de la maîtrise d’un petit nombre de primitives de coordination, dont l’implémentation programmatique par des agents à faible puissance et capacité calculatoire constitue l’un des enjeux majeurs du développement de telles applications réparties. Parmi ces dernières, citons par exemple la coordination du mouvement de réseaux mobiles et véhiculaires, l’aggrégation et le traitement distribué de mesures relevées par des réseaux de capteurs, et le a répartition de charge en temps réel au sein d’un réseau fournissant un service à grande échelle. L’implémentation distribuée de telles primitives se doit de répondre à différentes contraintes, qui ne résultent pas toutes de la nature numérique des entités constitutives du réseau ; en conséquence, l’étude théorique de ces primitives s’applique à la modélisation de comportements complexes de systèmes étudiés par les sciences naturelles, tels que les mouvements collectifs animaliers ou le système nerveux.Cette monographie traite spécifiquement d’algorithmes distribués qui réalisent le calcul asymptotique de la moyenne de valeurs initialement détenues par les agents d’un réseau dont les liens de communication sont amenés à changer au cours du temps, ceci en l’absence de coordination centralisée. Ces algorithmes doivent être implémentables localement, en n’exploitant que l’information qui peut être collectée par les agents lors de leurs interactions sur le réseau, et en l’absence de mécanisme particulier pour marquer le départ, tel qu’un signal global ou un agent initiateur.Nous développons des algorithmes qui réalisent un tel consensus de moyenne sur des réseaux dynamiques présentant certaines propriétés locales. Ces algorithmes sont simples à décrire, légers à implémenter, et opèrent en temps polynomial en le nombre d’agents.Sur des réseaux présentant des interactions bidirectionnelles, nous fournissons un algorithme déterministe qui réalise le calcul asymptotique de la moyenne dès lors que le réseau ne se sépare jamais de façon permanente. Pour le cas plus général d’interactions asymétriques, nous présentons un algorithme Monte Carlo stabilisant qui est efficace en termes de complexité spatiale et opère en temps linéaire. Ce dernier algorithme admet une extension dont les exécutions terminent en tolérant un départ asynchrone des agents. Nos algorithmes sont à considérer en regard de résultats et de méthodes qui reposent sur une information globale fournie externalement aux agents, sur des hypothèses de brisure initiale de symétrie, ou qui exploitent une topologie particulière et ne se généralisent pas à des réseaux quelconques. Dans ce contexte, nous contribuons des algorithmes dont les conditions de validité sont purement locales dans le temps et l’espace : pour le modèle d’interactions bidirectionnelles, nous montrons que le calcul asymptotique de la moyenne est réalisable par des agents déterministes, là où pour le modèle général nous fournissons des algorithmes randomisés dont les performances asymptotiques sont bien meilleures que celles de protocoles à information complète et robustes aux départs asynchrones.Par-delà l’intérêt immédiat à l’obtention d’algorithmes efficaces implémentables, notre étude s’inscrit dans un effort de cartographie des limites que la localité des interactions impose aux applications répartiesCompact 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
15
Terelius, Håkan. "Consensus Algorithms in Dynamical Network Systems." Licentiate thesis, KTH, Reglerteknik, 2013. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-133613.
Full textAbstract:
Dynamical network systems are complex interconnected systems describing many real world problems. The current trend is to connect more and more systems together, and at the same time requiring continuous availability. To this end, it is crucial to understand the dynamic behaviors of networked systems.This thesis makes three contributions in this area. First, we study the important problem of gathering data that are distributed among the nodes in a network. Two specific tasks are considered: to estimate the size of the network, and to aggregate the distribution of local measurements generated by the nodes. We consider a framework where the nodes require anonymity, and restricted computational resources. We propose probabilistic algorithms with low resource requirements, that quickly generate arbitrarily accurate estimates. For dynamical networks, we improve the accuracy through a regularization term which captures the trade-off between the gathered data and a-priori assumptions on the dynamics. In the second part of this thesis, we consider a dynamical network system where one node is misbehaving due to a failure. We specifically seek robustness conditions that guarantee that the entire network system is still functional. The nodes' dynamics is governed by consensus updates, and we present thresholds on the interaction strengths that determines if the system will reach consensus, or if the system will diverge. Finally, a P2P network is utilized to improve a live-streaming media application. In particular, we study how an overlay network, constructed from simple preference functions, can be used to build efficient topologies that reduce both network latency and interruptions. We present necessary and sufficient convergence conditions, as well as convergence speed estimates, and demonstrate the improvements for a real P2P video streaming application.QC 20131111
16
Koung, Daravuth. "Cooperative navigation of a fleet of mobile robots." Electronic Thesis or Diss., Ecole centrale de Nantes, 2022. http://www.theses.fr/2022ECDN0044.
Full textAbstract:
L’intérêt pour l’intégration des systèmes multi-robots (MRS) dans les applications du monde réel augmente de plus en plus, notamment pour l’exécution de tâches complexes. Pour les tâches de transport de charges, différentes stratégies de manutention de charges ont été proposées telles que : la poussée seule, la mise en cage et la préhension. Dans cette thèse, nous souhaitons utiliser une stratégie de manipulation simple : placer l’objet à transporter au sommet d’un groupe de robots mobiles. Ainsi, cela nécessite un contrôle de formation rigide. Nous proposons deux algorithmes de formation. L’algorithme de consensus est l’un d’entre eux. Nous adaptons un contrôleur de flocking dynamique pour qu’il soit utilisé dans le système à un seul intégrateur, et nous proposons un système d’évitement d’obstacles qui peut empêcher le fractionnement tout en évitant les obstacles. Le deuxième contrôle de formation est basé sur l’optimisation quadratique hiérarchique (HQP). Le problème est décomposé en plusieurs objectifs de tâches : formation, navigation,évitement d’obstacles et limites de vitesse. Ces tâches sont représentées par des contraintes d’égalité et d’inégalité avec différentsniveaux de priorité, qui sont résolues séquentiellement par le HQP. Enfin, une étude sur les algorithmes d’allocation des tâches(Contract Net Protocol et Tabu Search) est menée afin de déterminer une solution appropriée pour l’allocation des tâches dans l’environnementindustrielThe interest in integrating multirobot systems (MRS) into real-world applications is increasing more and more, especially for performing complex tasks. For loadcarrying tasks, various load-handling strategies have been proposed such as: pushingonly, caging, and grasping. In this thesis, we aim to use a simple handling strategy: placing the carrying object on top of a group of wheeled mobile robots. Thus, it requires a rigid formation control. A consensus algorithm is one of the two formation controllers we apply to the system. We adapt a dynamic flocking controller to be used in the singleintegrator system, and we propose an obstacle avoidance that can prevent splitting while evading the obstacles. The second formation control is based on hierarchical quadratic programming (HQP). The problem is decomposed into multiple task objectives: formation, navigation, obstacle avoidance, velocity limits. These tasks are represented by equality and inequality constraints with different levels of priority, which are solved sequentially by the HQP. Lastly, a study on task allocation algorithms (Contract Net Protocol and Tabu Search) is carried out in order to determine an appropriate solution for allocating tasks in the industrial environment
17
Zhao, Yue. "Biopsy needles localization and tracking methods in 3d medical ultrasound with ROI-RANSAC-KALMAN." Thesis, Lyon, INSA, 2014. http://www.theses.fr/2014ISAL0015/document.
Full textAbstract:
Dans les examens médicaux et les actes de thérapie, les techniques minimalement invasives sont de plus en plus utilisées. Des instruments comme des aiguilles de biopsie, ou des électrodes sont utilisés pour extraire des échantillons de cellules ou pour effectuer des traitements. Afin de réduire les traumatismes et de faciliter le suivi visuelle de ces interventions, des systèmes d’assistance par imagerie médicale, comme par exemple, par l’échographie 2D, sont utilisés dans la procédure chirurgicale. Nous proposons d’utiliser l’échographie 3D pour faciliter la visualisation de l’aiguille, mais en raison de l’aspect bruité de l’image ultrasonore (US) et la grande quantité de données d’un volume 3D, il est difficile de trouver l’aiguille de biopsie avec précision et de suivre sa position en temps réel. Afin de résoudre les deux principaux problèmes ci-dessus, nous avons proposé une méthode basée sur un algorithme RANSAC et un filtre de Kalman. De même l’étude est limitée à une région d’intérêt (ROI) pour obtenir une localisation robuste et le suivi de la position de l’aiguille de biopsie en temps réel. La méthode ROI-RK se compose de deux étapes: l’étape d’initialisation et l’étape de suivi. Dans la première étape, une stratégie d’initialisation d’une ROI en utilisant le filtrage de ligne à base de matrice de Hesse est mise en œuvre. Cette étape permet de réduire efficacement le bruit de granularité du volume US, et de renforcer les structures linéaires telles que des aiguilles de biopsie. Dans la deuxième étape, après l’initialisation de la ROI, un cycle de suivi commence. L’algorithme RK localise et suit l’aiguille de biopsie dans une situation dynamique. L’algorithme RANSAC est utilisé pour estimer la position des micro-outils et le filtrage de Kalman permet de mettre à jour la région d’intérêt et de corriger la localisation de l’aiguille. Une stratégie d’estimation de mouvement est également appliquée pour estimer la vitesse d’insertion de l’aiguille de biopsie. Des volumes 3D US avec un fond inhomogène ont été simulés pour vérifier les performances de la méthode ROI-RK. La méthode a été testée dans des conditions variables, telles que l’orientation d’insertion de l’aiguille par rapport à l’axe de la sonde et le niveau de contraste (CR). La précision de la localisation est de moins de 1 mm, quelle que soit la direction d’insertion de l’aiguille. Ce n’est que lorsque le CR est très faible que la méthode proposée peut échouer dans le suivi d’une structure incomplète de l’aiguille. Une autre méthode, utilisant l’algorithme RANSAC avec apprentissage automatique a été proposée. Cette méthode vise à classer les voxels en se basant non seulement sur l’intensité, mais aussi sur les caractéristiques de la structure de l’aiguille de biopsie. Les résultats des simulations montrent que l’algorithme RANSAC avec apprentissage automatique peut séparer les voxels de l’aiguille et les voxels de tissu de fond avec un CR faibleIn medical examinations and surgeries, minimally invasive technologies are getting used more and more often. Some specially designed surgical instruments, like biopsy needles, or electrodes are operated by radiologists or robotic systems and inserted in human’s body for extracting cell samples or delivering radiation therapy. To reduce the risk of tissue injury and facilitate the visual tracking, some medical vision assistance systems, as for example, ultrasound (US) systems can be used during the surgical procedure. We have proposed to use the 3D US to facilitate the visualization of the biopsy needle, however, due to the strong speckle noise of US images and the large calculation load involved as soon as 3D data are involved, it is a challenge to locate the biopsy needle accurately and to track its position in real time in 3D US. In order to solve the two main problems above, we propose a method based on the RANSAC algorithm and Kalman filter. In this method, a region of interest (ROI) has been limited to robustly localize and track the position of the biopsy needle in real time. The ROI-RK method consists of two steps: the initialization step and the tracking step. In the first step, a ROI initialization strategy using Hessian based line filter measurement is implemented. This step can efficiently reduce the speckle noise of the ultrasound volume, and enhance line-like structures as biopsy needles. In the second step, after the ROI is initialized, a tracking loop begins. The RK algorithm can robustly localize and track the biopsy needles in a dynamic situation. The RANSAC algorithm is used to estimate the position of the micro-tools and the Kalman filter helps to update the ROI and auto-correct the needle localization result. Because the ROI-RK method is involved in a dynamic situation, a motion estimation strategy is also implemented to estimate the insertion speed of the biopsy needle. 3D US volumes with inhomogeneous background have been simulated to evaluate the performance of the ROI-RK method. The method has been tested under different conditions, such as insertion orientations angles, and contrast ratio (CR). The localization accuracy is within 1 mm no matter what the insertion direction is. Only when the CR is very low, the proposed method could fail to track because of an incomplete ultrasound imaging of the needle. Another methodology, i.e. RANSAC with machine learning (ML) algorithm has been presented. This method aims at classifying the voxels not only depending on their intensities, but also using some structure features of the biopsy needle. The simulation results show that the RANSAC with ML algorithm can separate the needle voxels and background tissue voxels with low CR
18
Capdevielle, Claire. "Étude de la complexité des implémentations d'objets concurrents, sans attente, abandonnables et/ou solo-rapides." Thesis, Bordeaux, 2016. http://www.theses.fr/2016BORD0194/document.
Full textAbstract:
Dans un ordinateur multiprocesseur, lors de l'accès à la mémoire partagée, il faut synchroniser les entités de calcul (processus). Cela peut se faire à l'aide de verrous, mais des problèmes se posent (par exemple interblocages, mauvaise tolérance aux pannes). On s'est intéressé à l'implémentation d'abstractions (consensus et construction universelle) qui peuvent faciliter la programmation concurrente sans attente, sans utiliser de verrous mais basés sur des lectures/écritures atomiques (LEA). L'usage exclusive des LEA ne permet pas de réaliser un consensus sans attente. Néanmoins, autoriser l'usage de primitives offrant une puissance de synchronisation plus forte que des LEA, mais coûteuse en temps de calcul, le permet. Nous nous sommes donc intéressés dans cette thèse à des programmes qui limitent l'usage de ces primitives aux seules situations où les processus sont en concurrence, ces programmes sont dit solo-rapides. Une autre piste étudiée est de permettre à l'objet, lorsqu'il y a de la concurrence, de retourner une réponse spéciale "abandon" qui signifie l'abandon des calculs en cours. Ces objets sont dit abandonnables. D'une part, nous donnons des implémentations d'objets concurrents sans attente, abandonnables et/ou solo-rapides. Pour cela, nous proposons une construction universelle qui assure à l'objet implémenté d'être abandonnable et solo-rapide ; nous avons réalisés des algorithmes de consensus solo-rapides et des algorithmes de consensus abandonnable. D'autre part nous étudions la complexité en espace de ces implémentations en proposant des bornes inférieures sur l'implémentation des objets abandonnables et sur le consensusIn multiprocessor computer, synchronizations between processes are needed for the access to the shared memory. Usually this is done by using locks, but there are some issues as deadlocks or lack of fault-tolerance. We are interested in implementing abstractions (as consensus or universal construction) which ease the programming of wait-free concurrent objects, without using lock but based on atomic Read/Write operations (ARW). Only using the ARW does not permit to implement wait-free consensus. The use of primitives which offer a higher power of synchronization than the ARW is needed. But these primitives are more expensive in computing time. Therefore, we are interested in this thesis in the design of algorithms which restrict the use of these primitives only to the cases where processes are in contention. These algorithms are said solo-fast. Another direction is to allow the object to abort the computation in progress - and to return a special response "abort" - when there is contention. These objects are named abortable. On the one hand we give wait-free, abortable and/or solo-fast concurrent object implementations. Indeed we proposed a universal construction which ensure to the implemented object to be abortable and solo-fast. We have also realized solo-fast consensus algorithms and abortable consensus algorithms. On the other hand, we study the space complexity of these implementations : we prove space lower bound on the implementation of abortable object and consensus
19
Nicolas, François. "Alignement, séquence, consensus, recherche de similarités : complexité et approximabilité." Montpellier 2, 2005. http://www.theses.fr/2005MON20179.
Full text
20
Guillemot, Sylvain. "Approches combinatoires pour le consensus d'arbres et de séquences." Phd thesis, Montpellier 2, 2008. http://www.theses.fr/2008MON20234.
Full textAbstract:
Cette thèse étudie d'un point de vue algorithmique diverses méthodes de consensus portant sur des collections d'objets étiquetés. Les problèmes étudiés impliquent des objets étiquetés sans répétition d'étiquettes ; ces objets peuvent être des arbres enracinés ou des séquences, avec des applications à la bioinformatique. Ainsi, les problèmes sur les arbres considérés dans cette thèse peuvent trouver des applications pour l'estimation de congruence entre phylogénies, pour la construction de superarbres, et pour l'identification de transferts horizontaux de gènes. Pour leur part, les problèmes sur les séquences considérés dans cette thèse ont des applications potentielles pour le calcul de distance génomique basé sur les ordres de gènes. De manière générale, ce travail met à profit les théories de la complexité paramétrique et de l'approximabilité pour obtenir des algorithmes et des résultats de difficulté pour les problèmes étudiés.
21
Wu, Li-Fen. "Fault-tolerant distributed algorithms for consensus and termination detection /." The Ohio State University, 1994. http://rave.ohiolink.edu/etdc/view?acc_num=osu1487858417981925.
Full text
22
Arun, Balaji. "A Low-latency Consensus Algorithm for Geographically Distributed Systems." Thesis, Virginia Tech, 2017. http://hdl.handle.net/10919/79945.
Full textAbstract:
This thesis presents Caesar, a novel multi-leader Generalized Consensus protocol for geographically replicated systems. Caesar is able to achieve near-perfect availability, provide high performance - low latency and high throughput compared to the existing state-of-the- art, and tolerate replica failures. Recently, a number of state-of-the-art consensus protocols that implement the Generalized Consensus definition have been proposed. However, the major limitation of these existing approaches is the significant performance degradation when application workload produces conflicting requests. Caesar's main goal is to overcome this limitation by changing the way a fast decision is taken: its ordering protocol does not reject a fast decision for a client request if a quorum of nodes reply with different dependency sets for that request. It only switches to a slow decision if there is no chance to agree on the proposed order for that request. Caesar is able to achieve this using a combination of wait condition and logical time stamping. The effectiveness of Caesar is demonstrated through an evaluation study performed on Amazon's EC2 infrastructure using 5 geo-replicated sites. Caesar outperforms other multi-leader (e.g., EPaxos) competitors by as much as 1.7x in presence of 30% conflicting requests, and single-leader (e.g., Multi-Paxos) by as much as 3.5x. The protocol is also resistant to heavy client loads unlike existing protocols.Master of Science
23
Guillemot, Sylvain. "Approches Combinatoires pour le Consensus d'Arbres et de Séquences." Phd thesis, Université Montpellier II - Sciences et Techniques du Languedoc, 2008. http://tel.archives-ouvertes.fr/tel-00401456.
Full textAbstract:
Cette thèse étudie d'un point de vue algorithmique diverses méthodes de consensus portant sur des collections d'objets étiquetés. Les problèmes étudiés impliquent des objets étiquetés sans répétition d'étiquettes ; ces objets peuvent être des arbres enracinés ou des séquences, avec des applications à la bioinformatique. Ainsi, les problèmes sur les arbres considérés dans cette thèse peuvent trouver des applications pour l'estimation de congruence entre phylogénies, pour la construction de superarbres, et pour l'identification de transferts horizontaux de gènes. Pour leur part, les problèmes sur les séquences considérés dans cette thèse ont des applications potentielles pour le calcul de distance génomique basé sur les ordres de gènes. De manière générale, ce travail met à profit les théories de la complexité paramétrique et de l'approximabilité pour obtenir des algorithmes et des résultats de difficulté pour les problèmes étudiés.
24
Yang, Bo. "Analyses bioinformatiques et classements consensus pour les données biologiques à haut débit." Thesis, Paris 11, 2014. http://www.theses.fr/2014PA112250/document.
Full textAbstract:
Cette thèse aborde deux problèmes relatifs à l’analyse et au traitement des données biologiques à haut débit: le premier touche l’analyse bioinformatique des génomes à grande échelle, le deuxième est consacré au développement d’algorithmes pour le problème de la recherche d’un classement consensus de plusieurs classements.L’épissage des ARN est un processus cellulaire qui modifie un ARN pré-messager en en supprimant les introns et en raboutant les exons. L’hétérodimère U2AF a été très étudié pour son rôle dans processus d’épissage lorsqu’il se fixe sur des sites d’épissage fonctionnels. Cependant beaucoup de problèmes critiques restent en suspens, notamment l’impact fonctionnel des mutations de ces sites associées à des cancers. Par une analyse des interactions U2AF-ARN à l’échelle génomique, nous avons déterminé qu’U2AF a la capacité de reconnaître environ 88% des sites d’épissage fonctionnels dans le génome humain. Cependant on trouve de très nombreux autres sites de fixation d’U2AF dans le génome. Nos analyses suggèrent que certains de ces sites sont impliqués dans un processus de régulation de l’épissage alternatif. En utilisant une approche d’apprentissage automatique, nous avons développé une méthode de prédiction des sites de fixation d’UA2F, dont les résultats sont en accord avec notre modèle de régulation. Ces résultats permettent de mieux comprendre la fonction d’U2AF et les mécanismes de régulation dans lesquels elle intervient.Le classement des données biologiques est une nécessité cruciale. Nous nous sommes intéressés au problème du calcul d’un classement consensus de plusieurs classements de données, dans lesquels des égalités (ex-aequo) peuvent être présentes. Plus précisément, il s’agit de trouver un classement dont la somme des distances aux classements donnés en entrée est minimale. La mesure de distance utilisée le plus fréquemment pour ce problème est la distance de Kendall-tau généralisée. Or, il a été montré que, pour cette distance, le problème du consensus est NP-difficile dès lors qu’il y a plus de quatre classements en entrée. Nous proposons pour le résoudre une heuristique qui est une nouvelle variante d’algorithme à pivot. Cette heuristique, appelée Consistent-pivot, s’avère à la fois plus précise et plus rapide que les algorithmes à pivot qui avaient été proposés auparavantIt is thought to be more and more important to solve biological questions using Bioinformatics approaches in the post-genomic era. This thesis focuses on two problems related to high troughput data: bioinformatics analysis at a large scale, and development of algorithms of consensus ranking. In molecular biology and genetics, RNA splicing is a modification of the nascent pre-messenger RNA (pre-mRNA) transcript in which introns are removed and exons are joined. The U2AF heterodimer has been well studied for its role in defining functional 3’ splice sites in pre-mRNA splicing, but multiple critical problems are still outstanding, including the functional impact of their cancer-associated mutations. Through genome-wide analysis of U2AF-RNA interactions, we report that U2AF has the capacity to define ~88% of functional 3’ splice sites in the human genome. Numerous U2AF binding events also occur in other genomic locations, and metagene and minigene analysis suggests that upstream intronic binding events interfere with the immediate downstream 3’ splice site associated with either the alternative exon to cause exon skipping or competing constitutive exon to induce inclusion of the alternative exon. We further build up a U2AF65 scoring scheme for predicting its target sites based on the high throughput sequencing data using a Maximum Entropy machine learning method, and the scores on the up and down regulated cases are consistent with our regulation model. These findings reveal the genomic function and regulatory mechanism of U2AF, which facilitates us understanding those associated diseases.Ranking biological data is a crucial need. Instead of developing new ranking methods, Cohen-Boulakia and her colleagues proposed to generate a consensus ranking to highlight the common points of a set of rankings while minimizing their disagreements to combat the noise and error for biological data. However, it is a NP-hard questioneven for only four rankings based on the Kendall-tau distance. In this thesis, we propose a new variant of pivot algorithms named as Consistent-Pivot. It uses a new strategy of pivot selection and other elements assignment, which performs better both on computation time and accuracy than previous pivot algorithms
25
Bhattacharya, Shaondip. "Multi-agent System Distributed Sensor Fusion Algorithms." Thesis, Luleå tekniska universitet, Rymdteknik, 2017. http://urn.kb.se/resolve?urn=urn:nbn:se:ltu:diva-65839.
Full textAbstract:
The concept of consensus filters for sensor fusion is not an entirely new proposition but one with an internally implemented Bayesian fusion is. This work documents a novel state update algorithm for sensor fusion which works using the principle of Bayesian fusion of data with variance implemented on a single integrator consensus algorithm. Comparative demonstrations of how consensus over a pinning network is reached are presented along with a weighted Bayesian Luenberger type observer and a ’Consensus on estimates’ algorithm. This type of a filter is something that is novel and has not been encountered in previous literature related to this topic to the best of our knowledge. In this work, we also extend the proof for a distributed Luenberger type observer design to include the case where the network being considered is a strongly connected digraph.
26
Gramm, Jens. "Fixed-parameter algorithms for the consensus analysis of genomic data." [S.l. : s.n.], 2003. http://deposit.ddb.de/cgi-bin/dokserv?idn=973911271.
Full text
27
Johansson, Björn, T. Keviczky, Mikael Johansson, and Karl Henrik Johansson. "Subgradient methods and consensus algorithms for solving convex optimization problems." KTH, Reglerteknik, 2008. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-80707.
Full textAbstract:
In this paper we propose a subgradient method for solving coupled optimization problems in a distributed way given restrictions on the communication topology. The iterative procedure maintains local variables at each node and relies on local subgradient updates in combination with a consensus process. The local subgradient steps are applied simultaneously as opposed to the standard sequential or cyclic procedure. We study convergence properties of the proposed scheme using results from consensus theory and approximate subgradient methods. The framework is illustrated on an optimal distributed finite-time rendezvous problem.© 2008 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.
QC 20120214
28
Pan, Guodong, and 潘国栋. "Motion segmentation by adaptive mode seeking and clustering consensus." Thesis, The University of Hong Kong (Pokfulam, Hong Kong), 2012. http://hub.hku.hk/bib/B48199369.
Full textAbstract:
The task of multi-body motion segmentation refers to segmenting feature trajectories
in a sequence of images according to their 3D motion affinity without
knowing the number of motions in advance. It is critical for understanding and
reconstructing a dynamic scene. This problem essentially consists of two subproblems,
segmenting features and detecting the number of motions. While the
state-of-the-art LBF algorithm achieves segmentation accuracy as high as 96.5%,
it is still disturbed by a phenomenon called over-locality. A novel mode seeking
algorithm with an adaptive distance measure is proposed to avoid this problem,
and improves the accuracy to 98.1%. The LBF algorithm is incapable of detecting
the number of motions itself. A randomized version of the mode seeking algorithm
is presented, which could detect the number as well as preserve satisfactory
segmentation accuracy. To detect the number of motions, a kernel optimization
method locates it via kernel alignment. However, it suffers from over-locality and
over-detects the number of motions. An intersection measure and two mutual
information measures are presented to solve this problem. Using these measures,
the proposed clustering consensus framework recasts the motion number detection
problem to a clustering consensus problem. It extends the kernel optimization
method from two-clustering consensus to multiple-clustering consensus. A large
number of experiments and comparisons have been done, and convincing results
are obtained.published_or_final_version
Computer Science
Doctoral
Doctor of Philosophy
29
Silva, Pereira Silvana. "Distributed consensus algorithms for wireless sensor networks: convergence analysis and optimization." Doctoral thesis, Universitat Politècnica de Catalunya, 2012. http://hdl.handle.net/10803/131997.
Full textAbstract:
Wireless sensor networks are developed to monitor areas of interest with the purpose of estimating physical parameters or/and detecting emergency events in a variety of military and civil applications. A wireless sensor network can be seen as a distributed computer, where spatially deployed sensor nodes are in charge of gathering measurements from the environment to compute a given function. The research areas for wireless sensor networks extend from the design of small, reliable hardware to low-complexity algorithms and energy saving communication protocols.
Distributed consensus algorithms are low-complexity iterative schemes that have received increased attention in different fields due to a wide range of applications, where neighboring nodes communicate locally to compute the average of an initial set of measurements. Energy is a scarce resource in wireless sensor networks and therefore, the convergence of consensus algorithms, characterized by the total number of iterations until reaching a steady-state value, is an important topic of study.
This PhD thesis addresses the problem of convergence and optimization of distributed consensus algorithms for the estimation of parameters in wireless sensor networks. The impact of quantization noise in the convergence is studied in networks with fixed topologies and symmetric communication links. In particular, a new scheme including quantization is proposed, whose mean square error with respect to the average consensus converges. The limit of the mean square error admits a closed-form expression and an upper bound for this limit depending on general network parameters is also derived.
The convergence of consensus algorithms in networks with random topology is studied focusing particularly on convergence in expectation, mean square convergence and almost sure convergence. Closed-form expressions useful to minimize the convergence time of the algorithm are derived from the analysis.
Regarding random networks with asymmetric links, closed-form expressions are provided for the mean square error of the state assuming equally probable uniform link weights, and mean square convergence to the statistical mean of the initial measurements is shown. Moreover, an upper bound for the mean square error is derived for the case of different probabilities of connection for the links, and a practical scheme with randomized transmission power exhibiting an improved performance in terms of energy consumption with respect to a fixed network with the same consumption on average is proposed. The mean square error expressions derived provide a means to characterize the deviation of the state vector with respect to the initial average when the instantaneous links are asymmetric.
A useful criterion to minimize the convergence time in random networks with spatially correlated links is considered, establishing a sufficient condition for almost sure convergence to the consensus space. This criterion, valid also for topologies with spatially independent links, is based on the spectral radius of a positive semidefinite matrix for which we derive closed-form expressions assuming uniform link weights. The minimization of this spectral radius is a convex optimization problem and therefore, the optimum link weights minimizing the convergence time can be computed efficiently. The expressions derived are general and apply not only to random networks with instantaneous directed topologies but also to random networks with instantaneous undirected topologies. Furthermore, the general expressions can be particularized to obtain known protocols found in literature, showing that they can be seen as particular cases of the expressions derived in this thesis.Las redes de sensores inalámbricos se utilizan para monitorizar zonas de interés con el propósito final de estimar parámetros físicos y/o detectar situaciones de emergencia en gran variedad de aplicaciones militares y civiles. Una red de sensores inalámbricos puede ser considerada como un método de computación distribuido, donde nodos provistos de sensores toman medidas del entorno para calcular una función que depende de éstas. Las áreas de investigación comprenden desde el diseño de dispositivos hardware pequeños y fiables hasta algoritmos de baja complejidad o protocolos de comunicación de bajo consumo energético. Los algoritmos de consenso distribuidos son esquemas iterativos de baja complejidad que han suscitado mucha atención en diferentes campos debido a su gran espectro de aplicaciones, en los que nodos vecinos se comunican para calcular el promedio de un conjunto de medidas iniciales de la red. Dado que la energía es un recurso escaso en redes de sensores inalámbricos, la convergencia de dichos algoritmos de consenso, caracterizada por el número total de iteraciones hasta alcanzar un valor estacionario, es un importante tema de estudio. Esta tesis doctoral aborda problemas de convergencia y optimización de algoritmos de consenso distribuidos para la estimación de parámetros en redes de sensores inalámbricos. El impacto del ruido de cuantización en la convergencia se estudia en redes con topología fija y enlaces de comunicación simétricos. En particular, se propone un nuevo esquema que incluye el proceso de cuantización y se demuestra que el error cuadrático medio respecto del promedio inicial converge. Igualmente, se obtiene una expresión cerrada del límite del error cuadrático medio, y una cota superior para este límite que depende únicamente de parámetros generales de la red. La convergencia de los algoritmos de consenso en redes con topología aleatoria se estudia prestando especial atención a la convergencia en valor esperado, la convergencia en media cuadrática y la convergencia casi segura, y a partir del análisis se derivan expresiones cerradas útiles para minimizar el tiempo de convergencia. Para redes aleatorias con enlaces asimétricos, se obtienen expresiones cerradas del error cuadrático medio del estado suponiendo enlaces con probabilidad idéntica y con pesos uniformes, y se demuestra la convergencia en media cuadrática al promedio estadístico de las medidas iniciales. Se deduce una cota superior para el error cuadrático medio para el caso de enlaces con probabilidades de conexión diferentes y se propone, además, un esquema práctico con potencias de transmisión aleatorias, que mejora el rendimiento en términos de consumo de energía con respecto a una red fija. Las expresiones para el error cuadrático medio proporcionan una forma de caracterizar la desviación del vector de estado con respecto del promedio inicial cuando los enlaces instantáneos son asimétricos. Con el fin de minimizar el tiempo de convergencia en redes aleatorias con enlaces correlados espacialmente, se considera un criterio que establece una condición suficiente que garantiza la convergencia casi segura al espacio de consenso. Este criterio, que también es válido para topologías con enlaces espacialmente independientes, utiliza el radio espectral de una matriz semidefinida positiva para la cual se obtienen expresiones cerradas suponiendo enlaces con pesos uniformes. La minimización de dicho radio espectral es un problema de optimización convexa y, por lo tanto, el valor de los pesos óptimos puede calcularse de forma eficiente. Las expresiones obtenidas son generales y aplican no sólo para redes aleatorias con topologías dirigidas, sino también para redes aleatorias con topologías no dirigidas. Además, las expresiones generales pueden ser particularizadas para obtener protocolos conocidos en la literatura, demostrando que éstos últimos pueden ser considerados como casos particulares de las expresiones proporcionadas en esta tesis.
30
Liu, Yang. "Distributed Algorithms for Consensus and Formation Control in Scalable Robotic Swarms." Case Western Reserve University School of Graduate Studies / OhioLINK, 2018. http://rave.ohiolink.edu/etdc/view?acc_num=case1528376075213318.
Full text
31
FRANCESCHELLI, MAURO. "Consensus Algorithms for Estimation and Discrete Averaging in Networked Control Systems." Doctoral thesis, Università degli Studi di Cagliari, 2011. http://hdl.handle.net/11584/266297.
Full textAbstract:
In this thesis several topics on consensus and gossip algorithms for multi-agent systems are addressed. An agent is a dynamical system that can be fully described by a state-space representation of its dynamics. A multi-agent system is a network of agents whose pattern of interactions or couplings is described by a graph. Consensus problems in multi-agent systems consist in the study of local interaction rules between the agents such that as global emergent behavior the network converges to the so called "consensus" or "agreement" state where the value of each agent's state is the same and it is possibly a function of the initial network state, for instance the average. A consensus algorithm is thus a set of local interaction rules that solve the consensus problem under some assumptions on the network topology.
A gossip algorithm is a set of local state update rules between the agents that, disregarding their objective, are supposed to be implemented in a totally asynchronous way between pairs of neighboring agents, thus resembling the act of "gossiping" in a crowd of people.
In this thesis several algorithms based on gossip that solve the consensus and other related problems are presented.
In the �first part, several solutions to the consensus problem based on gossip under different sets of assumptions are proposed. In the fi�rst case, it is assumed that the state of the agents is discretized and represents a collection of tasks of different size. In the second case,
under the same discretization assumptions of the �rst case, it is assumed that the network is represented by a Hamiltonian graph and it is shown how under this assumption the convergence speed can be improved. In the third case, a solution for the consensus problem for networks represented by arbitrary strongly connected directed graphs is proposed, assuming that the state of the agents is a real number.
In the fourth case, a coordinate-free consensus algorithm based on gossip is designed and applied to a network of vehicles able to sense the relative distance between each other but with no access to absolute position information or to a common coordinate system. The proposed algorithm is then used to build in a decentralized way a common reference frame for the network of vehicles.
In the second part, a novel local interaction rule based on the consensus equation is proposed together with an algorithm to estimate in a decentralized way the spectrum of the Laplacian matrix that encodes the network topology. As emergent behavior, each agent's state oscillates only at frequencies corresponding to the eigenvalues of the
Laplacian matrix thus mapping the spectrum estimation problem into a signal processing problem solvable using the Fourier Transform. It is further shown that the constant component of the emergent behavior in the frequency domain solves the consensus on the average problem.
The spectrum estimation algorithm is then applied to leader-follower networks of mobile vehicles to infer in a decentralized way properties such as controllability, osservability and other topological features of
the network such as its topology.
Finally, a fault detection and recovery technique for sensor networks based on the so called motion-probes is presented to address the inherent lack of robustness against outlier agents in networks implementing
consensus algorithms to solve the distributed averaging problem.
32
Kueh, Reng Yi. "Evaluating Byzantine-Based Blockchain Consensus Algorithms for Sarawak’s Digitalized Pepper Value Chain." Thesis, Curtin University, 2022. http://hdl.handle.net/20.500.11937/88810.
Full textAbstract:
A chosen network structure of Practical Byzantine Fault Tolerance (PBFT), a Byzantine-based consensus algorithm, is proposed to minimize some of the identified pain points faced by the pepper stakeholders. Byzantine-based consensus algorithms are used to achieve the same agreement on a single data value, including transactions and block state, and to maintain system continuity even when several nodes have failed to respond or transmit inconsistent messages in the blockchain network.
33
Pedroncelli, Giovanni. "Distributed Discrete Consensus Algorithms: Theory and Applications for the Task Assignment Problem." Doctoral thesis, Università degli studi di Trieste, 2015. http://hdl.handle.net/10077/10975.
Full textAbstract:
2013/2014Distributed computation paradigms belong to a research field of increasing interest. Using these algorithms will allow to exploit the capabilities of large scale networks and systems in the near future. Relevant information for the resolution of a problem are distributed among a network of agents with limited memory and computation capability; the problem is solved only by means of local computation and message exchange between neighbour agents. In this thesis we consider the multi-agent assignment problem dealt with distributed computation: a network of agents has to cooperatively negotiate the assignment of a number of tasks by applying a distributed discrete consensus algorithm which defines how the agents exchange information. Consensus algorithms are dealt with always more frequently in the related scientific literature. Therefore, in the first chapter of this thesis we present a related literature review containing some of the most interesting works concerning distributed computation and, in particular, distributed consensus algorithms: some of these works deal with the theory of consensus algorithms, in particular convergence properties, others deal with applications of these algorithms. In the second chapter the main contribution of this thesis is presented: aniterative distributed discrete consensus algorithm based on the resolution of local linear integer optimization problems (L-ILPs) to be used for the multi-agent assignment problem. The algorithm is characterized by theorems proving convergence to a final solution and the value of the convergence time expressed in terms of number of iterations. The chapter is concluded by a performance analysis by means of the results of simulations performed with Matlab software. All the results are presented considering two different network topologies in order to model two different real life scenarios for the connection among agents. The third chapter presents an interesting application of the proposed algorithm: a network of charging stations (considered as agents) has to reach a consensus on the assignment of a number of Electric Vehicles (EVs) requiring to be recharged. In this application the algorithm proposed in the previous chapter undergoes several modifications in order to model effectively this case: considering the inter-arrival times of vehicles to a charging station, a non-linear element appears in the objective function and therefore a novel algorithm to be performed before the assignment algorithm is presented; this algorithm defines the order in which the assigned vehicles have to reach a charging station. Moreover, a communication protocol is proposed by which charging stations and vehicles can communicate and exchange information also allowing charging stations to send to each assigned vehicle the maximum waiting time which can pass before a vehicle loses its right to be recharged. The chapter ends with an example of application of the rivisited assignment algorithm. In the fourth and last chapter, we present an application in an industrial environment: a network of Autonomous Guided Vehicles (AGVs) in a warehouse modeled as a graph has to perform the distributed discrete consensus algorithm in order to assign themselves a set of destinations in which some tasks are located. This application deals not only with the task assignment problem but also with the following destination reaching problem: therefore a distributed coordination algorithm is proposed which allows the AGVs to move into the warehouse avoiding collisions and deadlock. An example of the control strategy application involving both the assignment and coordination algorithms concludes this chapter.
XXVII Ciclo
1986
34
Nguyen, Thanh-Khoa. "Image segmentation and extraction based on pixel communities." Thesis, La Rochelle, 2019. http://www.theses.fr/2019LAROS035.
Full textAbstract:
La segmentation d’images est devenue une tâche indispensable largement utilisée dans plusieurs applications de traitement d’images, notamment la détection d’objets, le suivi d’objets, l’assistance automatique à la conduite et les systèmes de contrôle du trafic, etc. La littérature regorge d’algorithmes permettant de réaliser des tâches de segmentation d’images. Ces méthodes peuvent être divisées en groupes principaux en fonction des approches sous-jacentes, telles que la segmentation d'images basée sur les régions, la classification basée sur les caractéristiques de l'image, les approches basées sur les graphes et la segmentation d'images basée sur les réseaux de neurones. Récemment, l'analyse de réseaux sociaux a proposé de nombreuses théories et méthodologies. En particulier, des techniques de segmentation d’images basées sur des algorithmes de détection de communautés ont été proposées et forment une famille d'approches visible dans la littérature. Dans cette thèse, nous proposons un nouveau cadre pour la segmentation d'images basée sur la détection de communautés. Si l'idée de base d'utiliser le domaine de l'analyse des réseaux sociaux dans la segmentation de l'image est tout à fait séduisante, la manière dont les algorithmes de détection de communautés peuvent être appliqués efficacement à la segmentation d'images est un sujet qui continue à interroger. L’apport de cette thèse est un effort pour construire de manière pertinente des meilleurs réseaux complexes en fonction de l'application, des méthodes utilisées pour la détection de communautés et pour proposer de nouvelles méthodes pour agréger les régions homogènes afin de produire de bonnes segmentations d’images.Par ailleurs, nous proposons également un système de recherche d’images par le contenu (content-based image retrieval) utilisant les mêmes caractéristiques que celles obtenues par les processus de segmentation d’images. Le moteur de recherche d'images proposé fonctionne pour des images de scènes naturelles et permet de rechercher les images les plus similaires à l'image requête. Ce moteur de recherche d’images par le contenu repose sur l’utilisation des régions extraites comme mots visuels dans le modèle Bag-of-Visual-Words. Ceci permet de valider la généricité de notre approche de segmentation d’images à partir de réseaux complexes et son utilisation dans plusieurs domaines d'applications liés au traitement d’images et de vision par ordinateur. Nos méthodes ont été testées sur plusieurs jeux de données et évaluées en utilisant différentes mesures classiques de la qualité d'une segmentation. Les méthodes proposées produisent des segmentations d'image dont la qualité est supérieure à l'état de l'artImage segmentation has become an indispensable task that is widely employed in several image processing applications including object detection, object tracking, automatic driver assistance, and traffic control systems, etc. The literature abounds with algorithms for achieving image segmentation tasks. These methods can be divided into some main groups according to the underlying approaches, such as Region-based image segmentation, Feature-based clustering, Graph-based approaches and Artificial Neural Network-based image segmentation. Recently, complex networks have mushroomed both theories and applications as a trend of developments. Hence, image segmentation techniques based on community detection algorithms have been proposed and have become an interesting discipline in the literature. In this thesis, we propose a novel framework for community detection based image segmentation. The idea that brings social networks analysis domain into image segmentation quite satisfies with most authors and harmony in those researches. However, how community detection algorithms can be applied in image segmentation efficiently is a topic that has challenged researchers for decades. The contribution of this thesis is an effort to construct best complex networks for applying community detection and proposal novel agglomerate methods in order to aggregate homogeneous regions producing good image segmentation results. Besides, we also propose a content based image retrieval system using the same features than the ones obtained by the image segmentation processes. The proposed image search engine for real images can implement to search the closest similarity images with query image. This content based image retrieval relies on the incorporation of our extracted features into Bag-of-Visual-Words model. This is one of representative applications denoted that image segmentation benefits several image processing and computer visions applications. Our methods have been tested on several data sets and evaluated by many well-known segmentation evaluation metrics. The proposed methods produce efficient image segmentation results compared to the state of the art
35
Macdonald, Edward A. "Multi-robot assignment and formation control." Thesis, Georgia Institute of Technology, 2011. http://hdl.handle.net/1853/41200.
Full textAbstract:
Our research focuses on one of the more fundamental issues in multi-agent, mobile
robotics: the formation control problem. The idea is to create controllers that cause
robots to move into a predefined formation shape. This is a well studied problem for
the scenario in which the robots know in advance to which point in the formation they
are assigned. In our case, we assume this information is not given in advance, but must
be determined dynamically. This thesis presents an algorithm that can be used by
a network of mobile robots to simultaneously determine efficient robot assignments
and formation pose for rotationally and translationally invariant formations. This
allows simultaneous role assignment and formation sysnthesis without the need for
additional control laws.
The thesis begins by introducing some general concepts regarding multi-agent
robotics. Next, previous work and background information specific to the formation
control and assignment problems are reviewed. Then the proposed assignment al-
gorithm for role assignment and formation control is introduced and its theoretical
properties are examined. This is followed by a discussion of simulation results. Lastly,
experimental results are presented based on the implementation of the assignment al-
gorithm on actual robots.
36
Brinda, Karel. "Nouvelles techniques informatiques pour la localisation et la classification de données de séquençage haut débit." Thesis, Paris Est, 2016. http://www.theses.fr/2016PESC1027/document.
Full textAbstract:
Depuis leur émergence autour de 2006, les technologies de séquençage haut débit ont révolutionné la recherche biologique et médicale. Obtenir instantanément une grande quantité de courtes ou longues lectures de presque tout échantillon biologique permet de détecter des variantes génomiques, révéler la composition en espèces d’un métagénome, déchiffrer la biologie du cancer, décoder l'évolution d’espèces vivantes ou disparues, ou mieux comprendre les schémas de la migration humaine et l'histoire humaine en général. La vitesse à laquelle augmente le débit des technologies de séquençage dépasse la croissance des capacités de calcul et de stockage, ce qui crée de nouveaux défis informatiques dans le traitement de données de séquençage haut débit. Dans cette thèse, nous présentons de nouvelles techniques informatiques pour la localisation (mapping) de lectures dans un génome de référence et pour la classification taxonomique. Avec plus d'une centaine d’outils de localisation publiés, ce problème peut être considéré comme entièrement résolu. Cependant, une grande majorité de programmes suivent le même paradigme et trop peu d'attention a été accordée à des approches non-standards. Ici, nous introduisons la localisation dynamique dont nous montrons qu’elle améliore significativement les alignements obtenus, par comparaison avec les approches traditionnelles. La localisation dynamique est basée sur l'exploitation de l'information fournie par les alignements calculés précédemment, afin d’améliorer les alignements des lectures suivantes. Nous faisons une première étude systématique de cette approche et démontrons ses qualités à l'aide de Dynamic Mapping Simulator, une pipeline pour comparer les différents scénarios de la localisation dynamique avec la localisation statique et le “référencement itératif”. Une composante importante de la localisation dynamique est un calculateur du consensus online, c’est-à-dire un programme qui collecte des statistiques des alignements pour guider, à la volée, les mises à jour de la référence. Nous présentons OCOCO, calculateur du consensus online qui maintient des statistiques des positions génomiques individuelles à l’aide de compteurs de bits compacts. Au-delà de son application à la localisation dynamique, OCOCO peut être utilisé comme un calculateur de SNP online dans divers pipelines d'analyse, ce qui permet de prédire des SNP à partir d'un flux sans avoir à enregistrer les alignements sur disque. Classification métagénomique de lectures d’ADN est un autre problème majeur étudié dans la thèse. Etant donné des milliers de génomes de référence placés sur un arbre taxonomique, le problème consiste à affecter rapidement aux nœuds de l'arbre une énorme quantité de lectures NGS, et éventuellement estimer l'abondance relative des espèces concernées. Dans cette thèse, nous proposons des techniques améliorées pour cette tâche. Dans une série d'expériences, nous montrons que les graines espacées améliorent la précision de la classification. Nous présentons Seed-Kraken, extension sur les graines espacées du logiciel populaire Kraken. En outre, nous introduisons une nouvelle stratégie d'indexation basée sur le transformé de Burrows-Wheeler (BWT), qui donne lieu à un indice beaucoup plus compact et plus informatif par rapport à Kraken. Nous présentons une version modifiée du logiciel BWA qui améliore l’index BWT pour la localisation rapide de k-mersSince their emergence around 2006, Next-Generation Sequencing technologies have been revolutionizing biological and medical research. Obtaining instantly an extensive amount of short or long reads from almost any biological sample enables detecting genomic variants, revealing the composition of species in a metagenome, deciphering cancer biology, decoding the evolution of living or extinct species, or understanding human migration patterns and human history in general. The pace at which the throughput of sequencing technologies is increasing surpasses the growth of storage and computer capacities, which still creates new computational challenges in NGS data processing. In this thesis, we present novel computational techniques for the problems of read mapping and taxonomic classification. With more than a hundred of published mappers, read mapping might be considered fully solved. However, the vast majority of mappers follow the same paradigm and only little attention has been paid to non-standard mapping approaches. Here, we propound the so-called dynamic mapping that we show to significantly improve the resulting alignments compared to traditional mapping approaches. Dynamic mapping is based on exploiting the information from previously computed alignments, helping to improve the mapping of subsequent reads. We provide the first comprehensive overview of this method and demonstrate its qualities using Dynamic Mapping Simulator, a pipeline that compares various dynamic mapping scenarios to static mapping and iterative referencing. An important component of a dynamic mapper is an online consensus caller, i.e., a program collecting alignment statistics and guiding updates of the reference in the online fashion. We provide OCOCO, the first online consensus caller that implements a smart statistics for individual genomic positions using compact bit counters. Beyond its application to dynamic mapping, OCOCO can be employed as an online SNP caller in various analysis pipelines, enabling calling SNPs from a stream without saving the alignments on disk. Metagenomic classification of NGS reads is another major problem studied in the thesis. Having a database of thousands reference genomes placed on a taxonomic tree, the task is to rapidly assign to tree nodes a huge amount of NGS reads, and possibly estimate the relative abundance of involved species. In this thesis, we propose improved computational techniques for this task. In a series of experiments, we show that spaced seeds consistently improve the classification accuracy. We provide Seed-Kraken, a spaced seed extension of Kraken, the most popular classifier at present. Furthermore, we suggest a new indexing strategy based on a BWT-index, obtaining a much smaller and more informative index compared to Kraken. We provide a modified version of BWA that improves the BWT-index for a quick k-mer look-up
37
Alekeish, Khaled. "Design and performance study of algorithms for consensus in sparse, mobile ad-hoc networks." Thesis, University of Newcastle Upon Tyne, 2011. http://hdl.handle.net/10443/1237.
Full textAbstract:
Mobile Ad-hoc Networks (MANETs) are self-organizing wireless networks that consist of mobile wireless devices (nodes). These networks operate without the aid of any form of supporting infrastructure, and thus need the participating nodes to co-operate by forwarding each other’s messages. MANETs can be deployed when urgent temporary communications are required or when installing network infrastructure is considered too costly or too slow, for example in environments such as battlefields, crisis management or space exploration. Consensus is central to several applications including collaborative ones which a MANET can facilitate for mobile users. This thesis solves the consensus problem in a sparse MANET in which a node can at times have no other node in its wireless range and useful end-to-end connectivity between nodes can just be a temporary feature that emerges at arbitrary intervals of time for any given node pair. Efficient one-to-many dissemination, essential for consensus, now becomes a challenge: enough number of destinations cannot deliver a multicast unless nodes retain the multicast message for exercising opportunistic forwarding. Seeking to keep storage and bandwidth costs low, we propose two protocols. An eventually relinquishing (}RC) protocol that does not store messages for long is used for attempting at consensus, and an eventually quiescent (}QC) one that stops forwarding messages after a while is used for concluding consensus. Use of }RC protocol poses additional challenges for consensus, when the fraction, f n, of nodes that can crash is: 1 4 f n < 1 2 . Consensus latency and packet overhead are measured through simulation indicating that they are not too high to be feasible in MANETs. They both decrease considerably even for a modest increase in network density.
38
Messina, Carl J. "Labeled sampling consensus a novel algorithm for robustly fitting multiple structures using compressed sampling." Master's thesis, University of Central Florida, 2011. http://digital.library.ucf.edu/cdm/ref/collection/ETD/id/4983.
Full textAbstract:
The ability to robustly fit structures in datasets that contain outliers is a very important task in Image Processing, Pattern Recognition and Computer Vision. Random Sampling Consensus or RANSAC is a very popular method for this task, due to its ability to handle over 50% outliers. The problem with RANSAC is that it is only capable of finding a single structure. Therefore, if a dataset contains multiple structures, they must be found sequentially by finding the best fit, removing the points, and repeating the process. However, removing incorrect points from the dataset could prove disastrous. This thesis offers a novel approach to sampling consensus that extends its ability to discover multiple structures in a single iteration through the dataset. The process introduced is an unsupervised method, requiring no previous knowledge to the distribution of the input data. It uniquely assigns labels to different instances of similar structures. The algorithm is thus called Labeled Sampling Consensus or L-SAC. These unique instances will tend to cluster around one another allowing the individual structures to be extracted using simple clustering techniques. Since divisions instead of modes are analyzed, only a single instance of a structure need be recovered. This ability of L-SAC allows a novel sampling procedure to be presented "compressing" the required samples needed compared to traditional sampling schemes while ensuring all structures have been found. L-SAC is a flexible framework that can be applied to many problem domains.ID: 030423298; System requirements: World Wide Web browser and PDF reader.; Mode of access: World Wide Web.; Thesis (M.S.E.E.)--University of Central Florida, 2011.; Includes bibliographical references (p. 70-72).
M.S.E.E.
Masters
Electrical Engineering and Computer Science
Engineering and Computer Science
Electrical Engineering
39
Hanaf, Anas. "Algorithmes distribués de consensus de moyenne et leurs applications dans la détection des trous de couverture dans un réseau de capteurs." Thesis, Reims, 2016. http://www.theses.fr/2016REIMS018/document.
Full textAbstract:
Les algorithmes distribués de consensus sont des algorithmes itératifs de faible complexité où les nœuds de capteurs voisins interagissent les uns avec les autres pour parvenir à un accord commun sans unité coordinatrice. Comme les nœuds dans un réseau de capteurs sans fil ont une puissance de calcul et une batterie limitées, ces algorithmes distribués doivent parvenir à un consensus en peu de temps et avec peu d’échange de messages. La première partie de cette thèse s’est basée sur l’étude et la comparaison des différents algorithmes de consensus en mode synchrone et asynchrone en termes de vitesse de convergence et taux de communications. La seconde partie de nos travaux concerne l’application de ces algorithmes de consensus au problème de la détection de trous de couverture dans les réseaux de capteurs sans fil.Ce problème de couverture fournit aussi le contexte de la suite de nos travaux. Il se décrit comme étant la façon dont une région d’intérêt est surveillée par des capteurs. Différentes approches géométriques ont été proposées mais elles sont limitées par la nécessité de connaitre exactement la position des capteurs ; or cette information peut ne pas être disponible si les dispositifs de localisation comme par exemple le GPS ne sont pas sur les capteurs. À partir de l’outil mathématique appelé topologie algébrique, nous avons développé un algorithme distribué de détection de trous de couverture qui recherche une fonction harmonique d’un réseau, c’est-à-dire annulant l’opérateur du Laplacien de dimension 1. Cette fonction harmonique est reliée au groupe d’homologie H1 qui recense les trous de couverture. Une fois une fonction harmonique obtenue, la détection des trous se réalise par une simple marche aléatoire dans le réseauDistributed consensus algorithms are iterative algorithms of low complexity where neighboring sensors interact with each other to reach an agreement without coordinating unit. As the nodes in a wireless sensor network have limited computing power and limited battery, these distributed algorithms must reach a consensus in a short time and with little message exchange. The first part of this thesis is based on the study and comparison of different consensus algorithms synchronously and asynchronously in terms of convergence speed and communication rates. The second part of our work concerns the application of these consensus algorithms to the problem of detecting coverage holes in wireless sensor networks.This coverage problem also provides the context for the continuation of our work. This problem is described as how a region of interest is monitored by sensors. Different geometrical approaches have been proposed but are limited by the need to know exactly the position of the sensors; but this information may not be available if the locating devices such as GPS are not on the sensors. From the mathematical tool called algebraic topology, we have developed a distributed algorithm of coverage hole detection searching a harmonic function of a network, that is to say canceling the operator of the 1-dimensional Laplacian. This harmonic function is connected to the homology group H1 which identifies the coverage holes. Once a harmonic function obtained, detection of the holes is realized by a simple random walk in the network
40
Yao, Lisha. "Distributed Consensus, Optimization and Computation in Networked Systems." Thesis, University of North Texas, 2018. https://digital.library.unt.edu/ark:/67531/metadc1404555/.
Full textAbstract:
In the first part of this thesis, we propose a distributed consensus algorithm under multi-layer multi-group structure with communication time delays. It is proven that the consensus will be achieved in both time-varying and fixed communication delays. In the second part, we study the distributed optimization problem with a finite-time mechanism. It is shown that our distributed proportional-integral algorithm can exponentially converge to the unique global minimizer when the gain parameters satisfy the sufficient conditions. Moreover, we equip the proposed algorithm with a decentralized algorithm, which enables an arbitrarily chosen agent to compute the exact global minimizer within a finite number of time steps, using its own states observed over a successive time steps. In the third part, it is shown the implementation of accelerated distributed energy management for microgrids is achieved. The results presented in the thesis are corroborated by simulations or experiments.
41
De, Martino Davide. "Analisi dei più diffusi Algoritmi di consenso Blockchain." Bachelor's thesis, Alma Mater Studiorum - Università di Bologna, 2020.
Find full textAbstract:
La nostra epoca è caratterizzata da innovazioni tecnologiche continue, alcune delle quali rappresentano delle vere e proprie sfide a sistemi esistenti e consolidati. Una di queste è sicuramente la tecnologia blockchain che, grazie ai suoi meccanismi, ha permesso di introdurre il concetto di criptovaluta, una moneta digitale (denominata anche criptomoneta) che può essere scambiata alla pari di quella cartacea.
Il grande successo di Bitcoin, la prima grande implementazione del concetto di criptovaluta, ha portato alla nascita di altre numerose monete digitali e ha favorito l’idea che la tecnologia blockchain potesse essere impiegata anche in ambiti diversi dai sistemi finanziari.
Con questo elaborato si intende dare un quadro dettagliato del funzionamento dei più diffusi algoritmi di consenso ad oggi esistenti nel panorama della tecnologia blockchain.
In particolare sono stati analizzati gli algoritmi Proof of Work, Proof of Stake, Delegated Proof of Stake e Proof of Authority (Aura e Clique).
Per ogni algoritmo di consenso sono state analizzate le principali differenze e sono stati realizzati degli algoritmi in pseudocodice per spiegare il funzionamento della creazione dei nuovi blocchi.
In conclusione si proporrà un’analisi comparativa degli algoritmi di consenso analizzati, dal punto di vista delle caratteristiche maggiormente desiderabili e delle prestazioni di un sistema blockchain.
42
Blanchard, Peva. "Synchronization and Fault-tolerance in Distributed Algorithms." Thesis, Paris 11, 2014. http://www.theses.fr/2014PA112219/document.
Full textAbstract:
Dans la première partie de ce mémoire, nous étudions le modèle des protocoles de population, introduit dans\cite{DBLP:conf/podc/BeauquierBCK10}. Ce modèle permet de représenter les grands réseaux de capteurs (ou agents) mobiles anonymes dotés de faibles ressources. Les contraintes de ce modèle sont si sévères que la plupart des problèmes classiques d'algorithmique répartie, tels que la collecte de données, le consensus ou l'élection d'un leader, sont difficiles à analyser, sinon impossibles à résoudre.Nous commençons notre étude par le problème de collecte de données. Celui-ci consiste principalement à transférer des valeurs réparties dans la population d'agents mobiles vers une station de base en un minimum de temps (temps de convergence). En utilisant un hypothèse d'équité, dite hypothèse de temps couvertures et introduite dans \cite{DBLP:conf/podc/BeauquierBCK10}, nous calculons des bornes optimales sur le temps de convergences de différents protocoles concrets. Ensuite, nous étudions le problème du consensus et d'élection de leader. Il a été montré que ces problèmes sont impossibles à résoudre dans le modèle original des protocoles de population. Pour contourner cette impossibilité, il est possible d'adjoindre au modèle certaines hypothèses sous la forme d'oracles. Nous proposons ensuite divers oracles permettant de résoudre le problème du consensus et d'élection de leader dans divers environnements, et nous étudions leurs puissances relatives. Ce faisant, nous développons un cadre formel permettant de représenter toutes les variétés d'oracles introduites, ainsi que leur possibles relations.Dans la seconde partie de ce mémoire, nous étudions le problème de la réplication de machine à états finis dans le modèle (classique) de communications asynchrones à passage de message. L'algorithme Paxos, introduit dans \cite{lamportPartTimeParliament,lamport01paxos} est une solution (partielle) bien connue au problème de la réplication capable de tolérer des pannes crash. Notre contribution, dans cette partie,consiste à améliorer Paxos afin qu'il puisse également tolérer des défaillances transitoires. Ce faisant, nous définissons la notions de machine répliquée pratiquement autostableIn the first part of this thesis, we focus on a recent model, calledpopulation protocols, which describes large networksof tiny wireless mobile anonymous agents with very limited resources.The harsh constraints of the original model makes most of theclassical problems of distributed algorithmics, such as datacollection, consensus and leader election, either difficult to analyzeor impossible to solve.We first study the data collection problem, which mainly consists intransferring some values to a base station. By using a fairnessassumption, known as cover times, we compute tight bounds on theconvergence time of concrete protocols. Next, we focus on theproblems of consensus and leader election. It is shown that theseproblems are impossible in the original model. To circumvent theseissues, we augment the original model with oracles, and study theirrelative power. We develop by the way a formal framework generalenough to encompass various sorts of oracles, as well as theirrelations.In the second part of the thesis, we study the problem ofstate-machine replication in the more classical model of asynchronousmessage-passing communication. The Paxos algorithm is a famous(partial) solution to the state-machine replication problem whichtolerates crash failures. Our contribution is the enhancement of Paxosin order to tolerate transient faults as well. Doing so, we define thenotion of practically self-stabilizing replicated state-machine
43
Saberian, Aminmohammad. "Applying adjacency based control to distribution networks." Thesis, Queensland University of Technology, 2019. https://eprints.qut.edu.au/126755/1/Aminmohammad_Saberian_Thesis.pdf.
Full textAbstract:
Due to environmental concerns, there is a trend to be less dependent on fossil fuels. This is leading to an increased usage of distributed energy resources in power systems. For the control of distribution networks, an idea has recently been proposed, that shows promising features for several control problems in distribution. This research project demonstrates the adjacency algorithm, including the communication structure for implementing consensus where each agent exchanges information with its immediate neighbours. The adjacency algorithm is demonstrated for three applications; namely voltage control, frequency control using battery reserve energy and the implementation of market clearing for distribution prosumers.
44
Travers, Corentin. "Derrière le consensus : coordination faiblement contrainte dans les systèmes distribués asynchrones." Phd thesis, Université Rennes 1, 2007. http://tel.archives-ouvertes.fr/tel-00485704.
Full textAbstract:
L'informatique moderne est distribuée. La distribution du calcul résulte parfois d'un besoin applicatif lorsque l'objectif est de connecter des ordinateurs distants. Parfois, elle naît du besoin de tolérer des défaillances. En effet, pour éviter qu'une application ne soit à la merci de la défaillance d'une machine, le calcul est dupliqué sur plusieurs machines. Au coeur de tout calcul réparti repose une forme de coordination. Le fait même que des ordinateurs aient une tâche commune implique un besoin de se concerter avant d'accomplir certaines tâches. Nous étudions les problèmes de coordination dans le modèle asynchrone, sans hypothèses sur des bornes de vitesse d'exécution des processeurs ou de transmission des messages. Les processus peuvent défaillir à n'importe quel moment. Le degré de coordination qui peut être atteint en fonction du degré d'incertitude du système est la question principale de cette thèse. Trois formes de coordination sont considérées : l'accord ensembliste, le renommage et le consensus simultané. Dans un premier temps, nous proposons différentes réductions algorithmiques entre ces problèmes, afin de prouver dans quelles conditions une solution à l'un de ces problèmes permet d'obtenir une solution à un autre problème. Nous étudions ensuite des hypothèses nécessaires et suffisantes sur la détection de défaillances permettant de résoudre les problèmes d'accord. Le formalisme utilisé ici est celui des détecteurs de défaillances. Enfin, nous proposons un autre point de vue sur les détecteur de défaillances. Nous caractérisons la puissance de calcul amenée par ces détecteurs par une restriction des exécutions du modèle itéré de Gafni.
45
Jafarizadeh, Saber. "Distributed coding and algorithm optimization for large-scale networked systems." Thesis, The University of Sydney, 2014. http://hdl.handle.net/2123/13238.
Full textAbstract:
In this thesis design and optimization of several distributed algorithms in large-scale networked systems is studied. The studied algorithms operate on networks of autonomous agents in general including the sensor networks and the ad hoc networks. The main focus here is on distributed algorithms operating on large-scale networks. This is due to their robustness to node failure and ability to extend according to the size and topology of the system. Regarding the optimization of the studied algorithms, it is aimed to increase their convergence rate to their equilibrium state considering the constraints of the system including the available bandwidth, memory and power for each agent. The first topic addresses the optimization of two algorithms; namely the distributed random gossip algorithm and the distributed average consensus algorithm. The underlying graph of the network is exploited to provide an analytical solution to the semidefinite programming formulation of the problems. In the second topic, two distributed algorithms are proposed for increasing data persistency in wireless sensor networks based on LT and Raptor codes. In the proposed algorithms, the sensed data is disseminated using random walks with the non-uniform stationary distribution. A new distributed method is proposed for assigning the transition probabilities of the random walks. The third topic studies distributed coding of LT codes in Y networks where multiple sources communicate with the same destination through a common relay node. The Adaptive Distributed LT coding algorithm is proposed that combines the LT codes with the network coding technique. The fourth topic addresses optimization of the LT codes for short message lengths. Unlike previous formulations, the provided novel semidefinite programming formulation has finite number of constraints while it is free of approximation.
46
Grandi, Raffaele <1976>. "Coordination and Control of Autonomous Mobile Robots Swarms by using Particle Swarm Optimization Algorithm and Consensus Theory." Doctoral thesis, Alma Mater Studiorum - Università di Bologna, 2013. http://amsdottorato.unibo.it/5904/1/Grandi_Raffaele_tesi.pdf.
Full textAbstract:
This thesis presents some different techniques designed to drive a swarm of robots in an a-priori unknown environment in order to move the group from a starting area to a final one avoiding obstacles. The presented techniques are based on two different theories used alone or in combination: Swarm Intelligence (SI) and Graph Theory. Both theories are based on the study of interactions between different entities (also called agents or units) in Multi- Agent Systems (MAS). The first one belongs to the Artificial Intelligence context and the second one to the Distributed Systems context. These theories, each one from its own point of view, exploit the emergent behaviour that comes from the interactive work of the entities, in order to achieve a common goal. The features of flexibility and adaptability of the swarm have been exploited with the aim to overcome and to minimize difficulties and problems that can affect one or more units of the group, having minimal impact to the whole group and to the common main target. Another aim of this work is to show the importance of the information shared between the units of the group, such as the communication topology, because it helps to maintain the environmental information, detected by each single agent, updated among the swarm. Swarm Intelligence has been applied to the presented technique, through the Particle Swarm Optimization algorithm (PSO), taking advantage of its features as a navigation system. The Graph Theory has been applied by
exploiting Consensus and the application of the agreement protocol with the aim to maintain the units in a desired and controlled formation. This approach has been followed in order to conserve the power of PSO and to control part of its random behaviour with a distributed control algorithm
like Consensus.
47
Grandi, Raffaele <1976>. "Coordination and Control of Autonomous Mobile Robots Swarms by using Particle Swarm Optimization Algorithm and Consensus Theory." Doctoral thesis, Alma Mater Studiorum - Università di Bologna, 2013. http://amsdottorato.unibo.it/5904/.
Full textAbstract:
This thesis presents some different techniques designed to drive a swarm of robots in an a-priori unknown environment in order to move the group from a starting area to a final one avoiding obstacles. The presented techniques are based on two different theories used alone or in combination: Swarm Intelligence (SI) and Graph Theory. Both theories are based on the study of interactions between different entities (also called agents or units) in Multi- Agent Systems (MAS). The first one belongs to the Artificial Intelligence context and the second one to the Distributed Systems context. These theories, each one from its own point of view, exploit the emergent behaviour that comes from the interactive work of the entities, in order to achieve a common goal. The features of flexibility and adaptability of the swarm have been exploited with the aim to overcome and to minimize difficulties and problems that can affect one or more units of the group, having minimal impact to the whole group and to the common main target. Another aim of this work is to show the importance of the information shared between the units of the group, such as the communication topology, because it helps to maintain the environmental information, detected by each single agent, updated among the swarm. Swarm Intelligence has been applied to the presented technique, through the Particle Swarm Optimization algorithm (PSO), taking advantage of its features as a navigation system. The Graph Theory has been applied by
exploiting Consensus and the application of the agreement protocol with the aim to maintain the units in a desired and controlled formation. This approach has been followed in order to conserve the power of PSO and to control part of its random behaviour with a distributed control algorithm
like Consensus.
48
Lovisari, Enrico. "Synchronization algorithms for multi-agent systems: Analysis, Synthesis and Applications." Doctoral thesis, Università degli studi di Padova, 2012. http://hdl.handle.net/11577/3422115.
Full textAbstract:
The main topic of this thesis is the study of the interaction of agents interconnected in a large-scale network. In the thesis, three complementary problems have been afforded: Analysis of Consensus Networks, Synthesis of Higher Order Consensus Networks, and Application of Synchronization algorithmsQuesta tesi di dottorato e incentrata sullo studio dell'interazione di agenti interconnessi in rete. In questa tesi vengono affrontati tre problemi complementari l'un l'altro: Analisi di reti di consenso, Sintesi di reti di consenso di ordine superiore, e Applicazione di algoritmi di sincronizzazione
49
Obando, Bravo German Dario. "Distributed methods for resource allocation : a passivity based approach." Thesis, Nantes, Ecole des Mines, 2015. http://www.theses.fr/2015EMNA0174/document.
Full textAbstract:
Durant les dernières années, la taille des systèmes ainsi que leur complexité ont pas mal évolué, entrainant le besoin d'approches distribuées pour la commande et l'aide à la décision. Cette thèse porte sur la résolution d'un problème incluant une commande distribuée et une aide à la décision, l'allocation dynamique de ressource dans un réseau.Pour résoudre ce problème, nous avons étudié un algorithme basé sur un consensus qui ne nécessite pas de calcul centralisé, et qui soit capable de traiter des applications modélisées par des systèmes dynamiques ou par des fonctions sans mémoires. La principale contribution de ce travail de thèse est d'avoir prouvé, en utilisant des outils issus de la théorie des graphes etl'analyse de la passivité, que le contrôleur atteint la solution optimale de façon asymptotique, sans obligation d'avoir une information complète.Afin d'illustrer la pertinence de notre résultat principal, plusieurs applications en ingénierie ont été étudiées, incluant la commande distribuée pour l'économie d'énergie dans des bâtiments intelligents, la gestion des clients dans un environnement de "smart grids", et le développement d'une méthode exacte d'optimisation distribuée pour un problème d'allocation de ressources soumis à des contraintes sur les bornes inférieures.Enfin, nous étudions les techniques d'allocation de ressources basées sur les modèlesde dynamique de populations. Pour les rendre distribuées, nous introduisons le concept dedynamique de populations "pas bien mélangées". Nous montrons que ces dynamiques peuventêtre utilisées pour des structures d'informations contraintes. Même si les dynamiquesde populations "pas bien mélangées" utilisent des informations partielles, ellesconservent des propriétés similaires aux dynamiques classiques qui utilisent desinformations complètes. Plus spécifiquement, la conservation de masse et la convergencevers l'équilibre de Nash sont prouvéesSince the complexity and scale of systems have been growing in the last years, distributed approaches for control and decision making are becoming more prevalent. This dissertation focuses on an important problem involving distributed control and decision making, the dynamic resource allocation in a network. To address this problem, we explore a consensus--based algorithm that does not require any centralized computation, and that is capable to deal with applications modeled either by dynamical systems or by memoryless functions. The main contribution of our research is to prove, by means of graph theoretical tools and passivity analysis, that the proposed controller asymptotically reaches an optimal solution without the need of full information. In order to illustrate the relevance of our main result, we address several engineering applications including: distributed control for energy saving in smart buildings, management of the customers of an aggregating entity in a smart grid environment, and development of an exact distributed optimization method that deals with resource allocation problems subject to lower--bound constraints. Finally, we explore resource allocation techniques based on classic population dynamics models. In order to make them distributed, we introduce the concept of non--well--mixed population dynamics. We show that these dynamics are capable to deal with constrained information structures that are characterized by non--complete graphs. Although the proposed non--well--mixed population dynamics use partial information, they preserve similar properties of their classic counterpart, which uses full information. Specifically, we prove mass conservation and convergence to Nash equilibrium
Dado que la complejidad y la escala de los sistemas sehan ido incrementando en los últimos años, las técnicas centralizadas de control y toma de decisiones están siendo reemplazadas por métodos distribuidos. Esta tesis se centra en un importante problema que involucra control y toma de decisiones distribuidas: la asignación dinámica de recursos en redes. Para abordar este problema, exploramos un algoritmo basado en consenso que no requiere computación centralizada, y que puede ser usado en aplicaciones modeladas ya sea por sistemas dinámicos o funciones sin memoria. La principal contribución de esta tesis es probar, por medio de teoría de grafos y pasividad, que el algoritmo propuesto alcanza asintóticamente una solución óptima sin la necesidad de usar información completa. Para ilustrar la relevancia del resultado principal de esta disertación, abordamos varias aplicaciones en ingeniería,incluyendo: el control distribuido en edificios inteligentes orientado a la eficiencia energética, la gestión de los clientes de un agregador en una red inteligente en la que se aplican estrategias de respuesta de la demanda, y el desarrollo de un método de optimización exacto que permite incluir restricciones de límite inferior. Finalmente, se exploran otras técnicas de asignación derecursos inspiradas en modelos de dinámicas poblacionales. Se introduce el concepto de poblaciones no—bien—mezcladas, y se muestra que las dinámicas asociadas a este tipo de poblaciones cuentan con una estructura de información local, caracterizada por grafos que no son completos. A pesar de que las dinámicas propuestas usan información parcial, ellas preservan características similares a las dinámicas poblacionales clásicas que usan información completa
50
Mezgebe, Tsegay Tesfay. "Algorithmes inspirés des sociales pour concevoir des nouveaux systèmes de pilotage dans le contexte de l'usine du futur." Electronic Thesis or Diss., Université de Lorraine, 2020. http://www.theses.fr/2020LORR0006.
Full textAbstract:
Le pilotage centralisé traditionnel de système manufacturier n’est plus capable de répondre aux besoins du marché en termes d’attentes des clients, de la variété et du cycle de vie des produits. En particulier, l’émergence des systèmes Cyber-Physiques (CPS), vus comme des réseaux de composants physiques et informatiques en interaction, a impacté le pilotage central prédictif pour contrer les perturbations dans les actuelles caractéristiques dynamiques du marché. Par exemple, la modification urgente des besoins de l’entreprise est l’une des perturbations les plus communes qui impacte le planning central d’une manière significative. A l’heure actuelle, le pilotage distribué, pouvant être basé sur les systèmes multi-agent, permet d’améliorer la réactivité pour répondre à différents types de perturbations afin que celles-ci ne soient plus des facteurs contraignants le pilotage. Les travaux de cette thèse explorent la conception de nouveaux algorithmes de pilotage en se basant sur les approches d’interactions sociales, telles que la négociation ou la théorie du consensus). Ces algorithmes intègrent les avantages des actifs liés à l’industrie du futur et englobent différentes entités intelligentes et hétérogènes, ainsi que des systèmes à évènements discrets. Chaque agent peut avoir des capacités différentes, en termes d’évolution, d’apprentissage ou autre, permettant d’une manière globale d’obtenir des comportements émergeants qui s’adaptent dynamiquement aux perturbations rencontrées. Ainsi, chaque agent intelligent décide quand il transmet son état actuel à son voisinage et la décision locale dépend du comportement de l’état des agents. Afin de vérifier l’efficacité des algorithmes proposés (négociation et consensus), ceux-ci ont été modélisés et formulés en mettant en réseau toutes les entités intelligentes, le tout basé sur deux ateliers industriels. Les algorithmes ont ensuite été testés en simulation et d’une manière expérimentale sur la cellule flexible de production du plateau technique TRACILOGIS. Des comparaisons ont été faites avec l’algorithme réactif actuellement implémenté sur cette plateforme, afin de montrer l’applicabilité des algorithmes dans l’obtention de ré-ordonnancement et re-séquencement de produits par priorité. Par conséquent, les résultats expérimentaux réalisés sur TRACILOGIS ont montré que les algorithmes de négociation et de consensus ont minimisé l’impact des perturbations en obtenant de meilleures performances globales qu’auparavantThe use of traditionally centralized control system does not able to meet the rapidly changing customer expectations, high product varieties, and shorter product life-cycles. In particular, the emergence of Cyber Physical System (CPS) which can be seen as interacting networks of physical and computational components has provided the foundation for many new factories’ infrastructures and improved the quality of products and processes. This Cyber Physical System has dramatically impacted the centrally predictive control system in responding to perturbation(s) in the current dynamic market characteristics. Urgent change for example is one of the common perturbations and has significant perturbing ability to a central predictive control system. Accordingly, it is now accepted that using agent-based control system improves the reactivity to treat these perturbation(s) until they are no longer limiting factors. In this study, the use of human-inspired interaction approach (by means of negotiation and consensus-based decision-making algorithms) is explored to design and propose a new control system. It has taken advantages from Industry 4.0 assets and encompassed heterogeneous and intelligent entities (mainly the product entities and resource entities) and discrete event systems. Each entity could have different capability (evolution, learning, etc.) and the whole physical and control system may lead emerging behaviors to dynamically adapt the perturbation(s). Hence, every intelligent entity decides when to broadcast its current state to neighbor entities and the controlling decision depends on the behavior of this state. The negotiation and consensus-based decision-making algorithms were initially formulated and modeled by networking all the contributing and heterogeneous entities considering two real industrial shop floors. Then after, simulation and application implementation tests on the basis of full-sized academic platform called TRACILOGIS platform have been conducted to verify and validate these decision-making algorithms. This has been done with expectations that the applicability of these algorithms will be more adaptable to set best priority-based product sequencing and rescheduling than another decision-making approach called pure reactive control approach. Accordingly, the experimental results have shown that the negotiation and consensus among the decisional entities have significantly minimized the impact of perturbation(s) on a production process launched on the TRACILOGIS platform. Meanwhile, using these two decision-making algorithms has conveyed better global performance (e.g., minimized makespan) over the pure reactive control approach