Distributed Gossip in networks is a well studied and observed problem which can be accomplished using different gossiping styles. This work focusses on the development, analysis and evaluation of a novel in-situ distributed gossip protocol framework design called (INDIGO). A core aspect of INDIGO is its ability to execute on a simulation setup as well as a system testbed setup in a seamless manner allowing easy portability. The evaluations focus on application of INDIGO to solve problems such as distributed average consensus, distributed seismic event location and lastly distributed seismic tomography. The results obtained herein validate the efficacy and reliability of INDIGO.

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>

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.

L'évolution rapide du web a changé la façon dont l'information est créée, distribuée, évaluée et consommée. L'utilisateur est dorénavant mis au centre du web en devenant le générateur de contenu le plus prolifique. Pour évoluer dans le flot d'informations, les utilisateurs ont besoin de filtrer le contenu en fonction de leurs centres d'intérêts. Pour bénéficier de contenus personnalisés, les utilisateurs font appel aux réseaux sociaux ou aux systèmes de recommandations exploitant leurs informations privées. Cependant, ces systèmes posent des problèmes de passage à l'échelle, ne prennent pas en compte la nature dynamique de l'information et soulèvent de multiples questions d'un point de vue de la vie privée. Dans cette thèse, nous exploitons les architectures pair-à-pair pour implémenter des systèmes de recommandations pour la dissémination personnalisée des news. Une approche pair-à-pair permet un passage à l'échelle naturel et évite qu'une entité centrale contrôle tous les profils des utilisateurs. Cependant, l'absence de connaissance globale fait appel à des schémas de filtrage collaboratif qui doivent palier les informations partielles et dynamiques des utilisateurs. De plus, ce schéma de filtrage doit pouvoir respecter la vie privée des utilisateurs. La première contribution de cette thèse démontre la faisabilité d'un système de recommandation de news totalement distribué. Le système proposé maintient dynamiquement un réseau social implicit pour chaque utilisateur basé sur les opinions qu'il exprime à propos des news reçues. Les news sont disséminées au travers d'un protocole épidémique hétérogène qui (1) biaise l'orientation des cibles et (2) amplifie la dissémination de chaque news en fonction du niveau d'intérêt qu'elle suscite. Ensuite, pour améliorer la vie privée des utilisateurs, nous proposons des mécanismes d'offuscation permettant de cacher le profil exact des utilisateurs sans trop dégrader la qualité de la recommandation fournie. Enfin, nous explorons un nouveau modèle tirant parti des avantages des systèmes distribués tout en conservant une architecture centralisée. Cette solution hybride et générique permet de démocratiser les systèmes de recommandations en offrant aux fournisseurs de contenu un système de personnalisation à faible coût. / The rapid evolution of the web has changed the way information is created, distributed, evaluated and consumed. Users are now at the center of the web and becoming the most prolific content generators. To effectively navigate through the stream of available news, users require tools to efficiently filter the content according to their interests. To receive personalized content, users exploit social networks and recommendation systems using their private data. However, these systems face scalability issues, have difficulties in coping with interest dynamics, and raise a multitude of privacy challenges. In this thesis, we exploit peer-to-peer networks to propose a recommendation system to disseminate news in a personalized manner. Peer-to-peer approaches provide highly-scalable systems and are an interesting alternative to Big brother type companies. However, the absence of any global knowledge calls for collaborative filtering schemes that can cope with partial and dynamic interest profiles. Furthermore, the collaborative filtering schemes must not hurt the privacy of users. The first contribution of this thesis conveys the feasibility of a fully decentralized news recommender. The proposed system constructs an implicit social network based on user profiles that express the opinions of users about the news items they receive. News items are disseminated through a heterogeneous gossip protocol that (1) biases the orientation of the dissemination, and (2) amplifies dissemination based on the level of interest in each news item. Then, we propose obfuscation mechanisms to preserve privacy without sacrificing the quality of the recommendation. Finally, we explore a novel scheme leveraging the power of the distribution in a centralized architecture. This hybrid and generic scheme democratizes personalized systems by providing an online, cost-effective and scalable architecture for content providers at a minimal investment cost.