Thesis (Th. M.)--Dallas Theological Seminary, 1983. / Includes bibliographical references (leaves 56-58).

Certificate Transparency (CT) logs are append-only tamper-evident data structures that can be verified by anyone. For example, it is possible to challenge a log to prove certificate inclusion (membership) and log consistency (append-only, no tampering) based on partial information. While these properties can convince an entity that a certificate is logged and not suddenly removed in the future, there is no guarantee that anyone else observes the same consistent view. To solve this issue a few gossip protocols have been proposed, each with different quirks, benefits, assumptions, and goals. We explore CT gossip below the application layer, finding that packet processors such as switches, routers, and middleboxes can aggregate gossip passively or actively to achieve herd immunity: (in)direct protection against undetectable log misbehaviour. Throughout the thesis we describe, instantiate, and discuss passive aggregation of gossip messages for a restricted data plane programming language: P4. The concept of active aggregation is also introduced. We conclude that (i) aggregation is independent of higher-level transparency applications and infrastructures, (ii) it appears most prominent to aggregate Signed Tree Heads (STHs) in terms of privacy and scalability, and (iii) passive aggregation can be a long-term solution if the CT ecosystem adapts. In other words, not all sources of gossip must be encrypted to preserve privacy. / HITS, 4707

This dissertation is an ethnographic exploration of gossip and rumour around the fear and distrust that surrounds a local hospital in KwaNdebele that has acquired a reputation as a slagpale (an Afrikaans term for slaughterhouse). Using ethnographic data gathered over an 18 month period, I examine how gossip (ukuhleba) and rumour (amahemuhemu) capture patient voices of discontent with hospital service while also being a means by which patients seek to discipline medical professionals and to warn others about possible abuse when visiting the hospital. The focus on gossip and rumour answers an often neglected question in scholarship, which is how patients respond to the widely reported power that medical professionals exercise over them? Furthermore, having broadly traced the uses of gossip and rumour in resistance to biomedical technologies to the 1800s, this dissertation moves beyond a focus on patient responses to examine the logic underpinning this resistance. To do this I compare three categories of traditional healers in KwaNdebele. I found that gossip and rumours also circulated about traditional healers although unequally among the three types. There is particular suspicion around non-initiating healers called amagedla who are thought to practice outside ancestral structures of control. I read the emphasis on ancestral regulation as a metaphor for communal control and accordingly conclude that biomedicine and its practitioners similarly meet with much resistance particularly because they are far removed and disempowering to what are often semi-literate and illiterate residents. Finally, the dissertation focuses on stories of hospital hauntings and deaths said to be connected with a diminishing traditional practice of ‘fetching’ the spirits of those who die at the hospital and shows that discourses around hospital deaths and burial rites are intimately connected to broader considerations that extend beyond the hospital setting to encompass socio-economic changes and resultant anxieties. These considerations are framed through an idiom of a call for a return to tradition and ultimately express a perceived crisis of social reproduction in post-apartheid KwaNdebele. / Dissertation (MSocSci)--University of Pretoria, 2018. / UP Postgraduate Merit Bursary / NRF Scarce Skills Master's Scholarship / Anthropology and Archaeology / MSocSci / Unrestricted

No description available.

