The impact of timing knowledge on the session problem
Academic Article
Overview
Research
Identity
Additional Document Info
Other
View All
Overview
abstract
The session problem is an abstraction of fundamental synchronization problems in distributed systems. It has previously been used as a test case to demonstrate the differences in the time needed to solve problems in several timing models. The goal of this paper is to compare the computational power of a family of partially synchronous models by studying the time needed to solve the session problem. Four timing parameters are considered: the maximum and minimum process step times and message delays. Timing models are obtained by considering independently whether each parameter is known (i.e., is hard-wired into the processes' code) or unknown, giving rise to four shared memory models and 16 message passing models. The models are compared based on the time complexity, measured in real time, of the session problem. This paper presents a modular proof technique for obtaining asymptotically tight bounds on the time complexity of the session problem for the four shared memory models and the 16 message passing models. Timing information known in each particular model can be exploited by algorithms to count sessions in different ways. This paper reports five different counting algorithms. The matching lower bound for each model suggests that they are the optimal ways to count sessions. Based on these bounds, a lattice among unknown parameter models is constructed, which confirms the common belief that as more timing information is known in a model, the model behaves more like a synchronous system.
