With the growth of the internet, distributed systems have become increasingly important in order to provide more available and scalable applications. Con- sensus is a fundamental problem in distributed systems where multiple pro- cesses have to agree on the same proposed value in the presence of partial failures. Distributed consensus allows for building various applications such as lock services, configuration manager services or distributed databases.Two well-known consensus algorithms for building distributed logs are Multi-Paxos and Raft. Multi-Paxos was published almost three decades before Raft and gained a lot of popularity. However, critics of Multi-Paxos consider it difficult to understand. Raft was therefore published with the motivation of being an easily understood consensus algorithm. The Raft algorithm shares similar characteristics with a practical version of Multi-Paxos called Leader- based Sequence Paxos. However, the algorithms differ in important aspects such as leader election and reconfiguration.Existing work mainly compares Multi-Paxos and Raft in theory, but there is a lack of performance comparisons in practice. Hence, prototypes of Leader- based Sequence Paxos and Raft have been designed and implemented in this thesis. The prototypes were implemented using the Rust programming lan- guage and the message-passing framework Kompact and then benchmarked in real-world scenarios to compare the performance of Leader-based Sequence Paxos and Raft.The results show that Leader-based Sequence Paxos and Raft have simi- lar performance in geographically distributed deployments. However, the un- predictable leader election in Raft could greatly affect the performance if the elected leader is in an undesired location. In our experiments, the location of the Raft leader affected the average throughput by up to 35%. Furthermore, the results indicate that implementation details could have a significant impact on performance even in the parts where the algorithms are similar. By batch- ing messages more efficiently, Leader-based Sequence Paxos achieved up to 17% higher average throughput than Raft. / Med tillväxten av internet har distribuerade system blivit allt mer viktiga för att bygga mer tillgängliga och skalbara applikationer. Konsensus är ett funda- mentalt problem i distribuerade system där flera processer ska komma överens om samma föreslagna värde, samtidigt som partiella fel kan ske. Distribuerad konsensus kan appliceras till olika användningsomården som låstjänster, kon- figurationshanterare och distribuerade databaser.Två välkända konsensusalgoritmer för att bygga distribuerade loggar är Multi-Paxos och Raft. Multi-Paxos publicerades nästintill tre årtionden före Raft och blev populär. Men kritiker av Multi-Paxos anser att algoritmen är svår att förstå. Av denna anledning publicerades Raft med motivationen att vara en konsensusalgoritm som är enkel att förstå. Raft delar likheter med Leader- based Sequence Paxos, en praktisk version av Multi-Paxos. Dock skiljer sig algoritmerna i viktiga aspekter som leaderval och rekonfigurering.Befintliga arbeten jämför i huvudsak Multi-Paxos och Raft i teorin, men det saknas jämförelse av prestandan i praktiken. Av denna anledning har pro- totyper av Leader-based Sequence Paxos och Raft blivit designade och imple- menterade i denna avhandling. Dessa prototyper implementerades i program- meringsspråket Rust och message-passing ramverket Kompact, som sedan tes- tades i verkliga situationer för att jämföra Leader-based Sequence Paxos och Raft.Resultaten visar att Leader-based Sequence Paxos och Raft har liknande prestanda i geografiskt distribuerade sammanhang. Dock kan det oförutsäga- bara ledarvalet i Raft påverka prestandan avsevärt ifall den valde ledaren befin- ner sig på en oönskad plats. I våra experiment påverkade Raft ledarens plats den genomsnittliga kapaciteten med upp till 35%. Resultaten visar även att implementationsdetaljer kan ha en signifikant effekt på prestandan även i de delar där algoritmerna är liknande. Genom att sammanfoga meddelanden mer effektivt uppnådde Leader-based Sequence Paxos 17% högre genomsnittlig kapacitet än Raft.

No description available.

On-line services already form an important part of modern life with an immense potential for growth. Most of these services are supported by transactional systems, which are backed by database management systems (DBMS) in many cases. Many on-line services use replication to ensure high-availability, fault tolerance and scalability. Replicated systems typically consist of different nodes running the service co-ordinated by a distributed algorithm which aims to drive all the nodes along the same sequence of states by providing a total order to their operations. Thus optimization of both local DBMS operations through concurrency control and the distributed algorithm driving replicated services can lead to enhancing the performance of the on-line services. Deferred Update Replication (DUR) is a well-known approach to design scalable replicated systems. In this method, the database is fully replicated on each distributed node. User threads perform transactions locally and optimistically before a total order is reached. DUR based systems find their best usage when remote transactions rarely conflict. Even in such scenarios, transactions may abort due to local contention on nodes. A generally adopted method to alleviate the local contention is to invoke a local certification phase to check if a transaction conflicts with other local transactions already completed. If so, the given transaction is aborted locally without burdening the ordering layer. However, this approach still results in many local aborts which significantly degrades the performance. The first main contribution of this thesis is PXDUR, a DUR based transactional system, which enhances the performance of DUR based systems by alleviating local contention and increasing the transaction commit rate. PXDUR alleviates local contention by allowing speculative forwarding of shared objects from locally committed transactions awaiting total order to running transactions. PXDUR allows transactions running in parallel to use speculative forwarding, thereby enabling the system to utilize the highly parallel multi-core platforms. PXDUR also enhances the performance by optimizing the transaction commit process. It allows the committing transactions to skip read-set validation when it is safe to do so. PXDUR achieves performance gains of an order of magnitude over closest competitors under favorable conditions. Transactions also form an important part of centralized DBMS, which tend to support multi-threaded access to utilize the highly parallel hardware platforms. The applications can be wrapped in transactions which can then access the DBMS as per the rules of concurrency control. This allows users to develop applications that can run on DBMSs without worrying about synchronization. texttt{Serializability} is the de-facto standard form of isolation required by transactions for many applications. The existing methods employed by DBMSs to enforce serializability employ explicit fine-grained locking. The eager-locking based approach is pessimistic and can be too conservative for many applications. The locking approach can severely limit the performance of DBMSs especially for scenarios with moderate to high contention. This leads to the second major contribution of this thesis is TSAsR, an adaptive transaction processing framework, which can be applied to DBMSs to improve performance. TSAsR allows the DBMS's internal synchronization to be more relaxed and enforces serializability through the processng of external meta-data in an optimistic manner. It does not require any changes in the application code and achieves orders of magnitude performance improvements for high and moderate contention cases. The replicated transaction processing systems require a distributed algorithm to keep the system consistent by ensuring that each node executes the same sequence of deterministic commands. These algorithms generally employ texttt{State Machine Replication (SMR)}. Enhancing the performance of such algorithms is a potential way to increase the performance of distributed systems. However, developing new SMR algorithms is limited in production settings because of the huge verification cost involved in proving their correctness. There are frameworks that allow easy specification of SMR algorithms and subsequent verification. However, algorithms implemented in such framework, give poor performance. This leads to the third major contribution of this thesis Verified JPaxos, a JPaxos based runtime system which can be integrated to an easy to verify I/O automaton based on Multipaxos protocol. Multipaxos is specified in Higher Order Logic (HOL) for ease of verification which is used to generates executable code representing the Multipaxos state changes (I/O Automaton). The runtime drives the HOL generated code and interacts with the service and network to create a fully functional replicated Multipaxos system. The runtime inherits its design from JPaxos along with some optimizations. It achieves significant improvement over a state-of-art SMR verification framework while still being comparable to the performance of non-verified systems. / Master of Science

The tourist streams have increased more and more over the years. Thanks to the technology and globalization, it has contributed to an increased tourism and impact on destinations. The purpose of the study was to investigate whether social sustainability is affected by tourism on Paxos and Boracay from a visitor perspective. The method used for the survey was questionnaires and a selection that focused on those who visited the two islands. It was also a comparison of Paxos and Boracay related to social sustainability. The result was presented in three categories, society, culture and crime and security. The result showed that the social sustainability of Boracay was most affected by tourism. The conclusion of the study showed that the social sustainability of Paxos and Boracay is affected by tourism in both negative and positive ways. It turned out that the most affected island by tourism within social sustainability was Boracay

