Over the last decade, Internet-based services, such as electronic-mail, music-on-demand, and social-network services, have changed the ways we communicate and access information. Usually, the key functionality of such a service is in backend components, which are located in a data center, a facility for hosting computing systems and related equipment. This thesis focuses on two fundamental problems related to the management, dimensioning, and provisioning of such backend components. The first problem centers around resource allocation for a large-scale cloud environment. Data centers have become very large; they often contain hundreds of thousands of machines and applications. In such a data center, resource allocation cannot be efficiently achieved through a traditional management system that is centralized in nature. Therefore, a more scalable solution is needed. To address this problem, we have developed and evaluated a scalable and generic protocol for resource allocation. The protocol is generic in the sense that it can be instantiated for different management objectives through objective functions. The protocol jointly allocates CPU, memory, and network resources to applications that are hosted by the cloud. We prove that the protocol converges to a solution, if an objective function satisfies a certain property. We perform a simulation study of the protocol for realistic scenarios. Simulation results suggest that the quality of the allocation is independent of the system size, up to 100,000 machines and applications, for the management objectives considered. The second problem is related to performance modeling of a distributed key-value store. The specific distributed key-value store we focus on in this thesis is the Spotify storage system. Understanding the performance of the Spotify storage system is essential for achieving a key quality of service objective, namely that the playback latency of a song is sufficiently low. To address this problem, we have developed and evaluated models for predicting the performance of a distributed key-value store for a lightly loaded system. First, we developed a model that allows us to predict the response time distribution of requests. Second, we modeled the capacity of the distributed key-value store for two different object allocation policies. We evaluate the models by comparing model predictions with measurements from two different environments: our lab testbed and a Spotify operational environment. We found that the models are accurate in the sense that the prediction error, i.e., the difference between the model predictions and the measurements from the real systems, is at most 11%. / <p>QC 20131001</p>

[pt] A presente Tese aborda a fofoca como fenômeno comunicativo, investigando, em específico, seu significado social e cultural no Brasil. A análise teórica concentra-se em três aspectos principais: (1) a dinâmica situacional dos elementos pragmaticamente constitutivos de uma ação caracterizável como fofoca; (2) a recorrência dos conteúdos de mensagens trocadas a tal título e sob outras variantes semânticas e (3) os empregos concretos da fofoca como instrumento na prática social. Uma vez delimitada como fenômeno geral, passo a apreciar a dinâmica específica da fofoca no Brasil. Assim, analiso sua relevância a partir da noção de liminaridade segundo Victor Turner, considerando certos eventos em que a fofoca se manifesta em uma cultura marcada por fortes traços de predomínio da oralidade, fixidez hierárquica e trânsito relacional. / [en] This Thesis addresses gossip as a communicative phenomenon, investigating, specifically, its social and cultural significance in Brazil. The theoretical analysis focuses on three main aspects: (1) the situational dynamics of the pragmatically constitutive elements of an action characterized as gossip; (2) the recurrence of the contents of messages exchanged under this name and under other semantic variants and (3) the concrete uses of gossip as an instrument in social practice. Once defined as a general phenomenon, I begin to appreciate the specific dynamics of gossip in Brazil. Thus, I analyze its relevance based on the notion of liminality according to Victor Turner, considering certain events in which gossip manifests itself in a culture marked by strong oral predominance, hierarchical fixity and relational transit.

