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

Distributed Transactional Memory (DTM) is an emerging, alternative concurrency control model that aims to overcome the challenges of distributed-lock based synchronization. DTM employs transactions in order to guarantee consistency in a concurrent execution. When two or more transactions conflict, all but one need to be delayed or rolled back. Transactional Memory supports code composability by nesting transactions. Nesting how- ever can be used as a strategy to improve performance. The closed nesting model enables partial rollback by allowing a sub-transaction to abort without aborting its parent, thus reducing the amount of work that needs to be retried. In the open nesting model, sub- transactions can commit to the shared state independently of their parents. This reduces isolation and increases concurrency. Our first main contribution in this dissertation are two extensions to the existing Transac- tional Forwarding Algorithm (TFA). Our extensions are N-TFA and TFA-ON, and support closed nesting and open nesting, respectively. We additionally extend the existing SCORe algorithm with support for open nesting (we call the result SCORe-ON). We implement these algorithms in a Java DTM framework and evaluate them. This represents the first study of transaction nesting in the context of DTM, and contributes the first DTM implementation which supports closed nesting or open nesting. Closed nesting through our N-TFA implementation proved insufficient for any significant throughput improvements. It ran on average 2% faster than flat nesting, while performance for individual tests varied between 42% slowdown and 84% speedup. The workloads that benefit most from closed nesting are characterized by short transactions, with between two and five sub-transactions. Open nesting, as exemplified by our TFA-ON and SCORe-ON implementations, showed promising results. We determined performance improvement to be a trade-off between the overhead of additional commits and the fundamental conflict rate. For write-intensive, high- conflict workloads, open nesting may not be appropriate, and we observed a maximum speedup of 30%. On the other hand, for lower fundamental-conflict workloads, open nesting enabled speedups of up to 167% in our tests. In addition to the two nesting algorithms, we also develop Hyflow2, a high-performance DTM framework for the Java Virtual Machine, written in Scala. It has a clean Scala API and a compatibility Java API. Hyflow2 was on average two times faster than Hyflow on high-contention workloads, and up to 16 times faster in low-contention workloads. Our second main contribution for improving DTM performance is automated data partition- ing. Modern transactional processing systems need to be fast and scalable, but this means many such systems settled for weak consistency models. It is however possible to achieve all of strong consistency, high scalability and high performance, by using fine-grained partitions and light-weight concurrency control that avoids superfluous synchronization and other over- heads such as lock management. Independent transactions are one such mechanism, that rely on good partitions and appropriately defined transactions. On the downside, it is not usually straightforward to determine optimal partitioning schemes, especially when dealing with non-trivial amounts of data. Our work attempts to solve this problem by automating the partitioning process, choosing the correct transactional primitive, and routing transactions appropriately. Our third main contribution is Alvin, a system for managing concurrently running trans- actions on a geographically replicated data-store. Alvin supports general-purpose transactions, and guarantees strong consistency criteria. Through a novel partial order broadcast protocol, Alvin maximizes the parallelism of ordering and local transaction processing, resulting in low client-perceived latency. Alvin can process read-only transactions either lo- cally or globally, according to the desired consistency criterion. Conflicting transactions are ordered across all sites. We built Alvin in the Go programming language. We conducted our evaluation study on Amazon EC2 infrastructure and compared against Paxos- and EPaxos- based state machine replication protocols. Our results reveal that Alvin provides significant speed-up for read-dominated TPC-C workloads: as much as 4.8x when compared to EPaxos on 7 datacenters, and up to 26% in write-intensive workloads. Our fourth and final contribution is M2Paxos, a multi-leader implementation of Generalized Consensus. Single leader-based consensus protocols are known to stop scaling once the leader reaches its saturation point. Ordering commands based on conflicts is appealing due to the potentially higher parallelism, but is imperfect due to the higher quorum sizes required for fast decisions and the need to compare commands and track their dependencies. M2Paxos on the other hand exploits fast decisions (i.e., delivery of a command in two communication delays) by leveraging a classic quorum size, matching a majority of nodes deployed. M2Paxos does not establish command dependencies based on conflicts, but it binds accessed objects to nodes, making sure commands operating on the same object will be ordered by the same node. Our evaluation study of M2Paxos (also built in Go) confirms the effectiveness of this approach, getting up to 7⨉ improvements in performance over state- of-the-art consensus and generalized consensus algorithms. / Ph. D.

