Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

THE EFFECT OF RESTRICTIONS ON R LATIV~ PROCESSOR SPEEDS TD DIFFERENCES IN EFFICIENCY BETWEEN SYNCHRONOUS ANA ASYNCHRONOUS SYSTEMS

IP.com Disclosure Number: IPCOM000128213D
Original Publication Date: 1982-Dec-31
Included in the Prior Art Database: 2005-Sep-15
Document File: 9 page(s) / 32K

Publishing Venue

Software Patent Institute

Related People

Paul G. Spirakiz: AUTHOR [+3]

Abstract

A system of parallel processes is said to be asynchronous if each process has its own independent clock. We show here how prune to restrictions on relative speeds of processes are differences in efficiency between synchronous and asynchronous systems, indicated by other researchers in the past (see [Arjomandi, Fisher, Lynch, 81]. For any s.n, a particular distributed problem (the [s,n]-session problem) (defined in [Arjomandi, Fischer, Lynch, 81]) requires time at least [Equation ommitted] in any asynchronous system with relative speed ratio v and assuming the concurrency is modellled as nondeterminism in a single sequence of steps of processes. The same problem requires at least O(s loglog n) time in any asynchronous system with quadratic relative acceleration and the same model of concurrency. In general, if we can partition the "distributed time" t, required to solve the [s,n]-session problem, in m(t) segments (non-overlapping) of sizes [Equation ommitted] such that in each segment, a message written on any variable T cannot be propagated to more than n-1 variables in the duration of the segment, then a lower bound for time is the smallest t satisfying [Equation ommitted] On the contrary, the [s,n]-session problem can be solved in time s in a synchronous system and in time [Equation ommitted] in an asynchronous system of relative speed ratio v whose model of concurrency is only a partial order of steps of processors and "real" parallelism is allowed. .

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 19% of the total text.

Page 1 of 9

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

THE EFFECT OF RESTRICTIONS ON R LATIV~ PROCESSOR SPEEDS TD DIFFERENCES IN EFFICIENCY BETWEEN SYNCHRONOUS ANA ASYNCHRONOUS SYSTEMS

by Paul G. Spirakiz

Ocxaben 192

Technicat Repant No. 49

..m Thih wothz wah 4upponted .in pant 6y the NSF GnanWMCS79-21024

ABSTRACT

A system of parallel processes is said to be asynchronous if each process has its own independent clock. We show here how prune to restrictions on relative speeds of processes are differences in efficiency between synchronous and asynchronous systems, indicated by other researchers in the past (see [Arjomandi, Fisher, Lynch, 81]. For any s.n, a particular distributed problem (the [s,n]-session problem) (defined in [Arjomandi, Fischer, Lynch, 81]) requires time at least

(Equation Omitted)

in any asynchronous system with relative speed ratio v and assuming the concurrency is modellled as nondeterminism in a single sequence of steps of processes. The same problem requires at least O(s loglog n) time in any asynchronous system with quadratic relative acceleration and the same model of concurrency. In general, if we can partition the "distributed time" t, required to solve the [s,n]-session problem, in m(t) segments (non-overlapping) of sizes

(Equation Omitted)

such that in each segment, a message written on any variable T cannot be propagated to more than n-1 variables in the duration of the segment, then a lower bound for time is the smallest t satisfying

(Equation Omitted)

On the contrary, the [s,n]-session problem can be solved in time s in a synchronous system and in time

(Equation Omitted)

in an asynchronous system of relative speed ratio v whose model of concurrency is only a partial order of steps of processors and "real" parallelism is allowed. .

1. Introduction

New York University Page 1 Dec 31, 1982

Page 2 of 9

THE EFFECT OF RESTRICTIONS ON R LATIV~ PROCESSOR SPEEDS TD DIFFERENCES IN EFFICIENCY BETWEEN

SYNCHRONOUS ANA ASYNCHRONOUS SYSTEMS

[Arjomandi, Fischer, Lynch, 81] showed a lower bound for the distributed time needed to solve the [s,n]-session problem on any asynchronous system. This bound is O(slogn). The systems considered were assumed to have no restrictions in speed behavior of processes but the number of processes that could access any particular communicationchannel (shar.ed variable) was bounded. We indicate here that additional knowledge about relative processor speeds lowers the bounds presented in [Arjomandi, Fischer, Lynch, 81]. We also indicate that seemingly identical restrictions on speeds may lead to different performance when the model of concurrency is changed. The above seems to imply that the notion of "minimal round" (see [Arjomandi, Fischer, Lynch, 81] as a measure of time in a distributed system is not suitable for cases in which additional knowledge about number of steps of processes in each round exists.

2. LOWER BOUNDS

2.1 The Model Where Concurrency is Nondeterminism.

We foll...