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.