| dc.description.abstract | In this thesis, we cover three major areas, namely, index coding, coded caching and gradient coding. We begin by considering unicast index coding problems where a server broadcasts coded messages over a noiseless channel, to a set of receivers which knows some messages a priori, in such a way that all the receivers can decode their desired messages. For unicast index coding problems with the special structure on the side-information graphs called Interlinked Cycle (IC) structures, index codes have been proposed in the literature. We relax the definition of IC structures by removing one of the requirements in the definition to define a wider class of side-information graphs called Generalized Interlinked Cycle (GIC) structures. In this thesis, optimal index code construction for GIC structures is explored. Construction of optimal length error correcting index code is also discussed for such GIC structures.
There have been several variants and extensions to the index coding problem studied in the literature. One such variant of index coding problem formulated in the literature is Pliable Index Coding (PICOD) problem, where the setting is same as that of index coding problem, i.e., we consider a server holding a set of messages and a set of users having a subset of messages available with them. The only difference is that in PICOD problem, each user is satisfied if it receives any of the messages it doesn't have. We study some of the extensions of PICOD problems in this thesis where we assume that the side-information is consecutive. We introduce the notion of security in PICOD problems where each user gets exactly one desired message. The second extension studied is PICOD problems where the total number of messages decoded by the effective users is maximized. Another extension of index coding problem is Constrained Pliable Index Coding Problem where each message is decoded by at most c users demanding that message. We provide index codes for all these three extensions of PICOD problems with consecutive side-information.
In index coding problem as well as PICOD problem, there will be a central server which is responsible for all the transmissions done. In contrast to this, a new extension called Embedded Index Coding Problem (EICP) was studied in literature which was motivated by its application in distributed computing where every user can act as sender for other users. We introduce the idea of sub-packetization of the messages in index coding problems to provide a novel code construction for a special class of EICP termed as Consecutive and Symmetric Embedded Index Coding Problem (CS-EICP) in contrast to the scalar linear solutions provided in the prior works. An extension to EICP- task based EICP is also studied, where each user can use transmissions from only one other user. We provide code construction for task based CS-EICP as well when each user demands only one message.
In the second part, we consider a generalization of well-known coded caching problem, referred as multi-access coded caching problem, where each user has access to z neighboring caches in a cyclic wrap-around way. We present placement scheme and delivery algorithms for this problem, under the restriction of uncoded placement. We consider two classes of multi-access coded caching problems in this thesis. The first class under consideration is a generalization of one of the cases considered in ``Multi-access coded caching : gains beyond cache-redundancy'' by B. Serbetci, E. Parrinello and P. Elia. To be precise, when our scheme is specialized to z={K-1}/{K \gamma }, for any K\gamma, where K is the number of users and \gamma is the normalized cache size, we show that our result coincides with their result.
We show that for the cases considered, our scheme outperforms the scheme proposed in ``Rate-memory trade-off for multi-access coded caching with uncoded placement'' by K. S. Reddy and N. Karamchandani, except for some special cases considered in that paper. We also show that for z= K-1, our scheme achieves the optimal transmission rate.
In this thesis, we construct a new class of Placement Delivery Array (PDA) which we call as t-cyclic g-regular PDA. This class of PDA is used for providing the delivery scheme for the second class of multi-access coded caching problems under consideration. The sub-packetization level required for our scheme is the least compared to the state-of-the-art schemes for this class. For certain ranges of values of z, the transmission rate is also less compared to some of the existing schemes.
Lastly, we address the gradient coding problem by finding efficient code construction that minimizes per-server task sizes with the flexibility of tiered launching of tasks. Coding theoretic techniques have been proposed for performing synchronous gradient descent on multiple servers to mitigate stragglers. These techniques provide the flexibility that the job is complete when any k out of n servers finish their assigned tasks. The task size on each server is found based on the values of k and n. However, it is assumed that all the n jobs are started when the job is requested. In contrast, we assume a tiered system, where we start with n_1> k tasks, and on completion of c tasks, we start n_2-n_1 more tasks. The aim is that as long as k servers can execute their tasks, the job gets completed. This thesis exploits the flexibility that not all servers are started at the request time to obtain reduced task sizes on each server. This helps to reduce the job completion time as well as the total server utilization cost (total time any server is being used for computation). | en_US |
