Abstract

MapReduce is a widely used framework for distributed computing. Data shuffling between the Map phase and Reduce phase of a job involves a large amount of data transfer across servers, which in turn accounts for increase in job completion time. Recently, Coded MapReduce has been proposed to offer savings with respect to the communication cost incurred in data shuffling. This is achieved by creating coded multicast opportunities for shuffling through repeating Map tasks at multiple servers. We consider a server-rack architecture for MapReduce and in this architecture, propose to divide the total communication cost into two: intrarack communication cost and cross-rack communication cost. Having noted that cross-rack data transfer operates at lower speed as compared to intrarack data transfer, we present a scheme termed as Hybrid Coded MapReduce which results in lower cross-rack communication than Coded MapReduce at the cost of increase in intra-rack communication. In addition, we pose the problem of assigning Map tasks to servers to maximize data locality in the framework of Hybrid Coded MapReduce as a constrained integer optimization problem. We show through simulations that data locality can be improved considerably by using the solution of optimization to assign Map tasks to servers.

Abstract

Linear index coding can be formulated as an inter-ference alignment problem, in which precoding vectors of theminimum possible length are to be assigned to the messagesin such a way that the precoding vector of a demand (at somereceiver) is independent of the space of the interference (non side-information) precoding vectors. An index code has rate1lif theassigned vectors are of lengthl. In this paper, we introduce thenotion of strictly rate1Lmessage subsets which must necessarilybe allocated precoding vectors from a strictlyL-dimensionalspace (L=1,2,3) in any rate13code. We develop a generalnecessary condition for rate13feasibility using intersections ofstrictly rate1Lmessage subsets. We apply the necessary conditionto show that the presence of certain interference configurationsmakes the index coding problem rate13infeasible. We alsoobtain a class of index coding problems, containing certaininterference configurations, which are rate13feasible based on theidea ofcontractionsof an index coding problem. Our necessaryconditions for rate13feasibility and the class of rate13feasibleproblems obtained subsume all such known results for rate13index coding

Abstract

An index coding problem withn messages has symmetric rate R if all n messages can be conveyed at rate R. In a recent work, a class of index coding problems for which symmetric rate13is achievable was characterised using special properties of the side-information available at the receivers. In this paper, we show a larger class of index coding problems(which includes the previous class of problems) for which symmetric rate13is achievable. In the process, we also obtain a stricter necessary condition for rate13feasibility than what is known in literature.

Abstract

A code is said to be data-local maximally recoverable if (i) all the information symbols have locality and (ii) any erasure pattern which can be potentially recovered (i.e., the number of equations is equal to the number of unknowns) is recovered by the code. A code is said to be local maximally recoverable if(i) all the symbols of the code have locality and (ii) from the above holds. In this paper, we establish the matroid structures corresponding to data-local and local maximally recoverable codes (MRC). The matroid structures of these codes can be used to determine the associated Tutte polynomial. Greene proved that the weight enumerators of any code can be determined from its associated Tutte polynomial. We will use this result to derive explicit expressions for the weight enumerators of data-local MRC. Also, Britz proved that the higher support weights of any code can be determined from its associated Tutte polynomial.We will use this result to derive expressions for the higher support weights of data-local and local MRC with two local codes.