This thesis poses and solves a distribution free learning problem with consensus that arises in the study of estimation and control strategies for distributed sensor networks. Each node i for i = 1, . . . , n of the sensor network collects independent and identically distributed local measurements {z i} := {z i j}j∈N := {(x i j , yi j )}j∈N ⊆ X × Y := Z that are generated by the probability measure ρ i on Z. Each node i for i = 1, . . . , n of the network constructs a sequence of estimates {f i k }k∈N from its local measurements {z i} and from information functionals whose values are exchanged with other nodes as specified by the communication graph G for the network. The optimal estimate of the distribution free learning problem with consensus is cast as a saddle point problem which characterizes the consensus-constrained optimal estimate. This thesis introduces a two stage learning dynamic wherein local estimation is carried out via local least square approximations based on wavelet constructions and information exchange is associated with the Lagrange multipliers of the saddle point problem. Rates of convergence for the two stage learning dynamic are derived based on certain recent probabilistic bounds derived for wavelet approximation of regressor functions. / Master of Science

Yes / Although the eurozone sovereign debt crisis took many by surprise following the Global Financial Crisis induced Great Recession, this chapter argues that this was an accident waiting to happen with unjustified emphasis placed upon unproven rules and institutions derived from contemporary neoliberal macroeconomic thinking. First, recent developments in macroeconomic are discussed and evaluated in terms of the so-called New Consensus Macroeconomics (NCM) that forms the current mainstream macroeconomic model comprising a blend of New Classical and New Keynesian theories is through adopting the rational behaviour hypothesis and supply-side-determined long-term equilibrium of output. A particular feature of these ideas is the inclusion of rules and institutions that are perceived to result in time consistent policymaking through essentially binding politicians from undertaking in non-optimal behaviour for either opportunistic, partisan or non-rational expectations reasons. Second, in addition to the general backdrop of macroeconomics the chapter considers the notion of a monetary union between countries under the rubric of both exogenous and endogenous Optimum Currency Area (OCA) theory. This combination of theoretical propositions form the bedrock of the eurozone where the TEU convergence criteria and SGP form the rules, while the European Central Bank is the key institution tasked with delivering low and stable price inflation. However, although these notions have become the staple diet of a generation of mainstream economists they comprehensively failed to insulate the eurozone from its sovereign debt crisis.

I used a multiple-linear-regression model to test the effects of meeting group members’ expectations on strength of consensus in a group decision-making situation. The combination of met expression-of-views expectations and met decision-quality expectations, along with their associated valences, had a significant effect on consensus (p = .01). Expression-of-views expectations are composed of expectations about opportunity to express views and the information sharing. I proposed a new model consisting of two terms. The first term was the sum of the individual products of met expression-of-views expectations times their respective valences. The second term was the sum of the individual products of met decision-quality expectations times their respective valences. This new model was a much better predictor of strength of consensus than the original (p = .001). The two terms used in the new model had an equivalent influence on strength of consensus (p = .05). The results of this research suggest managers should elicit and try to meet group members’ high-valence expectations (i.e., expectations group members feel are important to be met). Managers should also realize expression-of-views and decision-quality expectations are important to meet in a consensus-gaining process. / Master of Science

Mémoire numérisé par la Division de la gestion de documents et des archives de l'Université de Montréal.

