9308103 Chaudhuri The time and space complexity of a variety of problems that arise in distributed systems where processors have inexact timing information shall be studied. In particular, each processor is modeled to have a local clock, and to take steps at each tick of its clock. However, the local clocks of all processors may not be synchronized with each other, and may run at different speeds. Also, in a message-passing system of communication, messages may take varying amounts of time to be delivered. Processors therefore have uncertain knowledge about the time for processor steps and communication. A number of different ways in which to model this timing uncertainty shall be considered. These models will more closely imitate real systems than either the synchronous or the asynchronous models of distributed computing. A number of combinatorial problems like consensus, set consensus, resource allocation, and renaming, network problems like message transmission will be studied, as well as implementations of shared data objects. Obtaining upper and lower complexity bounds for these problems is a goal, taking into consideration a variety of failures and exploiting different timing assumptions. In most cases, robust algorithms that perform well whenever the system satisfies the timing restrictions specified will be of interest, but correctness shall not be compromised in case they are not. The main goal of this research is to understand the power of making inexact timing assumptions in solving these canonical problems in distributed computing. Some of the same questions that have been previously studied will be examined, 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 mo re abstract level, developing novel techniques for exploiting timing assumptions in both algorithm design and in obtaining lower bounds and impossibility results is desired. A second goal will be to develop a complexity hierarchy of shared objects in a timing-based distributed system. The ultimate objective will 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. ***