Consensus occurs within a multi-agent system when every agent is in agreement about the value of some particular state. For example, the color of an LED, the position or magnitude of a vector, a rendezvous location, the most recent state of data within a database, or the identity of a leader are all states that agents might need to agree on in order to execute their tasking. The task of the decentralized consensus problem for multi-agent systems is to design an algorithm that enables agents to communicate and exchange information such that, in finite time, agents are able to form a consensus without the use of a centralized control mechanism. The primary goal of this research is to introduce and provide supporting evidence for Stochastic Local Observation/Gossip (SLOG) algorithms as a new class of solutions to the decentralized consensus problem for multi-agent systems that lack a centralized controller, with the additional constraints that agents act asynchronously, information is discrete, and all consensus options are equally preferable to all agents. Examples of where these constraints might apply include the spread of social norms and conventions in artificial populations, rendezvous among a set of specific locations, and task assignment. This goal is achieved through a combination of theory and experimentation. Information propagation process and an information propagation algorithm are derived by unifying the general structure of multiple existing solutions to the decentralized consensus problem. They are then used to define two classes of algorithms that spread information across a network and solve the decentralized consensus problem: buffered gossip algorithms and local observation algorithms. Buffered gossip algorithms generalize the behavior of many push-based solutions to the decentralized consensus problem. Local observation algorithms generalize the behavior of many pull-based solutions to the decentralized consensus problem. In the language of object oriented design, buffered gossip algorithms and local observation algorithms are abstract classes; information propagation processes are interfaces. SLOG algorithms combine the transmission mechanisms of buffered gossip algorithms and local observation algorithms into a single "hybrid" algorithm that is able to push and pull information within the local neighborhood. A common mathematical framework is constructed and used to determine the conditions under which each of these algorithms are guaranteed to produce a consensus, and thus solve the decentralized consensus problem. Finally, a series of simulation experiments are conducted to study the performance of SLOG algorithms. These experiments compare the average speed of consensus formation between buffered gossip algorithms, local observation algorithms, and SLOG algorithms over four distinct network topologies. Beyond the introduction of the SLOG algorithm, this research also contributes to the existing literature on the decentralized consensus problem by: specifying a theoretical framework that can be used to explore the consensus behavior of push-based and pull-based information propagation algorithms; using this framework to define buffered gossip algorithms and local observation algorithms as generalizations for existing solutions to the decentralized consensus problem; highlighting the similarities between consensus algorithms within control theory and opinion dynamics within computational sociology, and showing how these research areas can be successfully combined to create new and powerful algorithms; and providing an empirical comparison between multiple information propagation algorithms.

Replication primarily provides data availability by having multiple copies over different systems and is exploited to make distributed systems scalable in num- bers and geographical areas. Placing a replica closer to the source of request can also significantly reduce the time required to service the request, improv- ing applications’ performance. However, modifications done at a single copy need to be propagated to all the standing copies to maintain the data’s consis- tency. Over the years, numerous strategies have been proposed for handling the tradeoff between consistency and availability, of which the majority pro- vides either strong consistency or eventual consistency. These models do not provide sufficient compatibility for developing modern applications for geo- distributed (edge) environments.Conflict-Free Replicated Data Types (CRDT) provides a new model of consistency referred to as strong eventual consistency. In principle, CRDTs guarantee conflict-free merge even when the updates arrive out of order using simple mathematical properties. Lasp is a coordination free distributed pro- gramming model for building modern distributed applications using CRDTs. Lasp uses a gossip protocol for disseminating state changes to all replicas in the system. The current implementation of gossip in Lasp is agnostic to the application’s behavior in propagating the updates efficiently to critical repli- cas in the system. In the thesis, we introduce an application-specific feature to optimize the dissemination of updates in Lasp. The proposed algorithm propagates the updates by catering to the different consistency requirements of the replicas in the system. The experimental results on a topology of 100 replicas found that the update latency at critical replicas with high consistency requirements is reduced by 40–50%, and the total bandwidth consumption in the system is reduced by 4–8% without significant repercussion on other repli- cas in the system. / Datareplikering erbjuder primärt tillgänglighet genom att tillhandahålla mul- tipla kopior fördelat över olika system, och utnyttjas för att göra distribuerade system skalbara i antal och över geografiska områden. Att placera en replika nära källan till en förfrågan kan dessutom signifikant reducera tiden det krävs att besvara förfrågan vilket förbättrar applikationens prestanda. Modifikatio- ner gjorda på en av kopiorna måste dock propageras till alla stående kopior för att upprätthålla datans konsistens . Över tid har många strategier föreslagits för att hantera avvägningen mellan konsistens och tillgänglighet, där majorite- ten erbjuder antingen stark eller eventuell konsistens. Dessa modeller erbjuder inte tillräcklig kompatibilitet för utveckling av moderna applikationer för geo- distribuerade (edge) miljöer.Konfliktfria replikerade datatyper (CRDT) erbjuder en ny modell av konsi- stens som kallas stark eventuell konsistens. I princip garanterar CRDTer kon- fliktfria sammanslagningar trots att uppdateringar sker i oordning, genom att använda dess matematiska egenskaper. Lasp är en koordineringsfri distribue- rad programmeringsmodell för att bygga moderna distribuerade applikationer med hjälp av CRDTer. Lasp använder skvallerprotokoll för att sprida tillstånds- förändringar till alla replikor i systemet. Den nuvarande implementationen av skvaller i Lasp är agnostiskt för applikationens beteende relaterat till effektiv propagering av uppdateringar till kritiska replikor i systemet. I det här exa- mensarbetet introducerar vi applikationsspecifik funktionalitet för att optime- ra spridandet av uppdateringar i Lasp. Den föreslagna algoritmen sprider upp- dateringarna genom att tillgodose de olika konsistenskraven för replikorna i systemet. Experimentella resultat i en topologi av 100 replikor visade att upp- dateringslatensen vid kritiska replikor med höga konsistenskrav minskas med 40–50% och att den totala bandbreddskonsumtionen i systemet minskas med 4–8% utan signifikanta negativa följder för andra replikor i systemet.

