Eventually consistent systems can be made more consistent by reducing the time until a write is fully replicated, thereby improving global update visibility. While gossip-based anti-entropy methods scale well, random selection of anti-entropy partners is less than efficient. Moreover, while eventual consistency may be consistent enough in a single data center, geographic replication increases visibility latency and leads to externally observable inconsistencies. In this paper, we explore an improvement to pairwise, bilateral anti-entropy; instead of uniform random selection, we introduce reinforcement learning mechanisms to assign selection probabilities to replicas most likely to have information. The result is more efficient replication, faster visibility, and stronger eventual consistency while maintaining high availability and partition tolerance.

Groups of strongly consistent devices can efficiently order events under ideal (data center) conditions, but become less effective in dynamic and heterogeneous environments. Weakly consistent devices efficiently tolerate both faults and dynamic conditions but are slow to converge on a single ordering of system events. We propose "federated consistency", which combines the strengths of both approaches into a single protocol. Federated groups use a strongly consistent inner core of devices to maintain a totally ordered, fault-tolerant sequence of events. A cloud of weakly-consistent devices disseminates orderings and enables progress despite varying connectivity and partitions. Though the constituent sub-protocols take different (nearly opposite) approaches to resolving conflicts; we show that expanding distributed version vectors with a forte component allows them to inter-operate effectively.

We introduce Hierarchical Consensus, an approach to generalizing consensus that allows us to scale groups beyond a handful of nodes, across wide areas. Hierarchical Consensus increases the availability of consensus groups by partitioning the decision space and nominating distinct leaders for each partition. Partitions eliminate distance by allowing decision-making to be co-located with replicas that are responding to accesses. A root quorum guarantees global consistency and fault tolerance. Hierarchical consensus is flexible locally, but improves upon prior approaches by balancing load, allowing fast replication across wide areas, and enabling consensus across large (> 100) systems of devices.

This paper describes the design and evaluation of\spore, a secure cloud-based file system that minimizes trust and functionality assumptions on underlying servers. \spore differs from other systems in that system relationships are formalized only through signed data objects, rather than in complicated protocols executed between clients and servers. This approach allows Spore to bootstrap a file system from a single object, providing integrity and security guarantees while storing all data as simple, immutable objects on untrusted servers. We use simulation to characterize the performance of this system, focusing primarily on the cost incurred in compensating for the minimal server support. We show that while a naive approach is quite inefficient, a series of simple optimizations can enable the system to perform well in real-world scenarios.