Search

This paper presents a practical set of algorithms for maintaining the consistency of a replicated file system with an optimistic update policy. These algorithms permit a system which allows updates to an object so long as any copy is available; the algorithms then return the various copies to consistency at their first opportunity. These algorithms have been used to build the Ficus replicated file system. >

Relay race is a method for maintaining the consistency of replicated copes. A relay is a stream of bitransactions (binary transactions) propagating updates like a wave. Each bitransaction is atomic while the global process is asynchronous in the sense that a bitransaction starts as soon as the previous one commits. The goal is to extend relay race for supporting temporal consistency constraints. Temporal consistency is treated through a couple of consistency rules; one simply checks the consistency of a copy and does not depend on any consistency predicate; the other one implements the protocol for restoring the consistency of a copy whenever the associated consistency predicate becomes true. >

In large scale distributed systems, caching and replication could greatly speedup access and increase availability. Consistency of replicated state can be guaranteed by forcing operations to occur in the same order at all sites. However some applications can preserve correctness with weaker consistency requirements leading to better performance. We propose an object lifetime based mutual consistency detection mechanism that is used to implement multiple consistency levels. This mechanism provides scalable implementations because caching overheads at client nodes depend only on the accesses done at the node. A contribution of this paper is the separation of the the mutual consistency detection mechanism from the policy that decides the desired consistency guarantees. This allows multiple consistency levels to coexist, thus improving system performance through the use of weaker consistency levels when possible. Besides improving performance, the mechanism allows for a graceful weakening of consistency requirements when stronger requirements cannot be maintained, as in the case of disconnection that can be experienced in mobile environments. The mutual consistency detection mechanism also provides a uniform way of hoarding a mutually consistent set of objects during voluntary disconnection.

A consistency constraint exists between two objects in a network management information base (MIB) if a change in value of one object will cause a change in another. Based on the definition of common knowledge, such constraints can be classified by the time needed to maintain them and the probability of correctly maintaining them. The practical issues of how to build an MIB with a set of objects and consistency constraints are discussed. Various kinds of consistency constraints and their relations with common knowledge are described. Also introduced is the concept of a consistency hierarchy, which presents a gateway between consistency constraints and the management protocols that would actually maintain the consistency between network entities. Building a network management information model using consistency constraints is considered. >

The proliferation of internetworks and distributed applications has increased the demand for geographically distributed replicated databases. The traditional approach of strong consistency is difficult to achieve across an internetwork. In contrast to strong consistency, a database replication system that provides weak consistency permits greater availability by allowing temporary inconsistencies to develop among the replicas. The Open System for Consistency and Replication (OSCAR), an architecture for a weak-consistency replication system, is presented. The approach to reliable replication is to use two complementary mechanisms. When an update initially enters the replication system, it is unreliably pushed to all other replicas. A novel technique called mediation ensures reliable propagation of the updates throughout the system. OSCAR provides appropriate weak consistency for a variety of applications by simultaneously supporting several weak-consistency methods. Its modular design permits its components to be configured for different networks and allows its algorithms to be selected and tuned for different environments and applications. >

Optimistically replicated systems provide highly available data even when communication between data replicas is unreliable or unavailable. The high availability comes at the cost of allowing inconsistent accesses, since users can read and write old copies of data. Session guarantees have been used to reduce such inconsistencies. They preserve most of the availability benefits of optimistic systems. We generalize session guarantees to apply to persistent as well as distributed entities. We implement these guarantees, called view consistency, on Ficus an optimistically replicated file system. Our implementation enforces consistency on a per-file basis and does not require changes to individual applications. View consistency is enforced by clients accessing the data and thus requires minimal changes to the replicated data servers. We show that view consistency allows access to available and high performing data replicas and can be implemented efficiently. Experimental results show that the consistency overhead for clients ranges from 1% to 8% of application runtime for the benchmarks studied in the prototype system. The benefits of the system are an improvement in access times due to better replica selection and improved consistency guarantees over a purely optimistic system.

The traditional distributed shared memory (DSM) model provides atomicity at levels of read and write on single objects. Therefore, multi-object operations such as double compare and swap, and atomic m-register assignment cannot be efficiently expressed in this model. We extend the traditional DSM model to allow operations to span multiple objects. We show that memory consistency conditions such as sequential consistency and linearizability can be extended to this general model. We also provide algorithms to implement these consistency conditions in a distributed system.

Where users are interacting in a distributed virtual environment, the actions of each user must be observed by peers with sufficient consistency and within a limited delay so as not to be detrimental to the interaction. The consistency control issue may be split into three parts: update control; consistent enactment and evolution of events; and causal consistency. The delay in the presentation of events, termed latency, is primarily dependent on the network propagation delay and the consistency control algorithms. The latency induced by the consistency control algorithm, in particular causal ordering, is proportional to the number of participants. This paper describes how the effect of network delays may be reduced and introduces a scalable solution that provides sufficient consistency control while minimising its effect on latency. The principles described have been developed at Reading over the past five years. Similar principles are now emerging in the simulation community through the HLA standard. This paper attempts to validate the suggested principles within the schema of distributed simulation and virtual environments and to compare and contrast with those described by the HLA definition documents.

