Soma Chaudhuri
Associate Professor

Office: 230 Atanasoff Phone: (515) 294-8547 Fax: (515) 294-0258 Email: chaudhur@cs.iastate.edu Homepage: http://www.cs.iastate.edu/~chaudhur/homepage.html

Research Interests

Theory of Distributed Computing; Algorithms, Lower Bounds and Impossibility Results for Asynchronous and Semi-synchronous Systems; Fault-Tolerance; Shared Memory and Message Passing Protocols. Parallel Algorithms and Complexity.

Research Areas

Algorithms, Computational Complexity, Distributed Computing and Networks, Software Systems, Theory of Computation

Research Statement

My research in distributed computing, has so far focussed on understanding the power of asynchronous distributed systems subject to various kinds of failures. A persistent question has been to determine the problems that are solvable in the presence of uncertainty due to processor asynchrony and failures. I have used combinatorial techniques to prove that certain problems are impossible to solve in these systems. My current focus has shifted to the study of systems that are semi-synchronous, i.e., that have partial but inexact information about timing. These systems are much more realistic and deserve further study. I intend to use similar combinatorial techniques with the goal of obtaining time and space complexity characterizations for problems in semi-synchronous systems analogous to the fault-resiliency characterization obtained for problems in asynchronous systems.

The main goal in this research, funded by a National Science Foundation Research Initiation Award, is to understand the power of making inexact timing assumptions in solving the canonical problems in distributed computing. I will be studying some of the same questions that have been previously studied, but in the context of certain timing assumptions. One goal of the research would be to develop general techniques which permit simulation of arbitrary synchronous (possibly round-based) fault-tolerant algorithms for various problems in the model with timing uncertainty. At a more abstract level, I would like to develop novel techniques for exploiting timing assumptions in both algorithm design and in obtaining lower bounds and impossibility results. A second goal would be to develop a complexity hierarchy of shared objects in a timing-based distributed system. The ultimate objective would be to understand in a formal sense the advantage that can be gained by considering timing-based models for distributed computing over asynchronous models, and the disadvantage they represent in relation to fully synchronous models.

Education

Ph.D.   University of Washington   1990
M.S.   University of Washington   1987
B.S.   Massachusetts Institute of Technology   1984

Representative Publications

Refereed Journal and Conference Publications

Jun Ge, Soma Chaudhuri, Akhilesh Tyagi. Control Flow Based Obfuscation. ACM Digital Rights Management Workshop, Alexandra, VA, ACM, Accepted, 2005.

Soma Chaudhuri, Maurice Herlihy, Nancy Lynch and Mark Tuttle. Tight Bounds for k-Set Agreement. Journal of the ACM, 2000.

Soma Chaudhuri, Martha Kosa and Jennifer L. Welch. One-Write Algorithms for Multivalued Regular and Atomic Registers. Acta Informatica, 2000.

Soma Chaudhuri, Maurice Herlihy and Mark Tuttle. Wait-Free Implementations in Message Passing Systems. Theoretical Computer Science, 1999.