Coding and Message-Passing for Large-Scale Storage and Inference

Georgios Alexandros Dimakis

EECS Department
University of California, Berkeley
Technical Report No. UCB/EECS-2008-153
December 10, 2008

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2008/EECS-2008-153.pdf

Recent advances in technology have catalyzed a paradigm shift away from centralized schemes and in the direction of distributed and cooperative architectures for large-scale systems. In applications like data centers, sensor networks, and peer-to-peer networks, coding is used to introduce redundancy for robustness. We develop and analyze novel coding constructions for distributed storage applications. We also present information theoretic performance bounds and explicit network codes that achieve optimal performance. For the case of large-scale distributed processing, we introduce new message-passing schemes and show explicit results on convergence rate. In particular, we introduce geographic gossip, an algorithm that can compute linear functions of data in a network, requiring a number of messages that scales optimally in the number of nodes for a large class of graphs.

Advisor: Kannan Ramchandran and Martin Wainwright


BibTeX citation:

@phdthesis{Dimakis:EECS-2008-153,
    Author = {Dimakis, Georgios Alexandros},
    Title = {Coding and Message-Passing for Large-Scale Storage and Inference},
    School = {EECS Department, University of California, Berkeley},
    Year = {2008},
    Month = {Dec},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2008/EECS-2008-153.html},
    Number = {UCB/EECS-2008-153},
    Abstract = {Recent advances in technology have catalyzed a paradigm shift away from centralized schemes and in the direction of distributed and cooperative architectures for large-scale systems. In applications like data centers, sensor networks, and peer-to-peer networks, coding is used to introduce redundancy for robustness. We develop and analyze novel coding constructions for distributed storage applications. We also present information theoretic performance bounds and explicit network codes that 
achieve optimal performance. For the case of large-scale distributed processing, we introduce new message-passing schemes and show explicit results on convergence rate. In particular, we introduce geographic gossip, an algorithm that can compute linear functions of data in a network, requiring a number of messages that scales optimally in the number of nodes for a large class of graphs.}
}

EndNote citation:

%0 Thesis
%A Dimakis, Georgios Alexandros
%T Coding and Message-Passing for Large-Scale Storage and Inference
%I EECS Department, University of California, Berkeley
%D 2008
%8 December 10
%@ UCB/EECS-2008-153
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2008/EECS-2008-153.html
%F Dimakis:EECS-2008-153