Large scale distributed learning aims at minimizing a loss function$L$that depends on a training dataset with respect to a$d$-length parameter vector. The distributed cluster typically consists of a parameter server (PS) and multiple workers. Gradient coding is a technique that makes the learning process resilient to straggling workers. It introduces redundancy within the assignment of data points to the workers and uses coding theoretic ideas so that the PS can recover$\nabla L$exactly or approximately, even in the presence of stragglers. Communication-efficient gradient coding allows the workers to communicate vectors of length smaller than$d$to the PS, thus reducing the communication time. While there have been schemes that address the exact recovery of$\nabla L$within communication-efficient gradient coding, to our best knowledge the approximate variant has not been considered in a systematic manner. In this work, we present constructions of communication-efficient approximate gradient coding schemes. Our schemes use structured matrices that arise from bipartite graphs, combinatorial designs and strongly regular graphs, along with randomization, and algebraic constraints. Moreover, we derive a corresponding lower bound on the approximation error of any scheme. Numerical experiments demonstrate that our schemes have low approximation error. Furthermore, in several cases, we are able to provide analytical upper bounds on the approximation error of our schemes.

In distributed large scale ML training, the problem is typically one of minimizing the empirical risk, a loss function$L$that depends on the training dataset with respect to a$d$-length parameter vector. Workers are assigned portions of the original dataset and at each iteration of the algorithm, they compute gradients on the data points assigned to them. These (partial) gradients are sent to a parameter server (PS) which aggregates them to compute either an exact or approximate version of ∇$L$(gradient of$L$) the PS generates a new parameter vector and the iterations continue thereafter. Gradient coding is a technique that helps mitigate the effect of slow or failed workers within distributed training. The basic idea is to introduce redundancy within the assignment of data points to the workers and use coding-theoretic ideas to allow the PS to recover an exact or approximate gradient even in the presence of failures. In this work, we present approximate gradient coding schemes by applying convex optimization methods to structured matrices such as circulants and transition matrices. For low complexity$(O(n))$decoding by the PS, our techniques perform significantly better. Furthermore, our schemes are applicable for any given number of workers and computation load.

Within distributed learning, workers typically compute gradients on their assigned dataset chunks and send them to the parameter server (PS), which aggregates them to compute either an exact or approximate version of $\nabla L$ (gradient of the loss function $L$). However, in large-scale clusters, many workers are slower than their promised speed or even failure-prone. A gradient coding solution introduces redundancy within the assignment of chunks to the workers and uses coding theoretic ideas to allow the PS to recover $\nabla L$ (exactly or approximately), even in the presence of stragglers. Unfortunately, most existing gradient coding protocols are inefficient from a computation perspective as they coarsely classify workers as operational or failed; the potentially valuable work performed by slow workers (partial stragglers) is ignored. In this work, we present novel gradient coding protocols that judiciously leverage the work performed by partial stragglers. Our protocols are efficient from a computation and communication perspective and numerically stable. For an important class of chunk assignments, we present efficient algorithms for optimizing the relative ordering of chunks within the workers; this ordering affects the overall execution time. For exact gradient reconstruction, our protocol is around $2\times$ faster than the original class of protocols and for approximate gradient reconstruction, the mean-squared-error of our reconstructed gradient is several orders of magnitude better.

Matrix computations are a fundamental building block of the edge computing systems, with a major recent uptick in demand due to their use in AI/ML training and inference procedures. Existing approaches for distributing the matrix computations involve allocating coded combinations of submatrices to worker nodes, to build resilience to slower nodes, called stragglers. In the edge learning context, however, these approaches will compromise sparsity properties that are often present in the original matrices found at the edge server. In this study, we consider the challenge of augmenting, such approaches to preserve input sparsity when distributing the task across the edge devices, thereby retaining the associated computational efficiency enhancements. First, we find a lower bound on the weight of coding, i.e., the number of submatrices to be combined to obtain coded submatrices to provide the resilience to the maximum possible number of straggler devices (for given number of devices and their storage constraints). Next, we propose distributed matrix computation schemes which meet the exact lower bound on the weight of the coding. Numerical experiments conducted in amazon Web services (AWSs) validate our assertions regarding straggler mitigation and computation speed for the sparse matrices.

A plethora of modern machine learning tasks require the utilization of large-scale distributed clusters as a critical component of the training pipeline. However, abnormal Byzantine behavior of the worker nodes can derail the training and compromise the quality of the inference. Such behavior can be attributed to unintentional system malfunctions or orchestrated attacks; as a result, some nodes may return arbitrary results to the parameter server (PS) that coordinates the training. Recent work considers a wide range of attack models and has explored robust aggregation and/or computational redundancy to correct the distorted gradients. In this work, we consider attack models ranging from strong ones:$q$omniscient adversaries with full knowledge of the defense protocol that can change from iteration to iteration to weak ones:$q$randomly chosen adversaries with limited collusion abilities which only change every few iterations at a time. Our algorithms rely on redundant task assignments coupled with detection of adversarial behavior. We also show the convergence of our method to the optimal point under common assumptions and settings considered in literature. For strong attacks, we demonstrate a reduction in the fraction of distorted gradients ranging from 16%–99% as compared to the prior state-of-the-art. Our top-1 classification accuracy results on the CIFAR-10 data set demonstrate 25% advantage in accuracy (averaged over strong and weak scenarios) under the most sophisticated attacks compared to state-of-the-art methods.

Federated learning (FL) is a popular technique for training a global model on data distributed across client devices. Like other distributed training techniques, FL is susceptible to straggler (slower or failed) clients. Recent work has proposed to address this through device-to-device (D2D) offloading, which introduces privacy concerns. In this paper, we propose a novel straggler-optimal approach for coded matrix computations which can significantly reduce the communication delay and privacy issues introduced from D2D data transmissions in FL. Moreover, our proposed approach leads to a considerable improvement of the local computation speed when the generated data matrix is sparse. Numerical evaluations confirm the superiority of our proposed method over baseline approaches.

Straggler nodes are well-known bottlenecks of distributed matrix computations which induce reductions in computation/communication speeds. A common strategy for mitigating such stragglers is to incorporate MDS (maximum distance separable) codes into the framework; this can achieve resilience against an optimal number of stragglers. However, these codes assign dense linear combinations of submatrices to the workers which increase the number of non-zero entries in the encoded matrices, and adversely affect the worker computation time. In this work, we develop a straggler-optimal distributed matrix computation approach where the assigned encoded submatrices are linear combinations of a small number of submatrices so that it is well suited for sparse input matrices. Numerical experiments conducted in Amazon Web Services (AWS) demonstrate up to 30% reduction in worker computation time and 100 times faster encoding compared to several recent methods.

Polynomial based approaches, such as the Mat-Dot and entangled polynomial codes (EPC) have been used extensively within coded matrix computations to obtain schemes with good recovery thresholds. However, these schemes are well-recognized to suffer from poor numerical stability in decoding. Moreover, the encoding process in these schemes involves linearly combining a large number of input submatrices, i.e., the encoding weight is high. For the practically relevant case of sparse input matrices, this can have the undesirable effect of significantly increasing the worker node computation time. In this work, we propose a generalization of the EPC scheme by combining the idea of gradient coding along with the basic EPC encoding. Our technique allows us to reduce the weight of the encoding and arrive at schemes that exhibit much better numerical stability; this is achieved at the expense of a worse threshold. By appropriately setting parameters in our scheme, we recover several well-known schemes in the literature. Simulation results show that our scheme provides excellent numerical stability and fast computation speed (for sparse input matrices) as compared to EPC and Mat-Dot codes.