Distributed databases generally have strict consistency requirements on data replicas, meaning that they are not allowed to diverge outside of transaction boundaries. For certain applications, this is too pessimistic, and it is often better to trade off consistency for higher availability, performance, or predictability. In this paper, we describe a replication protocol for a distributed database which is eventually consistent; it allows replicas to diverge if the system can be guaranteed to eventually converge to a consistent state. We also compare eventual consistency to self-stabilization, and outline how self-stabilization theory may help in proving properties of eventually consistent systems.

Distributed applications that share a dynamically changing state are increasingly being deployed in wide-area environments. Such applications must access the state in a consistent manner, but the consistency requirements vary significantly from other systems. For example, shared memory models, such as sequential consistency, focus on the ordering of operations, and the same level of consistency is provided to each process. In interactive distributed applications, the timeliness of updates becoming effective could be an extremely important consistency requirement, and it could be different across different users. We propose a system that provides both non-timed and time-sensitive read and write operations for dynamic shared state. For example, a timed read can be used by a process to read a recently written value, whereas a timed write can make a new value available to all readers within a certain amount of time. We develop a consistency model that precisely defines the semantics of timed and non-tinted read and write operations. A protocol that implements this model is also presented. We also describe an implementation and some performance measurements.

Existing Web proxy caches employ cache consistency mechanisms to ensure that locally cached data is consistent with that at the server. We argue that techniques for maintaining consistency of individual objects are not sufficient; a proxy should employ additional mechanisms to ensure that related Web objects are mutually consistent with one another. We formally define the notion of mutual consistency and the semantics provided by a mutual consistency mechanism to end users. We then present techniques for maintaining mutual consistency in the temporal and value domains. A novel aspect of our techniques is that they can adapt to the variations in the rate of change of the source data, resulting in judicious use of proxy and network resources. We evaluate our approaches using real-world Web traces and show that: (i) careful tuning can result in substantial savings in the network overhead incurred without any substantial loss in fidelity, of the consistency guarantees, and (ii) the incremental cost of providing mutual consistency guarantees over mechanisms to provide individual consistency guarantees is small.

Replication is a key approach to scaling wide-area applications. However, the overhead associated with large-scale replication quickly becomes prohibitive across wide-area networks. One effective approach to addressing this limitation is to allow applications to dynamically trade reduced consistency for increased performance and availability. Although extensive study has been performed on relaxed consistency models in traditional replicated databases, none of the models can simultaneously achieve the following two typically conflicting requirements imposed by wide-area applications: generality (capturing application-specific consistency semantics) and practicality (enabling efficient application-independent consistency protocols to be designed and providing natural ways to express application semantics). We propose a conit-based continuous consistency model designed to simultaneously achieve generality and practicality. Our conit theory provides generality, where application-specific consistency requirements are exported as conits. Practicality is achieved by using a simple, spanning set of metrics for conit consistency and by using a per-write weight specification. We demonstrate the generality of our model through representative wide-area applications and by showing that a number of existing models can be expressed as instances of our model. Our efficient, application-independent consistency protocols and prototype implementation verify its practicality.

A memory consistency model specifies certain aspects of the behavior of a memory system. Stronger consistency models are easier for programmers to use, but provide less flexibility for optimizing the memory implementation. More relaxed consistency models are just the opposite. The goal of our work is to develop a framework that captures the relationships among existing models, and maps the territory of possible models that have not yet been discovered. This work is based on the idea of orthogonal consistency properties. hypothesize that all consistency models can be represented by different combinations of a few primitive properties. The work comes from examining the PRAM, cache, processor, and causal consistency models. Processor is a combination of PRAM and cache, and causal is a combination of PRAM plus an additional requirement. These factors suggest an underlying structure to the models.

The paper proposes a novel view based consistency model for distributed shared memory. A view is a set of ordinary, data objects that a processor has the right to access in a data-race-free program. The view based consistency model only requires that the data objects of a view are updated before a processor accesses them. Compared with other memory consistency models, the view based consistency model can achieve data selection without user annotation and can reduce much false-sharing effect. This model has been implemented based on TreadMarks. Performance results have shown that for all our applications, the view based consistency model outperforms the lazy release consistency model.

A distributed computation satisfies sequential consistency if it is possible to establish a legal ordering of all the operations such that the program order of each site in the distributed system is respected. However, sequential consistency does not necessarily consider the particular real-time instant at which each operation is executed. A timed consistency model addresses how quickly the effects of an operation are perceived by the rest of the system, by requiring that if a write operation is executed at time t, it must be visible to the entire distributed system by time t+/spl Delta/.Timed consistency generalizes several existing consistency criteria and it is well suited for applications where the action of one user must be seen by others in a timely fashion.

