Scrambling bits for a more efficient Internet.
Todays Internet transmissions chop files into packets, each of which is passed from router to router until it reaches its final destination. But when files get big or are sent to many users, transmitting them without clogging the network becomes complicated. With “network coding,” an idea first proposed in 2000, routers would jumble together the bits from different packets, forming new packets. Recombining the data in this way gives the end user additional information, theoretically speeding downloads and increasing network capacity. But early network coding schemes required a godlike central authority that knew how the packets were to be combined – a practical impossibility. As a PhD student at MIT, Tracey Ho had a novel alternative: let network nodes mix packets together at random, tagging them with just enough information to help end users computers recover the original data. This decentralized method automatically optimizes bandwidth use. “It sounds kind of insane,” says Muriel Medard, Hos PhD advisor. “But its not just that it works; you cant make it work better.” As an assistant professor of electrical engineering and computer science, Ho still studies network coding. But only months after she first presented her “distributed random network coding” scheme, Microsoft researchers showed that it can clearly outperform todays multicast systems. The company has embarked on a project called Avalanche to commercialize the scheme.
Sharpening a computers listening skills.
Computers have difficulty doing what the brain does easily: concentrating on one voice while ignoring other sounds. University of Toronto electrical-engineering professor Parham Aarabi created an algorithm that calculates the difference between the times at which a sound reaches two closely spaced microphones. Based on the delay, the software can determine the direction of speakers and amplify the speech of any one of them; all other conversation is reprocessed into a slight hum. Aarabis invention, which is 30 percent more accurate than other multimicrophone systems, could filter out extraneous voices in cell-phone conversations or enhance voice control in cars.
Teaching computers to read and write.
For her doctoral dissertation at Columbia University, computer scientist Regina Barzilay led the development of Newsblaster, which does what no computer program could do before: recognize stories from different news services as being about the same basic subject, and then paraphrase elements from all of the stories to create a summary. Though humans can easily divine the meaning of a word from its context, computers cannot. Barzilay uses statistical machine-learning software to teach computers to make educated guesses. A computer is fed pairs of text samples that it is told are equivalent – two translations of the same sentence from Madame Bovary, say. The computer then derives its own set of rules for recognizing matches. Once trained, it can tackle new sentences, computing “syntactic trees” that parse out their structural elements in different ways and determining the probability that each interpretation is correct. Then it statistically compares the most likely trees from two sentences to see if they match. The Newsblaster software recognizes matches about 80 percent of the time. The software works best with news stories, because they exhibit some regularity; “the problem is more constrained,” says Barzilay, now an MIT assistant professor of electrical engineering and computer science. Shes working on a variation of Newsblaster for spoken language, which could yield applications that range from summarizing recorded lectures to handling airline reservation calls.
Building communities through photos.
In February 2004, Stewart Butterfield and his coworkers at Ludicorp, then engaged in developing an online game, launched a side product called Flickr – “kind of on a lark.” By summer, the project had taken over the company; today its the Webs fastest-growing photo-sharing site. Employing “tags” that allow people to make their photos searchable by content, Flickr encourages users to engage in discussions about their pictures. Acquired by Yahoo in March, Flickr now has more than one million users, who post hundreds of thousands of new photos a day.
Protecting software from crashes
As counterintuitive as it might seem, George Candeas “crash-only software” concept may actually help keep software crash free. According to Candea, software crashes and subsequent reboots neednt be catastrophic, systemwide events. He has described software that can be trained to monitor itself and, if it detects something amiss, to launch a surgical, or “micro,” reboot of just the problematic application element, while the system as a whole functions uninterrupted. “Microrebooting allows software to react to failure in machine time as opposed to human time,” says Candea, who recently got his doctorate in computer science at Stanford University.
Tracing software in real time.
Even with all the recent advances in information technology, systems administrators are still running blind: if a piece of software doesnt quite do what it should, administrators may spend days hunting down the problem and figuring out how to fix it. Bryan Cantrill, senior staff engineer at Sun Microsystems, has created an application called DTrace that offers real-time software diagnostics – giving IT folks a way to see whats going on and start improving performance in minutes. This kind of power elates many programmers. “With DTrace,” says Cantrill, “I can walk into a room of hardened technologists and get them giggling.”
Bringing Internet power to the have-nots.
As founding editor in 1999 and current director of the Digital Divide Network, Andy Carvin has helped build an online community of more than 7,500 technology activists, educators, small-business owners, and policy makers. Their mission is to devise remedies for the fundamental information-age inequity: most people in the world lack the ability to access the Internet or the skills to use it. Carvin is also promoting a way for technology to give voice to the disenfranchised: mobcasting. Carvins idea is to combine the ubiquity of cell phones with the ease of posting information to Web logs (blogs). Say protesting human-rights activists get roughed up by police, with no traditional media on hand to record their plight. Over their phones, the human-rights activists could send multiple reports on whats happening – either audio or video – to the same website. Carvin is pushing programmers to create mobcasting software that works outside the U.S. phone system. With the use of mobcasting, suggests Carvin, “suddenly, the very people who are victims are empowered to bear witness to the world almost instantaneously.”
Setting the mesh networking standard.
In the late 1990s, when Wi-Fi-equipped laptops were still a novelty, Narasimha Chari saw the possibility of creating large communications infrastructures using wireless mesh networks – which at the time were the exclusive province of the military. In 18 months of moonlighting while a physics grad student at Harvard University, he created elegant algorithms that tailored mesh networking for routine civilian communications. Tropos Networks, the company Chari founded in 2000 with coinventor Devabhaktuni Srikrishna, helped launch commercial wireless mesh networking. With their straightforward installation – routers attach to lampposts – and attendant low cost, mesh networks have eased into plentiful use both outdoors (on campuses, in public safety networks, and at gatherings such as festivals) and in (in hospitals and factories). But Tropos is focusing on the rapidly growing market for networks that serve entire municipalities. Thats the application of choice for one-third of the companys 200 customers. Troposs services, which are built around Charis routing protocols, dominate the nascent mesh-networking industry. Telecommunications companies fear the proliferation of the technology, seeing it as a threat to their Internet access businesses. In fact, the telecommunications industry is lobbying for legislation granting them – not local governments – first dibs on municipal Wi-Fi installations. Meanwhile, Tropos is gaining customers at a rapid clip; 75 signed on in the first half of 2005. Troposs expansion is bringing Chari full circle. In 1992, after receiving the third-highest score out of 80,000 on the Indian Institutes of Technology entrance exam, Chari left India for Caltech. Later, while at Harvard, he had late-night talks with Caltech pal Srikrishna about providing anytime, anywhere communications in developing countries. Now, as Tropos ships its first systems to India, Chari is seeing his innovation connect back to his homeland.
Upending the file-sharing world, bit by bit.
Bram Cohens creation, BitTorrent, answers a deceptively simple question: if someone requests a file over a network, and multiple people on the network possess the file, why should only one person send the file in its entirety to the requester? Cohens revolutionary solution: send tiny chunks of the file from multiple users, eliminating the bandwidth crunch that results when a single user sends a large file in its entirety. A 400-megabyte video file that could take hours for a single user to distribute can be broken up into thousands of pieces, each of which takes only a few seconds to send. The impact of the technology that Cohen developed goes far beyond the world of illicit file-swapping: game companies and Linux developers are now experimenting with BitTorrent distribution as well. Cohen is humble about his creation and its potential impact. It is, he says, “just a way to move bits around.”
Moving online socializing into the streets
When Dennis Crowley goes out clubbing in New York, hell text a message with his location to Dodgeball, the company that he founded. Crowleys message – “@ Luna Lounge,” for example – goes out to all the friends he has listed at the Dodgeball website. The companys computer checks the clubs address against its list of geographical locations in 22 cities. If someone who is not on Crowleys friend list but is on the list of one of his friends has checked in within the last three hours and a 10-block radius, the computer notifies both parties. If Crowley has listed a girl he doesnt know as a “crush,” shell get a message with his picture saying hes interested. Shell have the option to find him or dodge him, without his ever knowing where she is. Google liked the idea so much it bought Dodgeball in May. Crowley says its “a very powerful thing to know where your friends are all the time.”
Simplifying wireless sensor nets.
Wireless sensor networks enable the remote monitoring of everything from the habitat of an endangered bird species to a buildings response to an earthquake. The problem, says computer scientist Samuel Madden, is that proper programming of the nets data-gathering “motes” can require months of expert attention. In 2003, while a graduate student at the University of California, Berkeley, Madden created software called TinyDB that translates high-level queries like “Whats the average temperature in the forest?” into precise instructions. Madden, an assistant professor of computer science, is now installing sensors in cars to monitor operating conditions and figure out faster routes.
Predicting the future of markets
How could markets possibly be able to predict things like where a hurricane will strike? In part because they aggregate information well, says David Pennock, who studies how economic theory can be expressed via computation. Pennocks research underlies not only predictive markets but also the enormously successful sponsored search functions featured on Yahoo, Google, and elsewhere. Recommendation engines like those on Amazon.com also draw from Pennocks work. Most recently, Pennock designed a new type of market, the “dynamic pari-mutuel market,” now being offered at Yahoo Tech Buzz. Part horse racing, part futures market, it lets people bet on whether a product is a fad or for real.
Giving GPS a sharper image.
Inside buildings and the urban valleys of large cities, Global Positioning System technology is often inaccurate or unusable. Matthew Rabinowitz has sharpened GPS precision by exploiting the synchronization codes embedded in broadcast television signals. These codes allow a TV receiver to compile numerous signals into a single harmonious output. Rabinowitz, who cofounded Rosum and now serves as chief technology officer, has developed a handheld device that uses sync codes to calculate how far the user is from the source of the signals and thus determine his or her location. The Rosum technology refines GPS position readings to within a meter or two, even indoors and in cities.