Efficiency of semi-synchronous versus asynchronous systems: Atomic shared memory
Date
1993Author
Mavronicolas, MariosSource
Computers and Mathematics with ApplicationsVolume
25Issue
2Pages
81-91Google Scholar check
Metadata
Show full item recordAbstract
The s-session problem is studied in asynchronous and semi-synchronous shared-memory systems, under a particular shared-memory communication primitive-b-atomic registers-where b > 1 is an integer reflecting the communication bound in the model. A session is a part of an execution in which each of n processes takes at least one step an algorithm for the s-session problem guarantees the existence of at least s disjoint sessions. The existence of many sessions guarantees a degree of interleaving which is necessary for certain computations. In the asynchronous model, it is assumed that the time between any two consecutive steps of any process is in the interval [0,1] in the semi-synchtonous model, the time between any two consecutive steps of any process is in the interval [c,1] for some c such that 0 < c ≤ 1, the synchronous model being the special case where c = 1. All processes are initially synchronized and take a step at time 0. Our main result is a tight (within a constant factor) lower bound of 1 + min {⌊ 1 2c⌈, ⌊logb(n-1) - 1⌈}(s-2) for the time complexity of any semi-synchronous algorithm for the s-session problem. This result shows the inherent limitations on using timing information in shared-memory systems subject to communication bounds, and implies a time separation between semi-synchronous and asynchronous such systems. © 1992.