Abstract:
We describe a natural and general model of distributed storage. To ensure that a message stored in the system remains recoverable as nodes fail and are replaced with new nodes, a repairer continually accesses data stored at the nodes, performs computations on the accessed data, and stores results of the computations back to the nodes.

Our primary focus is on the trade-offs between storage overhead and the amount of repair traffic generated by the repairer to maintain recoverability of the message. We provide lower bounds and upper bounds on these trade-offs. The lower bounds are information-theoretic, i.e., we prove no repairer can operate below certain storage overhead/repair traffic trade-offs. The upper bounds are algorithmic, i.e., we prove there is a specific repairer algorithm that can operate within certain storage overhead/repair traffic trade-offs. In important cases the lower and upper bounds are essentially matching.

Bio:
Mike Luby is Vice President, Technology, Qualcomm Technologies, Inc, focusing on advanced research, including reliable distributed storage, broadcast multimedia delivery, and Internet streaming. He has been recognized for his work in coding theory, cryptography and content delivery technologies, including the IEEE Richard W. Hamming Medal, the ACM Paris Kannelakis Theory and Practice Award, the IEEE Eric E. Sumner Communications Theory Award, and the UC Berkeley Distinguished Alumni in Computer Science Award. Mike earned a BSc in Applied Math from MIT and a PhD in Theoretical Computer Science from UC Berkeley. He is a IEEE Fellow, ACM fellow, and member of the National Academy of Engineering.

Link to event.