Robust Subspace Tracking with missing data (RST-miss) has been extensively studied in the past decade. In this work we study RST-miss to the setting where the data is federated and when the over-air data communication modality is used for information exchange between the K peer nodes and the central server. To the best of our knowledge, there is no existing work in the literature. To this end, we develop the first fast, and provable algorithm that solves RST-miss in a federated over-air setting. We corroborate our theoretical claims with extensive numerical simulations.

The speed of distributed matrix computations over large clusters is often dominated by the stragglers (slow or failed worker nodes). Several techniques based on coding theory have been introduced to mitigate the straggler issue where every worker node is assigned smaller task(s) of multiplying encoded submatrices of the original matrices. However, many of these methods consider the stragglers as erasures, i.e., they discard the potentially useful partial computations done by the slower workers. Moreover, the "input" matrices can be sparse in many scenarios. In this case encoding schemes that combine a large number of input submatrices can adversely affect the worker computation time.In this work, we proposed an integrated approach which addresses both of the issues mentioned above. We allow limited amount of encoding for the submatrices of both A and B; this helps us to preserve the sparsity of the encoded matrices, so that the worker computation can be fast. Our approach provides a trade-off between straggler resilience and worker computation speed, while utilizing partial computations at the workers. Crucially, at one operating point we can ensure that the failure resilience of the system is optimal. Comprehensive numerical analysis done in Amazon Web Services (AWS) cluster confirms the superiority of our approach when compared with previous methods.

State-of-the-art machine learning models are routinely trained on large-scale distributed clusters. Crucially, such systems can be compromised when some of the computing devices exhibit abnormal (Byzantine) behavior and return arbitrary results to the parameter server (PS). This behavior may be attributed to a plethora of reasons, including system failures and orchestrated attacks. Existing work suggests robust aggregation and/or computational redundancy to alleviate the effect of distorted gradients. However, most of these schemes are ineffective when an adversary knows the task assignment and can choose the attacked workers judiciously to induce maximal damage. Our proposed method Aspis assigns gradient computations to workers using a subset-based assignment which allows for multiple consistency checks on the behavior of a worker. Examination of the calculated gradients and clique-finding in an appropriately constructed graph by the PS allows for efficient detection and exclusion of adversaries from the training. We prove the Byzantine resilience guarantees of Aspis under weak and strong attacks and extensively evaluate the system on various training scenarios and demonstrate an improvement of about 30% in accuracy compared to many state-of-the-art approaches on the CIFAR-10 dataset as well as reduction of the fraction of corrupted gradients ranging from 16% to 99%.

Distributed matrix computations over large clusters can suffer from the problem of slow or failed worker nodes (called stragglers) which can dominate the overall job execution time. Coded computation utilizes concepts from erasure coding to mitigate the effect of stragglers by running “coded” copies of tasks comprising a job; stragglers are typically treated as erasures. While this is useful, there are issues with applying, e.g., MDS codes in a straightforward manner. Several practical matrix computation scenarios involve sparse matrices. MDS codes typically require dense linear combinations of submatrices of the original matrices which destroy their inherent sparsity. This is problematic as it results in significantly higher worker computation times. Moreover, treating slow nodes as erasures ignores the potentially useful partial computations performed by them. Furthermore, some MDS techniques also suffer from significant numerical stability issues. In this work we present schemes that allow us to leverage partial computation by stragglers while imposing constraints on the level of coding that is required in generating the encoded submatrices. This significantly reduces the worker computation time as compared to previous approaches and results in improved numerical stability in the decoding process. Exhaustive numerical experiments on Amazon Web Services (AWS) clusters support our findings.

Polynomial based methods have recently been used in several works for mitigating the effect of stragglers (slow or failed nodes) in distributed matrix computations. For a system with$n$worker nodes where$s$can be stragglers, these approaches allow for an optimal recovery threshold, whereby the intended result can be decoded as long as any$(n-s)$worker nodes complete their tasks. However, they suffer from serious numerical issues owing to the condition number of the corresponding real Vandermonde-structured recovery matrices; this condition number grows exponentially in$n$. We present a novel approach that leverages the properties of circulant permutation matrices and rotation matrices for coded matrix computation. In addition to having an optimal recovery threshold, we demonstrate an upper bound on the worst-case condition number of our recovery matrices which grows as$\approx O(n^{s+5.5})$; in the practical scenario where$s$is a constant, this grows polynomially in$n$. Our schemes leverage the well-behaved conditioning of complex Vandermonde matrices with parameters on the complex unit circle, while still working with computation over the reals. Exhaustive experimental results demonstrate that our proposed method has condition numbers that are orders of magnitude lower than prior work.

Coded matrix computation utilizes concepts from erasure coding to mitigate the effect of slow worker nodes (stragglers) in the distributed setting. While this is useful, there are issues with applying, e.g., MDS codes in a straightforward manner for this problem. Several practical scenarios involve sparse matrices. MDS codes typically require dense linear combinations of submatrices of the original matrices which destroy their inherent sparsity; this leads to significantly higher worker computation times. Moreover, treating slow nodes as erasures ignores the potentially useful partial computations performed by them. In this work we present schemes that allow us to leverage partial computation by stragglers while imposing constraints on the level of coding that is required in generating the encoded submatrices. This significantly reduces the worker computation time as compared to previous approaches and results in improved numerical stability in the decoding process. Exhaustive numerical experiments support our findings.

Distributed matrix computations are well-recognized to suffer from the problem of stragglers (slow or failed worker nodes). The majority of prior work in this area has presented straggler mitigation strategies that are (i) either sub-optimal in terms of their straggler resilience, or (ii) suffer from numerical problems, i.e., there is a blow-up of round-off errors in the decoded result owing to the high condition numbers of the corresponding decoding matrices. This work introduces a novel solution framework, based on embedding the computations into the structure of a convolutional code, that removes these limitations. Our approach is provably optimal in terms of its straggler resilience, and has excellent numerical robustness which can be theoretically quantified by deriving a computable upper bound on the worst case condition number over all possible decoding matrices. All above claims are backed up by extensive experiments done on the AWS cloud platform.

Polynomial based methods have recently been used in several works for mitigating the effect of stragglers in distributed matrix computations. However, they suffer from serious numerical issues owing to the condition number of the corresponding real Vandermonde-structured recovery matrices. For a system with$n$worker nodes where$s$can be stragglers the condition number grows exponentially in n. We present a novel coded computation approach that leverages the properties of circulant permutation and rotation matrices. Our scheme has an optimal recovery threshold and an upper bound on the worst case condition number of our recovery matrices which grows as ≈$O$(ns+6); in the practical scenario where$s$is a constant, this grows polynomially in n. Our schemes leverage the well-behaved conditioning of complex Vandermonde matrices with parameters on the complex unit circle, while still working with computation over the reals. Exhaustive experimental results demonstrate that our proposed method has condition numbers that are orders of magnitude lower than prior work.

The overall execution time of distributed matrix computations is often dominated by slow worker nodes (stragglers) over the clusters. Recently, different coding techniques have been utilized to mitigate the effect of stragglers where worker nodes are assigned the task of processing encoded submatrices of the original matrices. In many machine learning or optimization problems the relevant matrices are often sparse. Several coded computation methods operate with dense linear combinations of the original submatrices; this can significantly increase the worker node computation times and consequently the overall job execution time. Moreover, several existing techniques treat the stragglers as failures (erasures) and discard their computations. In this work, we present a coding approach which operates with limited encoding of the original submatrices and utilizes the partial computations done by the slower workers. Our scheme continues to have the optimal threshold of prior work. Extensive numerical experiments done in AWS (Amazon Web Services) cluster confirm that the proposed approach enhances the speed of the worker computations (and thus the whole process) significantly.