An ultimate goal for modern Internet services is the development of scalable, high-performance, highly-available and fault-tolerant systems. Replication is an important approach to achieve this goal. However replication introduces the issue of consistency among replicas, which is further complicated by network partitions. Generally, higher consistency levels result in lower system availability in the presence of network partitions. Thus, there is a fundamental tradeoff between consistency and availability in building replicated Internet services. We argue that Internet services can benefit from dynamically choosing availability/consistency tradeoffs. With three consistency metrics, Unseen Writes, Uncommitted Writes and Staleness, we show how consistency can be meaningfully quantified for many Internet services. We present the design of the TACT (Tunable Availability and Consistency Tradeoffs) toolkit that allows Internet services to flexibly and dynamically choose their own availability/consistency, tradeoffs, enabling differentiated availability/consistency quality of service. Further TACT makes it possible for Internet services to dynamically trade consistency for performance.

This paper describes some preliminary steps towards defining a consistency criteria for mobile replicated systems using operational transformations. Our criterion lies between traditional strong criteria, preventing divergence, and traditional weak criteria, not enforcing any eventual form of convergence. We give a precise definition of our criterion and discuss its use to state the correctness and incorrectness of some existing practical algorithms.

In a distributed database system, pessimistic concurrency control is often used to ensure consistency which implies that the execution time of a transaction is not predictable. The execution time of a transaction is not dependent on the local transactions only, but on every transaction in the system. In real-time database systems it is important that transactions are predictable. One way to make transactions predictable is to use eventual consistency where transactions commit locally before they are propagated to other nodes in the system. It is then possible to get predictable transactions due to the fact that the execution time of the transaction only depends on concurrent transactions on the local node and not on delays on other nodes and delays from a network. In this report an investigation is made on how a replication protocol using eventual consistency can be designed for, and implemented in, DeeDS, a distributed real-time database prototype. The protocol consists of three parts: a propagation method, a conflict detection algorithm, and a conflict resolution mechanism. The conflict detection algorithm is based on version vectors. The focus is on the propagation mechanism and the conflict detection algorithm of the replication protocol. An implementation design of the replication protocol is made. A discussion on how the version vectors may be applied in terms of granularity (container, page, object or attribute) and how the log filter should be designed and implemented to suit the particular conflict detection algorithm is carried out. A number of test cases with focus on regression testing have been defined. It is concluded that the feasibility of the conflict detection algorithm is dependent on the application type that uses DeeDS.

An important class of large-scale distributed applications is insensitive to small inconsistencies among participants, as long as these events are temporary and not frequent. An efficient way for propagating information to participants in such cases is referred to as epidemic protocols. Epidemic protocols are simple, scale well and robust again common failures, and provide eventual consistency as well. They combine benefits of efficiency in hierarchical data dissemination with robustness in flooding protocols. These communication mechanisms have been mainly used for resolving inconsistencies in distributed database updates, failure detection, message loss recovery in multicast communication, network news distribution, group membership management, scalable system management, and resource discovery. In this paper, we focus on an end-to-end epidemic loss recovery mechanism for multicasting and give our simulation results discussing the performance of the approach in large-scale network settings.

The traditional assumption about memory is that a read returns the value written by the most recent write. However, in a shared memory multiprocessor several processes independently and simultaneously submit reads and writes resulting in a partial order of memory operations. In this partial order, the definition of most recent write may be ambiguous. Memory consistency models have been developed to specify what values may be returned by a read given that memory operations may only be partially ordered. Before this work, consistency models were defined independently. Each model followed a set of rules which was separate from the rules of every other model. In our work, we have defined a set of four consistency properties. Any subset of the four properties yields a set of rules which constitute a consistency model. Every consistency model previously described in the literature can be defined based on our four properties. Therefore, we present these properties as a unfied theory of shared memory consistency.Our unified theory provides several benefits. First, we claim that these four properties capture the underlying structure of memory consistency. That is, the goal of memory consistency is to ensure certain declarative properties which can be intuitively understood by a programmer, and hence allow him or her to write a correct program. Our unified theory provides a uniform, formal definition of all previously described consistency models, and in addition some combinations of properties produce new models that have not yet been described. We believe these new models will prove to be useful because they are based on declarative properties which programmers desire to be enforced. Finally, we introduce the idea of selecting a consistency model as an on-line activity. Before our work, a shared memory program would run start to finish under a single consistency model. Our unified theory allows the consistency model to change as the program runs while maintaining a consistent definition of what values may be returned by each read.

In many Internet scale replicated system, not all replicas can be dealt with in the same way, since some will be in greater demand than others. In the case of weak consistency algorithms, we have observed that updating first replicas having most demand, a greater number of clients would gain access to updated content in a shorter period of time. In this work we have investigated the benefits that can be obtained by prioritizing replicas with greater demand, and considerable improvements have been achieved. In zones of higher demand, the consistent state is reached up to six times quicker than with a normal weak consistency algorithm, without incurring the additional costs of the strong consistency.

We describe a family of three replication protocols, each of which can operate in three different modes of consistency. The protocols are tailored to satisfy the availability demands of interconnected databases that have a high degree of data locality. The protocols accomplish a grade of transaction completion which does not compromise availability, and ensure the consistency of replicas also if a transaction needs to be aborted. Flexibility of query answering is understood as optimizing the tradeoff between consistency and availability, i.e., between correctness and timeliness of query answering. This is achieved by choosing an appropriate protocol alternative, and changing the consistency mode of operation during the session, as appropriate for a given transaction.