Este trabalho estuda a implementação do sistema de Quorum associado ao algoritmo epidêmico Gossip, a implementação de um novo algoritmo de economia de energia - o PWSave - e o protocolo de roteamento AODV em um cenário com e sem falhas de uma rede ad hoc com mobilidade. Optou-se por implementar este trabalho em um ambiente de simulação, dado que a modelagem matemática da associação do Gossip, Quorum e PWSave com os 80 nós - quantidade de nós escolhida para o ambiente de simulação - apresentaria maior complexidade e demora ao abranger todas as variáveis de ambiente desse conjunto de soluções para cada nó presente na rede. A rotina de programação - com o uso de loops para os trabalhos repetitivos - presente no ambiente de simulação permite que os experimentos sejam efetuados mais rapidamente e com menor probabilidade de erros. Os estudos [1], [2] demonstraram, respectivamente, que soluções abrangendo o algoritmo epidêmico Gossip e o sistema de compartilhamento de dados Quorum apresentam resultados favoráveis para uma rede ad hoc com alta mobilidade. Em [1] é apresentado um cenário muito próximo ao implementado neste trabalho, com a utilização do algoritmo Gossip ao protocolo de roteamento Ad-Hoc On-Demand Distance Vector (AODV). Os parâmetros analisados foram os mesmos, a saber: routes requests (RREQ), perda de pacote, vazão e latência. Os resultados do cenário simulado mostram uma diminuição no número de RREQs em uma rede ad hoc, e os demais parâmetros, medidos no ambiente de simulação, são pouco afetados. De acordo com [2] constata-se que há um aumento da resiliência e da vazão da rede e uma menor sobrecarga causada pela distribuição da informação na rede ad hoc pelo sistema de Quorum. A associação do algoritmo Gossip com o sistema de Quorum resultou em uma diminuição considerável de RREQs e perda de pacotes, mas o parâmetro de consumo de energia, que deve ser um fator importante em uma rede ad hoc e/ou uma rede sensor, não apresentou nenhuma melhora. Portanto, foi implementada uma solução adicional ao Gossip e ao Quorum, com o desenvolvimento de um novo algoritmo de economia de energia denominado de PWSave, no simulador Glomosim com o protocolo de roteamento AODV. O PWSave é responsável pelo adormecimento dos nós da rede que não estejam processando informações, ou seja, os nós, no momento do adormecimento, não poderão trocar dados ou auxiliar na formação de rotas da rede. O PWSave associado ao Gossip e ao sistema de Quorum apresenta resultados que refletem ma diminuição no consumo de energia próxima a 10% em comparação com a solução da associação do Gossip com o sistema de Quorum sem a implementação de PWSave. Os resultados da simulação mostram que a associação de Gossip, Quorum e PWSave acarreta uma redução no número de RREQs e na taxa de perda de pacotes sem degradar muito características de fluxo e latência, além de propiciar uma considerável economia no consumo de energia. / This work studies the implementation of the Quorum system associated with the Gossip algorithm, the implementation of a new power saving algorithm - the PWSave - and the routing protocol AODV in a scenario with and without failures of an ad hoc network with mobility. It has been chosen to implement this work in an environment of simulation, because the mathematical modeling of the association of Gossip, Quorum and PWSave with 80 nodes - number of nodes that has been chosen for the simulation environment - would present a higher complexity and delay to address all environment variables of the solutions set for each node present in the network. The programming routine - with the use of loops for the repetitive works - present in the simulation environment allows the experiments to be performed faster and with less probability of errors. The studies [1], [2] have shown, respectively, that solutions covering the Gossip epidemic algorithm and the system for sharing data Quorum show favorable results for an ad hoc network with high mobility. In [1] is presented a scenario very close to that implemented in this work, using the Gossip algorithm associated to the routing protocol Ad-Hoc On-Demand Distance Vector (AODV). The parameters analyzed were the same: routes requests (RREQ), packet loss, throughput and latency. The simulated scenario results show a decrease in the number of RREQs in an ad hoc network, and the other parameters, measured in the simulation environment, are little afected. According to [2] it is noted that there is an increase in the resilience and throughput of the network and a lower overload caused by the distribution of the information in the ad hoc network by the Quorum system. The association of the Gossip algorithm with the Quorum system resulted in a considerable decrease of RREQs and packet loss, but the parameter of energy consumption, which is an important factor in an ad hoc network and/or a sensor network, shows no improvement. Therefore, an additional solution was associated to the Gossip and to the Quorum, with the development of a new power saving algorithm named PWSave, in the simulator Glomosim with the routing protocol AODV. The PWSave is responsable for the sleeping state of the network nodes when they are not processing information: the nodes at the time of sleep cannot exchange data or assist in the building of network routes. The PWSave associated with the Gossip and Quorum system provides a decrease of the energy consumption close to 10% compared to the association solution of the Gossip with the Quorum system without the PWSave implementation. The results of simulation show that the association of the Gossip, Quorum and PWSave produces a reduction in the number of RREQs and in the rate of packets loss without degrading much the throughput and latency characteristics, providing a considerable energy consumption economy.

