Browse Prior Art Database

Optimal Computation of Global Sensitive Functions in Fast Networks

IP.com Disclosure Number: IPCOM000109624D
Original Publication Date: 1992-Sep-01
Included in the Prior Art Database: 2005-Mar-24
Document File: 6 page(s) / 349K

Publishing Venue

IBM

Related People

Cidon, I: AUTHOR [+3]

Abstract

In this article we find optimal algorithms for optimal distributed computation of "global sensitive" functions in the case that the computing time is some given P, and the communication time is some given C. (Roughly speaking, a global sensitive function is one that depends on every one of its inputs).

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 23% of the total text.

Optimal Computation of Global Sensitive Functions in Fast Networks

       In this article we find optimal algorithms for optimal
distributed computation of "global sensitive" functions in the case
that the computing time is some given P, and the communication time
is some given C.  (Roughly speaking, a global sensitive function is
one that depends on every one of its inputs).

      The common practice in distributed algorithms research was to
assume that the computation time is zero, and assign a cost only to
the communication.  (See, e.g., (1)).  This was justified at the
times that the communication was the bottleneck of a network.
However, lately there has been a dramatic increase in the capacity of
communication links so that we can no longer make this assumption.

      In (2) we have investigated the complement assumption, i.e.,
that of zero communication cost, with a charge only for the
computation is investigated.  However, if the network is large, then
the propagation delay may still be significant.  In addition, the
speed of the computation may increase in the future.  Thus, it  makes
sense to analyze distributed computations when the ratio between the
computation time and the communication time is given as a parameter.

      In this article we make the first step, by analyzing the
distributed computation of "global sensitive" functions in the case
that the computing time is some given P, and the communication time
is some given C.  Roughly speaking, a global sensitive function is
one that depends on every one of its inputs, though a more formal
definition will be given later.  Most "natural" functions are global
sensitive.  In addition to their theoretical importance they arise in
many applications, e.g., call set-up (3), directory search, parallel
computing and more.

      An optimal protocol is presented.
Model and Problem Definition

      The communication network is represented by a graph (V,E) where
V is the set of nodes and E is the set of bidirectional communication
links.  We denote |V| by n, and assume, without loss of generality,
that the nodes are numbered 1,2,...,n.  In this article the graph is
complete.

      Messages are assumed to arrive within finite but unbounded
time.  For purposes of time complexity analysis, we count computation
and communication delays separately.  (In the terms of (2), the
computation delay is the delay of the software, or system call
complexity and the communication delay is the delay of the hardware.)
In particular, we assume that the communication delays are upper
bounded by C time units and the computation delays are upper bounded
by P time units.  (Note that these upper bounds are for the purposes
of the time complexity analysis only and the algorithm operates
correctly even if delays are unbounded.)  Thus, we define
.   Time Complexity - The time complexity is then the maximal time
which may elapse from the algorithm starting point to...