Leveraging the idea of group theory, we explore the distributed matrix multiplication problem posed in on-device edge computing. We first revisit how to embed matrix multiplication into group structure and then propose a distributed matrix multiplication scheme using the cyclic group. We identify the condition for the perfect reconstruction with the proposed scheme, and exhibit that the proposed scheme has better error performance than uncoded scheme in a noisy channel owing to the diversity gain of the proposed scheme.

Coded caching is a technique that promises huge reductions in network traffic in content-delivery networks. However, the original formulation and several subsequent contributions in the area, assume that the file requests from the users are synchronized, i.e., they arrive at the server at the same time. In this work, we formulate and study the coded caching problem when the file requests from the users arrive at different times. We assume that each user also has a prescribed deadline by which they want their request to be completed. In the offline case, we assume that the server knows the arrival times before starting transmission and in the online case, the user requests are revealed to the server over time. We present a linear programming formulation for the offline case that minimizes the overall transmission rate from the server subject to the constraint that each user meets his/her deadline. While the online case is much harder, we introduce a novel heuristic for it and show that under certain conditions, with high probability the request of each user can be satisfied with her/his deadline. Our simulation results indicate that in the presence of mild asynchronism, much of the benefit of coded caching can still be leveraged.

Distributed computing frameworks such as MapReduce are often used to process large computational jobs. They operate by partitioning each job into smaller tasks executed on different servers. The servers also need to exchange intermediate values to complete the computation. Experimental evidence suggests that this so-called Shuffle phase can be a significant part of the overall execution time for several classes of jobs. Prior work has demonstrated a natural tradeoff between computation and communication whereby running redundant copies of jobs can reduce the Shuffle traffic load, thereby leading to reduced overall execution times. For a single job, the main drawback of this approach is that it requires the original job to be split into a number of files that grows exponentially in the system parameters. When extended to multiple jobs (with specific function types), these techniques suffer from a limitation of a similar flavor, i.e., they require an exponentially large number of jobs to be executed. In practical scenarios, these requirements can significantly reduce the promised gains of the method. In this work, we show that a class of combinatorial structures called resolvable designs can be used to develop efficient coded distributed computing schemes for both the single and multiple job scenarios considered in prior work. We present both theoretical analysis and exhaustive experimental results (on Amazon EC2 clusters) that demonstrate the performance advantages of our method. For the single and multiple job cases, we obtain speed-ups of 4.69x (and 2.6x over prior work) and 4.31x over the baseline approach, respectively.

Distributed computing systems are well-known to suffer from the problem of slow or failed nodes; these are referred to as stragglers. Straggler mitigation (for distributed matrix computations) has recently been investigated from the standpoint of erasure coding in several works. In this work we present a strategy for distributed matrix-vector multiplication based on convolutional coding. Our scheme can be decoded using a lowcomplexity peeling decoder. The recovery process enjoys excellent numerical stability as compared to Reed-Solomon coding based approaches (which exhibit significant problems owing their badly conditioned decoding matrices). Finally, our schemes are better matched to the practically important case of sparse matrix-vector multiplication as compared to many previous schemes. Extensive simulation results corroborate our findings.

Many big data algorithms executed on MapReduce-like systems have a shuffle phase that often dominates the overall job execution time. Recent work has demonstrated schemes where the communication load in the shuffle phase can be traded off for the computation load in the map phase. In this work, we focus on a class of distributed algorithms, broadly used in deep learning, where intermediate computations of the same task can be combined. Even though prior techniques reduce the communication load significantly, they require a number of jobs that grows exponentially in the system parameters. This limitation is crucial and may diminish the load gains as the algorithm scales. We propose a new scheme which achieves the same load as the state-of-the-art while ensuring that the number of jobs as well as the number of subfiles that the data set needs to be split into remain small.

Coded computation is an emerging research area that leverages concepts from erasure coding to mitigate the effect of stragglers (slow nodes) in distributed computation clusters, especially for matrix computation problems. In this work, we present a class of distributed matrix-vector multiplication schemes that are based on codes in the Rosenbloom-Tsfasman metric and universally decodable matrices. Our schemes take into account the inherent computation order within a worker node. In particular, they allow us to effectively leverage partial computations performed by stragglers (a feature that many prior works lack). An additional main contribution of our work is a companion-matrix-based embedding of these codes that allows us to obtain sparse and numerically stable schemes for the problem at hand. Experimental results confirm the effectiveness of our techniques.

Large scale clusters running MapReduce, Spark etc. routinely process data that are on the orders of petabytes or more. The philosophy in these methods is to split the overall job into smaller tasks that are executed on different servers; this is called the map phase. This is followed by a data shuffling phase where appropriate data is exchanged between the servers. The final reduce phase, completes the computation. Prior work has explored a mechanism for reducing the overall execution time by operating on a computation vs. communication tradeoff. Specifically, the idea is to run redundant copies of map tasks that are placed on judiciously chosen servers. The shuffle phase exploits the location of the nodes and utilizes coded transmission. The main drawback of this approach is that it requires the original job to be split into a number of map tasks that grows exponentially in the system parameters. This is problematic, as we demonstrate that splitting jobs too finely can in fact adversely affect the overall execution time. In this work we show that one can simultaneously obtain low communication loads while ensuring that jobs do not need to be split too finely. Our approach uncovers a deep relationship between this problem and a class of combinatorial structures called resolvable designs. We present experimental results obtained on Amazon EC2 clusters for a widely known distributed algorithm, namely TeraSort. We obtain over 4.69× improvement in speedup over the baseline approach and more than 2.6× over current state of the art.

In distributed computing systems, it is well recognized that worker nodes that are slow (called stragglers) tend to dominate the overall job execution time. Coded computation utilizes concepts from erasure coding to mitigate the effect of stragglers by running “coded” copies of tasks comprising a job. Stragglers are typically treated as erasures in this process. While this is useful, there are issues with applying, e.g., MDS codes in a straightforward manner. Specifically, several applications such as matrix-vector products deal with sparse matrices. MDS codes typically require dense linear combinations of submatrices of the original matrix which destroy their inherent sparsity. This is problematic as it results in significantly higher processing times for computing the submatrix-vector products in coded computation. Furthermore, it also ignores partial computations at stragglers. In this work, we propose a fine-grained model that quantifies the level of non-trivial coding needed to obtain the benefits of coding in matrix-vector computation. Simultaneously, it allows us to leverage partial computations performed by the straggler nodes. For this model, we propose and evaluate several code designs and discuss their properties.

We study the rate region of variable-length source-network codes that are used to compute a function of messages observed over a network. The particular network considered here is the simplest instance of a directed acyclic graph (DAG) that is not a tree. Existing work on zero-error function computation in DAG networks provides bounds on the computation capacity, which is a measure of the amount of communication required per edge in the worst case. This work focuses on the average case: an achievable rate tuple describes the expected amount of communication required on each edge, where the expectation is over the probability mass function of the source messages. We describe a systematic procedure to obtain outer bounds to the rate region for computing an arbitrary demand function at the terminal. Our bounding technique works by lower bounding the entropy of the descriptions observed by the terminal conditioned on the function value and by utilizing the Schur-concave property of the entropy function.

