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.

Multidisciplinary computational simulations involve interactions between distributed applications, datasets, products, resources, and users. Because the very nature of the simulation software emphasizes a single-computer, small-usership and audience, the kinds of applications that have been developed often are unfriendly to incorporation into a distributed model. However, advances in networking infrastructure, and the natural tendency for information to be geographically distributed place strong requirements on integration of single-computer codes with distributed information sources, as well as multiple computer codes that are geographically distributed in their execution. The hypothesis of this dissertation is that it is possible, via novel integration of Internet, Distributed Computing, and Grid technologies, to create a distributed computational simulation systems that satisfies the requirements of modern multidisciplinary computational simulation systems without compromising functionality, performance, or security of existing applications. Furthermore, such a system would integrate disparate applications, resources, and users and would improve the productivity of users by providing new functionality not currently available. The hypothesis is proved constructively by first prototyping the Enterprise Computational Services framework based on a multi-tier architecture using the Java 2 Enterprise Edition platform and Web Services and then two distributed systems, the Distributed Marine Environment Forecast System and Distributed Simulation System for Seismic Performance of Urban Regions, are prototyped using this enabling framework. Several interfaces to the framework are prototyped to illustrate that the same framework can be used to develop multiple front-end clients required to support different types of users within a given computational domain. The two domain specific distributed environments prototyped using the framework illustrate that the framework provides a reusable common infrastructure irrespective of the computational domain. The effectiveness and utility of the distributed system and the framework are demonstrated by using a representative collection of computational simulations. Additional benefits provided by the distributed systems in terms of new functionality provided are evaluated to determine the impact on user productivity. The key contribution of this dissertation is a reusable infrastructure that could evolve to meet the requirements of next-generation hardware and software architectures while supporting interaction between a diverse set of users and distributed computational resources and multidisciplinary applications.

No description available.

No description available.

[pt] A programação por contratos é uma das técnicas voltadas para a melhoria da qualidade de software, sendo baseada no aumento do formalismo da especificação das interfaces. No contexto de componentes de software distribuídos, o uso de contratos envolve alguns desafios que o diferenciam do seu uso mais tradicional. O objetivo deste trabalho é a avaliaação do uso de contratos no desenvolvimento de sistemas distribuí­dos baseados em componentes de software, identificando as abordagens existentes e analisando as vantagens e desvantagens do seu uso. São também avaliadas caracterí­sticas como robustez, desempenho, flexibilidade, facilidade de uso e limitações. Como estudo de caso, foi desenvolvido um subsistema de suporte a contratos sobre um middleware CORBA implementado em Lua, servindo de base para experimentos realizados durante a pesquisa. / [en] Contract-based programming is one of the techniques used to improve the quality of software by enhancing the formalism of interface specifications. In the context of distributed software components, the use of contracts presents new challenges that make it di*erent from its traditional use. This work intends to evaluate the use of contracts in the development of component-based distributed systems, identifying the current approaches and analyzing its advantages and disadvantages. It also covers topics like robustness, performance, flexibility, ease of use and limitations. As a case study, a contract subsystem was developed over a CORBA middleware using Lua, serving as the basis for experiments in our study.

<p>Secure multi-party computation (MPC) enables mutually distrusting parties to compute securely over their private data. It is a natural approach for building distributed applications with strong privacy guarantees, and it has been used in more and more real-world privacy-preserving solutions such as privacy-preserving machine learning, secure financial analysis, and secure auctions.</p> <p><br></p> <p>The typical method of MPC is to represent the function with arithmetic circuits or binary circuits, then MPC can be applied to compute each gate privately. The practicality of secure multi-party computation (MPC) has been extensively analyzed and improved over the past decade, however, we are hitting the limits of efficiency with the traditional approaches as the circuits become more complicated. Therefore, we follow the design principle of identifying and constructing fast and provably-secure MPC protocols to evaluate useful high-level algebraic abstractions; thus, improving the efficiency of all applications relying on them. </p> <p><br></p> <p>To begin with, we construct an MPC protocol to efficiently evaluate the powers of a secret value. Then we use it as a building block to form a secure mixing protocol, which can be directly used for anonymous broadcast communication. We propose two different protocols to achieve secure mixing offering different tradeoffs between local computation and communication. Meanwhile, we study the necessity of robustness and fairness in many use cases, and provide these properties to general MPC protocols. As a follow-up work in this direction, we design more efficient MPC protocols for anonymous communication through the use of permutation matrices. We provide three variants targeting different MPC frameworks and input volumes. Besides, as the core of our protocols is a secure random permutation, our protocol is of independent interest to more applications such as secure sorting and secure two-way communication.</p> <p><br></p> <p>Meanwhile, we propose the solution and analysis for another useful arithmetic operation: secure multi-variable high-degree polynomial evaluation over both scalar and matrices. Secure polynomial evaluation is a basic operation in many applications including (but not limited to) privacy-preserving machine learning, secure Markov process evaluation, and non-linear function approximation. In this work, we illustrate how our protocol can be used to efficiently evaluate decision tree models, with both the client input and the tree models being private. We implement the prototypes of this idea and the benchmark shows that the polynomial evaluation becomes significantly faster and this makes the secure comparison the only bottleneck. Therefore, as a follow-up work, we design novel protocols to evaluate secure comparison efficiently with the help of pre-computed function tables. We implement and test this idea using Falcon, a state-of-the-art privacy-preserving machine learning framework and the benchmark results illustrate that we get significant performance improvement by simply replacing their secure comparison protocol with ours.</p> <p><br></p>