Made available in DSpace on 2016-06-02T19:07:10Z (GMT). No. of bitstreams: 1 PAULA_Anderson_2015.pdf: 815177 bytes, checksum: b64e699dd3ec918452fa1075460274f9 (MD5) Previous issue date: 2015-06-29 / Paxos is an active replication algorithm that keeps the same shared state consistently among servers that handle requests from an application. It is unusual to find applications where the main processing happens through a replication algorithm such as Paxos, mostly due to the high number of exchanged messages required to keep the state consistent. This restricts the system scalability to a handful of replicas. To increase the applicability of active replication, we would like be able to not only make the capacity of processing proportional to the number of servers employed, but also change dynamically the number of server according to demand. In this dissertation we explored reconfiguration on systems that use active replication. We proposed two mechanisms: (1) efficient protocolo for state transfer; and (2) incorporation of new replicas in the system with no significant increase in the cost to keep the whole system consistent. Our approach uses both mechanisms to create reader replicas, capable of answering all application requests without taking an active part in the costly operations of the Paxos algorithm. / Paxos é um mecanismo de replicação ativa que consegue manter um mesmo estado compartilhado entre servidores que atendem a requisições de uma aplicação. É incomum encontrar aplicações onde a parte principal do processamento acontece através de um algoritmo de replicação como Paxos devido ao seu custo em termos do número de mensagens trocadas, o que limita a escalabilidade do sistema para algumas poucas réplicas. Para aumentar a aplicabilidade de replicação ativa, gostaríamos de ser ser capazes de, não só tornar a capacidade de processamento proporcional ao número de servidores empregados, mas também de variar essa capacidade dinamicamente em resposta às mudanças da demanda gerada. Nessa dissertação exploramos a questão da reconfiguração em sistemas de replicação ativa. Em particular, cobiçamos transformar a biblioteca de replicação Treplica em um sistema reconfigurável. Propomos dois novos mecanismos: (1) protocolo eficiente para transferência de estado; e (2) adição de novas réplicas sem aumentar de forma significativa o custo de manutenção da consistência do sistema como um todo. Nossa estratégia utiliza os dois mecanismos para criação de réplicas leitoras, que são capazes de atender todas as requisições da aplicação sem no entanto participarem ativamente das operações custosas do algoritmo Paxos.

Le problème du Consensus est reconnu comme un paradigme important pour concevoir des systèmes répartis tolérants aux défaillances. Dans un système asynchrone pure, le consensus est impossible à résoudre de manière déterministe. En enrichissant le système avec des hypothèses de synchronie, plusieurs solutions (dont le protocole Paxos) ont été proposées pour contourner ce résultat d'impossibilité. Ce travail contribue à la conception de protocoles de consensus efficaces dans un système réparti asynchrone. La proposition d'un protocole efficace appelé Paxos-MIC, qui suit l'approche Paxos et intègre deux optimisations connues, est la contribution algorithmique de cette thèse. Paxos-MIC gère une séquence d'instances de consensus et garantie la persistance de toutes les décisions. L'adaptabilité est la principale qualité de ce protocole. Etant donné que l'une des optimisations peut être néfaste, Paxos-MIC intègre un mécanisme de déclenchement qui peut activer dynamiquement l'optimisation. Différents critères de déclenchement sont proposés pour prédire si l'utilisation de l'optimisation va être bénéfique. De nombreuses expérimentations ont été conduites sur la grille GRID'5000 afin d'évaluer le protocole et ces critères. Une seconde partie du travail se focalise sur l'utilisation du consensus comme une brique de base. Dans le contexte particulier des agents mobiles transactionnels, nous proposons une solution pour supporter l'exécution de transactions dans un réseaux ad-hoc. La solution repose sur une séquence de décisions construite de façon durable en invoquant des consensus. Ce service est fourni par le protocole Paxos-MIC.