As raw system performance continues to improve at exponential rates, the utility of many services is increasingly limited by availability rather than performance. A key approach to improving availability involves replicating the service across multiple, wide-area sites. However, replication introduces well-known trade-offs between service consistency and availability. Thus, this article explores the benefits of dynamically trading consistency for availability using a continuous consistency model . In this model, applications specify a maximum deviation from strong consistency on a per-replica basis. In this article, we: i) evaluate the availability of a prototype replication system running across the Internet as a function of consistency level, consistency protocol, and failure characteristics, ii) demonstrate that simple optimizations to existing consistency protocols result in significant availability improvements (more than an order of magnitude in some scenarios), iii) use our experience with these optimizations to prove tight upper bound on the availability of services, and iv) show that maximizing availability typically entails remaining as close to strong consistency as possible during times of good connectivity, resulting in a communication versus availability trade-off.

Projet SOR; This paper presents a consistency control protocol destined for groups of cooperative processes located world-wide. We assume that processes cooperate by sharing a replicated object. We consider processes with well-know- n profiles; however the actual behaviour of each process could diverge from the profile. The protocol aims at offering a good quality of service to cooperative processes, while guaranteeing replicated object consistency in the presence of disconnections and partitions. We are interested in the bounded consistency condition: the divergence between each replica and the «real object» remains smaller than a fixed bound during the lifetime of the application. We decompose this consistency condition into a set of local criteria concerning the effects of unexpected operations initiated by each process. We then associate to each process a consistency manager that enforces this precess local consistency criterium. To experiment with this protocol, we developed a highly available allocation service relying on it. The experimental results confirm that this approach provides a high degree of autonomy to each replica, especially when the actual behaviour of that replica conforms to the profile.

The demand for network-enabled limited-footprint mobile devices is increasing rapidly. A central challenge that must be addressed in order to use these next-generation devices effectively is efficient data management --- persistent data manipulated or required by applications executing on these computationally and communicationally impoverished devices must be consistently managed and made highly available. This data management has traditionally been the responsibility of the OS on which applications execute. In this paper, we extend this conventional OS functionality to include post-pc devices. We propose a novel programmatic solution to the problem of maintaining high data availability while attaining eventual consistency [16] in the presence of mobility and disconnected operations, device and network failures, and limited device capabilities. We achieve this by using a combination of a novel proxy architecture, a split request-reply queue based on soft-state principles, and a two-tier update/commit protocol. We also exploit strong object typing to provide application-specific conflict handling in order to attain faster eventual consistency, as well as greater probability of automatic reconciliation.

Current distributed systems, even the ones that work, tend to be very fragile: they are hard to keep up, hard to manage, hard to grow, hard to evolve, and hard to program. In this talk, I look at several issues in an attempt to clean up the way we think about these systems. These issues include the fault model, high availability, graceful degradation, data consistency, evolution, composition, and autonomy.These are not (yet) provable principles, but merely ways to think about the issues that simplify design in practice. They draw on experience at Berkeley and with giant-scale systems built at Inktomi, including the system that handles 50% of all web searches.

Traditionally, local consistency is defined as a relaxation of consistency which can be checked in polynomial time. It is accompanied by a corresponding "filtering" or "enforcing" algorithm that computes in polynomial time, and from any given CSP, an equivalent unique CSP which satisfies the local consistency property. The question whether the notion of local consistency can be extended to soft constraint frameworks has been addressed by several papers, in several settings [4, 14, 12]. The main positive conclusion of these works is that the notion of local consistency can be extended to soft constraints frameworks which rely on an idempotent violation combination operator. However, the question whether this can be done for non idempotent operators as eg, in the Max-CSP problem, is not clear and has lead to several different notions of arc consistency [14, 16, 1, 11, 10]. Each of these proposals lacks several of the original properties of local consistency. In this paper, we show that using a small additional axiom, satisfied by most existing soft constraints proposals (including Max-CSP), it is possible to define a notion of arc consistency that keeps all the good properties of classical arc consistency but the unicity of the arc consistent closure. We show that this notion directly provides improved lower bounds. Stronger alternative definitions, that allow partial inconsistencies to propagate are also considered.

Distributed object caching is essential for building and deploying Internet wide services based on middlewares such as CORBA. By caching objects, it is possible to mask much of the latency associated with accessing remote objects, to provide more predictable quality of service to clients, and to improve the scalability of the service. This paper presents a combined theoretical and practical view on specifying and implementing consistency conditions for such a service. First, a formal definition of a set of basic consistency conditions is given in an abstract, implementation independent manner. It is then shown that common consistency conditions such as sequential consistency, causal consistency, and PRAM can be formally specified as a combination of these more basic conditions. Finally, the paper describes the implementation of the proposed basic consistency conditions in CASCADE, a distributed CORBA object caching service.

