B.U. Bridge
BU Opera Institute Fall Fringe Festival’s one-act operas, October 25 to 27 and November 1 to 3
Week of 25 October 2002 · Vol. VI, No. 9

Current IssueIn the NewsResearch BriefsBulletin BoardBU YesterdayCalendarClassified AdsArchive

Search the Bridge

Contact Us


In sync, from PDA to PC
In mobile computing, a cure for the synchronization blues

By Brian Fitzgerald

Self-described “techno-freaks” are not the only people who love their personal digital assistant (PDA) handheld computers. Even some hunters are known to carry Palm Pilots in the deep woods to help with landmark navigation.

David Starobinski (left) and Ari Trachtenberg (right), ENG assistant professors of computer engineering, along with graduate student Sachin Agarwal (ENG’06), depend on their trusty personal digital assistants -- and want to make them more efficient. Photo by Kalman Zabarsky


David Starobinski (left) and Ari Trachtenberg (right), ENG assistant professors of computer engineering, along with graduate student Sachin Agarwal (ENG’06), depend on their trusty personal digital assistants -- and want to make them more efficient. Photo by Kalman Zabarsky


“Whenever I take my son to the pediatrician, the first thing the doctor does is take out his PDA because he can get instant access to the Physicians Desk Reference,” says Ari Trachtenberg, an ENG assistant professor of electrical and computer engineering.

PDAs are everywhere. But so are PDA problems -- problems that Trachtenberg and his colleagues at ENG’s Laboratory of Networking and Information Systems are trying to solve.

These devices, which were once associated with “Pilot geeks” as mere playthings and glorified Rolodexes, are quickly becoming an important tool for many -- even outside the white collar workday world. Truck drivers, for example, can use them to communicate with their company, send and receive e-mail, and keep track of expenses, shipping records, maps, and schedules.

“Early PDAs were primarily used as address books and day planners,” says David Starobinski, also an ENG assistant professor of electrical and computer engineering. “But a lot has changed in the past few years.” Today they offer an increasing range of functions, such as multimedia capacity, database software, and Internet access.

However, as these networked and mobile/wireless devices become more complex, they are also proving more difficult to manage. Starobinski and Trachtenberg, in a project partially supported by a grant from the National Science Foundation, are working on solving a growing concern in the industry: the often time-consuming and frustrating process of synchronizing data on PDAs with data on personal computers (PCs). They are using a novel synchronization scheme, called CPIsync (characteristic polynomial interpolation-based synchronization), to speed up the process. The theory behind it was developed by Trachtenberg, Cornell graduate student Yaron Minsky, and Rich Zippel, director of Compaq Computer’s Cambridge research lab.

“At best, conventional synchronization can take a minute or two,” says Trachtenberg. “But sometimes it can take up to 20 minutes. This is especially going to be a problem as more and more people use PDAs and have to synchronize them with different machines -- the home computer, the work computer, the secretary’s computer, and so on.”

Starobinski points out that few have the patience to wait 20 minutes for synchronization, especially a physician examining a patient. “When he makes a diagnosis, he wants to immediately update the information on his PDA, and propagate it to that patient’s log on his laptop or the PC at the hospital,” he says. But the notoriously stubborn synchronization process that uses the data transfer protocol known as “slow sync” has prompted even the most mild-mannered professional to use such unprofessional terminology as, “Hurry up, you %$#@!!” and “Don’t crash on me, you @#$%!!”

“Chances are, if you have to wait 20 minutes, you’re probably not going to use the PDA,” says Trachtenberg. “Part of enabling PDAs to become more useful is making synchronization time reasonable.”

Much of what can sour the love affair between users and their PDAs is the fact that the slow sync algorithm requires a transfer of all the PDA data to the PC in order to determine the differing records between their databases. This approach turns out to be particularly inefficient, in terms of bandwidth usage, because the actual number of differing entries is typically much smaller than the total number of records stored on the PDA. Starobinski and Trachtenberg have proposed, analyzed, and actually implemented CPIsync, which relies on recent information-theoretic research results.

“The most salient property of this scheme is that the amount of communication needed for synchronizing the databases of the PDA and the PC relates only to their mutual differences,” says Sachin Agarwal (GRS’06), who worked with Starobinski and Trachtenberg on the project. They published a research paper on CPIsync in the July/August issue of IEEE (Institute of Electrical and Electronics Engineers) Network Magazine.

Trachtenberg says that CPIsync is still at the prototype level. “We have developed a prototype memo pad,” he says. “The whole key to its synchronization is that the amount of time the user has to wait depends only on how many changes he makes. If you have only a few changes in the address book, for example, you have to wait only a little bit of time, instead of having to wait for the entire address book to go from one machine to the other and figure out what the differences are.”

Starobinski predicts that CPIsync will eventually have a lot of impact in mobile computing, an area that has interested all three researchers for years. Agarwal says that the field has a bright future, and that part of the appeal of their research is that it “is based on some really sound theoretical principles, and in order to show that it actually works in the real world, we have to put that theoretical work into mobile devices. It’s exciting to put theory into practice.”


25 October 2002
Boston University
Office of University Relations