In this dissertation, we consider scheduling distributed soft real-time tasks in unreliable (e.g., those with arbitrary node and network failures) and untrustworthy systems (e.g., those with Byzantine node behaviors). We present a distributed real-time scheduling algorithm called Gamma. Gamma considers a distributed (i.e., multi-node) task model where tasks are subject to Time/Utility Function (or TUF) end-to-end time constraints, and the scheduling optimality criterion of maximizing the total accrued utility. The algorithm makes three novel contributions. First, Gamma uses gossip for reliably propagating task scheduling parameters and for discovering task execution nodes. Second, Gamma achieves distributed real-time mutual exclusion in unreliable environments. Third, the algorithm guards against potential disruption of message propagation due to Byzantine attacks using a mechanism called Launcher-Attacker-Infective-Susceptible-Immunized-Removed-Consumer (or LAISIRC). By doing so, the algorithm schedules tasks with probabilistic termination-time satisfactions, despite system unreliability and untrustworthiness. We analytically establish several timeliness and non-timeliness properties of the algorithm including probabilistic end-to-end task termination time satisfactions, optimality of message overheads, mutual exclusion guarantees, and the mathematical model of the LAISIRC mechanism. We conducted simulation-based experimental studies and compared Gamma with its competitors. Our experimental studies reveal that Gamma's scheduling algorithm accrues greater utility and satisfies a greater number of deadlines than do competitor algorithms (e.g., HVDF) by as much as 47% and 45%, respectively. LAISIRC is more tolerant to Byzantine attacks than competitor protocols (e.g., Path Verification) by obtaining as much as 28% higher correctness ratio. Gamma's mutual exclusion algorithm accrues greater utility than do competitor algorithms (e.g., EDF-Sigma) by as much as 25%. Further, we implemented the basic Gamma algorithm in the Emulab/ChronOS 250-node testbed, and measured the algorithm's performance. Our implementation measurements validate our theoretical analysis and the algorithm's effectiveness and robustness. / Ph. D.

Previous studies on Cecily von Ziegesar's series Gossip Girl fail to explain the functionality of the series for the actual readers. Therefore, a discussion of the relationship between reader and text is necessary. By explaining from a literary perspective how reader and text interact, we can better understand why teen girls want to read the series and the exchanges that occur between the books and the readers. An exploration of how Gossip Girl relates to its series predecessors, like Nancy Drew, demonstrates how the popularity of Gossip Girl is not unique, but rather fits in with the established series pattern while receiving the same harsh criticism. As a result of analyzing the "bad" reputation Gossip Girl has earned, we can explicate how the series is currently seen to operate for the reader, questions left open when simply looking at series books historically. This exploration of the books as carriers of ideology examines how and if readers are invited to participate in a relationship with the text. However, simple reader-response theories only replicate a static relationship between reader and text. By also using a Deleuzo-Guattarian approach to the series, an understanding of how Gossip Girl acts as an "apparatus of capture" built on social conditions while still allowing the reader minimal agency for the channeling of energy/desiring flows can be found. These approaches work in conjunction in order to address the engagement readers experience with the Gossip Girl texts, which, in turn, help elucidate the phenomenon associated with von Ziegesar's books. / Master of Arts

