Shared memory emulation are important algorithms that bridge the two communication models of asynchronous distributed systems: the shared-memory model, and the message-passing model. Previous literature has developed several shared memory emulation algorithms based on replication and erasure coding techniques. In this talk, we present information-theoretic lower bounds on the storage costs incurred by such algorithms. We show that the storage cost is at least twice that of the Singleton-type of bound; and for a restricted class of write protocols, the storage cost grows approximately linearly with the number of servers failures and the number of concurrent writes in an execution. An interesting observation is that, when the number of concurrent writes is large, replication based algorithms have asymptotically optimal storage cost.
Jacobs Hall, Room 2903