Lewis Tseng: Resilient Causal Memory in Client-Server Model

We study how to emulate resilient causal memory in the client-server model over asynchronous message- passing network. Clients host applications and need to read and write the shared memory (in the forms of key-value pairs), whereas servers store and manage the memory so that it satisfies causal consistency. Any client and up to f servers may crash, i.e., suffer fail-stop failures. Under our model, we identify the tradeoff between correctness conditions and resilience bounds. In particular, we have the following contributions:
• We prove that 2f +1 is the lower bound on the number of servers for implementing resilient causal memory under two natural convergence properties (persistence and weak convergence).
• We present two optimal algorithms that match the bounds, proving that all the derived bounds are tight. One algorithm works for more general setup, whereas the other is faster due to its “non-blocking” property