Cloud applications and services are frequently built using multiple tiers and current trends such as micro-services further increase componentization, allowing us to place each component in a different physical machine in a distributed cloud. Ericsson owns and manages very large networks, which offer diverse infrastructure in terms of computational power, storage but most importantly position in the network. Typically, a machine which is closer to the edge of the network (closer to the end user) will have limited resources but it will offer less latency, for a higher price. At the same time, several enterprise/industrial areas expect to benefit from the cloud business model in a large-scale distributed environment. These types of applications have very diverse end-2-end Service-Level Agreements (SLA) to be fulfilled, while at the same time the cloud environment needs to optimize processing, storage, and networking costs. Moreover, customers might want to change and adjust SLAs/requirements themselves using selfmanagement portals. The objective of this project is to model the network and services offered by Ericsson. Then, given the SLA, finding a valid solution of the problem, using a constraint solver. A solution is a set of physical machines that host the components the required service is composed from. This approach has many challenges since the same service can be composed from different sets of components. The connected components form a connectivity graph, where nodes in the graph are connected by physical links. But, since the connection is described by higher level components (composed by simpler components), this graph can also be expressed as a tree. Leaves in the tree are the nodes that compose the higher-level services and the ones that must be hosted in the infrastructure. The characteristics of each leaf-node depend on its parent and/or siblings in the component tree. Finally, since the components are normally connected, the physical connection between nodes in the network must be taken into consideration. The proposed model is evaluated in several cases, in order to identify how the number of the software components and the infrastructure topology affect the solution finding. The results are promising, showing fast resolution of the problem instances, varying for each test case, from a few seconds to a couple of minutes. / Molnapplikationer och tjänster är ofta byggda med flera nivåer och nuvarande trender såsom mikro-tjänster ökar ytterligare komponentiseringen, vilket tillåter oss att placera varje komponent i en annan fysisk maskin på ett distribuerat moln. Ericsson äger och förvaltar väldigt stora nätverk som erbjuder varierande infrastruktur när det gäller beräkningskraft , lagring och framför allt position i nätverket. Typiskt kommer en maskin som är närmare kanten av nätet (närmare slutanvändaren) att ha begränsade resurser, men det kommer att erbjuda mindre latens till ett högre pris. Samtidigt räknar flera företag / industriområden med att dra nytta av moln affärsmodelltjänster i en storskalig och distribuerad miljö. Den här typen av applikationer har väldigt olika end-to-end varierande servicenivåavtal (SLA) som skall uppfyllas, medan moln miljön behöver optimera bearbetnings, lagrings och nätverks kostnader. Dessutom, kan kunden komma att vilja ändra och justera SLA / krav själva med hjälp av självhantering portaler. Målet för detta projekt är att modellera nät och tjänster som erbjuds av Ericsson. Sedan, givet ett SLA, att hitta en giltig lösning på problemet, med hjälp av en villkorslösare. En lösning är en uppsättning av fysiska maskiner som är värdar för komponenterna från vilka den efterfrågade tjänsten är sammansatt. Detta tillvägagångssätt är förenat med många utmaningar eftersom samma tjänst kan bestå av olika uppsättningar av komponenter. De anslutna komponenterna bildar ett förbindelseschema, där noder i grafen är anslutna med fysiska länkar. Men eftersom anslutningen beskrivs av komponenter högre nivå (bestående av enklare komponenter), denna graf kan också uttryckas som ett träd. Löv i trädet är noderna som utgör de högre nivå tjänster och de som måste finnas i infrastrukturen. Egenskaperna hos varje löv-nod att bero på dess förälder och / eller syskon i komponentträdet. Slutligen, eftersom komponenterna i normal fall är anslutna, måste den fysiska anslutningen mellan noder i nätet tas i beaktande. Den föreslagna modellen utvärderas i flera fall, för att identifiera hur antalet programvarukomponenter och infrastrukturens topologi påverkar resultatet av lösningen. Resultaten är lovande och visar snabb lösning av problemets instanser, varierande för varje testfall, från några sekunder till ett par minuter.

