Practical Client-side Replication: Weak Consistency Semantics for Insecure Settings

Client-side replication and direct client-to-client synchronization can be used to create highly available, low-latency interactive applications. Causal consistency, the strongest available consistency model under network partitions, is an attractive consistency model for these applications. This paper focuses on how client misbehaviour impacts causal consistency. We analyze the possible attacks to causal consistency and derive secure consistency models that preclude different types of misbehaviour. We propose a set of techniques for implementing such secure consistency models, which exhibit different trade-offs between the application guarantees, and the latency and communication overhead. Our evaluation shows that secure consistency models impose low overhead when compared with their insecure counterparts, while providing low user-to-user latency and server load compared with traditional client-server architectures. Secure consistency models can be used to enrich server-based architectures with fast and secure peer-to-peer interactions.