We study the problem of storing a data object in a set of data nodes that
fail independently with given probabilities. Our problem is a natural
generalization of a homogenous storage allocation problem where all the nodes
had the same reliability and is naturally motivated for peer-to-peer and cloud
storage systems with different types of nodes. Assuming optimal erasure coding
(MDS), the goal is to find a storage allocation (i.e, how much to store in each
node) to maximize the probability of successful recovery. This problem turns
out to be a challenging combinatorial optimization problem.
We suggest a novel approach to handle the ongoing explosive increase in the
demand for video content in wireless/mobile devices. We envision femtocell-like
base stations, which we call helpers, with weak backhaul links but large
storage capacity. These helpers form a wireless distributed caching network
that assists the macro base station by handling requests of popular files that
have been cached. Due to the short distances between helpers and requesting
devices, the transmission of cached files can be done very efficiently.
We examine the problem of creating an encoded distributed storage
representation of a data object for a network of mobile storage nodes so as to
achieve the optimal recovery delay. A source node creates a single data object
and disseminates an encoded representation of it to other nodes for storage,
subject to a given total storage budget. A data collector node subsequently
attempts to recover the original data object by contacting other nodes and
accessing the data stored in them.
In distributed storage systems that employ erasure coding, the issue of
minimizing the total {\it repair bandwidth} required to exactly regenerate a
storage node after a failure arises. This repair bandwidth depends on the
structure of the storage code and the repair strategies used to restore the
lost data.
We present a mathematical connection between channel coding and compressed
sensing. In particular, we link, on the one hand, \emph{channel coding linear
programming decoding (CC-LPD)}, which is a well-known relaxation of
maximum-likelihood channel decoding for binary linear codes, and, on the other
hand, \emph{compressed sensing linear programming decoding (CS-LPD)}, also
known as basis pursuit, which is a widely used linear programming relaxation
for the problem of finding the sparsest solution of an under-determined system
of linear equations.
In distributed storage systems that use coding, the issue of minimizing the
communication required to rebuild a storage node after a failure arises. We
consider the problem of repairing an erased node in a distributed storage
system that uses an EVENODD code. EVENODD codes are maximum distance separable
(MDS) array codes that are used to protect against erasures, and only require
XOR operations for encoding and decoding. We show that when there are two
redundancy nodes, to rebuild one erased systematic node, only 3/4 of the
information needs to be transmitted.
We consider the problem of optimally allocating a given total storage budget
in a distributed storage system. A source has a data object which it can code
and store over a set of storage nodes; it is allowed to store any amount of
coded data in each node, as long as the total amount of storage used does not
exceed the given budget. A data collector subsequently attempts to recover the
original data object by accessing each of the nodes independently with some
constant probability.
We investigate the problem of allocating energy from renewable sources to
flexible consumers in electricity markets. We assume there is a renewable
energy supplier that provides energy according to a time-varying (and possibly
unpredictable) supply process. The plant must serve consumers within a
specified delay window, and incurs a cost of drawing energy from other
(possibly non-renewable) sources if its own supply is not sufficient to meet
the deadlines.
Distributed storage systems often introduce redundancy to increase
reliability. When coding is used, the repair problem arises: if a node storing
encoded information fails, in order to maintain the same level of reliability
we need to create encoded information at a new node. This amounts to a partial
recovery of the code, whereas conventional erasure coding focuses on the
complete recovery of the information from a subset of encoded packets. The
consideration of the repair network traffic gives rise to new design
challenges.
Gossip algorithms are attractive for in-network processing in sensor networks
because they do not require any specialized routing, there is no bottleneck or
single point of failure, and they are robust to unreliable wireless network
conditions. Recently, there has been a surge of activity in the computer
science, control, signal processing, and information theory communities,
developing faster and more robust gossip algorithms and deriving theoretical
performance guarantees. This article presents an overview of recent work in the
area.
We analyze a simple network where a source and a receiver are connected by a
line of erasure channels of different reliabilities. Recent prior work has
shown that random linear network coding can achieve the min-cut capacity and
therefore the asymptotic rate is determined by the worst link of the line
network. In this paper we investigate the delay for transmitting a batch of
packets, which is a function of all the erasure probabilities and the number of
packets in the batch.
Regenerating codes allow distributed storage systems to recover from the loss
of a storage node while transmitting the minimum possible amount of data across
the network. We present a systematic computer search for optimal systematic
regenerating codes. To search the space of potential codes, we reduce the
potential search space in several ways. We impose an additional symmetry
condition on codes that we consider.
Regenerating codes allow distributed storage systems to recover from the loss
of a storage node while transmitting the minimum possible amount of data across
the network. We present a systematic computer search for optimal systematic
regenerating codes. To search the space of potential codes, we reduce the
potential search space in several ways. We impose an additional symmetry
condition on codes that we consider.
In this paper we study a Markov Chain Monte Carlo (MCMC) Gibbs sampler for
solving the integer least-squares problem. In digital communication the problem
is equivalent to performing Maximum Likelihood (ML) detection in Multiple-Input
Multiple-Output (MIMO) systems. While the use of MCMC methods for such problems
has already been proposed, our method is novel in that we optimize the
"temperature" parameter so that in steady state, i.e. after the Markov chain
has mixed, there is only polynomially (rather than exponentially) small
probability of encountering the optimal solution.
In this paper we study a Markov Chain Monte Carlo (MCMC) Gibbs sampler for
solving the integer least-squares problem. In digital communication the problem
is equivalent to performing Maximum Likelihood (ML) detection in Multiple-Input
Multiple-Output (MIMO) systems. While the use of MCMC methods for such problems
has already been proposed, our method is novel in that we optimize the
"temperature" parameter so that in steady state, i.e. after the Markov chain
has mixed, there is only polynomially (rather than exponentially) small
probability of encountering the optimal solution.
This is a tale of two linear programming decoders, namely channel coding
linear programming decoding (CC-LPD) and compressed sensing linear programming
decoding (CS-LPD). So far, they have evolved quite independently. The aim of
the present paper is to show that there is a tight connection between, on the
one hand, CS-LPD based on a zero-one measurement matrix over the reals and, on
the other hand, CC-LPD of the binary linear code that is obtained by viewing
this measurement matrix as a binary parity-check matrix.
This is a tale of two linear programming decoders, namely channel coding
linear programming decoding (CC-LPD) and compressed sensing linear programming
decoding (CS-LPD). So far, they have evolved quite independently. The aim of
the present paper is to show that there is a tight connection between, on the
one hand, CS-LPD based on a zero-one measurement matrix over the reals and, on
the other hand, CC-LPD of the binary linear code that is obtained by viewing
this measurement matrix as a binary parity-check matrix.