Este trabajo presenta un catálogo de técnicas y patrones de diseño aplicados actualmente en bases de datos NoSQL. El enfoque propuesto consiste en una presentación del estado del arte de las bases de datos NoSQL, una exposición de los conceptos claves relacionados y una posterior exhibición de un conjunto de técnicas y patrones de diseño orientados a la escalabilidad y alta disponibilidad. Para tal fin, • Se describen brevemente las características principales de los bases de datos NoSQL, cuales son los factores que motivaron su aparición, sus diferencias con sus pares relacionales, se presenta el teorema CAP y se contrasta las propiedades ACID contra las BASE. • Se introducen las problemáticas que motivan las técnicas y patrones de diseño a describir. • Se presentan técnicas y patrones de diseños que solucionen las problemáticas. • Finalmente, se concluye con un análisis integrador, y se indican otros temas de investigación pertinentes.

Ce mémoire s’attarde aux pratiques de lecture de lectrices du Échos Vedettes, magazine à potins québécois qui fête ses cinquante ans de publication en 2013. Cinq dimensions permettent de cerner et comprendre ces pratiques de lecture. Les trois premières prennent la forme d’un système composé de trois économies distinctes: l’économie spatio-temporelle, l’économie sociale et l’économie textuelle. Les répertoires de lecture ainsi que l’omniprésence de la photographie sont les deux dernières dimensions. Les données ont été recueillies dans le cadre d’entrevues individuelles de 6 lectrices régulières, recrutées par la méthode dite de « boule de neige ». L’analyse a, entre autres, permis de distinguer trois états que le Échos Vedettes incarne selon les moments, son rôle et son utilisation : une marchandise, un objet et un contenu. Les relations sociales entre femmes, les répertoires, la photographie ainsi que la ritualisation sont les principaux éléments qui caractérisent les pratiques de lecture des lectrices du Échos Vedettes. Ce sont des pratiques qui relèvent de l’amateur et de l’attachement à ce magazine à potins. Cette recherche a également mis en lumière les relations paradoxales de proximité, physique et / AbstractThis research is trying to understand the reading practices of the women who regularly reads the gossip magazine Échos Vedettes. Five concepts have been used, The first three are parts of an everyday reading economical system : spatio-temporal economy, social economy and economy of text. Reading repertoires and photography are the lasts concepts used. Six interviews have been done with women who regularly read Échos Vedettes. They have been recruted by the « snowball » method. The analysis showed that Échos Vedettes can have three different states depending on the moment, the use and its role. It can be seen as a commodity, as an object or as a content. Social relations between women, repertoires, photography and rituals are the principal elements that define the reading practices of women who read Échos Vedettes on a regular basis.