Depuis la prise de possession de la Nouvelle-Calédonie par la France en 1853, les tensions entre les autochtones et les allochtones ont toujours existé car cet archipel met en présence deux mondes qui se côtoient tout en s’ignorant. À une bipolarisation ethnique naturellement imparfaite entre les populations mélanésiennes et les colonisateurs, s’ajoute également une bipolarisation sociologique, politique, économique et sociale.Dès 1970, la majeure partie de la population mélanésienne de Nouvelle-Calédonie lutte pour une reconnaissance et une revalorisation de son identité culturelle et de son patrimoine, et c’est avec « Melanesia 2000 » en 1975 que le ciment culturel prend corps et avec le foncier que le fondement de la personnalité mélanésienne est affirmé. Les tensions allant crescendo aboutissent au drame d’Ouvéa. Partis d’une situation conflictuelle, les rapports deviennent consensuels avec les Accords de Matignon. La bipolarisation conflictuelle fait place à une bipolarisation contractuelle.La création de trois provinces constitue la première étape de ce long processus d’émancipation. L’Accord de Nouméa et sa loi organique de 1999 poussent la sophistication institutionnelle jusqu’à mettre en place un gouvernement local composé à la proportionnelle des membres du Congrès. Le rééquilibrage concerne les domaines politique, économique et social. En fin d’accord, les calédoniens devront se prononcer sur le transfert des pouvoirs régaliens à la Nouvelle-Calédonie. Comme toutes les élections sont clivées par rapport au concept d’indépendance, les électeurs se basent d’abord sur le positionnement des candidats par rapport à ce concept. L’Accord de Nouméa, de lecture plurielle, obvie les mésententes. Il permet le partage du pouvoir mais laisse en suspend la question essentielle du devenir ultérieur de la Nouvelle-Calédonie. La raison l’a emporté sur la violence, mais les convictions des uns et des autres restent apparemment intactes / Since taking possession of New Caledonia by France in 1853, tensions between natives and immigrants have always existed since the archipelago brings together two worlds that coexist while ignoring each other. At a naturally imperfect polarization between ethnic Melanesian and colonizers, also adds a polarization sociological, political, economic and social.By 1970, most of the Melanesian population of New Caledonia struggle for recognition and appreciation of cultural identity and heritage, and it is with "Melanesia 2000" in 1975 that cement cultural body and takes the property that the basis of personality is Melanesian said. Tensions ranging from tragedy to lead crescendo Uvea. Parties to a conflict situation, the reports become consensual with the Matignon Accords. The bipolar conflict gives way to a polarization of contract. The creation of three provinces is the first step in this long process of emancipation. The Noumea Accord and its organic law of 1999 to push the sophistication institutional set up a local government comprising proportional congressmen. Rebalancing for the political, economic and social development. At the end of agreement, the Caledonian will decide on the transfer of sovereign powers to New Caledonia. Like all elections are cleaved from the concept of independence, voters rely first on the positioning of candidates compared to that concept. The Noumea Accord, reading plural obviates the disagreements. It allows the sharing of power but leaves the key issue of suspending further becoming of New Caledonia. The reason has prevailed over violence, but the convictions of each others apparently remain intact

