Friday, December 7, 2018 - 1:00pm to 2:30pm

Location:

32-G631

Speaker:

Lewis Tseng

Biography:

Boston College

Seminar group:

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

• 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