Cardinal

Soma Chaudhuri

Soma Chaudhuri is an Associate Professor of Computer Science at the Iowa State University. She received her Bachelors degrees in Mathematics and Computer Science and Engineering from the Massachusetts Institute of Technology in 1984. She received her Masters and PhD degrees in Computer Science and Engineering from the University of Washington in 1987 and 1990, respectively, under the supervision of Professor Richard E. Ladner.

Teaching Interests

Major 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.

Current Research

The Power of Inexact Timing Information in Distributed Systems

My research in distributed computing, has so far focused 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.

Representative Publications

Tight Bounds for k-Set Agreement (with Maurice Herlihy, Nancy Lynch and Mark Tuttle), Journal of the ACM 47 (5), pp. 912-943, September 2000 (in postscript).

One-Write Algorithms for Multivalued Regular and Atomic Registers (with Martha Kosa and Jennifer L. Welch), Acta Informatica 37 (3), pp. 161-192, 2000.

Wait-Free Implementations in Message Passing Systems (with Maurice Herlihy and Mark Tuttle), Theoretical Computer Science 220 (1), pp. 211-245, June 1999.

Shared Memory Consistency Conditions for Non-Sequential Execution: Definitions and Programming Strategies (with Hagit Attiya, Roy Friedman, and Jennifer L. Welch), SIAM Journal on Computing 27 (1), pp. 65-89, February 1998.

Understanding the Set Consensus Partial Order Using the Borowsky-Gafni Simulation (with Paul Reiners), in WDAG'96, the Proceedings of the Tenth International Workshop on Distributed Algorithms, October 1996, Lecture Notes in Computer Science 1151, pp. 362-379, Springer-Verlag.

Using Adaptive Timeouts to Achieve At-Most-Once Message Delivery (with Brian Coan and Jennifer L. Welch), Distributed Computing 9 (3), pp. 109-117, September 1995.

Bounds on the Costs of Multi-Valued Register Implementations (with Jennifer L. Welch), SIAM Journal on Computing 23 (2), pp. 335-354, April 1994.

More Choices Allow More Faults: Set Consensus Problems in Totally Asynchronous Systems, Information and Computation 105 (1), pp. 132-158, July 1993.

Designing Algorithms for Distributed Systems with Partially Synchronized Clocks (with Rainer Gawlick and Nancy Lynch), in Proceedings of the Twelfth Annual ACM Symposium on Principles of Distributed Computing, August 1993.

Safety and Liveness of omega-context-Free Languages (with Richard E. Ladner), Information Processing Letters 37, pp. 13-20, January 1991.

Graph Bisection Algorithms with Good Average Case Behavior (with Thang Bui, Tom Leighton and Michael Sipser), Combinatorica, 7 (2), pp. 171-191, 1987.

Professional Service