Le consensus des systèmes multi-agents a eu une attention considérable au cours de la dernière décennie. Le consensus est un processus coopératif dans lequel les agents interagissent afin de parvenir à un accord. La plupart des études se sont engagés à l'analyse de l'état d'équilibre du comportement de ce processus. Toutefois, au cours de la transitoire de ce processus une énorme quantité de données est produite. Dans cette thèse, notre objectif est d'exploiter les données produites au cours de la transitoire d'algorithmes de consensus moyenne asymptotique afin de concevoir des protocoles de consensus moyenne en temps fini, évaluer la robustesse du graphique, et éventuellement récupérer la topologie du graphe de manière distribuée. Le consensus de moyenne en temps fini garantit un temps d'exécution minimal qui peut assurer l'efficacité et la précision des algorithmes distribués complexes dans lesquels il est impliqué. Nous nous concentrons d'abord sur l'étape de configuration consacrée à la conception de protocoles de consensus qui garantissent la convergence de la moyenne exacte dans un nombre donné d'étapes. En considérant des réseaux d'agents modélisés avec des graphes non orientés connectés, nous formulons le problème de la factorisation de la matrice de moyenne et étudions des solutions distribuées à ce problème. Puisque, les appareils communicants doivent apprendre leur environnement avant d'établir des liens de communication, nous suggérons l'utilisation de séquences d'apprentissage afin de résoudre le problème de la factorisation. Ensuite, un algorithme semblable à l'algorithme de rétro-propagation du gradient est proposé pour résoudre un problème d'optimisation non convexe sous contrainte. Nous montrons que tout minimum local de la fonction de coût donne une factorisation exacte de la matrice de moyenne. En contraignant les matrices de facteur à être comme les matrices de consensus basées sur la matrice laplacienne, il est maintenant bien connu que la factorisation de la matrice de moyenne est entièrement caractérisé par les valeurs propres non nulles du laplacien. Par conséquent, la résolution de la factorisation de la matrice de la moyenne de manière distribuée avec une telle contrainte sur la matrice laplacienne, permet d'estimer le spectre de la matrice laplacienne. Depuis le spectre peut être utilisé pour calculer des indices de la robustesse (Nombre d'arbres couvrant et la résistance effective du graphe), la deuxième partie de cette thèse est consacrée à l'évaluation de la robustesse du réseau à travers l'estimation distribuée du spectre du Laplacien. Le problème est posé comme un problème de consensus sous contrainte formulé de deux façons différentes. La première formulation (approche directe) cède à un problème d'optimisation non-convexe résolu de manière distribuée au moyen de la méthode des multiplicateurs de Lagrange. La seconde formulation (approche indirecte) est obtenue après une reparamétrisation adéquate. Le problème est alors convexe et résolu en utilisant l'algorithme du sous-gradient distribué et la méthode de direction alternée de multiplicateurs. En outre, trois cas sont considérés: la valeur moyenne finale est parfaitement connue, bruyant, ou complètement inconnue. Nous fournissons également une façon pour calculer les multiplicités des valeurs propres estimées au moyen d'une programmation linéaire en nombres entiers. L'efficacité des solutions proposées est évaluée au moyen de simulations. Cependant, dans plusieurs cas, la convergence des algorithmes proposés est lente et doit être améliorée dans les travaux futurs. En outre, l'approche indirecte n'est pas évolutive pour des graphes de taille importante car elle implique le calcul des racines d'un polynôme de degré égal à la taille du réseau. Cependant, au lieu d'estimer tout le spectre, il peut être possible de récupérer seulement un petit nombre des valeurs propres, puis déduire des limites significatives sur les indices de la robustesse. / Consensus of Multi-agent systems has received tremendous attention during the last decade. Consensus is a cooperative process in which agents interact in order to reach an agreement. Most of studies are committed to analysis of the steady-state behavior of this process. However, during the transient of this process a huge amount of data is produced. In this thesis, our aim is to exploit data produced during the transient of asymptotic average consensus algorithms in order to design finite-time average consensus protocols, assess the robustness of the graph, and eventually recover the topology of the graph in a distributed way. Finite-time Average Consensus guarantees a minimal execution time that can ensure the efficiency and the accuracy of sophisticated distributed algorithms in which it is involved. We first focus on the configuration step devoted to the design of consensus protocols that guarantee convergence to the exact average in a given number of steps. By considering networks of agents modelled with connected undirected graphs, we formulate the problem as the factorization of the averaging matrix and investigate distributed solutions to this problem. Since, communicating devices have to learn their environment before establishing communication links, we suggest the usage of learning sequences in order to solve the factorization problem. Then a gradient backpropagation-like algorithm is proposed to solve a non-convex constrained optimization problem. We show that any local minimum of the cost function provides an accurate factorization of the averaging matrix. By constraining the factor matrices to be as Laplacian-based consensus matrices, it is now well known that the factorization of the averaging matrix is fully characterized by the nonzero Laplacian eigenvalues. Therefore, solving the factorization of the averaging matrix in a distributed way with such Laplacian matrix constraint allows estimating the spectrum of the Laplacian matrix. Since that spectrum can be used to compute some robustness indices (Number of spanning trees and Effective graph Resistance also known as Kirchoff index), the second part of this dissertation is dedicated to Network Robustness Assessment through distributed estimation of the Laplacian spectrum. The problem is posed as a constrained consensus problem formulated in two ways. The first formulation (direct approach) yields a non-convex optimization problem solved in a distributed way by means of the method of Lagrange multipliers. The second formulation (indirect approach) is obtained after an adequate re-parameterization. The problem is then convex and solved by using the distributed subgradient algorithm and the alternating direction method of multipliers. Furthermore, three cases are considered: the final average value is perfectly known, noisy, or completely unknown. We also provide a way for computing the multiplicities of the estimated eigenvalues by means of an Integer programming. In this spectral approach, given the Laplacian spectrum, the network topology can be reconstructed through estimation of Laplacian eigenvector. The efficiency of the proposed solutions is evaluated by means of simulations. However, in several cases, convergence of the proposed algorithms is slow and needs to be improved in future works. In addition, the indirect approach is not scalable to very large graphs since it involves the computation of roots of a polynomial with degree equal to the size of the network. However, instead of estimating all the spectrum, it can be possible to recover only a few number of eigenvalues and then deduce some significant bounds on robustness indices.