Present-day commonly used systems like Cassandra, Spanner, and CockroachDB require high availability and strict consistency guarantees. High availability is attained through redundancy. In the field of computing, redundancy is attained through state machine repli- cation. Protocols like Raft, Multi-Paxos, ZAB, or other variants of Paxos are commonly used to achieve state machine replication. These protocols choose one of the processes from multiple processes running on various machines in a distributed setting as the leader. The leader is responsible for client interactions, replicating client operations on all the followers, and maintaining a consistent view across the system. In these protocols, the leader is more loaded than other nodes or followers in the system, making the leader a significant scalabil- ity bottleneck for multi-datacenter and edge deployments. The overall commit throughput and latency are further exacerbated in majority agreement with the hardware and network heterogeneity. This work aims to reduce the load on the leader by using reduced dynamic latency-aware flexible quorums while maintaining strict correctness guarantees like linearizability. In this thesis, we implement dynamic reduced-size commit quorums to reduce the leader’s load and improve throughput and latency, called FDRaft. The commit quorums are computed based on an exponentially moving weighted average of the followers’ time to respond to the leader, accounting for the heterogeneity in hardware and network. The reduced commit quorum requires a bigger election quorum, but elections rarely happen, and a single leader can serve for significant durations. We evaluate this protocol using a key-value store built on FDRaft and Raft and compare multi-datacenter and edge deployments. The evaluation shows 2x improved throughput and around 55% improved latency over Raft during normal operations and 45% improvement over Raft with vanilla flexible-quorums under failure conditions. / M.S. / In our day-to-day life, we rely heavily on different internet applications, be it Instagram for sharing pictures, Amazon for our shopping, Doordaash for our food orders, Spotify for listening to music, or Uber for traveling. These applications share many commonalities, like the scale at which they operate, maintaining strict latency guarantees, high availability to serve the users, and using databases to maintain shared states. The data is replicated across multiple servers to provide fault tolerance against failures. The replication across multiple servers is achieved through state-machine replication. In state-machine replication, multiple servers start with the same initial state and perform operations in the same order to reach the same final state. This process of replication in computing is achieved through a consensus algorithm. Con- sensus means agreement, and consensus algorithms are used to reach an agreement for a particular value. Raft, Multi-Paxos, or any other variant of Paxos are the commonly used consensus algorithms to achieve agreement on a particular value in a distributed setting. In these algorithms, one of the servers is chosen as the leader responsible for client interactions, replicating and maintaining the same state across all the servers, even when faced with server and network failures. Every time the leader receives a client operation, it starts the consensus process by forwarding the client request to all the servers and committing the client request after receiving an agreement from the majority. As the leader does most of the work, it is more loaded than other servers and becomes a significant scalability bottleneck. The leader bottleneck becomes more evident in multi-datacenters and edge deployments. The hardware and network heterogeneity also severely affects the overall commit throughput and latency in majority agreement. In this thesis, we reduce the load on the leader by building a smaller-sized dynamic commit quorum with latency-aware server selection based on an exponentially weighted moving av- erage of the followers’ response time to the leader’s requests without compromising safety and liveness properties. Our design also provides a higher efficiency for throughput and commit latency. We evaluate this protocol against multiple workloads and failure conditions and find that it outperforms Raft by 2x in terms of throughput and around 55% in latency over Raft during normal operations. It also shows improvement in throughput and latency by 45% over Raft with vanilla flexible-quorums under failure conditions.

No description available.

