Time Bounds on Synchronization in a Periodic Distributed System
This paper studies the time required to solve the session
problem in a new timing model, called the periodic
model, for shared memory distributed systems. In the
periodic model, each process runs at a constant unknown
rate and different processes may run at different rates.
Nearly matching upper and lower bounds are shown on the
time complexity of the session problem in the model.
These bounds indicate the inherent cost of
synchronizing periodic processes in shared memory
distributed systems, and
the existence of inherent time complexity gaps among the
synchronous, periodic, and asynchronous timing models.
PS COPY