Coded caching is a technique that generalizes conventional caching and promises significant reductions in traffic over caching networks. However, the basic coded caching scheme requires that each file hosted in the server be partitioned into a large number (i.e., the subpacketization level) of non-overlapping subfiles. From a practical perspective, this is problematic as it means that prior schemes are only applicable when the size of the files is extremely large. In this paper, we propose coded caching schemes based on combinatorial structures called resolvable designs. These structures can be obtained in a natural manner from linear block codes whose generator matrices possess certain rank properties. We obtain several schemes with subpacketization levels substantially lower than the basic scheme at the cost of an increased rate. Depending on the system parameters, our approach allows us to operate at various points on the subpacketization level vs. rate tradeoff.

A sum-network is an instance of a function computation problem over a directed acyclic network, in which each terminal node wants to compute the sum over a finite field of the information observed at all the source nodes. Many characteristics of the well-studied multiple unicast network communication problem also hold for sum-networks, due to a known reduction between the two problems. In this paper, we describe an algorithm to construct families of sum-network instances using incidence structures. The computation capacity of several of these sum-network families is evaluated. Unlike the coding capacity of a multiple unicast problem, the computation capacity of sum-networks depends on the characteristic of the finite field over which the sum is computed. This dependence is very strong; we show examples of sum-networks that have a rate-1 solution over one characteristic but a rate close to zero over a different characteristic. In addition, a sum-network can have arbitrarily different computation capacities for different alphabets.

Coded caching is a technique that promises huge reductions in network traffic in content-delivery networks. However, the original formulation and several subsequent contributions in the area, assume that the file requests from the users are synchronized, i.e., they arrive at the server at the same time. In this work we formulate and study the coded caching problem when the file requests from the users arrive at different times. We assume that each user also has a prescribed deadline by which they want their request to be completed. In the offline case, we assume that the server knows the arrival times before starting transmission and in the online case, the user requests are revealed to the server over time. We present a LP formulation for the offline case that minimizes the overall rate subject to constraint that each user meets his/her deadline. While the online case is much harder, we demonstrate that in the case when the server wishes to minimize the overall completion time, the online solution can be as good as the offline solution. Our simulation results indicate that in the presence of mild asynchronism, much of the benefit of coded caching can still be leveraged.

Coded caching is a technique that generalizes conventional caching and promises significant reductions in traffic over caching networks. However, the basic coded caching scheme requires that each file hosted in the server be partitioned into a large number (called the subpacketization level) of non-overlapping subfiles. From a practical perspective, this is problematic as it means that prior schemes are only applicable when the size of the files is extremely large. In this work, we propose coded caching schemes based on combinatorial structures called resolvable designs. These structures can be obtained in a natural manner from linear block codes whose generator matrices possess certain rank properties. We demonstrate that several schemes with subpacketization levels that are exponentially smaller than the basic scheme can be obtained.

Caching is often used in content delivery networks as a mechanism for reducing network traffic. Recently, the technique of coded caching was introduced whereby coding in the caches and coded transmission signals from the central server were considered. Prior results in this area demonstrate that carefully designing the placement of content in the caches and designing appropriate coded delivery signals from the server allow for a system where the delivery rates can be significantly smaller than conventional schemes. However, matching upper and lower bounds on the transmission rate have not yet been obtained. In this paper, we derive tighter lower bounds on the coded caching rate than were known previously. We demonstrate that this problem can equivalently be posed as a combinatorial problem of optimally labeling the leaves of a directed tree. Our proposed labeling algorithm allows for significantly improved lower bounds on the coded caching rate. Furthermore, we study certain structural properties of our algorithm that allow us to analytically quantify improvements on the rate lower bound for general values of the problem parameters. This allows us to obtain a multiplicative gap of at most four between the achievable rate and our lower bound.

We study cloud-storage systems with a very large number of files stored in a very large number of servers. In such systems, files are either replicated or coded to ensure reliability, i.e., file recovery from server failures. This redundancy in storage can further be exploited to improve system performance (mean file access delay) through appropriate load-balancing (routing) schemes. However, it is unclear whether coding or replication is better from a system performance perspective since the corresponding queueing analysis of such systems is, in general, quite difficult except for the trivial case when the system load asymptotically tends to zero. Here, we study the more difficult case where the system load is not asymptotically zero. Using the fact that the system size is large, we obtain a mean-field limit for the steady-state distribution of the number of file access requests waiting at each server. We then use the mean-field limit to show that, for a given storage capacity per file, coding strictly outperforms replication at all traffic loads while improving reliability. Further, the factor by which the performance improves in the heavy-traffic is at least as large as in the light-traffic case. Finally, we validate these results through extensive simulations.

Coded caching is a technique that promises huge rate savings in certain canonical content distribution scenarios over the Internet. In the coded caching setting, previous contributions have demonstrated a constant multiplicative gap between the achievable rate and corresponding lower bound on the rate, independent of the problem parameters. Our prior work demonstrated that good lower bounds on the coded caching rate can be obtained by equivalently considering a combinatorial problem on a directed tree. In this work, we study certain structural properties of our algorithm that allow us to analytically quantify improvements on the rate lower bound. This analysis allows us to obtain a multiplicative gap of at most four between the achievable rate and our lower bound. To our best knowledge, this is the best known multiplicative gap known for this problem.

Coded caching is a recently proposed technique for dealing with large scale content distribution over the Internet. As in conventional caching, it leverages the presence of local caches at the end users. However, it considers coding in the caches and/or coded transmission from the central server and demonstrates that huge savings in transmission rate are possible when the server and the end users are connected via a single shared link. In this work, we consider a more general topology where there is a layer of relay nodes between the server and the users, e.g., combination networks studied in network coding are an instance of these networks. We propose novel schemes for a class of such networks that satisfy a so-called resolvability property and demonstrate that the performance of our scheme is strictly better than previously proposed schemes.

For zero-error function computation over directed acyclic networks, existing upper and lower bounds on the computation capacity are known to be loose. In this work we consider the problem of computing the arithmetic sum over a specific directed acyclic network that is not a tree. We assume the sources to be i.i.d. Bernoulli with parameter 1/2. Even in this simple setting, we demonstrate that upper bounding the computation rate is quite nontrivial. In particular, it requires us to consider variable length network codes and relate the upper bound to equivalently lower bounding the entropy of descriptions observed by the terminal conditioned on the function value. This lower bound is obtained by further lower bounding the entropy of a so-called clumpy distribution. We also demonstrate an achievable scheme that uses variable length network codes and in-network compression.

Fractional repetition (FR) codes are a class of regenerating codes for distributed storage systems with an exact (table-based) repair process that is also uncoded, i.e., upon failure, a node is regenerated by simply downloading packets from the surviving nodes. In this paper, we present the constructions of FR codes based on Steiner systems and resolvable combinatorial designs, such as affine geometries, Hadamard designs, and mutually orthogonal Latin squares. The failure resilience of our codes can be varied in a simple manner. We construct codes with normalized repair bandwidth (β) strictly larger than one; these cannot be obtained trivially from codes with β = 1. Furthermore, we present the Kronecker product technique for generating new codes from existing ones and elaborate on their properties. FR codes with locality are those where the repair degree is smaller than the number of nodes contacted for reconstructing the stored file. For these codes, we establish a tradeoff between the local repair property and the failure resilience and construct codes that meet this tradeoff. Much of prior work only provided lower bounds on the FR code rate. In this paper, for most of our constructions, we determine the code rate for certain parameter ranges.

Content delivery networks often employ caching to reduce transmission rates from the central server to the end users. Recently, the technique of coded caching was introduced whereby coding in the caches and coded transmission signals from the central server are considered. Prior results in this area demonstrate that (a) carefully designing placement of content in the caches and (b) designing appropriate coded delivery signals allow for a system where the delivery rates can be significantly smaller than conventional schemes. However, matching lower bounds on the transmission rates have not yet been obtained. In this work, we derive tighter lower bounds on coded caching rates than were known previously. We demonstrate that this problem can equivalently be posed as one of optimally labeling the leaves of a directed tree. Several examples that demonstrate the utility of our bounds are presented.

