Show simple item record

dc.contributor.authorAttiya, H.en
dc.contributor.authorMavronicolas, Mariosen
dc.creatorAttiya, H.en
dc.creatorMavronicolas, Mariosen
dc.description.abstractThe 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 stepen
dc.description.abstractan 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]en
dc.description.abstractin 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 presenteden
dc.description.abstractdiam(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.en
dc.sourceMathematical Systems Theoryen
dc.titleEfficiency of semisynchronous versus asynchronous networksen
dc.description.endingpage571 Σχολή Θετικών και Εφαρμοσμένων Επιστημών / Faculty of Pure and Applied SciencesΤμήμα Πληροφορικής / Department of Computer Science
dc.description.notes<p>Cited By :8</p>en
dc.source.abbreviationMath.Systems Theoryen

Files in this item


There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record