Efficiency of Partial Synchrony, and Resource Allocation in Distributed Systems
Injong Rhee · 1995
This dissertation is in two parts, covering two distinct areas of distributed computing. The first part concerns timing models in distributed systems that lie between the synchronous and asynchronous models in terms of their assumption on synchrony. We study their time complexity for solving distributed computing problems in shared memory (SM) and message-passing (MP) systems. We consider four timing parameters: the upper and lower bounds on process step time and message delay. Timing models are obtained by considering independently whether each parameter is known (i.e., is hard-wired into processes' code) or unknown, giving rise to four SM models and 16 MP models. We also study other timing models that are not covered by this framework. We show a general time complexity hierarchy indicating inherent time complexity gaps among the models. The time complexity gaps are introduced by the time complexity of the session problem, an abstraction of fundamental synchronization problems in dist...