Distributed Shared Memory (DSM) systems typically support one consistency protocol [3,5,6]. However, recent work [1,11,12,14,17] proposes the use of adaptive consistency based on a heuristical analysis of recent access patterns. Although heuristic-based approaches can significantly improve runtime, the access pattern alone does not necessarily define the most appropriate consistency protocol. The size of updates and other factors related to the computing environment, such as heavily loaded links, heavily loaded nodes, bursty traffic patterns, and network latency all affect performance. Multiple access patterns within the application also make it difficult to select the most appropriate consistency protocol. This paper presents a measurement-based approach to the problem of selecting the most appropriate consistency protocol for the current application in the current runtime environment. We show that measurement-based analysis provides an accurate estimate of performance and therefore can be used to select the most appropriate consistency protocol, even in cases where hueristic-based approaches fail to select the appropriate protocol.

Ordering and time are two different aspects of consistency of shared objects in a distributed system. One avoids conflicts between operations, the other addresses how quickly the effects of an operation are perceived by the rest of the system. Consistency models such as sequential consistency and causal consistency do not consider the particular time at which an operation is executed to establish a valid order among all the operations of a computation. Timed consistency models require that if a write operation is executed at time t, it must be visible to all nodes by time t +Δ. Timed consistency generalizes several existing consistency criteria and it is well suited for interactive and collaborative applications, where the action of one user must be seen by others in a timely fashion.

Recovery is a fundamental service in database systems. In this work, we present a new mechanism for diskless real-time recovery in fully replicated distributed real-time database systems. Traditionally, recovery has relied on disk-resident redundant data. Unfortunately, disks cannot always be used in real-time systems since these systems are sometimes used in environments which do not allow the use of disks. Also, minimizing the amount of hardware can save money, especially in mass-produced products. Instead of loading the database from disk, our recovery mechanism enables a restarted node to retrieve a copy of the database from an arbitrary remote node. The recovery mechanism does not violate timeliness during normal processing and, during recovery, all nodes except for the recovering node can guarantee the timeliness of critical transactions. The mechanism uses fuzzy checkpointing to copy the database to the recovering node. Fuzzy checkpointing has been chosen since it copies the database without regard to concurrency control and, thus, does not increase data contention in the database. We conclude that the suggested recovery mechanism is a feasible option for fully replicated distributed real-time database systems.

The distinction between lazy and eager (or strict) evaluation has been studied in programming languages since Algol 60's call by name, as a way to avoid unnecessary work and to deal gracefully with infinite structures such as streams. It is deeply integrated in some languages, notably Haskell, and can be simulated in many languages by wrapping a lazy expression in a lambda. Less well studied is the role of laziness, and its opposite, speculation, in computer systems, both hardware and software. A wide range of techniques can be understood as applications of these two ideas. Laziness is the idea behind: Redo logging for maintaining persistent state and replicated state machines: the log represents the current state, but it is evaluated only after a failure or to bring a replica online. Copy-on-write schemes for maintaining multiple versions of a large, slowly changing state, usually in a database or file system. Write buffers and writeback caches in memory and file systems, which are lazy about updating the main store. Relaxed memory models and eventual consistency replication schemes (which require weakening the spec). Clipping regions and expose events in graphics and window systems. Carry-save adders, which defer propagating carries until a clean result is needed. "Infinity" and "Not a number" results of floating point operations. Futures (in programming) and out of order execution (in CPUs), which launch a computation but are lazy about consuming the result. Dataflow is a generalization. "Formatting operators" in text editors, which apply properties such as "italic" to large regions of text by attaching a sequence of functions that compute the properties; the functions are not evaluated until the text needs to be displayed. Stream processing in database queries, Unix pipes, etc., which conceptually applies operators to unbounded sequences of data, but rearranges the computation when possible to apply a sequence of operators to each data item in turn. Speculation is the idea behind: Optimistic concurrency control in databases, and more recently in transactional memory Prefetching in memory and file systems. Branch prediction, and speculative execution in general in modern CPUs. Data speculation, which works especially well when the data is cached but might be updated by a concurrent process. This is a form of optimistic concurrency control. Exponential backoff schemes for scheduling a resource, most notably in LANs such as WiFi or classical Ethernet. All forms of caching, which speculate that it's worth filling up some memory with data in the hope that it will be used again. In both cases it is usual to insist that the laziness or speculation is strictly a matter of scheduling that doesn't affect the result of a computation but only improves the performance. Sometimes, however, the spec is weakened, for example in eventual consistency. I will discuss many of these examples in detail and examine what they have in common, how they differ, and what factors govern the effectiveness of laziness and speculation in computer systems.

Techniques such as replication and caching of objects that implement distributed services lead to consistency problems that must be addressed. We explore new consistency protocols based on the notion of object value lifetimes. By keeping track of the lifetimes of the values stored in shared objects (i.e., the time interval that goes from the writing of a value until the latest time when this value is known to be valid), it is possible to check the mutual consistency of a set of related objects cached at a site. Initially, this technique is presented assuming the presence of physical clocks. Later, these clocks are replaced by vector clocks and then by plausible clocks. Lifetimes based on such clocks result in weaker consistency but do provide more efficient implementations.

