Efficiency of semi-synchronous versus asynchronous systems: Atomic shared memory

Abstract

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.