A Survey on Network Codes for Distributed Storage <s> B. Exact-MSR Codes <s> In a multiple-antenna system with two transmitters and two receivers, a scenario of data communication, known as the X channel, is studied in which each receiver receives data from both transmitters. In this scenario, it is assumed that each transmitter is unaware of the other transmitter's data (noncooperative scenario). This system can be considered as a combination of two broadcast channels (from the transmitters' points of view) and two multiple-access channels (from the receivers' points of view). Taking advantage of both perspectives, two signaling schemes for such a scenario are developed. In these schemes, some linear filters are employed at the transmitters and at the receivers which decompose the system into either two noninterfering multiple-antenna broadcast subchannels or two noninterfering multiple-antenna multiple-access subchannels. The main objective in the design of the filters is to exploit the structure of the channel matrices to achieve the highest multiplexing gain (MG). It is shown that the proposed noncooperative signaling schemes outperform other known noncooperative schemes in terms of the achievable MG. In particular, it is shown that in some specific cases, the achieved MG is the same as the MG of the system if full cooperation is provided either between the transmitters or between the receivers. In the second part of the paper, it is shown that by using mixed design schemes, rather than decomposition schemes, and taking the statistical properties of the interference terms into account, the power offset of the system can be improved. The power offset represents the horizontal shift in the curve of the sum-rate versus the total power in decibels. <s> BIB001 </s> A Survey on Network Codes for Distributed Storage <s> B. Exact-MSR Codes <s> In this paper, we propose a new way of interference management for cellular networks. We develop the scheme that approaches to interference-free degree-of-freedom (dof) as the number K of users in each cell increases. Also we find the corresponding bandwidth scaling conditions for typical wireless channels: multi-path channels and single-path channels with propagation delay. The scheme is based on interference alignment. Especially for more-than-two-cell cases where there are multiple non-intended BSs, we propose a new version of interference alignment, namely subspace interference alignment. The idea is to align interferences into multi-dimensional subspace (instead of one dimension) for simultaneous alignments at multiple non-intended BSs. The proposed scheme requires finite dimensions growing linearly with K, i.e., ~O(K). <s> BIB002 </s> A Survey on Network Codes for Distributed Storage <s> B. Exact-MSR Codes <s> We consider the problem of recovering from a single node failure in a storage system based on an (n, k) MDS code. In such a scenario, a straightforward solution is to perform a complete decoding, even though the data to be recovered only amount to 1/kth of the entire data. This paper presents techniques that can reduce the network traffic incurred. The techniques perform algebraic alignment so that the effective dimension of unwanted information is reduced. <s> BIB003 </s> A Survey on Network Codes for Distributed Storage <s> B. Exact-MSR Codes <s> The high repair cost of (n,k) Maximum Distance Separable (MDS) erasure codes has recently motivated a new class of codes, called Regenerating Codes, that optimally trade off storage cost for repair bandwidth. On one end of this spectrum of Regenerating Codes are Minimum Storage Regenerating (MSR) codes that can match the minimum storage cost of MDS codes while also significantly reducing repair bandwidth. In this paper, we describe Exact-MSR codes which allow for any failed nodes (whether they are systematic or parity nodes ) to be regenerated exactly rather than only functionally or information-equivalently. We show that Exact-MSR codes come with no loss of optimalitywith respect to random-network-coding based MSR codes (matching the cutset-based lower bound on repair bandwidth) for the cases of: (a) k/n � 1/2; and (b) k � 3. Our constructive approach is based on interference alignment techniques, and, unlike the previous class of random-network-coding based approaches, we provide explicit and deterministic coding schemes that require a finite-field size of at most 2(n − k). <s> BIB004
The new idea is interference alignment BIB001 ,  . The idea of interference alignment is to align multiple interference signals in a signal subspace whose dimension is smaller than the number of interferers. Specifically, consider the following setup where a decoder has to decode one desired signal that is linearly interfered with by two separate undesired signals. How many linear equations (relating to the number of channel uses) does the decoder need to recover its desired input signal? As the aggregate signal dimension spanned by desired and undesired signals is at most three, the decoder can naively recover its signal of interest with access to three linearly independent equations in the three unknown signals. However, as the decoder is interested in only one of the three signals, it can decode its desired unknown signal even if it has access to only two equations, provided the two undesired signals are judiciously aligned in a 1-D subspace. See BIB001 - BIB002 for details. This concept relates intimately to our repair problem that involves recovery of a subset (related to the subspace spanned by a failed node) of the overall aggregate signal space (related to the entire user data dimension). This attribute was first observed in BIB003 , where it was shown that interference alignment could be exploited for exact-MSR codes. Fig. 8 illustrates interference alignment for exact repair of failed node 1 for ðn; k; d; ; Þ ¼ ð4; 2; 3; 2; 2Þ where the maximum file size of M ¼ 4 can be stored. We introduce matrix notation for illustration purposes. Let a ¼ ða 1 ; a 2 Þ t and b ¼ ðb 1 ; b 2 Þ t be 2-D information-unit vectors. Let A i and B i be 2-by-2 encoding matrices for parity node i ði ¼ 1; 2Þ, which contain encoding coefficients for the linear combination of ða 1 ; a 2 Þ and ðb 1 ; b 2 Þ, respectively. For example, parity node 1 stores blocks in the form of a t A 1 þ b t B 1 , as shown in Fig. 8 . The encoding matrices for systematic nodes are not explicitly defined since those are trivially inferred. Finally, we define 2-D projection vectors v i 's ði ¼ 1; 2; 3Þ because of ¼ 1. Let us explain the interference-alignment scheme. First, two blocks in each storage node are projected into a scalar with projection vectors v i 's. By connecting to three nodes, we get: v t Here the goal is to decode two desired unknowns out of three equations including four unknowns. To achieve this goal, we need rank The second condition can be met by setting This choice forces the interference space to be collapsed into a 1-D linear subspace, thereby achieving interference alignment. On the other hand, we can satisfy the first condition as well by carefully choosing the A i 's and B i 's. For exact repair of node 2, we can apply the same idea. For parity node repair, we can remap parity node information and then apply the same technique. It turned out that this idea cannot be generalized to arbitrary ðn; kÞ case: it provides the optimal codes only for the case of k ¼ 2. Recently, significant progress has been made: for the case of ðk=nÞ ð1=2Þ, it has been shown that there is no price with exact repair for attaining the cutset lower bound of (5). BIB004 ): Suppose the MDS code rate is at most 1/2, i.e., ðk=nÞ ð1=2Þ and the degree d ! 2k À 1. Then, the cutset bound of (5) can be achieved with interference alignment. The achievable scheme is deterministic and requires a finite-field alphabet size of at most 2ðn À kÞ.