# 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

**Undergraduate Courses:**Design and Analysis of Algorithms, Discrete Computational Structures, Theory of Computing, Introduction to Operating Systems.**Graduate Courses:**Distributed Algorithms, Algorithms for Wireless and Mobile Networks, Advanced Data Structures, Theory of Computation, Design and Analysis of Algorithms, Parallel Algorithms and Complexity, Complexity Theory.

## 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

Member of the Program Committee for The 14th ACM Symposium on Principles of Distributed Computing (PODC'95), August 1995.

Member of the Program Committee for The 17th International Conference on Distributed Computing Systems (ICDCS'97), May 1997.

Member of the Program Committee for The 11th International Workshop on Distributed Algorithms (WDAG'97), September 1997.

Referee for scientific journals including