Multiple advances in diverse fields have catalyzed a paradigm shift away from centralized architectures and in the direction of distributed computing and cooperative communications in large-scale networks. The requirement for scalability imposes constraints on the cost and resources of individual nodes, resulting in nodes that are imprecise, statistically varying, and unreliable. The fundamental systems challenge is to overcome these individually unreliable components by deriving strength from numbers, and to form a network that is strong, reliable, robust, and capable of meeting specific performance guarantees. This proposal seeks to develop the theoretical foundations needed to realize this vision, focusing on the vital role of randomized signal processing and decentralized network coding to address two important system attributes, scalability and robustness.
1.1 Intellectual Merits The basis of this proposal is to develop both the theoretical foundations and constructive solutions for understanding the role of randomized signal processing and decentralized coding in distributed systems comprised of unreliable, resource-constrained elements. Motivated by the important considerations of scalability, robustness, node cost and resource limitations, and a lack of global system coordination, we propose to explore the following important research areas: . Distributed storage and ubiquitous access to data in large-scale networks founded on a new class of decentralized erasure codes; . Reliable communication in networks comprised of cheap, untuned radios and distributed transmitters through the novel use of randomized network coding and uncoordinated communication strategies; . Distributed data representation and summarization based on randomized multiresolution transforms and randomized in-network signal processing.
1.2 Broader Impact Our research is aimed at exploring the fundamental limits of randomized signal processing and decentralized coding, and the technology transfer of these theoretical constructs into the design and deployment of efficient and practical algorithms for large-scale networks. Our work will apply to a broad range of applications, ranging from computer science applications like peer-to-peer networks to system-theory-aided fault tolerant circuit design. In instrumenting this technology transfer, we will heavily leverage the implementational capabilities of the Berkeley Wireless Research Center (BWRC), as well as the theoretical prowess of the Berkeley Wireless Foundations Center. In continuing with a rich tradition at UC Berkeley, the theoretical and algorithmic results coming out of this innovative research will be integrated into the EECS curricula at Berkeley. The involvement of undergraduate research assistants will continue to be emphasized, helping to educate future leaders in signal processing and communications for both academia and industry.
