Abstract
The performance of complex systems depends on joint decision-making by a large number of components. As the system size increases, designs that require global coordination do not scale well, while designs based on just local knowledge perform poorly. Using examples from networking and medical imaging, I will show that global objectives can be achieved via simple local rules that exchange the right amount of information.
The first application concerns data measurement in networks. Networks collect detailed statistics on the data (bytes, packets, etc) sent by each flow. This requires large and fast memories for housing the counters.
However, such memories are prohibitively expensive. We introduce a novel architecture, called Counter Braids, which allows counters to be shared among the flows. While sharing leads to a large reduction in the space requirement, it diffuses flow size information across the entire architecture. A simple, local message passing algorithm subsequently recovers all flow sizes exactly.
Another application concerns the separation of water and fat signals in magnetic resonance imaging (MRI). A key step in this problem is the estimation of the field inhomogeneity map across the whole image from pixel-level observations. The large size of the data has prompted several local algorithms, which suffer from estimation error propagation.
We present an algorithm, called JIGSAW, which estimates the field map by spreading pixel-level information via simple local exchanges. It outperforms existing techniques to produce uniform water-fat separation in several challenging and clinically important imaging scenarios.
Biography
Yi Lu is a Ph.D. student in the Electrical Engineering Dept, Stanford University. She is interested in architectures and algorithms for high-performance networks, medical imaging, and inference on graphical models. She is a recipient of the Cisco Stanford Graduate Fellowship and a co-recipient of the Best Paper Award at ACM SIGMETRICS 2008.