Talks & Seminars
Title: Tight Time-Space Tradeoff for Mutual Exclusion
Prof. Prasad Jayanti, Dartmouth College, USA
Date & Time: July 24, 2013 16:00
Venue: Conference Room, 01st Floor, C Block, Department of Computer Science and Engineering, Kanwal Rekhi Building
Mutual Exclusion is a fundamental problem in distributed computing. In the last two decades, there has been a great deal of research on designing algorithms with small Remote Memory Reference (RMR) complexity (the "RMR complexity measure" captures how well concurrent algorithms perform on shared memory multiprocessors). In this talk, I will show how RMR complexity trades off with space complexity. Specifically I will show that, on cache coherent multiprocessors, constant RMR complexity is impossible with subpolynomial space and subpolynomial RMR complexity is impossible with constant space. The proofs are fascinating and are done via a purely combinatorial game that corresponds closely to mutual exclusion. (These results were presented at STOC 2012 and are joint work with Nikhil Bansal, Vibhor Bhatt, and Ranganath Kondapally.)
Speaker Profile:
I am James Frank Family Professor of Computer Science at Dartmouth College, USA. I graduated with a B.Tech in Mechanical Engineering from IIT Madras in 1984, two master's degrees from the University of Delaware (one in Mechanical Engineering in 1986 and another in Computer Science in 1988), and a Ph.D. in Computer Science from Cornell University in 1993, and have been on the Dartmouth computer science faculty since then. I received the NSF Research Initiation Award in 1994, Dartmouth's Distinguished Teacher Award in 1999, and Alfred P. Sloan Research Fellowship in 2000. I do research in concurrent computing and have published about two dozen papers in the ACM Symposium on Principles of Distributed Computing (PODC) and in DISC, and have served on the PODC Program Committee several times.
List of Talks


Faculty CSE IT
Forgot Password
    [+] Sitemap     Feedback