Timing-based, distributed computation: algorithms and impossibility results

Real distributed systems are subject to timing uncertainties: processes may lack a common notion of real time, or may even have only inexact information about the amount of real time needed for performing primitive computation steps. In this thesis, we embark on a study of the complexity theory of such systems and present combinatorial results that determine the inherent costs of some accomplishable tasks. We first consider continuous-time models, where processes obtain timing information from continuous-time clocks that run at the same rate as real time, but might not be initially synchronized. Due to an uncertainty in message delay time, absolute process synchronization is known to be impossible for such systems. We develop novel synchronization schemes for such systems and use them for building a distributed, full caching implementation of shared memory that supports linearizability. This implementation improves in efficiency over previous ones that support consistency conditions even weaker than linearizability and supports a quantitative degradation of the less frequently occurring operation. We present lower bound results which show that our implementation achieves efficiency close to optimal. We next turn to discrete-time models, where the time between any two consecutive steps of a process is in the interval (c, 1), for some constant c such that 0 $\leq$ c $\leq$ 1. We show time separation results between asynchronous and semi-synchronous such models, defined by taking c = 0 and c $>$ 0, respectively. Specifically, we use the session problem to show that the semi-synchronous model, for which the timing uncertainty, $1\over{c}$, is bounded, is strictly more powerful than the asynchronous one under either message-passing or shared-memory interprocess communication. We also present tight lower and upper bounds on the degree of precision that can be achieved in the semi-synchronous model. Our combinatorial results shed some light on the capabilities and limitations of distributed systems subject to timing uncertainties. In particular, the main argument of this thesis is that the goal of designing distributed algorithms so that their logical correctness is timing-independent, whereas their performance might depend on timing assumptions, will not always be achievable: for some tasks, the only practical solutions might be strongly timing-dependent.