Dans de nombreux domaines, les nouvelles technologies d'acquisition de l'information ou encore de mesure (e.g. serres de phénotypage robotisées) ont engendré une création phénoménale de données. Nous nous appuyons en particulier sur deux cas d'application réels: les observations de plantes en botanique et les données de phénotypage en biologie. Cependant, nos contributions peuvent être généralisées aux données du Web. Par ailleurs, s'ajoute à la quantité des données leur distribution. Chaque utilisateur stocke en effet ses données sur divers sites hétérogènes (e.g. ordinateurs personnels, serveurs, cloud), données qu'il souhaite partager. Que ce soit pour les observations de botanique ou pour les données de phénotypage en biologie, des solutions collaboratives, comprenant des outils de recherche et de recommandation distribués, bénéficieraient aux utilisateurs. L'objectif général de ce travail est donc de définir un ensemble de techniques permettant le partage et la découverte de données, via l'application d'approches de recherche et de recommandation, dans un environnement distribué (e.g. sites hétérogènes).Pour cela, la recherche et la recommandation permettent aux utilisateurs de se voir présenter des résultats, ou des recommandations, à la fois pertinents par rapport à une requête qu'ils auraient soumise et par rapport à leur profil. Les techniques de diversification permettent de présenter aux utilisateurs des résultats offrant une meilleure nouveauté tout en évitant de les lasser par des contenus redondants et répétitifs. Grâce à la diversité, une distance entre toutes les recommandations est en effet introduite afin que celles-ci soient les plus représentatives possibles de l'ensemble des résultats pertinents. Peu de travaux exploitent la diversité des profils des utilisateurs partageant les données. Dans ce travail de thèse, nous montrons notamment que dans certains scénarios, diversifier les profils des utilisateurs apporte une nette amélioration en ce qui concerne la qualité des résultats~: des sondages montrent que dans plus de 75% des cas, les utilisateurs préfèrent la diversité des profils à celle des contenus. Par ailleurs, afin d'aborder les problèmes de distribution des données sur des sites hétérogènes, deux approches sont possibles. La première, les réseaux P2P, consiste à établir des liens entre chaque pair (noeud du réseau): étant donné un pair p, ceux avec lesquels il a établi un lien représentent son voisinage. Celui-ci est utilisé lorsque p soumet une requête q, pour y répondre. Cependant, dans les solutions de l'état de l'art, la redondance des profils des pairs présents dans les différents voisinages limitent la capacité du système à retrouver des résultats pertinents sur le réseau, étant donné les requêtes soumises par les utilisateurs. Nous montrons, dans ce travail, qu'introduire de la diversité dans le calcul du voisinage, en augmentant la couverture, permet un net gain en termes de qualité. En effet, en tenant compte de la diversité, chaque pair du voisinage a une plus forte probabilité de retourner des résultats nouveaux à l'utilisateur courant: lorsqu'une requête est soumise par un pair, notre approche permet de retrouver jusqu'à trois fois plus de bons résultats sur le réseau. La seconde approche de la distribution est le multisite. Généralement, dans les solutions de l'état de l'art, les sites sont homogènes et représentés par de gros centres de données. Dans notre contexte, nous proposons une approche permettant la collaboration de sites hétérogènes, tels que de petits serveurs d'équipe, des ordinateurs personnels ou de gros sites dans le cloud. Un prototype est issu de cette contribution. Deux versions du prototype ont été réalisées afin de répondre aux deux cas d'application, en s'adaptant notamment aux types des données. / In many fields, novel technologies employed in information acquisition and measurement (e.g. phenotyping automated greenhouses) are at the basis of a phenomenal creation of data. In particular, we focus on two real use cases: plants observations in botany and phenotyping data in biology. Our contributions can be, however, generalized to Web data. In addition to their huge volume, data are also distributed. Indeed, each user stores their data in many heterogeneous sites (e.g. personal computers, servers, cloud); yet he wants to be able to share them. In both use cases, collaborative solutions, including distributed search and recommendation techniques, could benefit to the user.Thus, the global objective of this work is to define a set of techniques enabling sharing and discovery of data in heterogeneous distributed environment, through the use of search and recommendation approaches.For this purpose, search and recommendation allow users to be presented sets of results, or recommendations, that are both relevant to the queries submitted by the users and with respect to their profiles. Diversification techniques allow users to receive results with better novelty while avoiding redundant and repetitive content. By introducing a distance between each result presented to the user, diversity enables to return a broader set of relevant items.However, few works exploit profile diversity, which takes into account the users that share each item. In this work, we show that in some scenarios, considering profile diversity enables a consequent increase in results quality: surveys show that in more than 75% of the cases, users would prefer profile diversity to content diversity.Additionally, in order to address the problems related to data distribution among heterogeneous sites, two approaches are possible. First, P2P networks aim at establishing links between peers (nodes of the network): creating in this way an overlay network, where peers directly connected to a given peer p are known as his neighbors. This overlay is used to process queries submitted by each peer. However, in state of the art solutions, the redundancy of the peers in the various neighborhoods limits the capacity of the system to retrieve relevant items on the network, given the queries submitted by the users. In this work, we show that introducing diversity in the computation of the neighborhood, by increasing the coverage, enables a huge gain in terms of quality. By taking into account diversity, each peer in a given neighborhood has indeed, a higher probability to return different results given a keywords query compared to the other peers in the neighborhood. Whenever a query is submitted by a peer, our approach can retrieve up to three times more relevant items than state of the art solutions.The second category of approaches is called multi-site. Generally, in state of the art multi-sites solutions, the sites are homogeneous and consist in big data centers. In our context, we propose an approach enabling sharing among heterogeneous sites, such as small research teams servers, personal computers or big sites in the cloud. A prototype regrouping all contributions have been developed, with two versions addressing each of the use cases considered in this thesis.

