# 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://www.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://www.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://www.eecs.berkeley.edu/Pubs/TechRpts/2008/EECS-2008-153.html %F Dimakis:EECS-2008-153