Lower Bound On The Storage Cost Of Shared Memory Emulation

Date(s):

Location:
Jacobs Hall, Room 2512, Jacobs School of Engineering, 9500 Gilman Dr, La Jolla, San Diego, California 92093

Sponsored By:
Professor Young-Han Kim

Speaker(s):
Professor Zhiying Wang
Department of Electrical and Computer Science
University of California, Irvine
Zhiying Wang

Abstract:

 

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.


Speaker Bio:
Zhiying Wang is an Assistant Professor at University of California, Irvine. She was a postdoctoral research fellow at Stanford University. She received Ph.D. and M.S. in Electrical Engineering at California Institute of Technology, and B.S. in Information and Electronic Engineering at Tsinghua University. Her research interests include information theory, coding for data storage, and compression for genomic information. She is the recipient of IEEE data storage best paper award and NSF Center for Science of Information Postdoctoral Fellowship.

Contact:
Cheryl Wills
Jacobs Hall, Room 2903
858-534-2498
clwills@eng.ucsd.edu