In order to make a dependable distributed computer system resilient to arbitrary failures of its processors, deterministic interactive consistency algorithms (ICAs) are required. Thus far, in order to guarantee interactive consistency, all ICAs found in the literature require that all correct processors in the system start the algorithm simultaneously. In a distributed system, it is hard to satisfy this requirement. Therefore, in this paper, we describe a new class of self-synchronizing ICAs that guarantee interactive consistency without the above-mentioned requirement.

Consistency criteria adopted for the management of persistent replicated objects in a distributed system define the degree of concurrency allowed among operations accessing objects. Several notions of consistency are known from the literature, among them are causal consistency, causal serializability, and serializability. In this paper, we propose a generalizing algorithm for concurrency control in a transaction system that exhibits a clean separation between policy and mechanism. A consistency criterion selected is manifested as a set of rules forming the policy. The mechanism, however, remains unchanged regardless of the currently used policy. The mechanism implements causally consistent message delivery and uses tokens and quorums of tokens to enforce access operation ordering according to the specified consistency criterion. Since a policy is implemented as a set of rules, switching on-the-fly from one consistency criterion to another one can easily be done whenever changes in access patterns or cost/availability requirements suggest a modification. An example of an application exploiting the advantages of switching among various consistency criteria concludes the paper.

Bayou is a replicated, weakly consistent storage system designed for a mobile computing environment that includes portable machines with less than ideal network connectivity. To maximize availability, users can read and write any accessible replica. Bayou’s design has focused on supporting application-specific mechanisms to detect and resolve the update conflicts that naturally arise in such a system, ensuring that replicas move towards eventual consistency, and defining a protocol by which the resolution of update conflicts stabilizes. It includes novel methods for conflict detection, called dependency checks, and per -write conflict resolution based on client-provid ed mer ge procedures. To guarantee eventual consistency, Bayou servers must be able to rollback the effects of previously executed writes and redo them according to a global serialization order . Furthermore, Bayou permits clients to observe the results of all writes received by a server , including tentative writes whose conflicts have not been ultimately resolved. This paper presents the motivation for and design of these mechanisms and describes the experiences gained with an initial implementation of the system.

As the number of processors increases, so does communication latency and the probability of component failure. A technique that addresses these problems is data replication, which provides faster access and greater availability. Its drawback is that the replicas must be kept consistent. The author describes a family of fault-tolerant algorithms for maintaining the consistency of cacheable data. Processors specify the consistency requirements, strong or weak, of their shared data. Data are kept consistent by a fault-tolerant multicast protocol. The protocol ensures the reliable delivery of operations on strongly consistent data. Weakly consistent data updates are inserted as operation prologues. Depending on the consistency policy, the execution of an operation causes cached data to be either invalidated or updated. >

To enhance performance on shared memory multiprocessors, various techniques have been proposed to reduce the latency of memory accesses, including pipelining of accesses, out-of-order execution of accesses, and branch prediction with speculative execution. These optimizations can, however, complicate the user's model of memory. This paper attacks the problem of simplifying programming on two fronts. First, a general framework is presented for defining shared memory consistency conditions that allows nonsequential execution of memory accesses. The interface at which conditions are defined is between the program and the system and is architecture-independent. The framework is used to generalize three consistency conditions---sequential consistency, hybrid consistency, and weak consistency---for nonsequential execution. Thus, familiar consistency conditions can be precisely specified even in optimized architectures. Second, three techniques are described for structuring programs so that a shared memory that provides the weaker (and more efficient) condition of hybrid consistency appears to guarantee the stronger (and more costly) condition of sequential consistency. The benefit of these techniques is that sequentially consistent executions are easier to reason about. The first technique statically classifies accesses based on their type. This approach is extremely simple to use and leads to a general technique for writing efficient synchronization code. The third technique is to avoid data races in the program, which was previously studied in a somewhat different setting. Precise, yet short and comprehensible, proofs are provided for the correctness of the programming techniques. Such proofs shed light on the reasons these techniques work; we believe that the insight gained can lead to the development of other techniques.

Distributed systems with replicated resources need controlled access to these resources to maintain consistency. We state and prove some important properties related to update operations with so-called view-based algorithms for maintaining consistency.

Ubiquitous connectivity of web, mobile, and IoT computing platforms has fostered a variety of distributed applications with decentralized state. These applications execute across multiple devices with varying reliability and connectivity. Unfortunately, there is no declarative fault-tolerant programming model for distributed interactive applications with an inherently decentralized system model. We present a novel approach to automating fault tolerance using high-level programming abstractions tailored to the needs of distributed interactive applications. Specifically, we propose a calculus that enables formal reasoning about applications' dataflow within and across individual devices. Our calculus reinterprets the functional reactive programming model to seamlessly integrate its automated state change propagation with automated crash recovery of device-local dataflow and disconnection-tolerant distribution with guaranteed automated eventual consistency semantics based on conflict-free replicated datatypes. As a result, programmers are relieved of handling intricate details of distributing change propagation and coping with distribution failures in the presence of interactivity. We also provides proofs of our claims, an implementation of our calculus, and an empirical evaluation using a common interactive application.

