Monthly Archives: September 2016

Electrical Engineering and Computer Science

Nancy Lynch, the NEC Professor of Software Science and Engineering, has been appointed as associate head of the Department of Electrical Engineering and Computer Science (EECS), effective September 1.

Lynch is known for her fundamental contributions to the foundations of distributed computing. Her work applies a mathematical approach to explore the inherent limits on computability and complexity in distributed systems.

Her best-known research is the “FLP” impossibility result for distributed consensus in the presence of process failures. Other research includes the I/O automata system modeling frameworks. Lynch’s recent work focuses on wireless network algorithms and biological distributed algorithms.

The longtime head of the Theory of Distributed Systems (TDS) research group in the Computer Science and Artificial Intelligence Laboratory (CSAIL), Lynch joined MIT in 1981. She received her BS from Brooklyn College in 1968 and her PhD from MIT in 1972, both in mathematics. Recently, Lynch served as head of CSAIL’s Theory of Computation (TOC) group for several years.

She is also the author of several books and textbooks, including the graduate textbook Distributed Algorithms, considered a standard reference in the field. Lynch has also has co-authored several hundred articles about distributed algorithms and impossibility results, and about formal modeling and verification of distributed systems. She is the recipient of numerous awards, an ACM Fellow, a Fellow of the American Academy of Arts and Sciences, and a member of both the National Academy of Sciences and the National Academy of Engineering.

New computational imaging method

MIT researchers and their colleagues are designing an imaging system that can read closed books.

In the latest issue of Nature Communications, the researchers describe a prototype of the system, which they tested on a stack of papers, each with one letter printed on it. The system was able to correctly identify the letters on the top nine sheets.

“The Metropolitan Museum in New York showed a lot of interest in this, because they want to, for example, look into some antique books that they don’t even want to touch,” says Barmak Heshmat, a research scientist at the MIT Media Lab and corresponding author on the new paper. He adds that the system could be used to analyze any materials organized in thin layers, such as coatings on machine parts or pharmaceuticals.

Heshmat is joined on the paper by Ramesh Raskar, an associate professor of media arts and sciences; Albert Redo Sanchez, a research specialist in the Camera Culture group at the Media Lab; two of the group’s other members; and by Justin Romberg and Alireza Aghasi of Georgia Tech.

The MIT researchers developed the algorithms that acquire images from individual sheets in stacks of paper, and the Georgia Tech researchers developed the algorithm that interprets the often distorted or incomplete images as individual letters. “It’s actually kind of scary,” Heshmat says of the letter-interpretation algorithm. “A lot of websites have these letter certifications [captchas] to make sure you’re not a robot, and this algorithm can get through a lot of them.”

Timing terahertz

The system uses terahertz radiation, the band of electromagnetic radiation between microwaves and infrared light, which has several advantages over other types of waves that can penetrate surfaces, such as X-rays or sound waves. Terahertz radiation has been widely researched for use in security screening, because different chemicals absorb different frequencies of terahertz radiation to different degrees, yielding a distinctive frequency signature for each. By the same token, terahertz frequency profiles can distinguish between ink and blank paper, in a way that X-rays can’t.

Terahertz radiation can also be emitted in such short bursts that the distance it has traveled can be gauged from the difference between its emission time and the time at which reflected radiation returns to a sensor. That gives it much better depth resolution than ultrasound.

The system exploits the fact that trapped between the pages of a book are tiny air pockets only about 20 micrometers deep. The difference in refractive index — the degree to which they bend light — between the air and the paper means that the boundary between the two will reflect terahertz radiation back to a detector.

In the researchers’ setup, a standard terahertz camera emits ultrashort bursts of radiation, and the camera’s built-in sensor detects their reflections. From the reflections’ time of arrival, the MIT researchers’ algorithm can gauge the distance to the individual pages of the book.

True signals

While most of the radiation is either absorbed or reflected by the book, some of it bounces around between pages before returning to the sensor, producing a spurious signal. The sensor’s electronics also produce a background hum. One of the tasks of the MIT researchers’ algorithm is to filter out all this “noise.”

Programming language delivers fourfold speedups on problems

In today’s computer chips, memory management is based on what computer scientists call the principle of locality: If a program needs a chunk of data stored at some memory location, it probably needs the neighboring chunks as well.

But that assumption breaks down in the age of big data, now that computer programs more frequently act on just a few data items scattered arbitrarily across huge data sets. Since fetching data from their main memory banks is the major performance bottleneck in today’s chips, having to fetch it more frequently can dramatically slow program execution.

This week, at the International Conference on Parallel Architectures and Compilation Techniques, researchers from MIT’s Computer Science and Artificial Intelligence Laboratory (CSAIL) are presenting a new programming language, called Milk, that lets application developers manage memory more efficiently in programs that deal with scattered data points in large data sets.

