Student Wins Best Paper Award
09-28-2006
Maleq Khan, a Ph.D. student in the Department of Computer Science at Purdue University, received an award for the Best Student Paper at the 20th International Symposium on Distributed Computing (DISC 2006) held in Stockholm, Sweden on September 18-20, 2006. This work is joint work with his advisor, Gopal Pandurangan, an Assistant Professor in the department. The award winning paper is titled “A Fast Distributed Approximation Algorithm for Minimum Spanning Trees". The award is annually given to the best papers having at least one author as a full-time student. The winners were highlighted in the preface of the conference proceedings and received a certificate and technical books. The award was formally announced and given to the winners at the conference banquet on September 19, 2006.
The paper addresses the distributed minimum spanning tree (MST) problem, one of the most fundamental problems in distributed computing. A minimum spanning tree is the smallest (weighted) set of edges needed to maintain network connectivity. There has been a long line of research to develop efficient distributed algorithms for the MST problem. It is known that computing an MST can take significant time in a distributed environment, essentially time proportional to the square root of the number of nodes in the network. However, whether an approximation algorithm (that outputs a near optimal tree) can be developed that runs significantly faster than exact MST algorithms remained as an important open problem. In their paper, Khan and Pandurangan came up with a new distributed algorithm that computes a slightly sub-optimal MST, but can run significantly faster than exact MST algorithms. Their algorithm is expected to have significant impact on building low-cost spanning trees very quickly in large networks. An important application of their work is in the wireless networks, including large-scale sensor networks.
DISC is an established and highly recognized annual conference that focuses on all facets of distributed computing. Conference presentations detailed new research results in the theory, design, specification, analysis, implementation, or application of distributed systems and networks. DISC 2006 was organized in cooperation with the European Association for Theoretical Computer Science (EATCS). This year's conference accepted 35 papers out of a total of 145 submissions. DISC 2006 hosted invited talks by three leaders in the area of distributed computing: Michael Rabin (Harvard), Leslie Lamport (Microsoft), and Nancy Lynch (MIT).