Efficiency of semisynchronous versus asynchronous networks

Abstract

The s-session problem is studied in asynchronous and semisynchronous networks. Processes are located at the nodes of an undirected graph G and communicate by sending messages along links that correspond to the edges of G. A session is a part of an execution in which each process 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. It is assumed that the (real) time for message delivery is at most d. 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 semisynchronous 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. For the asynchronous model, an upper bound of diam(G)(d + l)(s - 1) and a lower bound of diam(G)d(s - 1) are presented

diam(G) is the diameter of G. For the semisynchronous model, an upper bound of 1 + min{⌊1/c⌋ + 1, diam(G)(d + 1)}(s - 2) is presented. The main result of the paper is a lower bound of 1 + min{⌊1/2 c⌋, diam(G)d}(s - 2) for the time complexity of any semisynchronous algorithm for the s-session problem, under the assumption that d ≥ (d/min{⌊1/2 c⌋, diam(G)d}) + 2. These results imply a time separation between semisynchronous (in particular, synchronous) and asynchronous networks. Similar results are proved for the case where delays are not uniform. © 1994 Springer-Verlag New York Inc.