Matrix is a new kind of decentralized, topic-based publish-subscribe middleware for communication and data storage that is getting particularly popular as a basis for secure instant messaging. By comparison with traditional decentralized communication systems, Matrix replaces pure message passing with a replicated data structure. This data structure, which we extract and call the Matrix Event Graph (MEG), depicts the causal history of messages. We show that this MEG represents an interesting and important replicated data type for decentralized applications that are based on causal histories of publish-subscribe events: First, we prove that the MEG is a Conflict-Free Replicated Data Type for causal histories and, thus, provides Strong Eventual Consistency (SEC). With SEC being among the best known achievable trade-offs in the scope of the well-known CAP theorem, the MEG provides a powerful consistency guarantee while being available during network partition. Second, we discuss the implications of byzantine attackers on the data type’s properties. We note that the MEG, as it does not strive for consensus or strong consistency, can cope with $n > f$ environments with $n$ participants, of which $f$ are byzantine. Furthermore, we analyze scalability: Using Markov chains, we study the number of forward extremities of the MEG over time and observe an almost optimal evolution. We conjecture that this property is inherent to the underlying spatially inhomogeneous random walk. With the properties shown, a MEG represents a promising element in the set of data structures for decentralized applications, but with distinct trade-offs compared to traditional blockchains and distributed ledger technologies.

Conflict-free Data Types (CRDTs) were designed to automatically resolve conflicts in eventually consistent systems. Different CRDTs were designed in both operation-based and state-based flavors such as Counters, Sets, Registers, Maps, etc. In a previous paper [2], Baquero et al. presented the problem with embedded CRDT counters and a solution, covering state-based counters that can be embedded in maps, but needing an ad-hoc extension to the standard counter API. Here, we present a resettable operation-based counter design, with the standard simple API and small state, through a causalstability- based state compaction., Project "Coral - Sustainable Ocean Exploitation: Tools and Sensors/NORTE-01-0145-FEDER-000036" is financed by the North Portugal Regional Operational Programme (NORTE 2020), under the PORTUGAL 2020 Partnership Agreement, and through the European Regional Development Fund (ERDF). The research leading to these results has received funding from the European Union’s Horizon 2020 - The EU Framework Programme for Research and Innovation 2014-2020, under grant agreement No. 732505, project LightKone. Project "TEC4Growth - Pervasive Intelligence, Enhancers and Proofs of Concept with Industrial Impact/NORTE-01-0145-FEDER-000020" is financed by the North Portugal Regional Operational Programme (NORTE 2020), under the PORTUGAL 2020 Partnership. Agreement, and through the European Regional Development Fund (ERDF).

Conflict-free Replicated Data Types (CRDTs) are data abstractions (registers, counters, sets, maps, among others) that provide a relaxed consistency model called Eventual Consistency. Current designs for CRDT counters do not scale, having a size linear with the number of both active and retired nodes (i.e., nodes that leave the system permanently after previously manipulating the value of the counter). In this paper we present a new counter design called Borrow-Counter, that provides a mechanism for the retirement of transient nodes, keeping the size of the counter linear with the number of active nodes., Project "TEC4Growth - Pervasive Intelligence, Enhancers and Proofs of Concept with Industrial Impact/NORTE-01-0145-FEDER-000020" is financed by the North Portugal Regional Operational Programme (NORTE 2020), under the PORTUGAL 2020 Partnership Agreement, and through the European Regional Development Fund (ERDF). The research leading to these results has received funding from the European Union’s Horizon 2020 - The EU Framework Programme for Research and Innovation 2014-2020, under grant agreement No. 732505, project LightKone., info:eu-repo/semantics/publishedVersion

This paper combines various self-stabilization techniques within a replication protocol that ensures eventual consistency in largescale distributed systems subject to network partitions and asynchrony. A simulation study shows that the resulting protocol is scalable and achieves high throughput under load. Our protocol does not rely on any form of consensus, which would lead to block the replicas in case of partitions and asynchrony. Our protocol instead ensures that (1) updates are continuously applied to the replicas and (2) no two updates are ever performed in a different order. Gaps might occur during periods of unreliable communication. They are filled whenever connectivity is provided, and consistency is then eventually ensured, but without any conscious commitment. That is, there is no point in the computation when replicas know that consistency is achieved. This unconsciousness is the key to tolerating perpetual asynchrony with no consensus support.