I distribuerade system, kommunicerar komponenter genom att skicka meddelanden till varan- dra och mellanprogramvara överlappar integrationen mellan olika applikationer. Syftet var att undersöka och analysera olika designmönster till en mellanprogramvara som hanterar kommunikationen i en en-till-många relation och som kan användas i en XFS baserad programvara samt identifiera eventuella problem som uppkom under utvecklingsprocessen.Reverse engineering användes för att rekonstruera vår uppdragsgivares XFS baserade mjukvara. Ingång- och utgångspunkter lokaliserades och visualiserades med hjälp av UML-diagram. Med hjälp av vår uppdragsgivares krav och rekonstruktion av deras mjukvara, de designmönster som valdes var Broker och Reactor. Dessa valdes för att frikoppla en-till-en relationen mot vår uppdragsgivares hårdvara. Arkitekturen i vår prototyp av mellanprogramvaran baserades på klient-server och prototypen använder en en-till-många interprocesskommunikation för att skicka JSON-meddelande över en pipe anslutning.Prototypen utvärderades med hjälp av testfall och utfallet av testen var till belåtenhet. Slutversionen av vår prototyp klarade av att hantera kommunikation mellan flera klienter till vår uppdragsgivares hårdvara genom en server. Callbacks hanterades och presenterades i alla klienter.Valen som gjordes under utvecklingen identifierade problem som är värdefulla för andra utvecklare. Två huvudproblem uppstod för att det är väldigt hög komplexitet i välutvecklade system samt att logiken bakom XFS standarden är öppen för fri tolkning. Vår lösning är bra vid en utvecklingsuppstart men det fastställs att asynkrona mönster är en möjlig optimering av mjukvarusystemet. / In distributed systems, components communicate by passing messages between each other and a middleware bridges gaps between the interaction of different applications. The aim was to investigate and analyse middleware designs that handle a one-to-many communication usable in XFS based software and identify possible problems during the development process.Reverse engineering was used to reconstruct our stakeholders XFS based software. Entry and exit points were localised and visualised with UML diagrams from the reconstruction. By focusing on the stakeholders requirements and the reconstruction, the design pattern Broker and Reactor were used to decouple a one-to-one relationship towards the stakeholders hardware. The architecture of the middleware prototype was based on a client-server architecture and the prototype utilises a one-to-many inter-process communication that sends JSON messages over a pipe connection.The prototype was evaluated using written test cases and the test cases presented satisfactory results. The final version of the prototype was able to handle several clients communicating with the stakeholders hardware through the server and all clients displayed callbacks.Choices made during the iterative development identified problems that are valuable to other developers. The two main problems were high complexity in a legacy software system and that all logic in the XFS standard is open to interpretation. Our solution is successful as a start-up approach but asynchronous patterns are determined as a possible optimisation for the software system.

The number and types of input devices and related interaction technique types are growing rapidly. Innovative input devices such as game controllers are no longer used just for games, propriety consoles and specific applications, they are also used in many distributed virtual environments, especially the so-called serious virtual environments. In this dissertation a distributed, service based framework is presented to offer context-sensitive interaction interoperability that can support mapping between input devices and suitable application tasks given the attributes (device, applications, users, and interaction techniques) and the current user context without negatively impacting performances of large scale distributed environments. The mapping is dynamic and context sensitive taking into account the context dimensions of both the virtual and real planes. What device or device component to use, how and when to use them depend on the application, task performed, the user and the overall context, including location and presence of other users. Another use of interaction interoperability is as a testbed for input devices, and interaction techniques making it possible to test reality based interfaces and interaction techniques with legacy applications. The dissertation provides a description how the framework provides these affordances and a discussion of motivations, goals and the addressed challenges. Several proof of the concept implementations were developed and an evaluation of the framework performance (in terms of system characteristics) demonstrates viability, scalability and negligible delays. / Ph. D.