In tests on several common algorithms, programs written in the new language were four times as fast as those written in existing languages. But the researchers believe that further work will yield even larger gains.

The reason that today’s big data sets pose problems for existing memory management techniques, explains Saman Amarasinghe, a professor of electrical engineering and computer science, is not so much that they are large as that they are what computer scientists call “sparse.” That is, with big data, the scale of the solution does not necessarily increase proportionally with the scale of the problem.

“In social settings, we used to look at smaller problems,” Amarasinghe says. “If you look at the people in this [CSAIL] building, we’re all connected. But if you look at the planet scale, I don’t scale my number of friends. The planet has billions of people, but I still have only hundreds of friends. Suddenly you have a very sparse problem.”

Similarly, Amarasinghe says, an online bookseller with, say, 1,000 customers might like to provide its visitors with a list of its 20 most popular books. It doesn’t follow, however, that an online bookseller with a million customers would want to provide its visitors with a list of its 20,000 most popular books.

Thinking locally

Today’s computer chips are not optimized for sparse data — in fact, the reverse is true. Because fetching data from the chip’s main memory bank is slow, every core, or processor, in a modern chip has its own “cache,” a relatively small, local, high-speed memory bank. Rather than fetching a single data item at a time from main memory, a core will fetch an entire block of data. And that block is selected according to the principle of locality.

It’s easy to see how the principle of locality works with, say, image processing. If the purpose of a program is to apply a visual filter to an image, and it works on one block of the image at a time, then when a core requests a block, it should receive all the adjacent blocks its cache can hold, so that it can grind away on block after block without fetching any more data.

But that approach doesn’t work if the algorithm is interested in only 20 books out of the 2 million in an online retailer’s database. If it requests the data associated with one book, it’s likely that the data associated with the 100 adjacent books will be irrelevant.

Going to main memory for a single data item at a time is woefully inefficient. “It’s as if, every time you want a spoonful of cereal, you open the fridge, open the milk carton, pour a spoonful of milk, close the carton, and put it back in the fridge,” says Vladimir Kiriansky, a PhD student in electrical engineering and computer science and first author on the new paper. He’s joined by Amarasinghe and Yunming Zhang, also a PhD student in electrical engineering and computer science.

Batch processing

Milk simply adds a few commands to OpenMP, an extension of languages such as C and Fortran that makes it easier to write code for multicore processors. With Milk, a programmer inserts a couple additional lines of code around any instruction that iterates through a large data collection looking for a comparatively small number of items. Milk’s compiler — the program that converts high-level code into low-level instructions — then figures out how to manage memory accordingly.

The secrets of cryptography

“Split up into groups of three,” directed Sophia Yakoubov, associate staff in the Secure Resilient Systems and Technology Group at MIT Lincoln Laboratory and instructor of the LLCipher cryptography workshop. “Within each group, the person sitting on the left is Alice, the person on the right is Bob, and the person in the middle is Eve. Alice must write a secret message in a notebook and pass it to Bob. Eve must figure out Alice’s message and intercept everything that Alice and Bob pass to each other. Alice and Bob each have a lock and matching key, however, they cannot exchange their keys. How can Alice pass her secret message to Bob so that Eve is unable to unlock and view the secret, and only Bob can read it?”

The 13 high school students participating in the workshop glanced at one another until one brave student addressed the entire class, starting a flurry of conversation: “Any ideas?”

Thus began one of the many hands-on challenges that students tackled at the LLCipher workshop held in August at the MIT campus in Cambridge, Massachusetts, and MIT Lincoln Laboratory in Lexington, Massachusetts. LLCipher is a one-week program that introduces students to modern cryptography, a theoretical approach to securing data such as Alice’s secret message. The program begins with lessons in abstract algebra and number theory that students use to understand theoretical cryptography during lessons later in the workshop.

“I decided that LLCipher was for me when I researched the course topics,” says student Evan Hughes. “As I made my way down the topic list, I didn’t understand many of the concepts, so I immediately applied to the program.”

Because of student feedback from LLCipher’s inaugural year in 2015, Yakoubov extended each lesson from two to six hours. “Many students said they wanted more time on learning,” says Yakoubov. “Specifically, they wanted to learn more than one cryptography technique and apply those techniques to ‘real-world’ scenarios, rather than just learn theory.” This year, in addition to the El Gamal public key cryptosystem, students learned the RSA public key cryptosystem. RSA is one of the most common methods to secure data and uses slightly different math from El Gamal. Both RSA and El Gamal use modular arithmetic, a type of math in which integers “wrap around” upon reaching a certain value, i.e., the modulus, similar to a clock that uses 12 numbers to represent 24 hours in one day. El Gamal uses a very large prime number as a modulus; RSA uses a very large composite number, i.e., a whole number that can be divided evenly by numbers other than 1 or itself, with a secret factorization.