The Internet is a formidable tool for education, communication and collaboration, however it is currently being monopolized by large corporations (GAFAM), which has consequences for many social issues such as respect of human rights and individual freedoms. This thesis focuses on ways to build decentralized applications: Internet applications that provide levels of functionality similar to those provided by the GAFAM, but that function in a decentralized manner, empowering the users to democratically decide of their functioning and their uses. We focus on epidemic algorithms, which are particularly suited to the context of very large open networks. We make contributions on causal broadcast in presence of Byzantine nodes, epidemic causal broadcast using an event store synchronized with an anti-entropy algorithm, random peer sampling in presence of Byzantine nodes and Sybil attacks, as well as a new epidemic total order broadcast which is tolerant to malicious nodes and provides high throughput message delivery.; Internet est un outil formidable pour l'éducation, la communication et la collaboration, mais ses usages majoritaires sont actuellement sous monopole de grandes multinationales (GAFAM), ce qui a des conséquences sur le respect des droits humains et des libertés individuelles. Cette thèse propose des outils pour le développement d'applications décentralisées : des applications sur Internet qui fournissent des fonctionnalités similaires aux plateformes des GAFAM, mais de manière décentralisée, afin de rendre le pouvoir aux utilisateur pour décider démocratiquement de leur fonctionnement et de leurs usages. Nous nous concentrons sur les algorithmes épidémiques qui sont particulièrement adaptés dans le cadre de réseaux ouverts à large échelle. Nous proposons des contributions sur la diffusion causale de messages tolérante aux nœuds Byzantins, la diffusion causale épidémique à l'aide d'un stockage d'événements synchronisé par anti-entropie, l'échantillonnage aléatoire de pairs résistants aux attaques Byzantines et aux attaques Sybil, ainsi qu'un nouvel algorithme épidémique de diffusion totalement ordonnée qui tolère les nœuds malicieux et fournit un débit de messages élevé.

Transmission faults allow us to reason about permanent and transient value faults in a uniform way. However, all existing solutions to consensus in this model are either in the synchronous system, or require strong conditions for termination, that exclude the case where all messages of a process can be corrupted. In this paper we introduce eventual consistency in order to overcome this limitation. Eventual consistency denotes the existence of rounds in which processes receive the same set of messages. We show how eventually consistent rounds can be simulated from eventually synchronous rounds, and how eventually consistent rounds can be used to solve consensus. Depending on the nature and number of permanent and transient transmission faults, we obtain different conditions on $$n$$ , the number of processes, in order to solve consensus in our weak model.

GentleRain is a new causally consistent geo-replicated data store that provides throughput comparable to eventual consistency and superior to current implementations of causal consistency. GentleRain uses a periodic aggregation protocol to deter- mine whether updates can be made visible in accordance with causal consistency. Unlike current implementations, it does not use explicit dependency check messages, result- ing in a major throughput improvement at the expense of a modest increase in update visibility. Furthermore, GentleRain tracks causal consistency by attaching to updates scalar timestamps derived from loosely synchronized physical clocks. Clock skew does not cause violations of causal consistency, but may delay the visibility of updates. By en- coding causality in a single scalar timestamp, GentleRain reduces storage and communication overhead for tracking causality. We evaluate GentleRain using Amazon EC2, and demonstrate that it achieves throughput equal to about 99% of eventual consistency, and 120% better than previous implementations of causal consistency.

Wireless communications along with portable computers, digital assistants and sensor devices provide a pervasive base for mobile computing. However realizing truly ubiquitous mobile computing requires innovative theories, paradigms and applications in various research areas including algorithms, networking, software architectures and data management. Topic 14 covers all such aspects. This topic attracted 33 submissions showing the increasing interest in the field. From the submitted papers, 8 were accepted as full papers (24% acceptance rate). The selected papers cover various aspects of mobile and ubiquitous computing highlighting the diversity of the field and thus making up an interesting and stimulating track. Paper presentations are divided into three sessions. Two papers in the first session address consistency issues. In “Efficient and Fault-Tolerant Update Commitment for Weakly Connected Replication”, J. Barreto and P. Ferreira propose a novel epidemic weighted voting protocol for achieving eventual consistency in optimistic replication that allows multiple update candidates in an election. In “Controlling Concurrency in Mobile Computing Environments with Broadcast-based Dissemination”, J. M. Monteiro and A. Brayner present a new serializability-based protocol for ensuring data consistency and currency when data are disseminated to clients through wireless broadcast. The last paper in this session, “Integrating Mobile Devices into the Grid: Design Considerations and Evaluation” by S. Isaiadis and V. Getov, discusses implementation and performance issues for integrating mobile devices into the grid. The second session is shared with Topic 8. The two papers address aspects related to frequency utilization in wireless networking. In “New Bounds on the Competitiveness of Randomized Online Call Control in Cellular Networks”, I. Karagiannis, C. Kaklamanis and E. Papaioannou present new upper and lower bounds for the online version of the call control problem in wireless cellular networks. In “A Multiple Channel Access Protocol for Ad Hoc Wireless Networks”, K-W. Jang considers the problem of enhancing channel utilization in wireless ad hoc networks through channel exchange between neighboring nodes. In the last session, in “Personalized Access to Semantic Web Agents Using Smart Cards”, R. C. Erdur and G. Kardas argue for storing personal information on smart cards. The other two papers focus on secure networking. K. Kim, J. Hong and J. Lim present a “Fast and Secure Communication Resume Protocol” to speed up connection resume after a communication error. In “On AAA with Extended IDK in Mobile IP Networks”, H. Jeon, M. Y. Chung and H. Choo discuss how to attain fast and secure mobile IP networking by addressing problems of the hand-off process in a secure way.