Combinatorial designs for distributed storage, function computation and coded caching

Friday, October 21, 2016
UTA 7.532

Combinatorial design theory has its roots in recreational mathematics and is concerned with the arrangement of the elements of a finite set into subsets, such that the collection of subsets has certain “nice” properties. In this talk we shall demonstrate that interpreting designs in the right manner yields improved solutions for distributed storage and content caching and novel impossibility results for distributed function computation.

Regenerating codes have been proposed as an efficient mechanism for dealing with the problem of reliability in large scale distributed storage systems. These systems also have additional requirements pertaining to repair. When nodes fail, the system needs to be repaired in a speedy manner by consuming as few resources (number of drives accessed, energy etc.) as possible. We will demonstrate that combinatorial designs allow us to design efficient systems that upon failure can be repaired by simply downloading packets from the surviving nodes.

Next, we will show that designs can be used to construct a family of directed acyclic networks that have several interesting properties. In particular, our work shows that the computation rate of such networks depends significantly on the source alphabets. This is in stark contrast with multiple unicast networks where the rate is independent of the source alphabet. We will conclude with an overview of the role of coding in content caching networks and our recent results on how combinatorial designs can play a central role in making coded caching more practical.

The talk will be self-contained; no background in combinatorial designs and/or network coding will be assumed.



Aditya Ramamoorthy is an Associate Professor of Electrical and Computer Engineering at Iowa State University. He received his B. Tech. degree in Electrical Engineering from the Indian Institute of Technology, Delhi in 1999 and the M.S. and Ph.D. degrees from the University of California, Los Angeles (UCLA) in 2002 and 2005 respectively. From 2005 to 2006 he was with the data storage signal processing group at Marvell Semiconductor Inc. His research interests are in the areas of network information theory, channel coding and signal processing for nanotechnology and bioinformatics. Dr. Ramamoorthy is currently serving as an associate editor for the IEEE Transactions on Information Theory. From 2011 – 2014, he served as an editor for the IEEE Transactions on Communications. He is the recipient of the 2012 Iowa State University's Early Career Engineering Faculty Research Award, the 2012 NSF CAREER award, and the Harpole-Pentair professorship in 2009 and 2010.