Solving Global Tasks with Local Information: Theory and Applications

演讲人: Thomas Moscibroda 微软总部
时间: 2010-12-09 14:00-2010-12-09 15:00
地点:FIT 1-222

Some of the most fascinating computer systems are complex and dynamic networks. In such systems, each individual entity only has a small partial view of the entirety of the network, yet collectively, the system as a whole is supposed to perform some global task or maintain an equilibrium. This talk investigates the fundamental possibilities and limitations of local computation for solving global tasks in large-scale networks. I describe which global structures can be computed locally and present upper and lower bounds on the trade-off between the amount of local knowledge and the quality of the resulting global solution. As an application example, I will present recent work on large-scale multi-core systems, in which important resources (e.g. on-chip network, DRAM memory) are distributed and shared by many cores. I will showcase practical examples of what can happen if this sharing is done wrongly, and describe how multiple DRAM controllers can efficiently schedule access to different parts of DRAM in spite of incomplete information.


Thomas Moscibroda is a Researcher in the Distributed Systems Research Group at Microsoft Research in Redmond. His research interests are in distributed computing, (wireless) networking, and multi-core computer architecture, with a particular focus on algorithmic and theoretical approaches to practical system problems. He obtained his M.Sc. and PhD in Computer Science from ETH Zurich in 2004 and 2006, respectively, and was awarded the ETH Medal for his doctoral thesis. Thomas' research is documented in more than 50 research publications, and he has received Best Paper Awards at several top-tier conferences, including PODC 2004, IPSN 2007, SIGCOMM 2009, NSDI 2009, and ASPLOS 2010. Two of his articles on DRAM scheduling and on-chip networking in multi-core systems were selected as computer architecture top picks by IEEE Micro. In 2009, he was awarded the Microsoft Gold Star Award. Thomas is currently co-leading Microsoft's White-Fi initiative on White Space networking, building the world's first operational urban White Space network. Spectrum regulators from India, China, Brazil, Singapore, and the US (including FCC Chairman Genachowski) have visited the Microsoft Campus in Redmond to see a live demonstration of his research, and his project has been instrumental in the recent FCC decision to open up TV bands for unlicensed use in the United States.