Esta pesquisa teve como objetivo identificar, descrever e examinar alguns aspectos da educação política no Brasil, mais especificamente as estratégias de uso de elementos da cultura empregadas pelos consultores de marketing político no seio das campanhas eleitorais. Neste estudo, defendeu-se duas teses: a) o marketing como uma matriz de educação política e b) os consultores como intérpretes da cultura. Observou-se, portanto, que esses agentes da política, da educação e da cultura agem como administradores de uma informação acumulada, por meio de uma ação pedagógica e socializadora difusa da população. Identificou-se os interesses diversificados de agentes na adesão a um espaço social específico, descreveu-se a institucionalização do marketing político no interior do campo científico e interpelou-se a categoria nativa intérpretes na produção de crenças e entendimentos sobre a política. Com o objetivo de aprofundar a compreensão das duas teses, discutiu-se a memória e a fofoca como conteúdos e didáticas das campanhas eleitorais. Para cumprir o empreendimento intelectual proposto, foi realizada uma etnografia multissituada, de caráter exploratório, inovador e inédito na área de educação, analisando um conjunto de dados multilocalizados e oriundos de propagandas eleitorais; de contextos de produção de uma campanha específica, realizada na Amazônia brasileira; de livros produzidos por consultores; de entrevistas realizadas com eles e de outras referências encontradas no trabalho de campo e vividas pelo autor da pesquisa. Com a intenção de que o presente estudo venha contribuir para um entendimento mais amplo e eficiente a respeito da construção social da realidade nos dias atuais, propôs-se investigar as formas de sintetizar a cultura no que se refere à produção de possíveis tentativas de educação dos modos de concepção, classificação, julgamento e imaginação da população no âmbito político. Por fim, buscou-se contribuir para a ampliação do escopo investigativo da sociologia da educação no que tange aos processos educacionais difusos e de massa, e que influem substancialmente no futuro do país, que não estão restritos à escola, mas que podem chegar à ela. / This research aimed at identifying, describing and examining some aspects of political education in Brazil, more precisely the use of cultural elements by political marketing consultants in electoral campaigns. Two theses were defended by this study: a) Marketing as a source for political education and b) consultants as the interpreters of culture. It was observed, therefore, that these agents of politics, education and culture operate as managers of accumulated information, by means of pedagogic action and socializing practices of the population. Diversified interests of these agents were identified in support of a particular social area, the institutionalization of political marketing within the scientific field was also depicted, and the native status of interpreters in the creation of political views and beliefs was questioned. With the objective of deepening the understanding of the two theses, collective memory and rumors were discussed as content of and educational approaches to electoral campaigns. In order to accomplish the proposed intellectual enterprise, a multi-sited ethnographic study that was exploratory and innovative in character and unprecedented in the educational field, was created by analyzing a set of multi-locational data derived from electoral campaigns; in fact as a result of a particular campaign, which took place in the Brazilian Amazon; from books written by those consultants; interviews and other references that were found during fieldwork and experienced by the author of the research. With the purpose to provide a broader and more efficient understanding concerning the construction of our current social reality, the present case study aimed at exploring ways to synthesize culture regarding the production of possible attempts to educate the population in of methods of conception, classification, judgment and imagination in the realm of politics. Lastly, the intention was to widen the investigative scope of sociology of education related to widespread and mass educational procedures, which have a substantial influence on the future of the country, and which arent limited to the school system, but that can reach it.