Este trabalho estuda a implementação do sistema de Quorum associado ao algoritmo epidêmico Gossip, a implementação de um novo algoritmo de economia de energia - o PWSave - e o protocolo de roteamento AODV em um cenário com e sem falhas de uma rede ad hoc com mobilidade. Optou-se por implementar este trabalho em um ambiente de simulação, dado que a modelagem matemática da associação do Gossip, Quorum e PWSave com os 80 nós - quantidade de nós escolhida para o ambiente de simulação - apresentaria maior complexidade e demora ao abranger todas as variáveis de ambiente desse conjunto de soluções para cada nó presente na rede. A rotina de programação - com o uso de loops para os trabalhos repetitivos - presente no ambiente de simulação permite que os experimentos sejam efetuados mais rapidamente e com menor probabilidade de erros. Os estudos [1], [2] demonstraram, respectivamente, que soluções abrangendo o algoritmo epidêmico Gossip e o sistema de compartilhamento de dados Quorum apresentam resultados favoráveis para uma rede ad hoc com alta mobilidade. Em [1] é apresentado um cenário muito próximo ao implementado neste trabalho, com a utilização do algoritmo Gossip ao protocolo de roteamento Ad-Hoc On-Demand Distance Vector (AODV). Os parâmetros analisados foram os mesmos, a saber: routes requests (RREQ), perda de pacote, vazão e latência. Os resultados do cenário simulado mostram uma diminuição no número de RREQs em uma rede ad hoc, e os demais parâmetros, medidos no ambiente de simulação, são pouco afetados. De acordo com [2] constata-se que há um aumento da resiliência e da vazão da rede e uma menor sobrecarga causada pela distribuição da informação na rede ad hoc pelo sistema de Quorum. A associação do algoritmo Gossip com o sistema de Quorum resultou em uma diminuição considerável de RREQs e perda de pacotes, mas o parâmetro de consumo de energia, que deve ser um fator importante em uma rede ad hoc e/ou uma rede sensor, não apresentou nenhuma melhora. Portanto, foi implementada uma solução adicional ao Gossip e ao Quorum, com o desenvolvimento de um novo algoritmo de economia de energia denominado de PWSave, no simulador Glomosim com o protocolo de roteamento AODV. O PWSave é responsável pelo adormecimento dos nós da rede que não estejam processando informações, ou seja, os nós, no momento do adormecimento, não poderão trocar dados ou auxiliar na formação de rotas da rede. O PWSave associado ao Gossip e ao sistema de Quorum apresenta resultados que refletem ma diminuição no consumo de energia próxima a 10% em comparação com a solução da associação do Gossip com o sistema de Quorum sem a implementação de PWSave. Os resultados da simulação mostram que a associação de Gossip, Quorum e PWSave acarreta uma redução no número de RREQs e na taxa de perda de pacotes sem degradar muito características de fluxo e latência, além de propiciar uma considerável economia no consumo de energia. / This work studies the implementation of the Quorum system associated with the Gossip algorithm, the implementation of a new power saving algorithm - the PWSave - and the routing protocol AODV in a scenario with and without failures of an ad hoc network with mobility. It has been chosen to implement this work in an environment of simulation, because the mathematical modeling of the association of Gossip, Quorum and PWSave with 80 nodes - number of nodes that has been chosen for the simulation environment - would present a higher complexity and delay to address all environment variables of the solutions set for each node present in the network. The programming routine - with the use of loops for the repetitive works - present in the simulation environment allows the experiments to be performed faster and with less probability of errors. The studies [1], [2] have shown, respectively, that solutions covering the Gossip epidemic algorithm and the system for sharing data Quorum show favorable results for an ad hoc network with high mobility. In [1] is presented a scenario very close to that implemented in this work, using the Gossip algorithm associated to the routing protocol Ad-Hoc On-Demand Distance Vector (AODV). The parameters analyzed were the same: routes requests (RREQ), packet loss, throughput and latency. The simulated scenario results show a decrease in the number of RREQs in an ad hoc network, and the other parameters, measured in the simulation environment, are little afected. According to [2] it is noted that there is an increase in the resilience and throughput of the network and a lower overload caused by the distribution of the information in the ad hoc network by the Quorum system. The association of the Gossip algorithm with the Quorum system resulted in a considerable decrease of RREQs and packet loss, but the parameter of energy consumption, which is an important factor in an ad hoc network and/or a sensor network, shows no improvement. Therefore, an additional solution was associated to the Gossip and to the Quorum, with the development of a new power saving algorithm named PWSave, in the simulator Glomosim with the routing protocol AODV. The PWSave is responsable for the sleeping state of the network nodes when they are not processing information: the nodes at the time of sleep cannot exchange data or assist in the building of network routes. The PWSave associated with the Gossip and Quorum system provides a decrease of the energy consumption close to 10% compared to the association solution of the Gossip with the Quorum system without the PWSave implementation. The results of simulation show that the association of the Gossip, Quorum and PWSave produces a reduction in the number of RREQs and in the rate of packets loss without degrading much the throughput and latency characteristics, providing a considerable energy consumption economy.

