{'fraction_non_alphanumeric': 0.04199863419075803, 'fraction_numerical': 0.009617573412246757, 'mean_word_length': 4.402090378112511, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 12, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Babel Storage: Uncoordinated Content Delivery from Multiple Coded Storage Systems

In future content-centric networks, content is identified independently of its location. From an end-user's perspective, individual storage systems dissolve into a seemingly omnipresent structureless `storage fog'. Content should be delivered oblivious of the network topology, using multiple storage systems simultaneously, and at minimal coordination overhead. Prior works have addressed the advantages of error correction coding for distributed storage and content delivery separately. This work takes a comprehensive approach to highlighting the tradeoff between storage overhead and transmission overhead in uncoordinated content delivery from multiple coded storage systems. Our contribution is twofold. First, we characterize the tradeoff between storage and transmission overhead when all participating storage systems employ the same code. Second, we show that the resulting stark inefficiencies can be avoided when storage systems use diverse codes. What is more, such code diversity is not just technically desirable, but presumably will be the reality in the increasingly heterogeneous networks of the future. To this end, we show that a mix of Reed-Solomon, low-density parity-check and random linear network codes achieves close-to-optimal performance at minimal coordination and operational overhead.


I. INTRODUCTION
In current communication networks, content is addressed by its (alleged) location, e.g., through its URL. Content delivery is carried out only by the hosting storage system. Different 'hacks', e.g., GeoDNS and IPv4 anycast [1], are used to overcome the shortcomings of this approach. In future contentcentric networks, content is identified independent of its location [2]. From an end-user's perspective, individual storage systems dissolve into a seemingly omnipresent, structureless and thus flexible 'storage fog'. This storage facility delivers the desired data without requiring the user to know about the data's location. File delivery can be carried out by multiple storage systems simultaneously, and transparently to the user.
Storage systems use error correcting codes [3] to improve reliability in the presence of temporary and permanent disk failures. Different code families have been investigated for application in coded storage systems, such as Reed-Solomon codes (RS-Cs) [4]- [6], random linear network codes (RLN-Cs) [7], low-density parity-check codes (LDPC-Cs) [8]- [11] and locally repairable codes (LR-Cs) [12], [13], among many other codes [14]- [18]. As there is no clear 'best' coding system, a diverse mix of codes is expected to be found among the different storage units of a storage fog. A separate line of works has studied the benefits of introducing redundant information via error correcting codes for content delivery in wireless networks [19], such as for caching [20], [21], using device-to-device communications [22], or in gossip protocols [23], [24].
How can multiple storage systems, employing a mix of different error correcting codes, jointly deliver content to a user with high throughput, low coordination overhead, and low complexity? In particular, how can we combine the two so far isolated approaches of coding for storage and coding for content delivery? This is the question guiding our work in this paper. We present our results as follows. In Section II, we introduce the system model. We then look at two extreme cases regarding the used codes. First, in Section III, we use exactly the same code on all participating storage systems. We show that storage redundancy, while originally introduced to improve reliability, also helps in efficient file delivery. We characterize the tradeoff between storage and transmission overhead. Second, in Section IV, we examine the opposite extreme of using different codes. In particular, we combine RS-Cs, RLN-Cs and LDPC-Cs, and demonstrate that the combination behaves similar to a low-field-size random code. We summarize the implications of our findings as relevant to system implementers and network operators in Section V.

II. SYSTEM MODEL
We denote the finite field of characteristic p as F p and its extension field of degree m as F p m . We sometimes write F q for F p m implying that q = p m . Note that F q m is isomorphic to the m-dimensional F q -vector space F m q . We use lower-case Greek letters for field elements, lower-case Latin bold letters for vectors, and upper-case Latin bold letters for matrices. As customary in coding theory, vectors denote row vectors unless stated otherwise. Transposition is (.) .
Fix a block length n, dimension k ≤ n, and field F q , then a [n, k] q linear block code C with rate R k n is a k-dimensional subspace of F n q . The code can equivalently be represented using a generator matrix G ∈ F k×n q or a parity-check matrix H ∈ F A file is stored and distributed using S different storage systems in the following way. For each storage system i ∈ {1, ..., S}, the file u is encoded into c i which is stored. Some symbols of c i get erased over time; the remaining ones are collected in the vectorĉ i . Of these, some are chosen for transmission; the symbols that arrive at the requesting user are denoted asc i . As long as rank G 1 . . .G S = k, the fileû = u can be decoded.
Note that neither G nor H are unique and that G fixes the mapping between information symbols u and codeword symbols c as During storage and transmission, some number n E of symbols of the codeword c might get erased, so that only a subsetc ∈ F n−nE q is received. Thec relate to u asc = uG via a reduced G ∈ F k×(n−nE) q where those columns of G are removed that correspond to the erased symbols in c. As long asG is full rank (i.e., rankG = k),c = uG has a unique solution and u can be recovered fromc, e.g., using Gaussian elimination in runtime complexity O(k 3 ).
The storage and distribution of a file using S different storage systems is depicted in Fig. 1 and proceeds as follows. For each storage system i ∈ {1, ..., S}, the file u ∈ F k q is encoded using a [n i , k] q code into c i = uG i ∈ F ni q . These codewords c i are stored. Some symbols get erased over time, the remaining ones are denotedĉ i ∈ Fn i q . Of these, some are chosen for transmission, so thatc i ∈ Fñ i q arrive at the requesting user. Letc [c 1 . . .c S ] andG G 1 . . .G S . As long as rankG = k, the fileû = u can be decoded.
The goal is to transmit as few symbols as possible, but enough so that the user can decode as soon as possible with very high probability. A codeword symbol is useful if and only if its corresponding column increases the rank of the matrixG. There should be no coordination, neither among the storage systems nor by the user, regarding the selection of symbols to be transmitted. Instead, using the metaphor of a 'digital fountain' [25], upon request each storage system sends a stream of symbols until the user asks it to stop. The system performance is dominated by a coupon collector's problem -how many transmissions (some of which might not add new information) are necessary to collect the required k independent pieces? In Sections III and IV we show how storage redundancy and code diversity can mitigate the loss in efficiency due to inadvertently transmitting duplicate pieces.

III. MINIMUM CODE DIVERSITY
In this section, we consider an extreme case of the system depicted in Fig. 1. All S storage systems use the same [n, k] q maximum distance separable (MDS) code, i.e., the information can be decoded from any k codeword symbols (and equivalently, any k columns of the code's G are linearly independent). The storage systems take turns transmitting a randomly selected codeword symbol to the user, e.g., for S = 2, the 1 st , 3 rd , ..., and 2 nd , 4 th , ..., symbols arrive from the first and second system, respectively. While each storage system ensures uniqueness among the symbols it sends, the user might receive the same symbol (and thus redundant information) multiple times, from different systems.
In the following, we analyze the underlying coupon collector's problem, both for large systems (block length n → ∞) as well as for systems with finite n. We model the number of symbols that were not seen among the first received symbols as the random variables U ('unknown'). The {U } and transitions where model coupon collecting and denote the probability of receiving a new or duplicate symbol in the -th transmission, respectively, if at that time i symbols are unknown to the receiver. In the -th round, the active storage system chooses uniformly at random one of the n − S pieces it has not transmitted in previous rounds. Out of these pieces, i pieces have not been seen previously by the receiver, hence the probability r i, for receiving novel information. Using this model, the probability mass functions (PMFs) P U (u ) can be obtained for all for any fixed n and S. Lemma 1. The following recursion holds: Proof.
For ease of exposition, we introduce random variables for the number of received unique symbols, K n − U , and rescaled variants with normalized time and amount of data, The following theorem provides an analytic expression for the system behavior in the large block length regime (n → ∞): Theorem 1. For n → ∞, the fraction of unseen symbols at any given point in time τ concentrates to its mean and follows Proof. First, we show the limit of the expectation.
Here, (a) uses S ≈ S for large , (b) uses log(1 − x) ≈ −x for x ≈ 0, and (c) uses the convergence of the left Riemann sum to the Riemann integral, for α τ , f (x) Hence, Here, (a) uses Lemma 1 and uses (18), (c) results from repeated application of inequality (20), (d) uses (17) and (18), and (e) uses (18). As a result, using Chebyshev's inequality, for any fixed ε > 0, Ergo, as n → ∞, the fraction of unique received symbols is fully characterized by 1 − u S (τ ) = 1 − 1 − τ S S . Fig. 3 visualizes the PMFs P K (k ) of the number of received unique symbols K after transmitting symbols, for the example of S = 2 and n = 50. The approximation based on Theorem 1, To analyze the system for finite block lengths, we turn to the random variable L denoting the number of transmissions required to complete the download (i.e., to receive k unique symbols). Exactly transmissions are required if the user receives k − 1 unique symbols in the first − 1 transmissions and a new symbol in the -th transmission, thus, The average number of transmissions required to complete the download is then obtained as the expected valueL E[L]. We normalize this toτ L n . In a similar fashion for n → ∞, τ is the fraction of time (i.e., number of transmissions) it takes to complete the download, which can be obtained from Assume the storage systems use an MDS code of rate R = k n . We call σ 1 R = n k the storage factor quantifying the storage overhead of the systems due to coding. Similarly, we call δ τ R the transmission factor, which quantifies the overhead in transmissions required for uncoordinated vs. coordinated (i.e., where duplicate symbols are avoided) download. Fig. 4 shows the tradeoff between σ and δ for large n and different number of storage systems S all employing the same MDS code. Clearly, uncoordinated file delivery incurs a loss in transmission efficiency. The loss gets worse the more independent servers participate in the delivery. However, even for an arbitrarily large number of sources, the loss remains bounded as long as σ 1. The storage redundancy can be used to mitigate the transmission overhead. Fig. 5 shows the behavior for some small block lengths n and two servers S = 2. In particular for σ close to 1, the system completes downloads slightly faster than for n → ∞. Note, however, that even for moderate code lengths n ≈ 64 the asymptotic expression is a good proxy for the system behavior.

IV. MAXIMUM CODE DIVERSITY
After examining the extreme case of minimum code diversity in the previous section, we turn to the opposite extreme, maximum code diversity, in this section. The possibilities of combining codes of different families have previously been investigated, for instance in [26]. We explore the interoperability of three systems employing an RLN-C, RS-C and LDPC-C, respectively, in an experimental case study of the framework depicted in Fig. 1. We assume the RLN-C and RS-C are of parameters [160, 128] 256 and constructed in the usual way [27]- [29]. As LDPC-C we use the AR4JA code [30], [31] of equivalent parameters [1280, 1024] 2 .
Linear codes can be defined as the nullspace of their paritycheck matrices H. To combine the codes, we transform the defining systems of linear equations to the common base field F 2 as in [26], [32]. Let {X} y denote the 'y-th' entry of X. in F m p . Let v : F p m → F m p be the isomorphism between F p m and F m p , and v −1 : F m p → F p m its inverse. Clearly, is linear, and thus equivalently represented by a matrix m (α) ∈ F m×m p associated with α, We thus get the equivalent system of equations in F p , ∀i ∈ {1, ..., n−k} : The construction applies analogously to the codes' generator matrices G. While technically all three codes have parameters [1280, 1024] 2 after this 'lifting operation' from F 256 to F 2 , we do not pick columns from the lifted generator matrices independently. Rather, we adopt block-aligned erasures, where blocks of eight columns are either jointly erased or jointly present, mimicking the erasure of F 256 rather than F 2 symbols. For the RLN-C and RS-C, this preserves their properties (both codes behave considerably worse under random erasure of F 2 sub-symbols), while the LDPC-C's performance is unaffected. Fig. 6 shows the probability of the user being able to decode (i.e., the matrixG being full-rank) after downloading the theoretical minimum of k = 8 · 128 = 1024 base field F 2 symbols in a block-aligned fashion to mimic F 256 symbols. It can be seen that RS-C and RLN-C symbols can be mixed without performance penalty and the close-tooptimal performance of RLN-Cs over large fields is preserved. As soon as LDPC-C symbols enter the mix, downloading the theoretical minimum of symbols is likely not sufficient. However, after downloading one, two and three additional F 256 symbols, the probability of successful decoding reaches 90%, 99% and 99.9%, respectively, independent of the mixturewhich is 2.34% transmission overhead (for 131 instead of 128 symbol transmissions). This is the performance one would expect for an RLN-C over small fields. In fact, when replacing the LDPC-C with a binary RLN-C, the qualitative system behavior remains unchanged.
Note that erasure decoding using Gaussian elimination over G was performed here. Its cubic runtime complexity is acceptable in the case at hand, as the resulting systems of linear equations are of manageable size, and the cost of Gaussian elimination is amortized over the length of the packets. Belief propagation decoding [33] is not feasible as neither RLN-Cs nor RS-Cs have the required sparse structure.
As a result of our empirical case study, we conclude that for system design purposes in uncoordinated content delivery, binary LDPC-Cs can be treated as binary RLN-Cs. The system incurs a small degradation in transmission efficiency due to the small field size, but the overall performance stays close to the theoretical optimum. Decoding is possible with high probability after downloading only k + ∆k symbols, with a small ∆k (in the order of three) number of excess symbols.
In contrast to the degradation observed in Section III from using the same code across multiple storage systems, code diversity enables close-to-optimal uncoordinated content delivery. Note, that lifting to the base field and random recoding transforms any code into an RLN-C over F 2 , providing an effective means to increase code diversity in existing systems.

V. CONCLUSION
In this paper we analyzed the performance of uncoordinated file delivery from multiple coded storage systems. System implementers and network operators should draw the following conclusions and actionable recommendations from our results. In Section III, we showed how uncoordinated content delivery from multiple storage systems using an identical code incurs a loss in transmission efficiency (in comparison to coordinated content delivery) due to a coupon collector effect. In Section IV, we showed that this degradation can be resolved (almost perfectly) by using different linearly independent codes in all the storage systems.
To leverage the benefits of coding for efficient uncoordinated content delivery from multiple sources, implementers should make the raw storage-coded data and details about the employed coding techniques available to the transport layer, rather than treating storage-coding as a hidden internal of the storage system. Implementers and operators should employ code families that allow the design of larger numbers of linearly independent codes. RLN-Cs and RS-Cs over larger field sizes are natural candidates. Network operators should assign codes to storage systems carefully to maintain proper code diversity (analogous to frequency reuse in mobile network base stations). When the same code is used multiple times, random remixing/recoding of the stored symbols before transmission can be used to emulate (close-to-optimal) RLN-C performance. Finally, the procedure outlined in this paper lets system operators change the employed codes without requiring downtime or instantaneous recoding of the whole database.