Alexandros G. Dimakis

  1. Allocations for Heterogenous Distributed Storage.

    Authors: Giuseppe Caire, Alexandros G. Dimakis, Vasileios Ntranos
    Subjects: Information Theory
    Abstract

    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.

  2. FemtoCaching: Wireless Video Content Delivery through Distributed Caching Helpers.

    Authors: Andreas F. Molisch, Giuseppe Caire, Alexandros G. Dimakis, Negin Golrezaei, Karthikeyan Shanmugam
    Subjects: Networking and Internet Architecture
    Abstract

    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.

  3. Distributed Storage Allocations for Optimal Delay.

    Authors: Alexandros G. Dimakis, Tracey Ho, Derek Leong
    Subjects: Information Theory
    Abstract

    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.

  4. Distributed Storage Codes through Hadamard Designs.

    Authors: Alexandros G. Dimakis, Dimitris S. Papailiopoulos
    Subjects: Information Theory
    Abstract

    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.

  5. LDPC Codes for Compressed Sensing.

    Authors: Roxana Smarandache, Alexandros G. Dimakis, Pascal O. Vontobel
    Subjects: Information Theory
    Abstract

    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.

  6. Rebuilding for Array Codes in Distributed Storage Systems.

    Authors: Alexandros G. Dimakis, Jehoshua Bruck, Zhiying Wang
    Subjects: Information Theory
    Abstract

    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.

  7. Symmetric Allocations for Distributed Storage.

    Authors: Alexandros G. Dimakis, Tracey Ho, Derek Leong
    Subjects: Information Theory
    Abstract

    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.

  8. Efficient Algorithms for Renewable Energy Allocation to Delay Tolerant Consumers.

    Authors: Michael J. Neely, Alexandros G. Dimakis, Arash Saber Tehrani
    Subjects: Optimization and Control
    Abstract

    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.

  9. A Survey on Network Codes for Distributed Storage.

    Authors: Kannan Ramchandran, Alexandros G. Dimakis, Yunnan Wu, Changho Suh
    Subjects: Information Theory
    Abstract

    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.

  10. Gossip Algorithms for Distributed Signal Processing.

    Authors: Alexandros G. Dimakis, Soummya Kar, Michael G. Rabbat, Jose M.F. Moura, Anna Scaglione
    Subjects: and Cluster Computing, Distributed, Parallel
    Abstract

    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.

  11. On the Delay of Network Coding over Line Networks.

    Authors: Alexandros G. Dimakis, Tracey Ho, Theodoros K. Dikaliotis, Michelle Effros
    Subjects: Information Theory
    Abstract

    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.

  12. Searching for Minimum Storage Regenerating Codes.

    Authors: Alexandros G. Dimakis, Daniel Cullina, Tracey Ho
    Subjects: Information Theory
    Abstract

    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.

  13. Searching for Minimum Storage Regenerating Codes.

    Authors: Alexandros G. Dimakis, Daniel Cullina, Tracey Ho
    Subjects: Information Theory
    Abstract

    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.

  14. Near-Optimal Detection in MIMO Systems using Gibbs Sampling.

    Authors: Babak Hassibi, Alexandros G. Dimakis, Morten Hansen, Weiyu Xu
    Subjects: Information Theory
    Abstract

    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.

  15. Near-Optimal Detection in MIMO Systems using Gibbs Sampling.

    Authors: Babak Hassibi, Alexandros G. Dimakis, Morten Hansen, Weiyu Xu
    Subjects: Information Theory
    Abstract

    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.

  16. LP Decoding meets LP Decoding: A Connection between Channel Coding and Compressed Sensing.

    Authors: Alexandros G. Dimakis, Pascal O. Vontobel
    Subjects: Information Theory
    Abstract

    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.

  17. LP Decoding meets LP Decoding: A Connection between Channel Coding and Compressed Sensing.

    Authors: Alexandros G. Dimakis, Pascal O. Vontobel
    Subjects: Information Theory
    Abstract

    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.

Syndicate content