Impact of time on the session problem - Texas A&M University (TAMU) Scholar

The session problem is an abstraction of synchronization problems in distributed systems. It has been used as a test-case to demonstrate the differences in the time needed to solve problems in various timing models, for both shared memory (SM) systems and message-passing (MP) systems. In this paper, the session problem continues to be used to compare timing models quantitatively. The session problem is studied in two new timing models, the periodic and the sporadic. Both SM and MP systems are considered. In the periodic model, each process takes steps at a constant unknown rate; different processes can have different rates. In the sporadic model, there exists a lower bound but no upper bound on step time, and message delay is bounded. We show upper and lower bounds on the time complexity of the session problem for these models. In addition, upper and lower bounds on running time are presented for the semi-synchronous SM model, closing an open problem from [4]. Our results suggest a hierarchy of various timing models in terms of time complexity for the session problem.

Impact of time on the session problem Conference Paper