Breaking bottlenecks
As sensors that do things like detect touch and motion in cell phones get smaller, cheaper and more reliable, computer manufacturers are beginning to take seriously the decade-old idea of “smart dust” — networks of tiny wireless devices that permeate the environment, monitoring everything from the structural integrity of buildings and bridges to the activity of live volcanoes. In order for such networks to make collective decisions, however — to, say, recognize that a volcano is getting restless — they need to integrate information gathered by hundreds or thousands of devices.But networks of cheap sensors scattered in punishing and protean environments are prone to “bottlenecks,” regions of sparse connectivity that all transmitted data must pass through in order to reach the whole network. At the 2011 ACM-SIAM Symposium on Discrete Algorithms, which took place in New Orleans the weekend of Jan. 9, Keren Censor-Hillel, a postdoc at MIT’s Computer Science...