A sum-network is a directed acyclic network in which all terminal nodes demand the `sum' of the independent information observed at the source nodes. Many characteristics of the well-studied multiple-unicast network communication problem also hold for sum-networks due to a known reduction between instances of these two problems. Our main result is that unlike a multiple unicast network, the coding capacity of a sum-network is dependent on the message alphabet. We demonstrate this using a construction procedure and show that the choice of a message alphabet can reduce the coding capacity of a sum-network from 1 to close to 0.

We consider the multiple-unicast problem with three source-terminal pairs over directed acyclic networks with unit-capacity edges. The three si-tipairs wish to communicate at unit-rate via network coding. The connectivity between the si-tipairs is quantified by means of a connectivity-level vector, [k1k2k3] such that there exist kiedge-disjoint paths between si and ti. In this paper, we attempt to classify networks based on the connectivity level. It can be observed that unit-rate transmission can be supported by routing if ki≥ 3, for all i = 1, ..., 3. In this paper, we consider connectivity-level vectors such that mini=1,...,3ki<; 3. We present either a constructive linear network coding scheme or an instance of a network that cannot support the desired unit-rate requirement, for all such connectivity-level vectors except the vector [1 2 4] (and its permutations). The benefits of our schemes extend to networks with higher and potentially different edge capacities. Specifically, our experimental results indicate that for networks where the different source-terminal paths have a significant overlap, our constructive unit-rate schemes can be packed along with routing to provide higher throughput as compared to a pure routing approach.

In this work we present a flexible, probabilistic and reference-free method of error correction for high throughput DNA sequencing data. The key is to exploit the high coverage of sequencing data and model short sequence outputs as independent realizations of a Hidden Markov Model (HMM). We pose the problem of error correction of reads as one of maximum likelihood sequence detection over this HMM. While time and memory considerations rule out an implementation of the optimal Baum-Welch algorithm (for parameter estimation) and the optimal Viterbi algorithm (for error correction), we propose low-complexity approximate versions of both. Specifically, we propose an approximate Viterbi and a sequential decoding based algorithm for the error correction. Our results show that when compared with Reptile, a state-of-the-art error correction method, our methods consistently achieve superior performances on both simulated and real data sets.

We consider the network communication scenario, over directed acyclic networks with unit capacity edges in which a number of sources si each holding independent unit-entropy information Xiwish to communicate the sum ΣXito a set of terminals tj. We show that in the case in which there are only two sources or only two terminals, communication is possible if and only if each source terminal pair si/tjis connected by at least a single path. For the more general communication problem in which there are three sources and three terminals, we prove that a single path connecting the source terminal pairs does not suffice to communicate ΣXi. We then present an efficient encoding scheme which enables the communication of ΣXifor the three sources, three terminals case, given that each source terminal pair is connected by two edge disjoint paths.

We consider the multiple unicast problem under network coding over directed acyclic networks when there are two source-terminal pairs, s1-t1and s2-t2. The capacity region for this problem is not known; furthermore, the outer bounds on the region have a large number of inequalities which makes them hard to explicitly evaluate. In this work we consider a related problem. We assume that we only know certain minimum cut values for the network, e.g., mincut(Si, Tj), where Si⊆ {s1, s2} and Tj⊆ {t1, t2} for different subsets Siand Tj. Based on these values, we propose an achievable rate region for this problem using linear network codes. Towards this end, we begin by defining a multicast region where both sources are multicast to both the terminals. Following this we enlarge the region by appropriately encoding the information at the source nodes, such that terminal tiis only guaranteed to decode information from the intended source si, while decoding a linear function of the other source. The rate region depends upon the relationship of the different cut values in the network.

In this work we present practical coding schemes for the problem of lossless distributed source coding for multiple sources. We consider two scenarios - the classical Slepian-Wolf case where there is no feedback from the terminal to the sources and a case where there is feedback from the terminal to the source encoders. The correlation model of interest is given by a system of linear equations, a generalization of the work of Stankovic et al. '06. We propose a transformation of correlation model and a way to determine proper decoding schedules, both of which are required to obtain the optimal sum rate. Our scheme allows us to exploit more correlations than those in the previous work. Simulation results show that the proposed coding scheme has lower sum rate than previous work in both scenarios.

We consider a single-hop interference network withKtransmitters andJreceivers, all havingMantennas. Each transmitter emits an independent message and each receiver requests an arbitrary subset of the messages. This generalizes the well-knownK-userM-antenna interference channel, where each message is requested by a unique receiver. For our setup, we derive the degrees of freedom (DoF) region. The achievability scheme generalizes the interference alignment schemes proposed by Cadambe and Jafar. In particular, we achieve general points in the DoF region by using multiple base vectors and aligning all interferers at a given receiver to the interferer with the largest DoF. As a byproduct, we obtain the DoF region for the original interference channel. We also discuss extensions of our approach where the same region can be achieved by considering a reduced set of interference alignment constraints, thus reducing the time-expansion duration needed. The DoF region for the considered system depends only on a subset of receivers whose demands meet certain characteristics. The geometric shape of the DoF region is also discussed.

We consider the min-cost multicast problem (under network coding) with multiple correlated sources where each terminal wants to losslessly reconstruct all the sources. We study the inefficiency brought forth by the selfish behavior of the terminals in this scenario by modeling it as a noncooperative game among the terminals. The degradation in performance due to the lack of regulation is measured by the Price of Anarchy (POA), which is defined as the ratio between the cost of the worst possible Wardrop equilibrium and the socially optimum cost. Our main result is that in contrast with the case of independent sources, the presence of source correlations can significantly increase the price of anarchy. Toward establishing this result, we first characterize the socially optimal flow and rate allocation in terms of four intuitive conditions. Next, we show that the Wardrop equilibrium is a socially optimal solution for a different set of (related) cost functions. Using this, we construct explicit examples that demonstrate that the POA >; 1 and determine near-tight upper bounds on the POA as well. The main techniques in our analysis are Lagrangian duality theory and the usage of the supermodularity of conditional entropy.

We consider the multiple unicast problem under network coding over directed acyclic networks with unit capacity edges. There is a set of n source-terminal (si-ti) pairs that wish to communicate at unit rate over this network. The connectivity between the si-tipairs is quantified by means of a connectivity level vector, [k1k2... kn] such that there exist kiedge-disjoint paths between siand ti. Our main aim is to characterize the feasibility of achieving this for different values of n and [k1... kn]. For 3 unicast connections (n = 3), we characterize several achievable and unachievable values of the connectivity 3-tuple. In addition, in this work, we have found certain network topologies, and capacity characterizations that are useful in understanding the case of general n.

We consider a single hop interference network with K transmitters, each with an independent message and J receivers, all having the same number (M) of antennas. Each receiver requests an arbitrary subset of the messages. This generalizes the well-known K user M antenna interference channel, where each message is requested by a unique receiver. For this setup, we derive the exact degrees of freedom (DoF) region. Our achievability scheme generalizes the interference alignment scheme proposed by Cadambe and Jafar '08. In particular, we achieve general points in the DoF region by using multiple base vectors and aligning the interference at each receiver to its largest (in the DoF sense) interferer. As a byproduct of our analysis, we recover the DoF region for the original interference channel.

Practical constructions of lossless distributed source codes (for the Slepian-Wolf problem) have been the subject of much investigation in the past decade. In particular, near-capacity achieving code designs based on LDPC codes have been presented for the case of two binary sources, with a binary-symmetric correlation. However, constructing practical codes for the case of non-binary sources with arbitrary correlation remains by and large open. From a practical perspective it is also interesting to consider coding schemes whose performance remains robust to uncertainties in the joint distribution of the sources. In this work we propose the usage of Reed-Solomon (RS) codes for the asymmetric version of this problem. We show that algebraic soft-decision decoding of RS codes can be used effectively under certain correlation structures. In addition, RS codes offer natural rate adaptivity and performance that remains constant across a family of correlation structures with the same conditional entropy. The performance of RS codes is compared with dedicated and rate adaptive multistage LDPC codes (Varodayan et al. '06), where each LDPC code is used to compress the individual bit planes. Our simulations show that in classical Slepian-Wolf scenario, RS codes outperform both dedicated and rate-adaptive LDPC codes under q-ary symmetric correlation, and are better than rate-adaptive LDPC codes in the case of sparse correlation models, where the conditional distribution of the sources has only a few dominant entries. In a feedback scenario, the performance of RS codes is comparable with both designs of LDPC codes. Our simulations also demonstrate that the performance of RS codes in the presence of inaccuracies in the joint distribution of the sources is much better as compared to multistage LDPC codes.

We consider the multiple unicast problem under network coding over directed acyclic networks when there are two source-terminal pairs, s1- t1and s2- t2. Current characterizations of the multiple unicast capacity region in this setting have a large number of inequalities, which makes them hard to explicitly evaluate. In this work we consider a slightly different problem. We assume that we only know certain minimum cut values for the network, e.g., mincut(Si, Tj), where Si⊆ {si, s2} and Tj⊆ {t1, t2} for different subsets Siand Tj. Based on these values, we propose an achievable rate region for this problem based on linear codes. Towards this end, we begin by defining a base region where both sources are multicast to both the terminals. Following this we enlarge the region by appropriately encoding the information at the source nodes, such that terminal tiis only guaranteed to decode information from the intended source si, while decoding a linear function of the other source. The rate region takes different forms depending upon the relationship of the different cut values in the network.

We propose a network-coding based scheme to protect multiple bidirectional unicast connections against adversarial errors and failures in a network. The network consists of a set of bidirectional primary path connections that carry the uncoded traffic. The end nodes of the bidirectional connections are connected by a set of shared protection paths that provide the redundancy required for protection. Such protection strategies are employed in the domain of optical networks for recovery from failures. In this work we consider the problem of simultaneous protection against adversarial errors and failures. Suppose that nepaths are corrupted by the omniscient adversary. Under our proposed protocol, the errors can be corrected at all the end nodes with 4neprotection paths. More generally, if there are neadversarial errors and nffailures, 4ne+ 2nfprotection paths are sufficient. The number of protection paths only depends on the number of errors and failures being protected against and is independent of the number of unicast connections.

Content distribution over networks is often achieved by using mirror sites that hold copies of files or portions thereof to avoid congestion and delay issues arising from excessive demands to a single location. Accordingly, there are distributed storage solutions that divide the file into pieces and place copies of the pieces (replication) or coded versions of the pieces (coding) at multiple source nodes. We consider a network which uses network coding for multicasting the file. There is a set of source nodes that contains either subsets or coded versions of the pieces of the file. The cost of a given storage solution is defined as the sum of the storage cost and the cost of the flows required to support the multicast. Our interest is in finding the storage capacities and flows at minimum combined cost. We formulate the corresponding optimization problems by using the theory of information measures. In particular, we show that when there are two source nodes, there is no loss in considering subset sources. For three source nodes, we derive a tight upper bound on the cost gap between the coded and uncoded cases. We also present algorithms for determining the content of the source nodes.

This paper considers the problem of transmitting multiple compressible sources over a network at minimum cost. The aim is to find the optimal rates at which the sources should be compressed and the network flows using which they should be transmitted so that the cost of the transmission is minimal. We consider networks with capacity constraints and linear cost functions. The problem is complicated by the fact that the description of the feasible rate region of distributed source coding problems typically has a number of constraints that is exponential in the number of sources. This renders general purpose solvers inefficient. We present a framework in which these problems can be solved efficiently by exploiting the structure of the feasible rate regions coupled with dual decomposition and optimization techniques such as the subgradient method and the proximal bundle method.

This paper introduces a network coding-based protection scheme against single- and multiple-link failures. The proposed strategy ensures that in a connection, each node receives two copies of the same data unit: one copy on the working circuit and a second copy that can be extracted from linear combinations of data units transmitted on a shared protection path. This guarantees instantaneous recovery of data units upon the failure of a working circuit. The strategy can be implemented at an overlay layer, which makes its deployment simple and scalable. While the proposed strategy is similar in spirit to the work of Kamal in 2007 2010, there are significant differences. In particular, it provides protection against multiple-link failures. The new scheme is simpler, less expensive, and does not require the synchronization required by the original scheme. The sharing of the protection circuit by a number of connections is the key to the reduction of the cost of protection. This paper also conducts a comparison of the cost of the proposed scheme to the 1+1 and shared backup path protection (SBPP) strategies and establishes the benefits of our strategy.

Inter-symbol interference (ISI) channels with data dependent Gauss Markov noise have been used to model read channels in magnetic recording and other data storage systems. The Viterbi algorithm can be adapted for performing maximum likelihood sequence detection in such channels. However, the problem of finding an analytical upper bound on the bit error rate of the Viterbi detector in this case has not been fully investigated. Current techniques rely on an exhaustive enumeration of short error events and determine the BER using a union bound. In this work, we consider a subset of the class of ISI channels with data dependent Gauss-Markov noise. We derive an upper bound on the pairwise error probability (PEP) between the transmitted bit sequence and the decoded bit sequence that can be expressed as a product of functions depending on current and previous states in the (incorrect) decoded sequence and the (correct) transmitted sequence. In general, the PEP is asymmetric. The average BER over all possible bit sequences is then determined using a pairwise state diagram. Simulations results which corroborate the analysis of upper bound, demonstrate that analytic bound on BER is tight in high SNR regime. In the high SNR regime, our proposed upper bound obviates the need for computationally expensive simulation.

We consider the problem of multicasting sums over directed acyclic networks with unit capacity edges. A set of source nodes siobserve independent unit-entropy source processes Xiand want to communicate Σ Xito a set of terminals tj. Previous work on this problem has established necessary and sufficient conditions on the si-tjconnectivity in the case when there are two sources or two terminals (Ramamoorthy '08), and in the case of three sources and three terminals (Langberg-Ramamoorthy '09). In particular the latter result establishes that each terminal can recover the sum if there are two edge disjoint paths between each si-tjpair. In this work, we provide a new and significantly simpler proof of this result, and introduce techniques that may be of independent interest in other network coding problems.

There is an increasing need for high density data storage devices driven by the increased demand of consumer electronics. In this work, we consider a data storage system that operates by encoding information as topographic profiles on a polymer medium. A cantilever probe with a sharp tip (few nm radius) is used to create and sense the presence of topographic profiles, resulting in a density of few Tb per in.2. The prevalent mode of using the cantilever probe is the static mode that is harsh on the probe and the media. In this article, the high quality factor dynamic mode operation, that is less harsh on the media and the probe, is analyzed. The read operation is modeled as a communication channel which incorporates system memory due to inter-symbol interference and the cantilever state. We demonstrate an appropriate level of abstraction of this complex nanoscale system that obviates the need for an involved physical model. Next, a solution to the maximum likelihood sequence detection problem based on the Viterbi algorithm is devised. Experimental and simulation results demonstrate that the performance of this detector is several orders of magnitude better than the performance of other existing schemes.

There is an ever increasing need for storing data in small form factors driven by the ubiquitous use and increased demands of consumer electronics. A new data storage approach that achieves a few Tb per in2areal densities, utilizes a cantilever probe with a sharp tip that can be used to deform and assess the topography of a polymer medium. The information may be encoded by means of topographic profiles on the medium. The prevalent mode of using the cantilever probe is the static mode that is known to be harsh on the probe and the media. In this paper, the high quality factor dynamic mode operation, which is known to be less harsh on the media and the probe, is analyzed for probe based high density data storage purposes. It is demonstrated that an appropriate level of abstraction is possible that obviates the need for an involved physical model. The read operation is modeled as a communication channel which incorporates the inherent system memory due to the intersymbol interference and the cantilever state that can be identified using training data. Using the identified model, a solution to the maximum likelihood sequence detection problem based on the Viterbi algorithm is devised. Experimental and simulation results demonstrate that the performance of this detector is several orders of magnitude better than the other existing schemes and confirms performance gains that can render the dynamic mode operation feasible for high density data storage purposes.

We present the design and analysis of a family of codes based on the efflciently-encodable rate-compatible irregular LDPC codes (E2RC codes) introduced by Kim, Ramamoorthy and Mclaughlin '06. The basic idea is to utilize the structured parity part (of the parity check matrix) of E2RC codes and design optimal degree distributions for the systematic part based on EXIT chart analysis. In this work, we propose a new technique for computing EXIT functions of the structured parity part without resorting to Monte Carlo simulations. Our method provides smoother EXIT functions in substantially lesser time. Furthermore, we pose and solve the problem of designing good codes using linear programming. Next, we consider the performance of rate-compatible codes under puncturing using EXIT charts. Finally, we propose joint optimization of our codes at any specified code rate(s) which has not been explored in previous design of rate-compatible punctured codes.

We consider the min-cost multicast problem (under network coding) with multiple correlated sources where each terminal wants to losslessly reconstruct all the sources. This can be considered as the network generalization of the classical distributed source coding (Slepian-Wolf) problem. We study the inefficiency brought forth by the selfish behavior of the terminals in this scenario by modeling it as a noncooperative game among the terminals. The solution concept that we adopt for this game is the popular local Nash equilibrium (Waldrop equilibrium) adapted for the scenario with multiple sources. The degradation in performance due to the lack of regulation is measured by the price of anarchy (POA), which is defined as the ratio between the cost of the worst possible Waldrop equilibrium and the socially optimum cost. Our main result is that in contrast with the case of independent sources, the presence of source correlations can significantly increase the price of anarchy. Towards establishing this result we make several contributions. We characterize the socially optimal flow and rate allocation in terms of four intuitive conditions. This result is a key technical contribution of this paper and is of independent interest as well. Next, we show that the Waldrop equilibrium is a socially optimal solution for a different set of (related) cost functions. Using this, we construct explicit examples that demonstrate that the POA > 1 and determine near- tight upper bounds on the POA as well. The main techniques in our analysis are Lagrangian duality theory and the usage of the supermodularity of conditional entropy. Finally, all the techniques and results in this paper will naturally extend to a large class of network information flow problems where the Slepian-Wolf polytope is replaced by any contra-polymatroid (or more generally polymatroid-like set), leading to a nice class of succinct multi-player games and allow the investigation of other practical and meaningful scenarios beyond network coding as well.

We consider the network communication scenario in which a number of sources sieach holding independent information Xiwish to communicate the sum ¿Xito a set of terminals tj. In this work we consider directed acyclic graphs with unit capacity edges and independent sources of unit-entropy. The case in which there are only two sources or only two terminals was considered by the work of Ramamoorthy [ISIT 2008] where it was shown that communication is possible if and only if each source terminal pair si/tjis connected by at least a single path. In this work we study the communication problem in general, and show that even for the case of three sources and three terminals, a single path connecting source/terminal pairs does not suffice to communicate ¿Xi. We then present an efficient encoding scheme which enables the communication of ¿Xifor the three sources, three terminals case, given that each source terminal pair is connected by two edge disjoint paths. Our encoding scheme includes a structural decomposition of the network at hand which may be found useful for other network coding problems as well.

We propose a network-coding based scheme to protect multiple bidirectional unicast connections against adversarial errors and failures in a network. The end nodes of the bidirectional connections are connected by a set of shared protection paths that provide the redundancy required for protection. Suppose that ne paths are corrupted by an omniscient, computationally unbounded adversary. Under our proposed protocol, the errors can be corrected at all the end nodes with 4neprotection paths. More generally, if there are neadversarial errors and nƒfailures, 4ne+ 2nƒprotection paths are sufficient. The number of protection paths only depends on the number of errors and failures being protected against and is independent of the number of unicast connections.

We consider the design and analysis of the efficiently-encodable rate-compatible (E2RC) irregular LDPC codes proposed in previous work. In this work we introduce semi-structured E2RC-like codes and protograph E2RC codes. EXIT chart based methods are developed for the design of semi-structured E2RC-like codes that allow us to determine near-optimal degree distributions for the systematic part of the code while taking into account the structure of the deterministic parity part, thus resolving one of the open issues in the original construction. We develop a fast EXIT function computation method that does not rely on Monte-Carlo simulations and can be used in other scenarios as well. Our approach allows us to jointly optimize code performance across the range of rates under puncturing. We then consider protograph E2RC codes (that have a protograph representation) and propose rules for designing a family of rate-compatible punctured protographs with low thresholds. For both the semi-structured and protograph E2RC families we obtain codes whose gap to capacity is at most 0.3 dB across the range of rates when the maximum variable node degree is twenty.

We present a new class of irregular low-density parity-check (LDPC) codes for moderate block lengths (up to a few thousand bits) that are well-suited for rate-compatible puncturing. The proposed codes show good performance under puncturing over a wide range of rates and are suitable for usage in incremental redundancy hybrid-automatic repeat request (ARQ) systems. In addition, these codes are linear-time encodable with simple shift-register circuits. For a block length of 1200 bits the codes outperform optimized irregular LDPC codes and extended irregular repeat-accumulate (eIRA) codes for all puncturing rates 0.6~0.9 (base code performance is almost the same) and are particularly good at high puncturing rates where good puncturing performance has been previously difficult to achieve.

We consider the problem of rate and power allocation for a sensor network under the pairwise distributed source coding constraint. For noiseless source-terminal channels, we show that the minimum sum rate assignment can be found by finding a minimum weight arborescence in an appropriately defined directed graph. For orthogonal noisy source-terminal channels, the minimum sum power allocation can be found by finding a minimum weight matching forest in a mixed graph. Numerical results are presented for both cases showing that our solutions always outperform previously proposed solutions. The gains are considerable when source correlations are high.

We propose a construction of rate-compatible punctured codes based on protographs that have a special E2RC structure in their parity part (E2RC codes were introduced in Kim, Ramamoorthy and McLaughlin '06) . The protograph representation of these codes facilitates their asymptotic performance analysis and allows the implementation of high speed decoders. The construction process starts with a good high rate protograph. The protographs of lower rate codes are derived from the higher rate protographs via the process of check-splitting. The check-splitting is done in a specific manner so that the parity nodes in the protograph have the special E2RC structure. We also present additional design rules that ensure that the gap to capacity remains low across the range of rates. Using our approach we exhibit protographs that have a gap of at most 0.27 dB to capacity across the range of rates 1/2 to 8/9. These conclusions are supported by our simulation results. Our work, therefore presents a systematic method for the design of E2RC-like codes.

We explore the problem of rate and power allocation for a sensor network where pairwise distributed source coding is employed (introduced by Roumy and Gesbert ’07). For noiseless node-terminal channels, we show that the minimum sum rate assignment with this property can be found by finding a minimum weight arborescence in an appropriately defined directed graph. For orthogonal noisy node-terminal channels, the minimum sum power allocation can be found by finding a minimum weight matching forest in a mixed graph. Numerical results are presented for the noiseless case showing that our solution outperforms previous solutions when source correlations are high.

We consider a network (that is capable of network coding) with a set of sources and terminals, where each terminal is interested in recovering the sum of the sources. Considering directed acyclic graphs with unit capacity edges and independent, unit-entropy sources, we show the rate region when (a) there are two sources and n terminals, and (b) n sources and two terminals. In these cases as long as there exists at least one path from each source to each terminal we demonstrate that there exists a valid assignment of coding vectors to the edges such that the terminals can recover the sum of the sources.

In recent years performance prediction for communication systems utilizing iteratively decodable codes has been of considerable interest. There have been significant breakthroughs as far as the analysis of LDPC code ensembles is concerned but the more practical problem of predicting the FER/BER of a particular code has proved to be much more difficult. In this work we present a technique (based on the work of Richardson '03) for finding lower and upper bounds on the performance of LDPC coded BICM systems for a given code. The insight gained from the prediction technique is used to design interleavers that improve the error floors of these systems.

This work considers the problem of transmitting multiple compressible sources over a network with minimum cost. The problem is complicated by the fact that the description of the feasible rate region of distributed source coding problems typically has a number of constraints that is exponential in the number of sources that renders general purpose solvers inefficient. We present a framework in which these problems can be solved efficiently by exploiting the structure of the feasible rate regions coupled with dual decomposition and subgradient methods.

Wireless networks have historically considered support for mobile elements's an extra overhead. However, recent research has provided the means by which a network can take advantage of mobile elements. Particularly in the case of wireless sensor networks, mobile elements can be deliberately built into the system to improve the lifetime of the network and act as mechanical carriers of data. The mobile element, whose mobility is controlled, visits the nodes to collect their data before their buffers are full. In general, the spatio-temporal dynamics of the sensed phenomenon may require sensor nodes to collect samples at different rates, in which case, some nodes need to be visited more frequently than others. This work formulates the problem of scheduling the mobile element in the network so that there is no data loss due to buffer overflow. The problem is shown to be NP-complete and an integer-linear-programming formulation is given. Finally, some computationally practical algorithms for a single mobile and for the case of multiple mobiles are presented and their performances compared

We present a new class of irregular low-density parity-check (LDPC) codes for finite block length (up to a few thousand symbols). The proposed codes are efficiently encodable and have a simple rate-compatible puncturing structure. For block lengths on the order of n=1000 bits, the codes show good puncturing performance over a wide range of rates. The codes outperform optimized irregular LDPC codes and (extended) irregular repeat-accumulate codes for all rates 0.5~0.9, and are particularly good at high puncturing rates where good puncturing performance has been previously difficult to achieve.

We present a new class of irregular low-density parity-check (LDPC) codes for finite block length (up to a few thousand symbols). The proposed codes are efficiently encodable and have a simple rate-compatible puncturing structure which is suitable for incremental redundancy hybrid automatic repeat request (IR-HARQ) systems. The codes outperform optimized irregular LDPC codes and (extended) irregular repeat-accumulate codes for rates 0.67-0.94, and are particularly good at high puncturing rates where good puncturing performance has been previously difficult to achieve. These characteristics result in good throughput performance over time-varying channels in IR-HARQ systems

This correspondence considers the problem of distributed source coding of multiple sources over a network with multiple receivers. Each receiver seeks to reconstruct all of the original sources. The work by Ho et al. 2004 demonstrates that random network coding can solve this problem at the potentially high cost of jointly decoding the source and the network code. Motivated by complexity considerations we consider the performance of separate source and network codes. Previous work by Effros et al. 2003 demonstrates the failure of separation between source and network codes for nonmulticast networks. We demonstrate that failure for multicast networks. We study networks with capacity constraints on edges. It is shown that the problem with two sources and two receivers is always separable. Counterexamples are presented for other cases.

Fidelity is one of the key considerations in data collection schemes for sensor networks. A second important consideration is the energy expense of achieving that fidelity. Data from multiple correlated sensors is collected over multi-hop routes and fused to reproduce the phenomenon. However, the same distortion may be achieved using multiple rate allocations among the correlated sensors. These rate allocations would typically have different energy cost in routing depending on the network topology. We consider the interplay between these two considerations of distortion and energy. First, we describe the various factors that affect this trade-off. Second, we discuss bounds on the achievable performance with respect to this trade-off. Specifically, we relate the network lifetime Ltto the distortion D of the delivered data. Finally, we present low-complexity approximations for the efficient computation of the Lt(D) bound

We study the maximum flow possible between a single-source and multiple terminals in a weighted random graph (modeling a wired network) and a weighted random geometric graph (modeling an ad-hoc wireless network) using network coding. For the weighted random graph model, we show that the network coding capacity concentrates around the expected number of nearest neighbors of the source and the terminals. Specifically, for a network with a single source, l terminals, and n relay nodes such that the link capacities between any two nodes is independent and identically distributed (i.i.d.) /spl sim/X, the maximum flow between the source and the terminals is approximately nE[X] with high probability. For the weighted random geometric graph model where two nodes are connected if they are within a certain distance of each other we show that with high probability the network coding capacity is greater than or equal to the expected number of nearest neighbors of the node with the least coverage area.

We present a construction algorithm for short block length irregular low-density parity-check (LDPC) codes. Based on a novel interpretation of stopping sets in terms of the parity-check matrix, we present an approximate trellis-based search algorithm that detects many stopping sets. Growing the parity check matrix by a combination of random generation and the trellis-based search, we obtain codes that possess error floors orders of magnitude below randomly constructed codes and significantly better than other comparable constructions.

This work presents a rigorous analysis of an algorithm proposed by Tian et al. (2003) for the construction of irregular LDPC codes with reduced stopping sets and low error floors. Computation of the expected number of stopping sets of a given size proves that the algorithm significantly outperforms a random construction. We show that the algorithm provably reduces the expected number of stopping sets up to a certain size (based on the input parameters). The expected number of cycles of a given size is computed for both constructions.

Wireless networks have historically considered support for mobile elements as an extra overhead. However, recent research has provided means by which network can take advantage of mobile elements. Particularly, in the case of wireless sensor networks, mobile elements are deliberately built into the system to improve the lifetime of the network, and act as mechanical carriers of data. The mobile element, which is controlled, visits the nodes to collect their data before their buffers are full. It may happen that the sensor nodes are sampling at different rates, in which case some nodes need to be visited more frequently than others. We present this problem of scheduling the mobile element in the network, so that there is no data loss due to buffer overflow. We prove that the problem is NP-complete and give an ILP formulation. We give some practical algorithms, and compare their performances.

Many content-based image retrieval (CBIR) systems utilize image segmentation for enabling the user to perform object-level database querying. We propose an integrated segmentation technique for interactive image retrieval, that is reasonably accurate and fast. An initial over-segmentation is generated by finding the dominant color modes in the global histogram of the image using the mean-shift algorithm. Edge-based processing is performed at the initial segment boundaries to merge non-obvious segments. Finally segment shapes are regularized using a Hopfield (1985) type neural network to improve their perceptual quality. A scalable implementation is presented for ensuring fast serial execution of the Hopfield network. The entire segmentation process takes less than 10 seconds to segment 128/spl times/192 stock photos on a standard workstation.