To reinforce the techniques and allow students to apply the theory, Yakoubov, along with the help of Uri Blumenthal and Jeff Diewald of the Secure Resilient Systems and Technology Group, created an online platform that includes El Gamal- and RSA-based challenges. “With these exercises, we are able to show students examples of flawed cryptography so that they can see how easily it can be broken,” says Yakoubov. “Students can visualize huge numbers and see why concepts like randomization are so important to effective encryption.” The platform is used throughout the course and includes six challenges that bolster teamwork and creativity.

“Learning about public key encryption is fun because it is so complicated and secretive,” says student Garrett Mallinson. “I like creating codes that no one else can break or unlock — this is like what characters do on television shows in just 45 minutes.”

During the final day of the course, students toured several Lincoln Laboratory facilities, such as the anechoic chambers and the Flight Test Facility. “I enjoyed the tour around Lincoln Laboratory,” says Hughes. “We always hear about theoretical concepts at school, so it is inspiring to see people applying and making the things we hear about.”

After the tour, students listened to a guest lecture from Emily Shen of the Secure Resilient Systems and Technology Group on a more specialized cryptography topic. Shen explained secure multiparty computation, a tool that allows multiple users with secret inputs to compute a joint function on their inputs without having to reveal anything beyond the output of the joint function. To demonstrate the concept, students participated in an activity to find out whether the majority of the group likes pie or cake without each student revealing his or her preference. First, the group assigned pie and cake a binary representation — 0 for pie and 1 for cake. The group also picked a modulus larger than the size of the group; in this case, the modulus was 14. The first participant secretly chose an auxiliary value between 0 and 13, added his vote, 0 or 1, to that value, and then used modular arithmetic to get a new value. For example, if he chose an auxiliary value of 13 and his vote was 1, he took the remainder modulo of 14 to get a total of 0. He then passed on the sum to the next student. This pattern continued until the last student gave her value to the original participant, who then subtracted the secret auxiliary number from the last value. The remaining value represented the amount of votes for cake and indicated whether the majority of the group likes cake or pie.

Urban travel patterns from cellphone data

In making decisions about infrastructure development and resource allocation, city planners rely on models of how people move through their cities, on foot, in cars, and on public transportation. Those models are largely based on surveys of residents’ travel habits.

But conducting surveys and analyzing their results is costly and time consuming: A city might go more than a decade between surveys. And even a broad survey will cover only a tiny fraction of a city’s population.

In the latest issue of the Proceedings of the National Academy of Sciences, researchers from MIT and Ford Motor Company describe a new computational system that uses cellphone location data to infer urban mobility patterns. Applying the system to six weeks of data from residents of the Boston area, the researchers were able to quickly assemble the kind of model of urban mobility patterns that typically takes years to build.

The system holds the promise of not only more accurate and timely data about urban mobility but the ability to quickly determine whether particular attempts to address cities’ transportation needs are working.

“In the U.S., every metropolitan area has an MPO, which is a metropolitan planning organization, and their main job is to use travel surveys to derive the travel demand model, which is their baseline for predicting and forecasting travel demand to build infrastructure,” says Shan Jiang, a postdoc in the Human Mobility and Networks Lab in MIT’s Department of Civil and Environmental Engineering and first author on the new paper. “So our method and model could be the next generation of tools for the planners to plan for the next generation of infrastructure.”

To validate their new system, the researchers compared the model it generated to the model currently used by Boston’s MPO. The two models accorded very well.

“The great advantage of our framework is that it learns mobility features from a large number of users, without having to ask them directly about their mobility choices,” says Marta González, an associate professor of civil and environmental engineering (CEE) at MIT and senior author on the paper. “Based on that, we create individual models to estimate complete daily trajectories of the vast majority of mobile-phone users. Likely, in time, we will see that this brings the comparative advantage of making urban transportation planning faster and smarter and even allows directly communicating recommendations to device users.”

Joining Jiang and González on the paper are Daniele Veneziano, a professor of CEE at MIT; Yingxiang Yang, a graduate student in CEE; Siddharth Gupta, a research assistant in the Human Mobility and Networks Lab, which González leads; and Shounak Athavale, an information technology manager at Ford Motor’s Palo Alto Research and Innovation Center.

Model building

The Boston MPO’s practices are fairly typical of a major city’s. Boston conducted one urban mobility survey in 1994 and another in 2010. Its current mobility model, however, still uses the data from 1994. That’s because it’s taken the intervening six years simply to sort through all the data collected in 2010. Only now has the work of organizing that data into a predictive model begun.

The 2010 survey asked each of 25,000 residents of the Boston area to keep a travel diary for a single day. From those diaries, combined with census data and information from traffic sensors, the MPO attempts to model the movements of 3.5 million residents of the greater Boston area.