Cette thèse adresse le problème du consensus dans les réseaux. On étudie des réseaux composés d'agents identiques capables de communiquer entre eux, qui ont une mémoire et des capacités de calcul. Le réseau ne possède pas de nœud central de fusion. Chaque agent stocke une valeur qui n'est pas initialement connue par les autres agents. L'objectif est d'atteindre le consensus, i.e. tous les agents ont la même valeur, d'une manière distribuée. De plus, seul les agents voisins peuvent communiquer entre eux. Ce problème a une longue et riche histoire. Si toutes les valeurs appartiennent à un espace vectoriel, il existe plusieurs protocoles pour résoudre le problème. Une des solutions connues est l'algorithme du gossip qui atteint le consensus de manière asymptotique. C'est un protocole itératif qui consiste à choisir deux nœuds adjacents à chaque itération et de les moyenner. La spécificité de cette thèse est dans le fait que les données stockées par les agents n'appartiennent pas nécessairement à un espace vectoriel, mais à un espace métrique. Par exemple, chaque agent stocke une direction (l'espace métrique est l'espace projectif) ou une position dans un graphe métrique (l'espace métrique est le graphe sous-jacent). Là, les protocoles de gossip mentionnés plus haut n'ont plus de sens car l'addition qui n'est plus disponibles dans les espaces métriques. Cependant, dans les espaces métriques les points milieu ont du sens dans certains cas. Et là ils peuvent se substituer aux moyennes arithmétiques. Dans ce travail, on a compris que la convergence du gossip avec les points milieu dépend de la courbure. On s'est focalisés sur le cas où l'espace des données appartient à une classe d'espaces métriques appelés les espaces CAT(k). Et on a pu démontrer que si les données initiales sont suffisamment "proches" dans un sens bien précis, alors le gossip avec les points milieu - qu'on a appelé le Random Parwise Midpoints- converge asymptotiquement vers un consensus / This thesis deals with the problem of consensus on networks. Networks under study consists of identical agents that can communicate with each other, have memory and computational capacity. The network has no central node. Each agent stores a value that, initially, is not known by other agents. The goal is to achieve consensus, i.e. all agents having the same value, in a fully distributed way. Hence, only neighboring agents can have direct communication. This problem has a long and fruitful history. If all values belong to some vector space, several protocols are known to solve this problem. A well-known solution is the pairwise gossip protocol that achieves consensus asymptotically. It is an iterative protocol that consists in choosing two adjacent nodes at each iteration and average them. The specificity of this Ph.D. thesis lies in the fact that the data stored by the agents does not necessarily belong to a vector space, but some metric space. For instance, each agent stores a direction (the metric space is the projective space) or position on a sphere (the metric space is a sphere) or even a position on a metric graph (the metric space is the underlying graph). Then the mentioned pairwise gossip protocols makes no sense since averaging implies additions and multiplications that are not available in metric spaces: what is the average of two directions, for instance? However, in metric spaces midpoints sometimes make sense and when they do, they can advantageously replace averages. In this work, we realized that, if one wants midpoints to converge, curvature matters. We focused on the case where the data space belongs to some special class of metric spaces called CAT(k) spaces. And we were able to show that, provided initial data is "close enough" is some precise meaning, midpoints-based gossip algorithm – that we refer to as Random Pairwise Midpoints - does converge to consensus asymptotically. Our generalization allows to treat new cases of data spaces such as positive definite matrices, the rotations group and metamorphic systems

Τα τελευταία χρόνια έχουν γίνει σημαντικές προσπάθειες o Πληροφορικός-Επιστήμονας των Υπολογισμών να εκθέσει με εύληπτο τρόπο τη γνώση και εμπειρία του στις κοινότητες εκείνων που θέλουν να κάνουν υπολογισμούς. Κάτι τέτοιο έχει καταστεί δυνατό με την κατασκευή σύνθετων στη δομή, αλλά εύκολων στη χρήση, εργαλείων-περιβαλλόντων υπολογισμού στα οποία κανείς μπορεί με εντελώς φυσικό τρόπο να προδιαγράψει το πρόβλημά του και -ανάλογα με την εμπειρία του- να επέμβει στη ροή επίλυσής του. Τα Περιβάλλοντα Επίλυσης Προβλημάτων (ΠΕΠ) προβάλλουν λοιπόν ως μια πολύ ελκυστική λύση για τον επιστήμονα των εφαρμογών που αναζητεί μια εύχρηστη, ισχυρή και αξιόπιστη πλατφόρμα λογισμικού για τους υπολογισμούς του. Σε πολλές περιπτώσεις αυτοί οι υπολογισμοί είναι πολύ μεγάλης κλίμακας και απαιτούν πολυάριθμους και αποδοτικούς πόρους. Η τιθάσευσή τους σε κάποια έκταση έγινε δυνατή με τη στροφή σε παράλληλες-κατανεμημένες αρχιτεκτονικές, πρόσφατα μεγάλης κλίμακας, με έμφαση στην ευχρηστία, στην ασφάλεια πρόσβασης και στη συνεργατικότητα (Πλέγμα (Grid)). Σε άλλες περιπτώσεις οι πολυπύρηνοι επεξεργαστές που εξοπλίζουν πλέον τους τυπικούς οικιακούς υπολογιστές μας και οι προβλέψεις για αθρόα κλιμάκωση του αριθμού των προσφερόμενων πυρήνων, προτρέπουν σε επαναδιαπραγμάτευση κλασικών αλγορίθμων με στόχευση στην εξαγωγή παραλληλίας, αφού πλέον αυτή μπορεί να απεικονιστεί άμεσα στο διαθέσιμο υλικό. Επιπρόσθετα μια τέτοια στροφή ώθησε και τη διερεύνηση εναλλακτικών μοντέλων υπολογισμού: Το ασύγχρονο μοντέλο υπολογισμού προσφέροντας τη δυνατότητα για εξάλειψη των χρονοβόρων φάσεων συγχρονισμού των πολλαπλών μονάδων επεξεργασίας προβάλλει ως μια ενδιαφέρουσα επιλογή. Συστηματοποιούμε τη μελέτη των Περιβαλλόντων Επίλυσης Προβλημάτων (ΠΕΠ) εντοπίζοντας τους άξονες που χαρακτηρίζουν αυτήν την κατηγορία συστημάτων λογισμικού και υλοποιώντας το Jylab, ένα πρωτότυπο ΠΕΠ με έμφαση στη φορητότητα, την επαναχρησιμοποίηση ελεύθερα διαθέσιμου κώδικα και τη δυνατότητα για ακολουθιακό, παράλληλο και κατανεμημένο υπολογισμό σε πολλαπλές πλατφόρμες. Ειδικότερα, το Jylab περιλαμβάνει υποστήριξη για ασύγχρονο κατανεμημένο υπολογισμό, ανάλυση ιστογραφημάτων και εκτέλεση υπολογισμών στο Πλέγμα (Grid). Αμέσως μετά εισάγουμε το ασύγχρονο μοντέλο υπολογισμού εστιάζοντας σε καίρια ζητήματα όπως η ανάλυση της σύγκλισης, η ανίχνευση του τερματισμού και η υλοποίησή του. Προτείνουμε πιθανοτικό πλαίσιο εντοπισμού της σύγκλισης και διερευνούμε την πολυπλοκότητα του μοντέλου. Στη συνέχεια μελετούμε αλγορίθμους διάταξης των κόμβων ενός γραφήματος, επικεντρώνοντας στον υπολογισμό του διανύσματος του PageRank το οποίο χρησιμοποιεί η Google για να διατάξει τα αποτελέσματα μιας ερώτησης που υποβάλλουμε στη μηχανή αναζήτησής της. Αποδεικνύουμε πως και άλλες μέθοδοι διάταξης, οι οποίες εκφράζονται πρωταρχικά ως δυναμοσειρές ενός τροποποιημένου μητρώου συνδέσμων μπορούν να γραφτούν ως γινόμενα των επαναληπτικών μητρώων που χρησιμοποιούνται στον υπολογισμό του διανύσματος PageRank, αλλά με διαφορετική παράμετρο σε κάθε όρο τους (μέθοδος της πολυπαραμετρικής απόσβεσης). Στη συνέχεια εκθέτουμε την πειραματική συμπεριφορά του ασύγχρονου μοντέλου, όπως αυτή προκύπτει από υλοποιήσεις κυρίως του αλγορίθμου του PageRank, σε διάφορες πλατφόρμες (τοπικά, στη συστάδα υπολογισμών και στο Πλέγμα (Grid)) και με μονάδες εκτέλεσης νήματα ή διεργασίες. To Jylab χρησιμοποιήθηκε εντατικά σε αυτές τις διερευνήσεις και αποδείχτηκε πως όλοι οι πειραματισμοί μπορούν να τεθούν κάτω από ενιαίο πλαίσιο λογισμικού. Επίσης εισάγουμε μια κλάση αλγορίθμων κατανεμημένου υπολογισμού στατιστικών μεγεθών, τους gossip αλγορίθμους, σε κάθε στοιχειώδες βήμα των οποίων μόνο δύο οντότητες επικοινωνούν και υπολογίζουν. Επεκτείνουμε αυτούς τους αλγορίθμους επιτρέποντας σε k > 2 οντότητες να αλληλεπιδρούν ανά βήμα, προσομοιώνουμε τη συμπεριφορά τους και προτείνουμε πρωτόκολλα υλοποίησής τους. / In recent years computational scientists strive to expose their knowledge and experience to the communities of people interested in performing computations. This endeavor focuses on the construction of complex in structure, however simple in use, toolchains and environments in which a researcher can specify his or her problem and - depending on his experience - change its exact solution flow. In many cases these computations necessitate large-scale and performant resources. Harnessing them, to some extent, became possible by turning to parallel-distributed architectures, recently of large scale, emphasizing usability, security in accessing them and collaboration perspectives (Grid). In other cases, the multicore processors, nowadays powering even typical personal computers, coupled with predictions for dramatic increase in the number of available cores in the near future, suggest a reconsideration of classic algorithms aiming at extracting parallelism, since this can be directly mapped to underlying hardware. Additionally, such a move, also fuels the investigation of alternative computation models: The asynchronous computation model, offering the flexibility for the complete removal of time-consuming synchronization phases, is a very interesting option. We study Problem Solving Environments (PSEs) in a systematic manner, specifying the axes characterizing this category of systems of software also implementing Jylab, a prototype PSE emphasizing portability and the reuse of freely available code and enabling sequential, parallel and distributed computing over multiple platforms. More specifically, Jylab includes support for asynchronous distributed computations, Web graph analysis and Grid computing. Then we introduce the asynchronous computation model, focusing in three core subjects, namely its convergence analysis, the termination detection problem and its implementation. We propose a probabilistic framework for convergence detection and explore the complexity of the model. Afterwards, we survey algorithms for ranking the nodes of a graph, focusing on computing the PageRank vector, which is used by Google for ranking the results of a query submitted to its search engine. We prove that a whole class of ranking methods, primarily expressed as a power series of a modified link matrix can be written as products of iterative matrices similar to those used in computing the PageRank vector, albeit with a different damping parameter for each of its terms (multidamping). Next, we present the experimental behavior of the asynchronous model, mainly as applied in computing the PageRank vector, over different platforms (locally, in a computer cluster and over the Grid) using either threads or processes as its units of execution. Jylab was intensively used in these investigations and it was proved that all experimentations can be cast under a unifying software framework. We also introduce a class of algorithms for the distributed computation of statistical quantities, namely gossip algorithms, for which only two entities communicate and compute at each elementary step. We extend these algorithms be permitting k > 2 entities to interact on a per elementary step basis, simulate their behavior and propose protocols for implementing them.

Replikation kann helfen, in einem verteilten System die Fehlertoleranz und Datensicherheit zu verbessern. In Systemen, die über Weitverkehrsnetze kommunizieren oder mobile Endgeräte einschließen, muß das Replikationssystem mit großen Kommunikationslatenzen umgehen können. Deshalb werden in solchen Systemen in der Regel nur asynchrone Replikationsalgorithmen mit schwach-konsistenter Änderungssemantik eingesetzt, da diese die lokale Annahme von Änderungen der Daten und deren Koordinierung mit anderen Replikaten entkoppeln und somit ein schnelles Antwortverhalten bieten können. Diese Dissertation stellt einen Ansatz für die Entwicklung schwach-konsistenter Replikationssysteme mit erweiterten kausalen Konsistenzgarantien vor und weist nach, daß auf seiner Grundlage effiziente Replikationssysteme konstruiert werden können. Dazu werden Mechanismen, Algorithmen und Protokolle vorgestellt, die Änderungen an replizierten Daten aufzeichnen und verteilen und dabei Kausalitätsbeziehungen erhalten. Kern ist ein Änderungsprotokoll, das sowohl als grundlegende Datenstruktur der verteilten Algorithmen agiert, als auch für die Konsistenz der lokalen Daten nach Systemabstürzen sorgt. Die kausalen Garantien werden mit Hilfe von zwei Algorithmen erweitet, die gleichzeitige Änderungen konsistent handhaben. Beide Algorithmen basieren auf der Beobachtung, daß die Divergenz der Replikate durch unkoordinierte, gleichzeitige Änderungen nicht unbedingt als Inkonsistenz gesehen werden muß, sondern auch als das Erzeugen verschiedener Versionen der Daten modelliert werden kann. Distributed Consistent Branching (DCB) erzeugt diese alternativen Versionen der Daten konsistent auf allen Replikaten; Distributed Consistent Cutting (DCC) wählt eine der Versionen konsistent aus. Die vorgestellten Algorithmen und Protokolle wurden in einer Datenbankimplementierung validiert. Mehrere Experimente zeigen ihre Einsetzbarkeit und helfen, ihr Verhalten unter verschiedenen Bedingungen einzuschätzen. / Data replication techniques introduce redundancy into a distributed system architecture that can help solve several of its persistent problems. In wide area or mobile systems, a replication system must be able to deal with the presence of unreliable, high-latency links. Only asynchronous replication algorithms with weak-consistency guarantees can be deployed in these environments, as these algorithms decouple the local acceptance of changes to the replicated data from coordination with remote replicas. This dissertation proposes a framework for building weak-consistency replication systems that provides the application developer with causal consistency guarantees and mechanisms for handling concurrency. By presenting an integrated set of mechanisms, algorithms and protocols for capturing and disseminating changes to the replicated data, we show that causal consistency and concurrency handling can be implemented in an efficient and versatile manner. The framework is founded on log of changes, which both acts the core data structure for its distributed algorithms and protocols and serves as the database log that ensures the consistency of the local data replica. The causal consistency guarantees are complemented with two distributed algorithms that handle concurrent operations. Both algorithms are based on the observation that uncoordinated concurrent operations introduce a divergence of state in a replication system that can be modeled as the creation of version branches. Distributed Consistent Branching (DCB) recreates these branches on all participating processes in a consistent manner. Distributed Consistent Cutting (DCC) selects one of the possible branches in a consistent and application-controllable manner and enforces a total causal order for all its operations. The contributed algorithms and protocols were validated in an database system implementation, and several experiments assess the behavior of these algorithms and protocols under varying conditions.

Στις ημέρες μας, η εμφάνιση των ασύρματων δικτύων σε πολλές πτυχές της καθημερινότητας, είναι συνεχώς αυξανομενη. Το γεγονός αυτό, έχει ως συνέπεια να υπάρχει μεγάλη ερευνητική δραστηριότητα γύρω από τα ασύρματα δίκτυα, η οποία αφορά όχι μόνο το σχεδιασμό τους και την ανάπτυξη διάφορων πρωτοκόλλων, αλλά και άλλες εφαρμογές, όπως είναι για παράδειγμα η εκτίμηση παραμέτρων. Στα πλαίσια της εργασίας αυτής, μελετάται η ανάπτυξη των αλγορίθμων φλυαρίας, οι οποίοι αφορούν μία κατανεμημένη προσέγγιση του προβλήματος της εκτίμησης παραμέτρων σε ένα δίκτυο. Πιο συγκεκριμένα, σε αντίθεση με τις κλασσικές μεθόδους στις οποίες αναλαμβάνει ένας κεντρικός κόμβος με μεγάλη υπολογιστική ισχύ να λύσει το πρόβλημα της εκτίμησης της παραμέτρου ενδιαφέροντος, με τους αλγόριθμους φλυαρίας αναιρείται η έννοια του κεντρικού κόμβου και η εκτίμηση στηρίζεται στη συνεχή ανταλλαγή πληροφοριών μεταξύ των κόμβων του δικτύου. Με τις προσομοιώσεις που έγιναν στα πλαίσια αυτής της εργασίας, αποδεικνύεται ότι οι εν λόγω αλγόριθμοι εξασφαλίζουν επιτυχημένη προσέγγιση του προβλήματος που καλούνται να επιλύσουν παρότι οι αλγόριθμοι φλυαρίας στηρίζονται σε υποβέλτιστες τεχνικές εκτίμησης παραμέτρων οι οποίες βασίζονται σε αναδρομικούς προσαρμοστικούς αλγορίθμους. Τέλος, αντιμετωπίζεται το πρόβλημα της εκτίμησης της θέσης ενός στόχου που κινείται στην περιοχή ενός δικτύου με βάση τη διαδικασία της φλυαρίας. / In recent years, the emergence of wireless networks in many aspects of daily life, is increasingly growing. This fact has as consequence a strong research activity around various types of wireless networks, not only in the design and development of various protocols, but also in other applications such as parameter estimation. In this thesis, we study the development of gossip algorithms that are related to a distributed approach to the problem of parameter estimation in a network. More specifically, in contrast with classical methods that assume a central node with high computational power to solve the problem of estimation of the parameter of interest, the use of gossip algorithms negates this concept and the estimation process is based on continuing exchange of information between network nodes. Additionally, despite the fact that gossip algorithms belong to suboptimal parameter estimation techniques, that are based on recursive adaptive algorithms, the simulation results presented show that these algorithms ensure successful approach to the problem they have to solve. Finally, the process of gossiping deals with the problem of estimating the position of a moving target in the region of a wireless network.