Consistency preservation of replicated data is a critical aspect for distributed databaseswhich are strongly consistent. Further, in fail-recovery model each process also needs todeal with the management of stable storage and amnesia [1]. CATS is a key/value datastore which combines the Distributed Hash Table (DHT) like scalability and selforganization and also provides atomic consistency of the replicated items. However beingan in memory data store with consistency and partition tolerance (CP), it suffers frompermanent unavailability in the event of majority failure. The goals of this thesis were twofold (i) to implement disk persistent storage in CATS,which would allow the records and state of the nodes to be persisted on disk and (ii) todesign nodes failure recovery-algorithm for CATS which enable the system to run with theassumption of a Fail Recovery model without violating consistency. For disk persistent storage two existing key/value databases LevelDB [2] and BerkleyDB[3] are used. LevelDB is an implementation of log structured merged trees [4] where asBerkleyDB is an implementation of log structured B+ trees [5]. Both have been used as anunderlying local storage for nodes and throughput and latency of the system with each isdiscussed. A technique to improve the performance by allowing concurrent operations onthe nodes is also discussed. The nodes failure-recovery algorithm is designed with a goalto allow the nodes to crash and then recover without violating consistency and also toreinstate availability once the majority of nodes recover. The recovery algorithm is based onpersisting the state variables of Paxos [6] acceptor and proposer and consistent groupmemberships. For fault-tolerance and recovery, processes also need to copy records from the replicationgroup. This becomes problematic when the number of records and the amount of data ishuge. For this problem a technique for transferring key/value records in bulk is alsodescribed, and its effect on the latency and throughput of the system is discussed.

Submitted by Milena Rubi (milenarubi@ufscar.br) on 2017-06-01T17:22:55Z No. of bitstreams: 1 BARBIERI_Rodrigo_2016.pdf: 14770872 bytes, checksum: 86ee1d6f53ed262fa0977a741b0d1d78 (MD5) / Approved for entry into archive by Milena Rubi (milenarubi@ufscar.br) on 2017-06-01T17:23:03Z (GMT) No. of bitstreams: 1 BARBIERI_Rodrigo_2016.pdf: 14770872 bytes, checksum: 86ee1d6f53ed262fa0977a741b0d1d78 (MD5) / Approved for entry into archive by Milena Rubi (milenarubi@ufscar.br) on 2017-06-01T17:23:08Z (GMT) No. of bitstreams: 1 BARBIERI_Rodrigo_2016.pdf: 14770872 bytes, checksum: 86ee1d6f53ed262fa0977a741b0d1d78 (MD5) / Made available in DSpace on 2017-06-01T17:23:13Z (GMT). No. of bitstreams: 1 BARBIERI_Rodrigo_2016.pdf: 14770872 bytes, checksum: 86ee1d6f53ed262fa0977a741b0d1d78 (MD5) Previous issue date: 2016-08-04 / Não recebi financiamento / Due to the widespread adoption of distributed systems when building applications, demand for reliability and availability has increased. These properties can be achieved through replication techniques using algorithms that must be capable of tolerating faults. Certain faults such as arbitrary faults, however, may be more difficult to tolerate, resulting in more complex and resource intensive algorithms that end up being not very practical to use. Using an existing benign fault-tolerant middleware based on Paxos, we propose and experiment with the usage of consistency validation techniques and a distributed validation mechanism to harden it, thus allowing any application built on top of this hardened middleware to tolerate non-malicious arbitrary faults. / Devido a crescente adoção de sistemas distribuídos ao se desenvolver aplicações, a demanda por confiabilidade e disponibilidade tem aumentado. Essas propriedades podem ser alcançadas através de técnicas de replicação que utilizam algoritmos capazes de tolerar falhas. Alguns tipos de falhas como falhas arbitrárias, porém, podem ser mais difíceis de tolerar, resultando em algoritmos mais complexos e custosos que acabam não sendo tão viáveis de serem usados. Utilizando um middleware tolerante a falhas benignas já existente baseado em Paxos, nós propomos e experimentamos o uso de técnicas de validação de consistência e um mecanismo de validação distribuída para fortalecê-lo, permitindo então que qualquer aplicação desenvolvida em cima deste middleware fortalecido tolere falhas arbitrárias não-maliciosas.