[month] [year]

Shailja Agrawal – ECE

Shailja Agrawal   received her MS Dual Degree in Electronics and Communication Engineering (ECE). Her  research work was supervised by Dr. Prasad Krishnan. Here’s a summary of  Shailja Agrawal’s M.S thesis, Designing Low Complexity Coded Caching and Coded Computing Schemes using Combinatorial Designs as explained by her: 

The major contribution of this work is the construction of binary matrices from combinatorial designs. These binary matrices with certain properties are used to construct different coded caching and distributed computing schemes. The coded caching scenario consists of a broadcast setup with a single server broadcasting information to a number of clients, each of which contains local storage (called cache) of some size, which can store some parts of the available files at the server. The centralized coded caching framework, consists of a caching phase and a delivery phase, both of which are carefully designed in order to use the cache and the channel together optimally. In prior literature, various combinatorial structures have been used to construct coded caching schemes. The binary matrix model proposed in this work, is used to construct the coded caching scheme. The ones in such a caching matrix indicate uncached subfiles at the users. Identity submatrices of the caching matrix represent transmissions in the delivery phase. Using this model, we then propose several novel constructions for coded caching based on the various types of combinatorial designs. While most of the schemes constructed in this work (based on existing designs) have a high cache requirement (uncached fraction being Θ( √ 1 K ) or Θ( 1 K ), K being the number of users), they provide a rate that is either constant or decreasing (O( 1 K )) with increasing K, and moreover require competitively small levels of subpacketization (being O(Ki ), 1 ≤ i ≤ 3), which is an extremely important parameter in practical applications of coded caching. We also consider the distributed computing framework of MapReduce, which consists of three phases, the Map phase, the Shuffle phase and the Reduce phase. For this framework, we propose the use of binary matrices (with 0, 1 entries) called computing matrices to describe the map phase and the shuffle phase. Similar binary matrices were recently proposed for the coded caching framework. The structure of ones and zeroes in the binary computing matrix captures the map phase of the MapReduce framework. We present a new simple coded data shuffling scheme for this binary matrix model, based on an identity submatrix cover of the computing matrix. This new coded shuffling scheme has in general a larger communication load than existing schemes, but has the advantage of less complexity overhead than the well-known earlier schemes in literature in terms of the file-splitting and associated indexing and coordination required. We also show that there exists a binary matrix based distributed computing scheme with our new data-shuffling scheme which has strictly less than twice than the communication load of the known optimal scheme in literature. The structure of this new scheme enables it to be applied to the framework of MapReduce with stragglers also, in a straightforward manner, borrowing its advantages and disadvantages from the no-straggler situation. Finally, using binary matrices derived from combinatorial designs, we show specific classes of computing schemes with very low file complexity (number of subfiles in the file), with marginally higher communication load compared to the optimal scheme for equivalent parameters. We mark this work as another attempt to exploit the well-developed theory of combinatorial designs for the problem of constructing caching schemes and distributed computing schemes, utilizing the binary caching model we develop.

  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •