We investigate the applications of ovals in projective planes to distributed storage, with a focus on the Service Rate Region problem. Leveraging the incidence relations between lines and ovals, we describe a class of non-systematic MDS matrices with a large number of small and disjoint recovery sets. For certain parameter choices, the service-rate region of these matrices contains the region of a systematic generator matrix for the same code, yielding better service performance. We further apply our construction to analyze the PIR properties of the considered MDS matrices and present a one-step majority-logic decoding algorithm with strong error-correcting capability. These results highlight how ovals, a classical object in finite geometry, re-emerge as a useful tool in modern coding theory.

The classical majority-logic decoder proposed by Reed for Reed-Muller codes RM(r, m) of order r and length 2^m, unfolds in r+1 sequential steps, decoding message symbols from highest to lowest degree. Several follow-up decoding algorithms reduced the number of steps, but for a limited set of parameters, or at the expense of reduced performance, or relying on the existence of some combinatorial structures. We show that any one-step majority-logic decoder-that is, a decoder performing all majority votes in one step simultaneously without sequential processing-can correct at most d_min/4 errors for all values of r and m, where d_min denotes the code's minimum distance. We then introduce a new hard-decision decoder that completes the decoding in a single step and attains this error-correction limit. It applies to all r and m, and can be viewed as a parallel realization of Reed's original algorithm, decoding all message symbols simultaneously. Remarkably, we also prove that the decoder is optimum in the erasure setting: it recovers the message from any erasure pattern of up to d_min-1 symbols-the theoretical limit. To our knowledge, this is the first 1-step decoder for RM codes that achieves both optimal erasure correction and the maximum one-step error correction capability.

Locally repairable codes (LRCs) were originally introduced to enable efficient recovery from erasures in distributed storage systems by accessing only a small number of other symbols. While their structural properties-such as bounds and constructions-have been extensively studied, the performance of LRCs under random erasures and errors has remained largely unexplored. In this work, we study the error- and erasure-correction performance of binary linear LRCs under majority-logic decoding (MLD). Focusing on LRCs with fixed locality and varying availability, we derive explicit upper bounds on the probability of decoding failure over the memoryless Binary Erasure Channel (BEC) and Binary Symmetric Channel (BSC). Our analysis characterizes the behavior of the bit-error rate (BER) and block-error rate (BLER) as functions of the locality and availability parameters. We show that, under mild growth conditions on the availability, the block decoding failure probability vanishes asymptotically, and that majority-logic decoding can successfully correct virtually all of error and erasure patterns of weight linear in the blocklength. The results reveal a substantial gap between worst-case guarantees and typical performance under stochastic channel models.

We study the Service Rate Region of Reed–Muller codes in the context of distributed storage systems. The service rate region is a convex polytope comprising all achievable data access request rates under a given coding scheme. It represents a critical metric for evaluating system efficiency and scalability. Using the geometric properties of Reed–Muller codes, we characterize recovery sets for data objects, including their existence, uniqueness, and enumeration. This analysis reveals a connection between recovery sets and minimum-weight codewords in the dual Reed–Muller code, providing a framework for identifying those recovery sets. Leveraging these results, we derive explicit and tight bounds on the maximal achievable demand for individual data objects, thereby defining the maximal simplex contained within the service rate region, and the smallest simplex containing it. These two simplices provide a tight approximation to the service-rate region of Reed–Muller codes.

We study the Service Rate Region (SRR) of distributed storage systems that store data using Reed-Muller (RM) codes. We focus on systems where each server stores an RM codeword symbol, and each user aims to decode a single data symbol by accessing the servers storing one of the data symbol's recovery groups. The cumulative access rate to each server cannot exceed its given service rate. The SRR is a convex polytope comprising all achievable data access request rates. It represents a critical metric for evaluating system efficiency and scalability. We characterize recovery sets for data objects using the geometric properties of RM codes. This analysis reveals a connection between the RM code's recovery sets and minimumweight codewords in the dual RM code. Using these results, we derive explicit and tight bounds for the maximal achievable demand for individual data objects, which define the maximal simplex polytope within the service rate region.

We consider computing systems that partition jobs into tasks, add redundancy through coding, and assign the encoded tasks to different computing nodes for parallel execution. The expected execution time depends on the level of redundancy. The computing nodes execute large jobs in batches of tasks. We show that the expected execution time depends on the batch size as well. The optimal batch size that minimizes the execution time depends on the level of redundancy under a fixed number of parallel servers and other system parameters. Furthermore, we show how to (jointly) optimize the redundancy level and batch size to reduce the expected job completion time for two service-time distributions. The simulation presented helps us appreciate the claims.

Edge computing operates between the cloud and end users and strives to provide low-latency computing services for simultaneous users. Redundant use of multiple edge nodes can reduce latency, as edge systems often operate in uncertain environments. However, since edge systems have limited computing and storage resources, directing more resources to some computing jobs will either block the execution of others or pass their execution to the cloud, thus increasing latency. This paper uses the average system computing time and blocking probability to evaluate edge system performance and analyzes the optimal resource allocation accordingly. We also propose blocking probability and average system time optimization algorithms. Simulation results show that both algorithms significantly outperform the benchmark for different service time distributions and show how the optimal replication factor changes with varying parameters of the system.

This paper studies two crucial problems in the context of coded distributed storage systems directly related to their performance: 1) for a fixed alphabet size, determine the minimum number of servers the system must have for its service rate region to contain a prescribed set of points; 2) for a given number of servers, determine the minimum alphabet size for which the service rate region of the system contains a prescribed set of points. The paper establishes rigorous upper and lower bounds, as well as code constructions based on techniques from coding theory, optimization, and projective geometry.

Edge systems promise to bring data and computing closer to the users of time-critical applications. Specifically, edge storage systems are emerging as a new system paradigm, where users can retrieve data from small-scale servers inter-operating at the network’s edge. The analysis, design, and optimization of such systems require a tractable model that will reflect their costs and bottlenecks. Alas, most existing mathematical models for edge systems focus on stateless tasks, network performance, or isolated nodes and are inapplicable for evaluating edge-based storage performance. We analyze the capacity-region model–the most promising model proposed so far for edge storage systems. The model addresses the system’s ability to serve a set of user demands. Our analysis reveals five inherent gaps between this model and reality, demonstrating the significant remaining challenges in modeling storage service at the edge.

We develop new methods of quantifying the impact of photon detector imperfections on possible secret key rates in Time-Entanglement based Quantum Key Distribution (QKD). We address photon detection timing jitter, detector downtime, and dark photon counts and show how each may decrease the maximum achievable secret key rate differently. We begin with a standard Discrete Memoryless Channel (DMC) model to get a good bound on the mutual information lost due to the timing jitter, then introduce a novel Markov Chain (MC) based model to characterize the effect of detector downtime and show how it introduces memory to the key generation process. Finally, we propose a new method of including dark counts in the analysis that shows how dark counts can be especially detrimental when using the common Pulse Position Modulation (PPM) for key generation. Our results show that these three imperfections can significantly reduce the achievable secret key rate when using PPM for QKD. One of our main results is providing tooling for experimentalists to predict their systems’ achievable secret key rate given the detector specifications.

In time entanglement-based quantum key distribution (TE-QKD), Alice and Bob extract the raw key bits from the arrival times of entangled photon pairs. Each entangled pair can contribute to multiple key bits depending on how precisely Alice and Bob can measure the photon arrival times. Thus, TE-QKD can potentially increase the secret key rate compared to typical QKD implementations, which extract up to a bit per photon. Because of entanglement, the times of photon arrivals at Alice’s and Bob’s detectors and, thus, their raw keys should be identical. However, practical photon detectors suffer from time jitter errors. These errors cause discrepancies between Alice’s and Bob’s raw keys. Therefore, Alice must send information to Bob through the public channel to reconcile their raw keys. The amount of data sent for reconciliation represents a loss, rendering secret keys shorter than the raw keys. We compute the secret key rates possible in systems with detector jitter errors and show that they are much higher than those achievable in polarization entanglement-based QKD. We then construct codes for information reconciliation to approach these rates. We demonstrate that short and moderate-length standard error-correcting codes represent excellent information reconciliation choices, making TE-QKD a promising technology.

We are concerned with linear redundancy storage schemes regarding their ability to provide concurrent (local) recovery of multiple data objects. This paper initiates a study of such systems within the classical coding theory. We show how we can use the structural properties of the generator matrix defining the scheme to obtain a bounding polytope for the set of data access rates the system can support. We derive two dual distance outer bounds, which are sharp for some large classes of matrix families.

We introduce a gossip-like protocol for covert message passing between Alice and Bob as they move in an area watched over by a warden Willie. The area hosts a multitude of Internet of (Battlefield) Things (Io$\beta \text{T}$) objects. Alice and Bob perform random walks on a random regular graph. The Io$\beta \text{T}$objects reside on the vertices of this graph, and some can serve as relays between Alice and Bob. The protocol starts with Alice splitting her message into small chunks, which she can covertly deposit to the relays she encounters. The protocol ends with Bob collecting the chunks. Alice may encode her data before the dissemination. Willie can either perform random walks as Alice and Bob do or conduct uniform surveillance of the area. In either case, he can only observe one relay at a time. We evaluate the system performance by the covertness probability and the message passing delay. In our protocol, Alice splits her message to increase the covertness probability and adds (coded) redundancy to reduce the transmission delay. The performance metrics depend on the graph, communications delay, and code parameters. We show that, in most scenarios, it is impossible to find the design parameters that simultaneously maximize the covertness probability and minimize the message delay.

Distributed computing enablesparallelexecution of smaller tasks that make up a large computing job. Its purpose is to reduce the job completion time. However, random fluctuations in task service times lead to straggling tasks with long execution times. Redundancy providesdiversitythat allows job completion when only a subset of redundant tasks is executed, thus removing the dependency on the straggling tasks. Under constrained resources (here, a fixed number of parallel servers), increasing redundancy reduces the available resources for parallelism. In this paper, we characterize thediversity vs. parallelismtrade-off and identify the optimal strategy among replication, coding, and splitting, which minimizes the expected job completion time. We consider three common service time distributions and establish three models that describe the scaling of these distributions with the task size. We find that different distributions with different scaling models operate optimally at different redundancy levels, thus requiring very different code rates.

The paper presents techniques for analyzing the expected download time in distributed storage systems that employ systematic availability codes. These codes provide access to hot data through the systematic server containing the object and multiple recovery groups. When a request for an object is received, it can be replicated (forked) to the systematic server and all recovery groups. We first consider the low-traffic regime and present the close-form expression for the download time. By comparison across systems with availability, maximum distance separable (MDS), and replication codes, we demonstrate that availability codes can reduce download time in some settings but are not always optimal. In the high-traffic regime, the system contains multiple inter-dependent Fork-Join queues, making exact analysis intractable. Accordingly, we present upper and lower bounds on the download time, and an M/G/1 queue approximation for several cases of interest. Via extensive numerical simulations, we evaluate our bounds and demonstrate that the M/G/1 queue approximation has a high degree of accuracy.

Distributed systems operate under storage access and download service uncertainty. We consider two access models. In one, a user can access each storage node with a fixed probability, and in the other, a user can access any fixed-size subset of nodes. We consider two download service models. In the first (small file) model, the time to transmit file data is negligible compared to the overall average download time. In the second (large file) model, the download time scales with the amount of downloaded data. The performance metric is the system’s service rate. For a fixed redundancy level, the systems’ service rate depends on the allocation of coded chunks over the storage nodes. Since finding the general optimal allocation is prohibitively hard, we consider quasi-uniform allocations, where coded content is equally spread among a subset of nodes. The question we address asks what the size of this subset (spreading) should be. We show that concentrating the coded content to a minimum-size subset is universally optimal for the small file model. However, for the large file model, the optimal spreading depends on the system parameters. These conclusions hold for both access models.

To facilitate load balancing, distributed systems store data redundantly. We evaluate the load balancing performance of storage schemes in which each object is stored at d different nodes, and each node stores the same number of objects. In our model, the load offered for the objects is sampled uniformly at random from all the load vectors with a fixed cumulative value. We find that the load balance in a system of n nodes improves multiplicatively with d as long as d = o(log(n)), and improves exponentially once d = Θ(log(n)). We show that the load balance improves in the same way with d when the service choices are created with XOR's of r objects rather than object replicas. In such redundancy schemes, storage overhead is reduced multiplicatively by r. However, recovery of an object requires downloading content from r nodes. At the same time, the load balance increases additively by r. We express the system's load balance in terms of the maximal spacing or maximum of d consecutive spacings between the ordered statistics of uniform random variables. Using this connection and the limit results on the maximal d-spacings, we derive our main results.

Erasure coding has been recognized as a powerful method to mitigate delays due to slow or straggling nodes in distributed systems. This work shows that erasure coding of data objects can flexibly handle skews in the request rates. Coding can help boost theservice rate region, that is, increase the overall volume of data access requests that the system can handle. This paper aims to postulate the service rate region as an important consideration in the design of erasure-coded distributed systems. We highlight several open problems that can be grouped into two broad threads: 1) characterizing the service rate region of a given code and finding the optimal request allocation, and 2) designing the underlying erasure code for a given service rate region. As contributions along the first thread, we find the rate regions of maximum-distance-separable, locally repairable, and simplex codes. We show the effectiveness of hybrid codes that combine replication and erasure coding in terms of code design. We also discover fundamental connections between multi-set batch codes and the problem of maximizing the service rate region.

Master-worker distributed computing systems use task replication to mitigate the effect of slow workers on job compute time. The master node groups tasks into batches and assigns each batch to one or more workers. We first assume that the batches do not overlap. Using majorization theory, we show that a balanced replication of batches minimizes the average job compute time for a general class of service time distributions. We then show that the balanced assignment of non-overlapping batches achieves a lower average job compute time than the overlapping schemes proposed in the literature. Next, we derive the optimum redundancy level as a function of the task service time distribution. We show that the redundancy level that minimizes the average job compute time may not coincide with the redundancy level that maximizes job compute time predictability. Therefore, there is a trade-off in optimizing the two metrics. By running experiments on Google cluster traces, we observe that redundancy can reduce the job compute time by one order of magnitude. The optimum level of redundancy depends on the distribution of task service time.

Leader-based data replication improves consistency in highly available distributed storage systems via sequential writes to the "leader" nodes. After a write has been committed by the leaders, "follower" nodes are written by a multicast mechanism and are only guaranteed to be eventually consistent. With Age of Information (AoI) as the freshness metric, we characterize how the number of leaders affects the freshness of the data retrieved by an instantaneous read query. In particular, we derive the average age of a read query for a deterministic model for the leader writing time and a probabilistic model for the follower writing time. We obtain a closed-form expression for the average age for exponentially distributed follower writing time. Our numerical results show that, depending on the relative speed of the write operation to the two groups of nodes, there exists an optimal number of leaders which minimizes the average age of the retrieved data, and that this number increases as the relative speed of writing on leaders increases.

Service rate is an important, recently introduced, performance metric associated with distributed coded storage systems. Among other interpretations, it measures the number of users that can be simultaneously served by the system. We introduce a geometric approach to address this problem. One of the most significant advantages of this approach over the existing ones is that it allows one to derive bounds on the service rate of a code without explicitly knowing the list of all possible recovery sets. To illustrate the power of our geometric approach, we derive upper bounds on the service rates of the first order Reed-Muller codes and the simplex codes. Then, we show how these upper bounds can be achieved. Furthermore, utilizing the proposed geometric technique, we show that given the service rate region of a code, a lower bound on the minimum distance of the code can be obtained.

We propose a novel technique for constructing a graph representation of a code through which we establish a significant connection between the service rate problem and the well-known fractional matching problem. Using this connection, we show that the service capacity of a coded storage system equals the fractional matching number in the graph representation of the code, and thus is lower bounded and upper bounded by the matching number and the vertex cover number, respectively. This is of great interest because if the graph representation of a code is bipartite, then the derived upper and lower bounds are equal, and we obtain the capacity. Leveraging this result, we characterize the service capacity of the binary simplex code whose graph representation is bipartite. Moreover, we show that the service rate problem can be viewed as a generalization of the multiset primitive batch codes problem.

Distributed computing enables parallel execution of tasks that make up a large computing job. Random fluctuations in service times (inherent to computing environments) often cause a non-negligible number of straggling tasks with long completion time. Redundancy, in the form of task replication and erasure coding, has emerged as a potentially powerful way to curtail the variability in service time, as it provides diversity that allows a job to be completed when only a subset of redundant tasks gets executed. Thus both redundancy and parallelism reduce the execution time, but compete for resources of the system. In situations of constrained resources (here fixed number of parallel servers), increasing redundancy reduces the available level of parallelism. We characterize the diversity vs. parallelism tradeoff for three common models of task size dependent execution times. We find that different models operate optimally at different levels of redundancy, and thus may require very different code rates.

A major concern in cloud/edge storage systems is serving a large number of users simultaneously. The service rate region is introduced recently as an important performance metric for coded distributed systems, which is defined as the set of all data access requests that can be simultaneously handled by the system. This paper studies the problem of designing a coded distributed storage system storing k files where a desired service rate region $\mathcal{R}$ of the system is given and the goal is 1) to determine the minimum number of storage nodes $n(\mathcal{R})$ for serving all demand vectors inside the set $\mathcal{R}$ and 2) to design the most storage-efficient redundancy scheme with the service rate region covering the set $\mathcal{R}$. Towards this goal, we propose three general lower bounds for $n(\mathcal{R})$. Also, for k = 2, we characterize $n(\mathcal{R})$, i.e., we show that the proposed lower bounds are tight, via designing a novel storage-efficient redundancy scheme with $n(\mathcal{R})$ storage nodes and service rate region covering $\mathcal{R}$.

In distributed computing systems with stragglers, various forms of redundancy can improve the average delay performance. We study the optimal replication of data in systems where the job execution time is a stochastically decreasing and convex random variable. We show that in such systems, the optimum assignment policy is the balanced replication of disjoint batches of data. Furthermore, for Exponential and Shifted-Exponential service times, we derive the optimum redundancy levels for minimizing both expected value and the variance of the job completion time. Our analysis shows that, the optimum redundancy level may not be the same for the two metrics, thus there is a trade-off between reducing the expected value of the completion time and reducing its variance.

We study the performance of non-adaptive scheduling policies in computing systems with multiple servers. Compute jobs are mostly regular, with modest service requirements. However, there are sporadic data intensive jobs, whose expected service time is much higher than that of the regular jobs. For this model, we are interested in the effect of scheduling policies on the average time a job spends in the system. To this end, we introduce two performance indicators in a simplified, only-arrival system. We believe that these performance indicators are good predictors of the relative performance of the policies in the queuing system, which is supported by simulations results.

Anonymity platforms route the traffic over a network of special routers that are known as mixes and implement various traffic disruption techniques to hide the communicating users' identities. Batch mixes in particular anonymize communicating peers by allowing message exchange to take place only after a sufficient number of messages (a batch) accumulate, thus introducing delay. We introduce a queueing model for batch mix and study its delay properties. Our analysis shows that delay of a batch mix grows quickly as the batch size gets close to the number of senders connected to the mix. We then propose a randomized batch mixing strategy and show that it achieves much better delay scaling in terms of the batch size. However, randomization is shown to reduce the anonymity preserving capabilities of the mix. We also observe that queueing models are particularly useful to study anonymity metrics that are more practically relevant such as the time-to-deanonymize metric.

Runtime performance variability has been a major issue, hindering predictable and scalable performance in modern distributed systems. Executing requests or jobs redundantly over multiple servers have been shown to be effective for mitigating variability, both in theory and practice. Systems that employ redundancy has drawn significant attention, and numerous papers have analyzed the pain and gain of redundancy under various service models and assumptions on the runtime variability. This paper presents a cost (pain) vs. latency (gain) analysis of executing jobs of many tasks by employing replicated or erasure coded redundancy. The tail heaviness of service time variability is decisive on the pain and gain of redundancy and we quantify its effect by deriving expressions for cost and latency. Specifically, we try to answer four questions: 1) How do replicated and coded redundancy compare in the cost vs. latency tradeoff? 2) Can we introduce redundancy after waiting some time and expect it to reduce the cost? 3) Can relaunching the tasks that appear to be straggling after some time help to reduce cost and/or latency? 4) Is it effective to use redundancy and relaunching together? We validate the answers we found for each of these questions via simulations that use empirical distributions extracted from a Google cluster data.

There has been a growing interest, in both theory and practice, in using the available redundancy in storage systems for mitigating stragglers in content download. This paper is concerned with MDS coded storage systems and studies (n, k) data access model. When k = n, system is equivalent to a fork-join queue, which is known to be notoriously hard to analyze, while system with k = 1 has been previously shown to be equivalent to an M/G/1 queue. We here argue that the system with k = 2 is of practical interest, and then present a method that approximates the system as an M/G/1 queue. Approximated download time is shown to be more accurate than the bounds available in the literature. We also note that the presented method can be used for approximating systems that employ other newly designed and deployed storage codes.

We consider a cache refresh system where a local server is connected to multiple remote sources and maintains local copies of the data items at the sources. The data at each source is updated randomly and independently without notifying the local server, while the local server refreshes the corresponding cached data periodically. The freshness of the local cache is measured by two different freshness metrics,age of synchronization(AoS) andage of information(AoI). We address the following problem: given a constrained total refresh rate, how does the local server allocate the refresh rate for each source to maintain overall data freshness? We derive the AoI optimal policy which depends only on the square root of the source popularity. For a large refresh rate, we propose an AoS near-optimal rate allocation policy that is proportional to the cube root of both the source update rate and the source popularity. For small refresh rates, we also prove that the square root law with respect to the popularity minimizes both AoS and AoI.

We consider storage systems in which K files are stored over N nodes. A node may be systematic for a particular file in the sense that access to it gives access to the file. Alternatively, a node may be coded, meaning that it gives access to a particular file only when combined with other nodes (which may be coded or systematic). Requests for file fkarrive at rate λk, and we are interested in the rate that can be served by a particular system. In this paper, we determine the set of request arrival rates for the a 3-file coded storage system. We also provide an algorithm to maximize the rate of requests served for file K given λ1, . . . , λK-1in a general K-file case.

We consider a real-time streaming source coding system in which an encoder observes a sequence of randomly arriving symbols from an i.i.d. source, and feeds binary code-words to a FIFO buffer that outputs one bit per time unit to a decoder. Each source symbol represents a status update by the source, and the timeliness of the system is quantified by the age of information (AoI), defined as the time difference between the present time and the generation time of the most up-to-date symbol at the output of the decoder. When the FIFO buffer is allowed to be empty, we propose an optimal prefix-free lossless coding scheme that minimizes the average peak age based on the analysis of discrete-time Geo/G/1 queue. For more practical scenarios in which a special codeword is reserved for indicating an empty buffer, we propose an encoding scheme that assigns a codeword to the empty buffer state based on an estimate of the buffer idle time.

We consider a system where randomly generated updates are to be transmitted to a monitor, but only a single update can be in the system at a time. Therefore, the source has to prioritize between the two possible transmission policies: preempting the current update or discarding the new one. We consider Poisson arrivals and general service time, and refer to this system as the M/G/1/1 queue. We start by studying the average status update age and the optimal update arrival rate for these two schemes under general service time distribution. We then apply these results on two practical scenarios in which updates are sent through an erasure channel using (a) an infinite incremental redundancy (IIR) HARQ system and (b) a fixed redundancy (FR) HARQ system. We show that in both schemes the best strategy would be not to preempt. Moreover, we also prove that, from an age point of view, IIR is better than FR.

Using an age of information (AoI) metric, we examine the transmission of coded updates through a binary erasure channel to a monitor/receiver. We start by deriving the average status update age of an infinite incremental redundancy (IIR) system in which the transmission of a k-symbol update continues until k symbols are received. This system is then compared to a fixed redundancy (FR) system in which each update is transmitted as an n symbol packet and the packet is successfully received if and only if at least k symbols are received. If fewer than k symbols are received, the update is discarded. Unlike the IIR system, the FR system requires no feedback from the receiver. For a single monitor system, we show that tuning the redundancy to the symbol erasure rate enables the FR system to perform as well as the IIR system. As the number of monitors is increased, the FR system outperforms the IIR system that guarantees delivery of all updates to all monitors.

The end-to-end delay of streaming source coding is characterized by an age of information (AoI) metric that measures the number of symbol periods the decoder output lags behind the encoder input. The source encoder receives input source symbols one per unit time and sequentially outputs binary codewords to a constant rate channel that transmits bits to the decoder. We examine a system in which knowledge of the busy/idle state at the channel interface enables the encoder to switch among codebooks with different source blocklengths based on the backlog of symbols at the encoder. We start by introducing two source sequence parsing policies and show that in each of them the blocklength process can be modeled by a Markov chain. We show by experiments that blocklength adjustment based on the channel interface state provides lower average age than codes with fixed blocklength. Aiming to avoid unnecessary frequent blocklength changes by the encoder backlog, we propose maximum blocklength control scheme at the encoder to further reduce the average age.

Storage allocation affects important performance measures of distributed storage systems. Most previous studies on the storage allocation consider its effect separately either on the success of the data recovery or on the service rate (time) where it is assumed that no access failure happens in the system. In this paper, we go one step further and incorporate the access model and the success of data recovery into the service rate analysis. In particular, we focus on quasi-uniform storage allocation and provide a service rate analysis for both fixed-size and probabilistic access models at the nodes. Using this analysis, we then show that for the case of exponential waiting time distribution at individuals storage nodes, minimal spreading allocation results in the highest system service rate for both access models. This means that for a given storage budget, replication provides a better service rate than a coded storage solution.

Motivated by error correction coding in multimedia applications, we study the problem of broadcasting a single common source to multiple receivers over heterogeneous erasure channels. Each receiver is required to partially reconstruct the source sequence by decoding a certain fraction of the source symbols. We propose a coding scheme that requires only off-the-shelf erasure codes and can be easily adapted as users join and leave the network. Our scheme involves splitting the source sequence into multiple segments and applying a systematic erasure code to each such segment. We formulate the problem of minimizing the transmission latency at the server as a linear programming problem and explicitly characterize an optimal choice for the code rates and segment sizes. Through numerical comparisons, we demonstrate that our proposed scheme outperforms both separation-based coding schemes and degree-optimized rateless codes and performs close to a natural outer (lower) bound in certain cases. We further study individual user decoding delays for various orderings of segments in our scheme. We provide closed-form expressions for each individual user's excess latency when parity checks are successively transmitted in both increasing order and decreasing order of their segment's coded rate and also qualitatively discuss the merits of each order.

Coding techniques for storage systems are gaining traction in data center (DC) applications, owing to their data survivability performance, and more recently, to their ability to mitigate traffic congestion. This paper considers stochastic allocation schedules in networks that admit bulk file requests, across three drive blocking models. We consider a block-based code and a stochastic scheduling algorithm which is beneficial in the case of continuous chunk read patterns. In particular, we demonstrate that in systems with continuous chunk reading patterns, when drive blocking is either independent or from traffic congestion, block coded storage can reduce average download time by 10 -- 66%, given modern system parameters. However, a distinction should be made between systems with continuous and those with interrupted chunk read patterns. For interrupted chunk read systems, given our allocation algorithm that performs well for continuous reads, block coded storage performance can be worse than replication, numerical illustrations show relative losses over 66%. These illustrations demonstrate that to harness the full benefits of coded storage and to avoid pitfalls, careful attention must be paid to continuous vs. Interrupted chunk reading patterns, codes other than block codes should be considered, as could joint code-scheduling design.

In this paper, we examine the information-theoretic security of multiple-input-multiple-output space-division multiplexed (MIMO-SDM) fiber-optic communication systems in the presence of multiple eavesdroppers. In particular, we analyze the achievable secrecy rate for the two special cases that reflect different capabilities of the eavesdroppers: independent eavesdroppers who do not share received information and colluding (cooperating) eavesdroppers who can combine and jointly process the received signals. Our results show that MIMO-SDM systems are robust against multiple independent tapping attacks, in the sense that the average achievable secrecy rate is strictly positive even with an infinite number of eavesdroppers. Though extremely difficult to implement in practice, if all the eavesdroppers could cooperate coherently, the average secrecy rate decreases quickly with the number of eavesdroppers. As such, to counter the colluding eavesdroppers, a combination of much higher SNR for the legitimate receiver and higher mode-dependent loss (MDL) for the eavesdroppers is needed.

In distributed storage systems, a special sub-class of locally repairable codes, referred to as availability codes, has been proposed to enable recovery of each data block from one of its repair groups. A repair group typically contains a small number of nodes and does not overlap with any other repair group of the same data block. Availability codes have several important benefits, including high degree of fault tolerance, efficient recovery from failures, and efficient access to data by multiple users. In this paper, we study the availability codes from a queuing-theoretical perspective. Specifically, we analyze the average time necessary to download a block of data under the Poisson request arrival model in two service/scheduling scenarios. We compare the availability codes with several alternatives such as MDS codes and replication schemes. Our results indicate that availability codes can minimize the download time in some settings, but are not always optimal.

We study a source-broadcasting problem involving an erasure broadcast channel with feedback. The receivers each require a certain fraction of a source sequence, and we are interested in the minimum latency, or transmission time, required to serve them all. We first show that for a two-user broadcast channel, a point-to-point outer bound can always be achieved. For broadcasting to three users, we propose a queue-based hybrid digital-analog coding scheme that achieves optimal performance for the duration of analog transmissions. We propose a method of characterizing the number of analog transmissions that can be sent, which involves solving a linear program, and furthermore give sufficient conditions for which all users can be optimal. In some cases, we find that users can be point-to-point optimal regardless of their distortion constraints. Finally, we propose a channel coding phase for when the analog transmissions are insufficient in meeting user demands and provide simulations that highlight the benefits of feedback.

Today's cloud storage services must offer storage reliability and fast data retrieval for large amount of data without sacrificing storage cost. We present SEARS, a cloud-based storage system which integrates erasure coding and data deduplication to support efficient and reliable data storage with fast user response time. With proper association of data to storage server clusters, SEARS provides flexible mixing of different configurations, suitable for real-time and archival applications. Our prototype implementation of SEARS over Amazon EC2 shows that it outperforms existing storage systems in storage efficiency and file retrieval time. For 3 MB files, SEARS delivers retrieval time of 2.5 s compared to 7 s with existing systems.

Space-division multiplexed (SDM) fiber optic transmission systems can not only increase system capacity, but also achieve physical-layer security against fiber tapping attacks. In this paper, we examine the information-theoretic security of optical multiple-input-multiple-output (MIMO) SDM by evaluating the tradeoff between the achievable information rate and the confidentiality for different channel dynamics. In particular, we provide problem formulations for secure communication over these channels and study three types of secrecy capacities: 1) guaranteed capacity; 2) outage capacity; and 3) average capacity, each serving as a performance metric for a coding strategy tailored to a specific type of MIMO-SDM channel. We also assess the impact of key system parameters, such as the number of modes, the mode-dependent loss (MDL), and the signal-to-noise ratio (SNR), on the various secrecy capacities. Our results indicate that, with a proper design of channel codes that balance information rate and security, an SDM system has the potential of offering confidential data transmission at a rate that could be orders of magnitude higher than what can be achieved through other means of encryption. Moreover, we show that MDL, unavoidably induced by fiber tapping, can allow information-theoretic security even if the SNR of the eavesdropper's receiver is better than that of the legitimate receiver.

We study a successive segmentation-based coding scheme for broadcasting a binary source over a multi-receiver erasure broadcast channel. Each receiver has a certain demand on the fraction of source symbols to be reconstructed, and its channel is a memoryless erasure channel. We study the minimum achievable latency at the source to simultaneously meet all the receiver constraints. We consider a class of schemes that partition the source sequence into multiple segments and apply a systematic erasure code to each segment. We formulate the optimal choice of segment sizes and code-rates in this class of schemes as a linear programming problem and provide an explicit solution.We further show that the optimal solution can be interpreted as a successive segmentation scheme that naturally adjusts when users are added or deleted from the system. Numerical plots indicate significant gains over a baseline separation-based coding scheme.

In the Adaptive Video Streaming (AVS), a server stores multiple video quality versions for each chunk in a video file, and a client takes decision which chunk quality to download in order to adapt to changing channel conditions. This paper presents a simple and effective algorithm for video quality selection and buffer control, which is based only on the current state of the client's playback buffer. The performance of the algorithm is analyzed regarding three important QoE measures and the tradeoff between them: 1) likelihood of play-out interruptions and video packet loss, 2) fraction of video watched in high quality, and 3) amount of fluctuations in video quality.

We study how coding in distributed storage reduces expected download time, in addition to providing reliability against disk failures. The expected download time is reduced because when a content file is encoded with redundancy and distributed across multiple disks, reading only a subset of the disks is sufficient for content reconstruction. For the same total storage used, coding exploits the diversity in storage better than simple replication, and hence gives faster download. We use a novel fork-join queueing framework to model multiple users requesting the content simultaneously, and derive bounds on the expected download time. Our system model and results are a novel generalization of the fork-join system that is studied in queueing theory literature. Our results demonstrate the fundamental trade-off between the expected download time and the amount of storage space. This trade-off can be used for design of the amount of redundancy required to meet the delay constraints on content delivery.

Optical networks are vulnerable to physical layer attacks; wiretappers can improperly receive messages intended for legitimate recipients. Multimode fiber (MMF) transmission can be modeled via a broadcast channel in which both the legitimate receiver's and wiretapper's channels are multiple-input-multiple-output complex Gaussian channels. This work considers the theoretical aspects of this security problem in the domain of a broadcast channel. Source-channel coding analyses based on the use of distortion as the metric for secrecy are developed. Alice has a source sequence to be encoded and transmitted over this broadcast channel so that the legitimate user Bob can reliably decode it while forcing the distortion of the wiretapper, or eavesdropper, Eve's estimate to be as high as possible. Tradeoffs between transmission rate and distortion under two extreme scenarios are examined: the best case where Eve has only her channel output and the worst case where she also knows the past realization of the source. It is shown that under the best case, an operationally separate source-channel coding scheme guarantees maximum distortion at the same rate as needed for reliable transmission. Theoretical bounds are given, and particularized for MMF. Numerical results showing the rate distortion tradeoff are presented and compared with corresponding results for the perfect secrecy case.

The paper considers the impact of changing code parameters on the network load, for some given storage-flexible Data Center Network (DCN), i.e. such DCN in which the reliability and the storage volume can be modified during the storage life of the DCN data. Two regimes of the network load are considered: transition (during the migration process) and stationary (at the end of the migration process). Our main result is the derivation of the link between reliability and network load via code parameters; clearly, this link is code-dependent. Two different erasure-coding families are considered as examples (MDS and LDPC codes), to illustrate the dependence in two different coding cases.

We analyze the download time of a large file, divided into chunks called generations, and transmitted over an erasure channel without feedback. For non-overlapping generations, we derive how the download time scales with the number of generations, for the round-robin and random scheduling policies. We then analyze coding with overlapping generations and show that the optimal overlap size is small compared to the number of generations, which implies that the download time can be reduced with only a small increase in computational complexity. Further, for a given overlap size, we propose overlap structures that have low complexity and are easy to implement, but still give file download as fast as the best previously proposed structures.

Information and coding theory have traditionally been used in point-to-point scenarios, to compute and achieve the transmission channel capacity as well as to compute and achieve the optimal compression rate vs. source distortion tradeoff. In today's networks, the same (video) data is often transmitted to multiple users, simultaneously over diverse channels. The users may differ not only in the size and resolution of their displays and computing power, but may also be interested in different video scenes, with different levels of distortion, or even with different distortion measures. This paper describes several transmission and compression problems that arise in such heterogeneous network scenarios, and discusses how information and coding theory could be used to address them.

We study a lossy source-broadcasting problem involving the transmission of a binary source over a two-receiver erasure broadcast channel. The motivation of our work stems from the problem faced by a server that wishes to singly broadcast content to a diverse set of users with fractional source reconstruction requirements. In this problem, the server wishes to minimize the overall network latency incurred (measured by the number of channel uses per source symbol) when faced with users of heterogeneous channel qualities, computing capabilities, content demand etc. We provide two complementary approaches to this problem. The first approach is to consider the problem from a joint source-channel coding formulation. Under this formulation, we provide both inner and outer bounds for the network latency under an erasure distortion criterion. Alternatively, the second approach employs rateless coding and formulates an optimization problem so as to find a degree distribution that minimizes the network latency. We compare both approaches with numerical simulations.

We propose an efficient application layer coding scheme suitable for time-limited wireless broadcast framework of the MBMS standards. The scheme, referred to as doped broadcast, is based on Fountain codes, and uses feedback to implement and control the tradeoff between the reconstruction delay, broadcast overhead, and decoding time/complexity. As the standardized schemes, our doped broadcast operates in two phases consisting of the limited time broadcast followed by an individualized repair phase in order to ensure (possibly prioritized) quality of service (QoS) to most users. The goal of the scheme is not to improve on any particular performance metric where highly optimized standard recommendations already perform exceptionally well, but rather to enable flexible and transparent mechanisms to implement and control tradeoff between different performance metrics. Toward this goal, we develop an analytically tractable model for doped broadcast with Ideal Soliton based codes leading to a repair strategy parameter estimation. The impact that inactivation and doping mechanisms employed by the decoder have on the complexity and overhead metrics is quantified and discussed for the proposed model. Hence, our approach guides a practical design tradeoff, which is important in today's highly heterogeneous environments requiring individualized QoS.

We study the problem of broadcasting a Gaussian source over a Gaussian broadcast channel to two users with individual source-channel bandwidth mismatches, under a quadratic distortion measure. Specifically we study the tradeoff between the achievable distortion pairs between the two users. The case when the bandwidth-expansion factors of the two users are identical has been well studied in the literature and to our best knowledge remains an open problem. Surprisingly, when the bandwidth expansion factors are different, we characterize a range of values where both the users simultaneously attain their point-to-point optimal distortion. Furthermore in the high signal-to-noise ratio regime, this set includes nearly all points where the weaker user has the higher bandwidth expansion factor. In other cases, we propose an achievable tradeoff between the distortion pairs.

We study incremental redundancy hybrid automatic repeat request (IR-HARQ) schemes based on punctured, finite-length, low-density, parity-check (LDPC) codes. The transmission is assumed to take place over time-varying binary erasure channels, such as mobile wireless channels at the application layer. We analyze and optimize the throughput and delay performance of these IR-HARQ protocols under iterative, message-passing decoding. We derive bounds on the performance that are achievable by such schemes, and show that, with a simple extension, the iteratively decoded, punctured LDPC code-based IR-HARQ protocol can be made rateless and operating close to the general theoretical optimum for a wide range of channel erasure rates.

This paper studies the throughput-delay performance tradeoff in large-scale wireless ad hoc networks. It has been shown that the per source-destination pair throughput can be improved from Θ(1/√{nlogn}) to Θ(1) if nodes are allowed to move and a two-hop relay scheme is employed. The price paid for such a throughput improvement is large delay. Indeed, the delay scaling of the two-hop relay scheme is Θ(nlogn) under the random walk mobility model. In this paper, coding techniques are used to improve the throughput-delay tradeoff for mobile wireless networks. For the random walk mobility model, the delay is reduced from Θ(nlogn) to Θ(n) by employing a maximum distance separable Reed-Solomon coding scheme. This coding approach maintains the diversity gained by mobility while decreasing the delay.

We consider the problem of securing a multicast network against a wiretapper that can eavesdrop on the packets on a limited number of network edges of its choice. We assume that the network employs network coding to simultaneously deliver the packets available at the source to all the destinations. We show that this problem can be looked at as a network generalization of the wiretap channel of type II introduced in a seminal paper by Ozarow and Wyner. In particular, we show that the transmitted information can be secured by using the Ozarow–Wyner approach of coset coding at the source on top of the existing network code. This way, we quickly and transparently recover some of the results available in the literature on secure network coding for wiretap networks. Moreover, we use this framework to derive new bounds on the code alphabet size that are independent of the network size, and provide algorithms for explicit construction of secure network codes. We also analyze the amount of information that can be leaked to the wiretapper as a function of the number of wiretapped edges.

We propose a compression/transmission scheme that allows the quality of the reconstructed signal to gracefully degrade as the channel quality drops, as well as steadily improve with the channel improvement. The main idea is to partition the channel and/or network resources into m units (e.g., sub-bands, packets) and compress the source independently m times to perfectly match single unit resources, thus creating m independently distorted source versions. Consequently, we create a multiple-description, joint source-channel like architecture, that enables efficient reconstruction starting from a single received description with improvements onward. We further split the compression rate in two parts, allocating one to a rate-distortion optimal encoder, and the other to transmitting uncoded source symbols. We show how this architecture can easily leverage modularity in terms of adjustable rate-splitting ratio and the maximum number of descriptions, e.g., through software parameters, to simultaneously and robustly (i.e. avoiding the cliff effect) achieve operating points close to rate-distortion curve for many channel states. We demonstrate how statistical description of channel states (or performance statistics of content delivery network) can be used to set the two parameters constructively in terms of converging to optimal operation in the range of interest.

This paper determines mechanisms for distributed storage that are simultaneously repair and update efficient. Repair efficiency demands that minimum information be downloaded from surviving nodes to reconstruct failed storage nodes. Update efficiency desires that changes in the original data require minimal updates at the storage nodes. These two requirements can be seen as counteracting one another, as the latter imposes a sparsity constraint on the encoding process that is not desirable for the former. In this paper we establish the existence of the codes that meet both requirements: require only logarithmic updates when data changes, while simultaneously minimizing repair bandwidth for exact reconstruction. To show this, we use a combination of KG codes for update efficiency with interference-alignment strategies for distributed storage.

To reduce computational complexity and delay in randomized network coded content distribution, and for some other practical reasons, coding is not performed simultaneously over all content blocks, but over much smaller, possibly overlapping subsets of these blocks, known as generations. A penalty of this strategy is throughput reduction. To analyze the throughput loss, we model coding over generations with random generation scheduling as a coupon collector's brotherhood problem. This model enables us to derive the expected number of coded packets needed for successful decoding of the entire content as well as the probability of decoding failure (the latter only when generations do not overlap) and further, to quantify the tradeoff between computational complexity and throughput. Interestingly, with a moderate increase in the generation size, throughput quickly approaches link capacity. Overlaps between generations can further improve throughput substantially for relatively small generation sizes.

To reduce computational complexity and delay in randomized network coded content distribution (and for some other practical reasons), coding is not performed simultaneously over all content blocks but over much smaller subsets known as generations. A penalty is throughput reduction. We model coding over generations as the coupon collector's brotherhood problem. This model enables us to theoretically compute the expected number of coded packets needed for successful decoding of the entire content, as well as a bound on the probability of decoding failure, and further, to quantify the tradeoff between computational complexity and throughput. Interestingly, with a moderate increase in the generation size, throughput quickly approaches link capacity. As an additional contribution, we derive new results for the generalized collector's brotherhood problem which can also be used for further study of many other aspects of coding over generations.

We consider the problem of distributing a file in a network of storage nodes whose storage budget is limited but at least equals the size file. We first generate T encoded symbols (from the file) which are then distributed among the nodes. We investigate the optimal allocation of T encoded packets to the storage nodes such that the probability of reconstructing the file by using any r out of n nodes is maximized. Since the optimal allocation of encoded packets is difficult to find in general, we find another objective function which well approximates the original problem and yet is easier to optimize. We find the optimal symmetric allocation for all coding redundancy constraints using the equivalent approximate problem. We also investigate the optimal allocation in random graphs. Finally, we provide simulations to verify the theoretical results.

We consider large-scale wireless sensor networks with n nodes, out of which k are in possession, (e.g., have sensed or collected in some other way) k information packets. In the scenarios in which network nodes are vulnerable because of, for example, limited energy or a hostile environment, it is desirable to disseminate the acquired information throughout the network so that each of the n nodes stores one (possibly coded) packet so that the original k source packets can be recovered, locally and in a computationally simple way from any k(1 + ¿) nodes for some small ¿ > 0. We develop decentralized Fountain codes based algorithms to solve this problem. Unlike all previously developed schemes, our algorithms are truly distributed, that is, nodes do not know n, k or connectivity in the network, except in their own neighborhoods, and they do not maintain any routing tables.

We study the throughput-delay performance trade-off in large-scale wireless ad hoc networks. It has been shown that the per source-destination pair throughput can be improved from Θ(1/√n log n) to Θ(1) if nodes are allowed to move and a 2-hop relay scheme is employed. The price paid for such an improvement on throughput is large delay. Indeed, the delay scaling of the 2-hop relay scheme is Θ(n log n) under the random walk mobility model. In this paper, we employ coding techniques to improve the throughput-delay trade-off for mobile wireless networks. For the random walk mobility model, we improve the delay from Θ(n log n) to Θ(n) by employing Reed-Solomon (RS) codes. Our approach maintains the diversity gained by mobility while decreasing the delay.

This paper studies decentralized, Fountain and network-coding based strategies for facilitating data collection in circular wireless sensor networks, which rely on the stochastic diversity of data storage. The goal is to allow for a reduced delay collection by a data collector who accesses the network at a random position and random time. Data dissemination is performed by a set of relays which form a circular route to exchange source packets. The storage nodes within the transmission range of the route's relays linearly combine and store overheard relay transmissions using random decentralized strategies. An intelligent data collector first collects a minimum set of coded packets from a subset of storage nodes in its proximity, which might be sufficient for recovering the original packets and, by using a message-passing decoder, attempts recovering all original source packets from this set. Whenever the decoder stalls, the source packet which restarts decoding is polled/doped from its original source node. The random-walk-based analysis of the decoding/doping process furnishes the collection delay analysis with a prediction on the number of required doped packets. The number of doped packets can be surprisingly small when employed with an Ideal Soliton code degree distribution and, hence, the doping strategy may have the least collection delay when the density of source nodes is sufficiently large. Furthermore, we demonstrate that network coding makes dissemination more efficient at the expense of a larger collection delay. Not surprisingly, a circular network allows for a significantly more (analytically and otherwise) tractable strategies relative to a network whose model is a random geometric graph.

We consider large-scale networks with n nodes, out of which k are in possession, (e.g., have sensed or collected in some other way) k information packets. In the scenarios in which network nodes are vulnerable because of, for example, limited energy or a hostile environment, it is desirable to disseminate the acquired information throughout the network so that each of the n nodes stores one (possibly coded) packet and the original k source packets can be recovered later in a computationally simple way from any (1 + isin)k nodes for some small isin > 0. We developed two distributed algorithms for solving this problem based on simple random walks and Fountain codes. Unlike all previously developed schemes, our solution is truly distributed, that is, nodes do not know n, k or connectivity in the network, except in their own neighborhoods, and they do not maintain any routing tables. In the first algorithm, all the sensors have the knowledge of n and k. In the second algorithm, each sensor estimates these parameters through the random walk dissemination. We present analysis of the communication/transmission and encoding/decoding complexity of these two algorithms, and provide extensive simulation results as well.

We consider a distributed storage problem in a large-scale wireless sensor network with n nodes among which k acquire (sense) independent data. The goal is to disseminate the acquired information throughout the network so that each of the n sensors stores one possibly coded packet and the original k data packets can be recovered later in a computationally simple way from any (1 + ∈)k of nodes for some small ∈ ≫ 0. We propose two Raptor codes based distributed storage algorithms for solving this problem. In the first algorithm, all the sensors have the knowledge of n and k. In the second one, we assume that no sensor has such global information.

This paper studies the secrecy capacity of unicast communication in a wireless erasure network setting in the presence of a wire-tapper. From an information-theoretic setting of perfect secrecy, both upper bounds and achievable secrecy rates are presented. Secrecy capacity is determined in closed form for a class of broadcast constrained erasure networks.

We study anincremental redundancy(IR) cooperative coding scheme for wireless networks. To exploit the distributed spatial diversity we propose a cluster-based collaborating strategy for a quasi-static Rayleigh-fading channel model. Our scheme allows for enhancing the reliability performance of a direct communication over a single hop. The collaborative cluster consists of$M-1$nodes between the sender and the destination. The transmitted message is encoded using a mother code which is partitioned into$M$blocks each assigned to one of$M$transmission slots. In the first slot, the sender broadcasts its information by transmitting the first block, and its helpers attempt to decode this message. In the remaining slots, each of the next$M-1$blocks is sent either through a helper which has successfully decoded the message or directly by the sender where a dynamic schedule is based on the ACK-based feedback from the cluster. By employing powerfulgood codesincluding turbo, low-density parity-check (LDPC), and repeat–accumulate (RA) codes, our approach illustrates the benefit of collaboration through not only a cooperation diversity gain but also a coding advantage. The basis of our error rate performance analysis is based on a derived code threshold for the Bhattacharyya distance which describes the behavior of good codes. The new simple code threshold is based on the modified Shulman–Feder bound and the relationship between the Bhattacharyya parameter and the channel capacity for an arbitrary binary-input symmetric-output memoryless channel. An average frame-error rate (FER) upper bound and its asymptotic (in signal-to-noise ratio (SNR)) version are derived as a function of the average fading channel SNRs and the code threshold. Based on the asymptotic bound, we investigate both the diversity, the coding, and the transmission energy gain in the high and moderate SNR regimes for three different scenarios: transmitter clustering, receiver clustering, and cluster hopping. We observe that the energy saving of the IR cooperative coding scheme isuniversalfor all good code families in the sense that the gain does not depend on the sender-to-destination distance and the code threshold.

Let Aq(n, d) be the maximum order (maximum number of codewords) of a q-ary code of length n and Hamming distance at least d. And let A(n, d, w) that of a binary code of constant weight w. Building on results from algebraic graph theory and Erdos-ko-Rado like theorems in extremal combinatorics, we show how several known bounds on Aq(n,d) and A(n,d, w) can be easily obtained in a single framework. For instance, both the Hamming and Singleton bounds can derived as an application of a property relating the clique number and the independence number of vertex transitive graphs. Using the same techniques, we also derive some new bounds and present some additional applications.

We consider the problem of securing a multicast network against a wiretapper that can intercept the packets on a limited number of arbitrary network links of his choice. We assume that the network implements network coding techniques to simultaneously deliver all the packets available at the source to all the destinations. We show how this problem can be looked at as a network generalization of the Ozarow-Wyner wiretap channel of type II. In particular, we show that network security can be achieved by using the Ozarow-Wyner approach of coset coding at the source on top of the implemented network code. This way, we quickly and transparently recover some of the results available in the literature on secure network coding for wiretapped networks. We also derive new bounds on the required secure code alphabet size and an algorithm for code construction.

Hybrid ARQ transmission schemes combine the conventional ARQ with forward error correction. Incremental redundancy hybrid ARQ schemes adapt their error correcting code redundancy to varying channel gains, and thus achieve better throughput performance than ordinary ARQ, particularly over wireless channels with fluctuating channel conditions. Consequently, the scheme has been adopted by a number of standards for mobile phone networks. We provide a brief survey of theory and state of the art of hybrid ARQ, and present some possible future directions keeping in mind practical considerations.

We evaluate the asymptotic normalized average distributions of a class of combinatorial configurations in random, regular and irregular, binary low-density parity-check (LDPC) code ensembles. Among the configurations considered are trapping and stopping sets. These sets represent subsets of variable nodes in the Tanner graph of a code that play an important role in determining the height and point of onset of the error-floor in its performance curve. The techniques used for deriving the spectra include large deviations theory and statistical methods for enumerating binary matrices with prescribed row and column sums. These techniques can also be applied in a setting that involves more general structural entities such as subcodes and/or minimal codewords, that are known to characterize other important properties of soft-decision decoders of linear block codes

Trapping sets represent subgraphs in the Tanner graph of a code that, for certain classes of channels, exhibit a strong influence on the height and point of onset of the error-floor. We compute the asymptotic normalized distributions of trapping sets in random, irregular, binary low-density parity-check (LDPC) code ensembles. Our derivations rely on techniques from large deviation theory and statistical methods for enumeracting random-like matrices. Similar methods can be used for computing the spectra of other combinatorial entities in LDPC code, such as subcodes and/or minimal codewords.

A non-uniform demand network consists of a source and a set of receivers that have different min-cut values from the source. We look at the case where each receiver would like to receive information from the source at a rate that is equal to its min-cut value. This problem has been formulated before, and in contrast to the uniform case, it has been shown that the non-uniform case does not admit a good characterization. Motivated by this, we formulate relaxations of the problem and present some preliminary results

Two incremental redundancy hybrid ARQ (IR-HARQ) schemes are compared: one is based on LDPC code ensembles with random transmission assignments, the other is based on recently introduced Raptor codes. A number of important issues, such as rate and power control, and error rate performance after each transmission on time varying binary-input, symmetric-output channels are addressed by analyzing performance of LDPC and Raptor codes on parallel channels. The theoretical results obtained for random code ensembles are tested on several practical code examples by simulation. Both theoretical and simulation results show that both LDPC and Raptor codes are suitable for HARQ schemes. Which codes would make a better choice depends mainly on the width of the signal-to-noise operating range of the HARQ scheme, prior knowledge of that range, and other design parameters and constraints dictated by standards.

We examine the throughput benefits that network coding offers with respect to the average throughput achievable by routing, where the average throughput refers to the average of the rates that the individual receivers experience. We relate these benefits to the integrality gap of a standard linear programming formulation for the directed Steiner tree problem. We describe families of configurations over which network coding at most doubles the average throughput, and analyze a class of directed graph configurations with N receivers where network coding offers benefits proportional to /spl radic/N. We also discuss other throughput measures in networks, and show how in certain classes of networks, average throughput bounds can be translated into minimum throughput bounds, by employing vector routing and channel coding. Finally, we show configurations where use of randomized coding may require an alphabet size exponentially larger than the minimum alphabet size required.

We propose a method to identify structural properties of multicast network configurations, by decomposing networks into regions through which the same information flows. This decomposition allows us to show that very different networks are equivalent from a coding point of view, and offers a means to identify such equivalence classes. It also allows us to divide the network coding problem into two almost independent tasks: one of graph theory and the other of classical channel coding theory. This approach to network coding enables us to derive the smallest code alphabet size sufficient to code any network configuration with two sources as a function of the number of receivers in the network. But perhaps the most significant strength of our approach concerns future network coding practice. Namely, we propose deterministic algorithms to specify the coding operations at network nodes without the knowledge of the overall network topology. Such decentralized designs facilitate the construction of codes that can easily accommodate future changes in the network, e.g., addition of receivers and loss of links

We study the average error probability performance of binary linear code ensembles when each codeword is divided into J subcodewords with each being transmitted over one of J parallel channels. This model is widely accepted for a number of important practical channels and signaling schemes including block-fading channels, incremental redundancy retransmission schemes, and multicarrier communication techniques for frequency-selective channels. Our focus is on ensembles of good codes whose performance in a single channel model is characterized by a threshold behavior, e.g., turbo and low-density parity-check (LDPC) codes. For a given good code ensemble, we investigate reliable channel regions which ensure reliable communications over parallel channels under maximum-likelihood (ML) decoding. To construct reliable regions, we study a modifed 1961 Gallager bound for parallel channels. By allowing codeword bits to be randomly assigned to each component channel, the average parallel-channel Gallager bound is simplified to be a function of code weight enumerators and channel assignment rates. Special cases of this bound, average union-Bhattacharyya (UB), Shulman-Feder (SF), simplified-sphere (SS), and modified Shulman-Feder (MSF) parallel-channel bounds, allow for describing reliable channel regions using simple functions of channel and code spectrum parameters. Parameters describing the channel are the average parallel-channel Bhattacharyya noise parameter, the average channel mutual information, and parallel Gaussian channel signal-to-noise ratios (SNRs). Code parameters include the union-Bhattacharyya noise threshold and the weight spectrum distance to the random binary code ensemble. Reliable channel regions of repeat-accumulate (RA) codes for parallel binary erasure channels (BECs) and of turbo codes for parallel additive white Gaussian noise (AWGN) channels are numerically computed and compared with simulation results based on iterative decoding. In addition, an examp

We examine the throughput benefits that network coding offers with respect to the average through- put achievable by routing, where the average throughput refers to the average of the rates that the indi- vidual receivers experience. We relate these benefits to the integrality gap of a standard LP formulation for the directed Steiner tree problem. We describe families of configurations over which network coding at most doubles the average throughput, and analyze a class of directed graph configurations with N receivers where network coding offers benefits proportional to √N. We also discuss other throughput measures in networks, and show how in certain classes of networks, the average throughput can be achieved uniformly by all receivers by employing vector routing and channel coding. Finally, we show configurations where use of randomized coding may require an alphabet size exponentially larger than the minimum alphabet size required.

An LDPC code based hybrid ARQ scheme with random transmission assignments is analyzed. The spectrum properties of LDPC code ensembles that are necessary for this analysis are derived. Very good estimates of maximum-likelihood decoding error rates after each transmission are provided. The results are tested on practical code examples by simulation

The weight spectrum of sequences of binary linear codes that achieve arbitrarily small word error probability on a class of noisy channels at a nonzero rate is studied. We refer to such sequences as good codes. The class of good codes includes turbo, low-density parity-check, and repeat-accumulate codes. We show that a sequence of codes is good when transmitted over a memoryless binary-symmetric channel (BSC) or an additive white Gaussian noise (AWGN) channel if and only if the slope of its spectrum is finite everywhere and its minimum Hamming distance goes to infinity with no requirement on its rate growth. The extension of these results to code ensembles in probabilistic terms follows in a direct manner. We also show that the sufficient condition holds for any binary-input memoryless channel.

The min-cut, max-flow theorem states that a source node can send a commodity through a network to a sink node at the rate determined by the flow of the min-cut separating the source and the sink. Recently it has been shown that by linear re-encoding at nodes in communication networks, the min-cut rate can be also achieved in multicasting to several sinks. In this paper we discuss connections between such coding schemes and convolutional codes. We propose a method to simplify the convolutional encoder design that is based on a subtree decomposition of the network line graph, describe the structure of the associated matrices, investigate methods to reduce decoding complexity and discuss possible binary implementation.

A subtree decomposition method for network coding is proposed in this paper. This approach enables derivation of tight bounds on the network code alphabet size, makes connections with convolutional codes transparent, allows specification of coding operations at network nodes without the knowledge of the overall network topology, and facilitates design of codes which can easily accommodate future changes in the network, such as addition of receivers and loss of links.

This paper describes a given ensemble of good binary codes and a codeword-symbol with channel assignment rule and error probability performance. The reliable channel regions based on the parallel-channel Gallager bound achieves all functions of the code weight enumerators, parallel-channel transition probabilities, and the channel assignment rates. The channel model consists of parallel binary-input symmetric-output (BISO) discrete memoryless channels. The uniform codeword partition and decoded iteratively of a reliable channel regions for good codes transmitted over parallel channels is studied.

This paper proposes deterministic algorithms for decentralized network coding. Decentralized coding allows us to locally specify the coding operations at network nodes without knowledge of the overall network topology, and to accommodate future changes in the network such as addition of receivers. To the best of our knowledge, these are the first deterministic decentralized algorithms proposed for network coding.

In multi-hop networks, messages are traditionally relayed over a set of sequential point-to-point communication links. An overheard message is typically discarded since the noisy packet is below the detection threshold. However, an overheard packet still contains useful information about the original message, and its consideration can improve the energy efficiency of a transmission scheme. Hence, we study an incremental redundancy multi-hop transmission scheme which enhances the overheard information hop-by-hop. The j-th sequential node combines the previously (over)heard hop transmissions which together form a codeword of a "good" code of rate sufficient for reliable decoding. The analysis of punctured codes whose symbols are distributed over a number of hops is based on a random hop assignment technique. This technique allows for a performance threshold behavior description as a function of the hop rates and a derivation of the asymptotic (as the number of relays goes to infinity) reliable hop rate threshold as a function of channel and mother code parameters. The significant energy savings of the cooperative transmission relative to schemes that discard overheard packets are a function of only the channel parameters.

We analyze the asymptotic performance of punctured turbo codes. The analysis is based on the union bound on the word error probability of maximum likelihood decoding for punctured turbo code ensembles averaged over all possible puncturing patterns and interleavers. By using special probabilistic puncturing, we prove that, for a given mother turbo code ensemble, [C], with a finite noise threshold, c/sub 0//sup [C]/, if the asymptotic puncturing turing rate, /spl lambda/, satisfies log /spl lambda/ < -c/sub 0//sup [C]/, there exists a finite noise threshold, c/sub 0//sup [Cp]/, for the punctured turbo code ensemble which is bounded by a function of c/sub 0//sup [C]/ and /spl lambda/. Based on this result, we prove that, on any binary-input memoryless channel whose Bhattacharyya noise distance is greater than c/sub 0//sup [Cp]/, the average ML decoding word error probability of the punctured turbo code ensemble approaches zero at least as fast as n/sup -/spl beta//, where /spl beta/ is the well known "interleaver gain" exponent. This enables us to answer an important question in the practice of HARQ (hybrid ARQ) schemes, namely, up to which puncturing rate "good" turbo codes give rise to "good" punctured codes.

Color descriptors are among the most important features used in image analysis and retrieval. Due to its compact representation and low complexity, direct histogram comparison is a commonly used technique for measuring the color similarity. However, it has many serious drawbacks, including a high degree of dependency on color codebook design, sensitivity to quantization boundaries, and inefficiency in representing images with few dominant colors. In this paper, we present a new algorithm for color matching that models behavior of the human visual system in capturing color appearance of an image. We first develop a new method for color codebook design in the Lab space. The method is well suited for creating small fixed color codebooks; for image analysis, matching, and retrieval. Then we introduce a statistical technique to extract perceptually relevant colors. We also propose a new color distance measure that is based on the optimal mapping between two sets of color components representing two images. Experiments comparing the new algorithm to some existing techniques show that these novel elements lead to better match to human perception in judging image similarity in terms of color composition.

The problem of arranging two-dimensional arrays of data into one-dimensional sequences comes up in image processing, color quantization, and optical and magnetic data recording. A good arrangement should enable the one-dimensional sequences to be modeled as Markov chains or shifts of finite type. Since this is not possible in general, two-dimensional data is most commonly scanned by rows, columns, or diagonals. We look into three unusual ways to write a sequence,in the plane: by Penrose tilings, by space-filling curves, and by cylindrical and spiral lattices. We show how Penrose tilings can be used to record information and how some spiral lattices can be used for quantization of color spaces.

We consider visible compression for discrete memoryless sources of mixed quantum states when only classical information can be sent from Alice to Bob. We assume that Bob knows the source statistics, and that Alice and Bob have access to the same source of random numbers. We put in an information-theoretic framework some previous results on visible compression for sources of states with commuting density operators, and remove the commutativity requirement. We derive a general achievable compression rate, which is for the noncommutative case still higher than the known lower bound. We also present several related problems of classical information theory, and show how they can be used to answer some questions of the mixed-state compression problem.

We present advanced combinatorial techniques for constructing maximum runlength-limited (RLL) block codes and maximum transition run (MTR) codes. These codes find widespread application in recording systems. The proposed techniques are used to construct a high-rate multipurpose modulation code for recording systems. The code, a rate 16/17, (0,3,2,2) MTR code, that also fulfills (0,15,9,9) RLL constraints is a high-rate distance-enhancing code with additional constraints for improving timing and gain control. The encoder and decoder have a particularly efficient architecture and allow an instantaneous translation of 16-bit source words into 17-bit codewords and vice versa. The code has been implemented in Lucent read-channel chips and has excellent performance.

Color quantization is sampling of three-dimensional (3-D) color spaces (such as RGB or Lab) which results in a discrete subset of colors known as a color codebook or palette. It is extensively used for display, transfer, and storage of natural images in Internet-based applications, computer graphics, and animation. We propose a sampling scheme which provides a uniform quantization of the Lab space. The idea is based on several results from number theory and phyllotaxy. The sampling algorithm is very much systematic and allows easy design of universal (image-independent) color codebooks for a given set of parameters. The codebook structure allows fast quantization and ordered dither of color images. The display quality of images quantized by the proposed color codebooks is comparable with that of image-dependent quantizers. Most importantly, the quantized images are more amenable to the type of processing used for grayscale ones. Methods for processing grayscale images cannot be simply extended to color images because they rely on the fact that each gray-level is described by a single number and the fact that a relation of full order can be easily established on the set of those numbers. Color spaces (such as RGB or Lab) are, on the other hand, 3-D. The proposed color quantization, i.e., color space sampling and numbering of sampled points, makes methods for processing grayscale images extendible to color images. We illustrate possible processing of color images by first introducing the basic average and difference operations and then implementing edge detection and compression of color quantized images.

Partial-response (PR) signaling is used to model communications channels with intersymbol interference (ISI) such as the magnetic recording channel and the copper-wire channel for digital subscriber lines. Coding for improving noise immunity in higher order partial-response channels, such as the "extended" class-4 channels denoted EPR4, E/sup 2/PR4, E/sup 3/PR4, has become an important subject as the linear densities in magnetic recording approach those at which these partial-response channels are the best models of real channels. In this paper, we consider partial-response channels for which ISI is so severe that the channels fail to achieve the matched-filter bound (MFB) for symbol error rate, assuming maximum-likelihood decoding. We show that their performance can be improved to the MFB by high-rate codes based on constrained systems, some of which may even simplify the Viterbi (1979) detectors relative to the uncoded channels. We present several examples of high-rate constrained codes for E/sup 2/PR4 and E/sup 3/PR4 channels and evaluate their performance by simulation.

We look at multiple-track detection for magnetic recording systems that use array heads to write and read over multiple tracks simultaneously. The recording channel is modeled as having intersymbol interference (ISI) in the axial direction, and intertrack interference (ITI) in the radial direction. Optimum multihead and single-head detectors are derived and analyzed in terms of error-probability performance for various levels of intertrack interference. Among other results, it is seen that for a range of ITI levels, codes designed to increase distance in single-head systems can provide the same coding gains for multihead systems.

A previously proposed coding scheme (Soljanin 1997) for generating bipolar dc-free sequences allowed construction of several new dc-free codes with lower encoding complexity than the existing codes with comparable rates. We here discuss decoding of the new codes on a 1-D/sup 2/ partial response channel (PR4), and test the performance of the optimal and various suboptimal detectors by simulation. In particular, we show how the special codeword structure of the newly constructed codes can be advantageously used to reduce the decoding complexity.

A reduction in the track width in disc-recording systems results in a desirable increase in areal density, but also in the undesirable appearance of inter-track interference (ITI) and loss of signal-to-noise ratio (SNR). One way the effects of ITI may be alleviated is through the use of multiple-head systems simultaneously writing and reading a number of adjacent tracks. In this paper we investigate the performance of two-track detectors, and design codes that combat two-dimensional interference patterns, ISI in the axial dimension, and ITI in the radial dimension, and recover the loss in SNR due to track-narrowing. Sliding-block decoders and reduced-complexity Viterbi detectors are also designed for these codes, which are seen to more than compensate for the performance loss for a large range of ITI levels.>