Mémoire numérisé par la Division de la gestion de documents et des archives de l'Université de Montréal

La Tunisie a longtemps été un laboratoire de recherches pour les sociologues occidentaux sur l'apport des sciences sociales dans un pays du Maghreb. Toutefois ces études sociologiques restent encore centrées sur une période très précise qui dénotait l'existence d'un pouvoir autoritaire et les abus du gouvernement. Le débat occidental s'est alors cristallisé sur la forme du régime et les contestations protestataires en Tunisie. Il a fallu attendre le 13 Janvier 2011 lors du discours au palais de Carthage, pour que la question de la remise en question se pose sans équivoque. Le président Ben Ali avait atteint avec cet ultime affront aux citoyens tunisiens, les limites de son autorité abusive. Au 14 Janvier 2011, la fuite du président déchu Ben Ali a consommé la rupture avec l'ancien régime et a créé ce phénomène que l'on nomme à tort ou à raison la transitologie. Pour la première fois dans le pays, les élections étaient ouvertes à différentes catégories socio-professionnelles, de cultures politiques différentes, à tous les partis hormis le RCD ancien parti du régime, et aux femmes comme aux hommes. Cette initiative a créé un tel engouement, que le jour d’entrée des élus parlementaires au sein du Palais du Bardo, il était nécessaire de déterminer qui étaient ces nouveaux locataires du palais. C’est ainsi que débutent ces travaux de recherche / Tunisia has been, for a long time, a research laboratory for Western sociologists in terms of the contribution of social sciences in a Maghreb country. However, these sociological studies are still focused on a very precise period which pointed out the existence of an authoritarian power and the abuses of the government. The Western debate then froze on the form of the regime and protests in Tunisia. It was not until January 13, 2011 that the issue of questioning arises unequivocally, during the speech at the palace of Carthage. President Ben Ali had reached the limits of his abusive authority with this ultimate outrage to Tunisian citizens. On January 14, 2011, the flight of the deposed President Ben Ali consumed the break with the old regime and created this phenomenon that is rightly or wrongly called transitology. For the first time in the country, elections were open to different socio-professional categories, from different political cultures, to all parties except the former RCD party of the regime, and to both women and men. This initiative has created such a craze, that the day of entry of elected MPs in the Palace of Bardo, it was necessary to determine who were these new tenants of the palace. This is how this research begins