Distributed transactional memory (DTM) is an emerging, alternative concurrency control model that promises to alleviate the difficulties of lock-based distributed synchronization. In DTM, transactional conflicts are traditionally resolved by a contention manager. A complementary approach for handling conflicts is through a transactional scheduler, which orders transactional requests to avoid or minimize conflicts. We present a suite of transactional schedulers: Bi-interval, Commutative Requests First (CRF), Reactive Transactional Scheduler (RTS), Dependency-Aware Transactional Scheduler} (DATS), Scheduling-based Parallel Nesting} (SPN), Cluster-based Transactional Scheduler} (CTS), and Locality-aware Transactional Scheduler} (LTS). The schedulers consider Herlihy and Sun's dataflow execution model, where transactions are immobile and objects are migrated to invoking transactions, relying on directory-based cache-coherence protocols to locate and move objects. Within this execution model, the proposed schedulers target different DTM models. Bi-interval considers the single object copy DTM model, and categorizes concurrent requests into read and write intervals to maximize the concurrency of read transactions. This allows an object to be simultaneously sent to read transactions, improving transactional makespan. We show that Bi-interval improves the makespan competitive ratio of DTM without such a scheduler to O(log(N)) for the worst-case and (log(N - k) for the average-case, for N nodes and k read transactions. Our implementation reveals that Bi-interval enhances transactional throughput over the no-scheduler case by as much as 1.71x, on average. CRF considers multi-versioned DTM. Traditional multi-versioned TM models use multiple object versions to guarantee commits of read transactions, but limit concurrency of write transactions. CRF relies on the notion of commutative transactions, i.e., those that ensure consistency of the shared data-set even when they are validated and committed concurrently. CRF detects conflicts between commutative and non-commutative write transactions and then schedules them according to the execution state, enhancing the concurrency of write transactions. Our implementation shows that transactional throughput is improved by up to 5x over a state-of-the-art competitor (DecentSTM). RTS and DATS consider transactional nesting in DTM, and focus on the closed and open nesting models, respectively. RTS determines whether a conflicting outer transaction must be aborted or enqueued according to the level of contention. If a transaction is enqueued, its closed-nested transactions do not have to retrieve objects again, resulting in reduced communication delays. DATS's goal is to boost the throughput of open-nested transactions by reducing the overhead of running expensive compensating actions and acquiring/releasing abstract locks when the outer transaction aborts. The contribution of DATS is twofold. First, it allows commutable outer transactions to be validated concurrently and allows non-commutable outer transactions -- depending on their inner transactions -- to be committed before others without dependencies. Implementations reveal effectiveness: RTS and DATS improve throughput (over the no-scheduler case), by as much as 1.88x and 2.2x, respectively. SPN considers parallel nested transactions in DTM. The idea of parallel nesting is to execute the inner transactions that access different objects concurrently, and execute the inner transactions that access the same objects serially, increasing performance. However, the parallel nesting model may be ineffective if all inner transactions access the same object due to the additional overheads needed to identify both types of inner transactions. SPN avoids this overhead and allows inner transactions to request objects and to execute them in parallel. Implementations reveal that SPN outperforms non-parallel nesting (i.e., closed nesting) by up to 3.5x and 4.5x on a micro-benchmark (bank) and the TPC-C transactional benchmark, respectively. CTS considers the replicated DTM model: object replicas are distributed across clusters of nodes, where clusters are determined based on inter-node distance, to maximize locality and fault-tolerance, and to minimize memory usage and communication overhead. CTS enqueues transactions that are aborted due to early validation over clusters and assigns their backoff times, reducing communication overhead. Implementation reveals that CTS improves throughput over competitor replicated DTM solutions including GenRSTM and DecentSTM by as much as 1.64x, on average. LTS considers the genuine partial replicated DTM model. In this model, LTS exploits locality by: 1) employing a transaction scheduler, which enables/disables object ownership changes depending on workload fluctuations, and 2) splitting hot-spot objects into multiple replicas for reducing contention. Our implementation reveals that LTS outperforms state-of-the-art competitors (Score and CTS) by up to 2.6x on micro-benchmarks (Linked List and Skip List) and by up to 2.2x on TPC-C. / Ph. D.