On the Performance of Synchronized Programs in Distributed Networks with Random Processing Times and Transmission Delays.
A synchronizer is a compiler that transforms a program designed to run in a synchronousnetwork into a program that runs in an asynchronous network. The behavior of a simplesynchronizer, which also represents a basic mechanism for distributed computing and forthe analysis of marked graphs, was studied by S. Even and S. Rajsbaum (1990) under theassumption that message transmission delays and processing times are constant. Westudy the behavior of the simple synchronizer when processing times and transmissiondelays are random. The main performance measure is the rate of a network, i.e., theaverage number of computational steps executed by a processor in the network per unittime. We analyze the effect of the topology and the probability distributions of therandom variables on the behavior of the network. For random variables with exponentialdistribution, we provide tight (i.e., attainable) bounds and study the effect of abottleneck processor on the rate.
INTRODUCTION
Consider a network of processors which communicate by sending messages along communication
links. The network is synchronous if there is a global clock whose beats are heard by
all the processors simultaneously, and the time interval between clock beats is long enough
for all messages to reach their destinations and for local computational steps to be completed
before the clock beats again. The network is asynchronous if there is no global clock, and the
transmission times of messages are unpredictable.
Computer Science Department. Present address: Instituto de Matematicas-UNAM, Ciudad Universitaria,
D.F. 04510, Mexico. (rajsbaum@redvax1.dgsca.unam.mx)
y Electrical Engineering Department (moshe@techsel)
In general, a program designed for a synchronous network will not run correctly in an
asynchronous network. Instead of designing a new program for the asynchronous network, it
is possible to use a synchronizer, [A1], i.e., a compiler that converts a program designed for
a synchronous network, to run correctly in an asynchronous network. Synchronizers provide
a useful tool because programs for synchronous networks are easier to design, debug and test
than programs for asynchronous networks. Furthermore, an important use of synchronizers is
the design of more efficient asynchronous algorithms [A2]. The problem of designing efficient
synchronizers has been studied in the past (e.g. [A1], [AP90], [PU89]).
The (worst case) time complexity of a distributed algorithm is usually computed assuming
that processing times and message transmission delays are equal to some constant which
represents an upper bound on these durations. The goal of this paper is to study the effect
of random processing times and transmission delays on the performance of synchronous programs
running in an asynchronous network under the control of a simple synchronizer. We
compare the results with the deterministic case [ER1], [ER2], in which processing times, as
well as message delays, are constant (or bounded).
The operation of the synchronizer is as follows: Each processor waits for a message to
arrive on each of its in-coming links before performing the next computational step. When
a computational step is completed (after a random time), it sends one message on each of
its out-going links. The implementation of this synchronizer may require, for instance, that
every message is followed by an end-of-message marker, even if the message is empty. These
end-of-message markers model the flow of information that must exist between every pair of
processors connected by a link in each computational step [A2]. This is how a processor knows
it has to wait for a message which was sent to it, or if no message was sent.
We use this synchronizer in our analysis since it is very simple, yet, it captures the essence
of the synchronizer methodology, i.e., it ensures that a processor does not initiate a new
phase of computation before knowing that all the messages sent to it during the previous
phase have already arrived. Moreover, the synchronizer is equivalent to a marked graph (e.g.
[CHEP]) in which the initial marking has one token per edge. In [Ra91] and [RM92] the
relationship between synchronizers and marked graphs is studied, and it is shown how the
simple synchronizer can model the behavior of any marked graph, of the synchronizers of
[A1], and of distributed schedulers in [BG89], [MMZ88]. Thus, our work is closely related to
problems in stochastic petri nets, where, due to the huge size of the state space, the solution
techniques often rely on simulation (e.g. [M1], [M2], [Ma89]).
Many distributed protocols are based on this simple synchronizer. For example, the snap-shot
algorithm [CL85], clock synchronization algorithms (e.g. [BS88], [OG87]), the synchronizers
of [A1], the distributed schedulers in [BG89], [MMZ88], the optimistic synchronizer
[GRST92]. The synchronizer is similar to synchronizer ff in [A1], but can be be used also in
directed networks, as opposed to other synchronizers suggested in [A1] that require all links to
be bidirectional. In [ER1] and [ER2] the benefits of using the synchronizer as an initialization
procedure are described.
Main Results
This paper is devoted to the performance analysis of strongly connected directed networks
controlled by the simple synchronizer, in which transmission delays, as well as the time it takes
a processor to complete a computational step are random variables. Our main performance
measure is the rate of computation R v , i.e., the average number of computational steps executed
by a processor in the network, per unit time. To facilitate the presentation, we first assume
that the transmission delays are negligible, and only at the end of the paper describe how to
extend the results for networks with non-negligible delays.
In Section 3 we study the case in which the random variables have general probability
distributions. We consider two approaches. First (Section 3.1) we analyze the effect of the
topology on the rate. We use stochastic comparison techniques to compare the rate of networks
with different topologies. We give examples of networks with different topologies, but
with the same rate. Then (Section 3.2) we analyze networks with the same topology but different
processing times. By defining a partial order on the set of distributions, we show that
deterministic (i.e. constant) processing times maximize the rate of computation. For this case,
it is shown in [ER1] that if the processing times are equal to - \Gamma1 , the rate of the network is -,
regardless of the number of processors in the network or its topology. In the next section we
show that in case the processing times are random and unbounded, the rate may be degraded
by a logarithmic factor in the number of processors. This occurs in the case of exponentially
distributed processing times. However, in this section we show that the exponential is the
worst, among a large and natural class of distributions (it yields the minimum rate within a
class of distributions).
In Section 4 we concentrate on the case of processing times that are exponentially distributed
random variables with mean - \Gamma1 . We prove that the rate is between -=4
and -= log(ffi is the maximum (minimum) vertex in-degree or out-degree.
Hence, for regular-degree (either in or out-degree) networks, the rate is \Theta(-= log(ffi
compute the exact rate and the stationary probabilities for the extreme cases of a directed
cycle and a complete graph. Finally, we study the effect of having one processor that runs
slower than the rest of the processors, and we show that in some sense, the directed cycle
network is more sensitive to such a bottleneck processor than a complete network.
In the last section we show that it is easy to extend the results to networks with non-negligible
transmission delays. We consider the exponential distribution case, and show that
adding transmission delays to a regular degree network may reduce its rate by at most a
constant factor, provided that they are not larger (w.r.t. the partial order) than the processing
times. In networks with processing times exponentially distributed with mean 1, and larger
delays with mean - \Gamma1 , we compare the results with those of [ER2], where it was shown that for
the corresponding deterministic case the rate is -. In the probabilistic case of a regular-degree
network, the rate is at least \Theta(-= log ffi). Thus, in both cases (small and large delays), the rate
of a bounded degree network is reduced only by a constant factor.
Previous Work
There exist several results related to our results in Section 3.2 in the literature on stochastic
petri-nets. For instance, dominance results for rather general stochastic petri-nets have been
obtained in [Ba89] and more recently in [BL91] by using Subadditive Ergodic Theory (e.g.
[K73]). It should be noted, however, that the proofs we provide for the simple synchronizer
are different and much simpler and do not require heavy mathematical tools. Other stochastic
ordering studies exist. Papers on acyclic networks and fork-join queues are [PV89] and [BM89,
BMS89, BMT89], respectively. For closed queueing networks the effect of increasing the service
rate of a subset of stations for systems such that the distribution of the number of works in
each station has a product form solution is studied in [SY86].
A model similar to our model in Section 4 is considered in [BT89], where it is claimed
that the rate is '(1= log ffi out ), for regular networks with out-degree equal to ffi out , identically
exponentially distributed transmission delays with mean 1, and negligible processing times.
In [BS88] only a lower bound of \Theta(1= log ffi in ) on the rate is given, for regular networks with
in-degree equal to ffi in , with negligible transmission delays, and identically exponentially distributed
processing times. Recently, it has been shown in [BK91] that subadditive ergodic
theory can be used to derive more general lower bounds on the rate. A bottleneck problem
related to ours has been considered by [B88] where an asymptotic analysis of cyclic queues as
the number of costumers grows is presented. Asymptotic performance of stochastic marked
graphs as the number of tokens grows is studied in [M2]. The class of networks with exponentially
distributed processing times belongs to the more general model of stochastic petri nets
(see [Ma89] for a survey), where it is usually assumed that the state space (of exponential size,
in our case) is given.
The network is modeled by a (finite) directed, strongly connected graph G(V; E), where
ng is the set of vertices of the graph and E ' V \Theta V is the set of directed edges. A
vertex of the graph corresponds to a processor that is running its own program, and a directed
edge corresponds to a communication link from processor u to processor v. In this case,
we shall say that u is an in-neighbor of v, and v is an out-neighbor of u in the network. The
processors communicate by sending messages along the communication links. To facilitate the
presentation, we assume that the message transmission delays are negligible. At the end we
briefly discuss the case of non-negligible transmission delays.
Initially, all processors are in a quiescent state, in which they send no messages and perform
no computations. Once a processor leaves the quiescent state, it never reenters it and is
considered awake. When awakened, each processor operates in phases as described in the
sequel. Assume that at an arbitrary time, t(v), processor v leaves the quiescent state and
enters its first processing state, PS 0 (this may be caused by a message from another processor,
or a signal from the outside world, not considered in our model). Then, processor v remains in
units of time and then transits to its first waiting state, WS 0 . ?From this time
on, let PS k and WS k , k - 0, denote the processing state and the waiting state, respectively,
for the k-th phase. Observe that we are concerned with the rate of computation of the network;
the nature of the computation is of no concern to us here. Thus we take the liberty of denoting
with the same symbol the k-th processing state of all the processors.
The transition rules between states are as follows: If a processor v transits from state PS k
to WS k , it sends one message on each of its outgoing edges. These messages are denoted by
. Note that this labeling is not needed for the implementation of the protocol; it is used
only for its analysis. When v sends the M k messages, we say that v has completed its k-th
processing step.
If a processor v is in state WS k , and has received a message (M k ) on each of its incoming
edges, it removes one message from each of its incoming edges, transits to state PS k+1 , remains
there for - k+1 (v) units of time and then transits to state WS k+1 . Otherwise, (if at least on one
incoming edge, M k has not yet arrived) processor v remains in state WS k until it receives a
message from each of its in-neighbors, and then operates as described above.
The processing times, - k (v), correspond to the time it takes for processor v to complete
the k-th computation step. The processing times - k (v), k - 0, are positive, real-valued
random variables defined over some probability space.
For
k (v) (or t k (v), whenever G is understood) be the k-th completion time, i.e.,
the time at which processor v sends messages M k in network G. Let the in-set of a vertex v in
G, IN G (v) ( or simply IN(v)), be the set of vertices in G that have an edge to v, including v
itself, that is, fvg. With this notation, the operation of processor
is as follows. Once v has sent a message M k at time t k (v), it waits until all processors
with an edge to it send message M k , and then starts its 1)-st computation step; that is,
after the maximum of t k (u), u 2 IN(v), it starts the 1)-st computation step, which takes
units of time, and then sends out M k+1 . For this reason we shall assume in the rest of
the paper that for each vertex v the edge v ! v is in E. The evolution of the network can be
described by the following recursions:
(1)
It is interesting to note that the completion times t k (v) have a simple graph theoretic
interpretation. For a vertex v, let S k (v) be the set of all directed paths of length k ending in v.
For 0, the only path of length 0 ending in v consists of v itself. For a path P
(v)g. Thus,
is a set of random variables; each one is the sum of k+1 random variables. Note that
these random variables are not independent, even if the - i (v)'s are independent. The explicit
computation of t k (v) is as follows.
Theorem 2.1 For every
Proof: By induction on k. For note that the only path of length 0 to v, is v itself, i.e.
(v)g. Hence,
Assume that the Theorem holds for k - 0. From the recursion above we have that
By the inductive hypothesis,
which gives the desired result
The Performance Measures
The most important performance measures investigated in this paper are the completion
times t k (v), k - 0, v 2 V . A related performance measure of interest is the counting process
t (v) (or simply N t (v)), associated with processor v defined by
that is, N t (v) is the number of computation steps (minus 1) completed by v up to time t,
or the highest index of an M k message that has been sent by v up to time t. Similarly,
denotes the total number of processing steps (minus n) executed in the
network up to time t. The following claim indicates that no processor can advance (in terms
of executed processing steps) too far ahead of any other processor.
2.2 Let d be the diameter of a directed, strongly connected graph G. Then for all
Proof: Denote by l the length of a simple path from u to v. A simple inductive argument
on l, shows that the fact that the last message sent by u up to time t is MN t (u) , implies that
d. The same argument for a simple path from
v to u proves that N t (u) \Gamma N t (v) - d.
Another important performance measure is the computation rate, R G (v), (or simply R(v))
of processor v in network G, defined by
whenever the limit exists. Similarly, the computation rate of the network is defined by
R \Delta
2.2 implies that for every u;
3 GENERAL PROBABILITY DISTRIBUTIONS
In this section we compare the performance of different networks, with general distributions
of the processing times - k (v). We first show that adding edges to a network with an arbitrary
topology slows down the operation of each of the processors in the network. We show how
the theory of graph embedding can be used to compare the rates of different networks. As
an example we present graphs, which have the same rate (up to a constant factor) for general
distributions, although they have different topologies. Finally, we compare networks with the
same (arbitrary) topology but different distributions of the processing times. Specifically, we
show that determinism maximizes the rate, and exponential distributions minimize the rate,
among a large class of distributions.
3.1 Topology of the Network
3.1.1 Monotonicity
Here we show that adding edges to a network with an arbitrary topology slows down the operation
of each of the processors in the network. The basic methodology used is the sample
path comparison; that is, we compare the evolution of message transmissions in different networks
for every instance, or realization, of the random variables - k (v). This yields a stochastic
ordering between various networks [Ro83], [S84].
Theorem 3.1 Let G(V; E) be a graph, and E be a set of directed edges. Let
be the graph obtained from G by adding edges Assume that processor v,
awakens in both G and H at the same time t(v). For every realization of the
random variables - k (v), k - 0, 1 - v - n, the following inequalities hold
Proof: The proof is by induction on k. The basis of the induction is trivial since
The induction hypothesis is t G
(v). We need to show that t G
(v). ?From
equation (1) we have that
Since IN G (v) ' IN H (v), it follows that
and therefore it follows from (2) that t G
k+1 (v), for all v.
The previous theorem implies immediately
Corollary 3.2 Under the conditions of Theorem 3.1 we have that N G
t (v) and
R G (v) - R H (v) (when the limits exist) for all v 2 V . Also N G
t .
Remark 1 Notice that no assumption was made about the random variables - k (v). In partic-
ular, they need not be independent.
Remark 2 The sample path proof above implies that the random variable N G
t is stochastically
larger than the random variable N H
t , denoted N G
all ff.
Remark 3 The above implies that if one starts with a simple, directed cycle (a strongly connected
graph with the least number of edges) and successively adds edges, a complete graph is
obtained, without ever increasing the rate.
3.1.2 Embedding
The theory of graph embedding has been used to model the notion of one network simulating
another on a general computational task (see for example [R88]). Here we show how the
notion of graph embedding can be helpful in comparing the behavior and the rates of different
networks controlled by the synchronizer.
An embedding of graph G in graph H is specified by a one-to-one assignment ff
of the nodes of G to the nodes of H , and a routing ae : EG ! Paths(H) of each edge of G along
a distinct path in H . The dilation of the embedding is the maximum amount that the routing
ae "stretches" any edge of G:
The dilation is a measure of the delay incurred by the simulation according to the embedding.
The following theorem is a generalization of Theorem 3.1.
Theorem 3.3 Let (ff; ae) be an embedding with dilation D, of a graph G(VG ; EG ) in a graph
have the same distribution. For every realization of the random variables
the following inequalities hold
Proof: For each path of length k - 0 in G,
one can use ae to construct a path in H of length less than or equal to k \Delta D from ff(v 0 ) to ff(v k ),
passing through ff(v 1
Moreover, there is such a path of length exactly k \Delta D, since one can revisit vertices (each vertex
has a selfloop) each time between a pair of vertices ff(v i ), and ff(v i+1 ), there are less than D
edges in the path ae(v there is a path in H :
where
We are assuming a realization - k for every u 2 VG . It follows that for
every path P G
k , there exists a path P H
kD , such that
and thus
By Theorem 2.1, t G
kD (ff(v)).
Corollary 3.4 Under the conditions of Theorem 3.3 we have that D \Delta N G
t (ff(v)) and
D (when the limits exist) for all v 2 VG .
Remarks 1-3 hold in this case too.
A simple corollary of Theorem 3.3 is that if G is a subgraph of H , N G
This is because if G is a subgraph of H , then there is an embedding from G in H with dilation 1.
In addition, if the number of vertices in G and H are equal, and the dilation of the embedding
is D, then G is a D-spanner of H (e.g. [PS89], [PU89]), and we have the following.
Corollary 3.5 If H has a D-spanner G, then R G =D - R H - R G .
A motivation for the the theory of embedding is simulation. Namely, one expects that
if there is an embedding (ff; ae) from G in H with dilation D, then the architecture H can
simulate T steps of the architecture G on a general computation in order of D \Delta T steps, by
routing messages according to ae. In our approach, we compare the performance of G and of H
under the synchronizer, without using ae; the embedding is used only for the purpose of proving
statements about the performance of the networks. Consider for example the following two
results of the theory of embedding [R88].
Proposition 3.6 For all One can embed the order n Shuffle-Exchange graph in the
order n deBruijn graph with dilation 2. One can embed the order n deBruijn graph in the order
n Shuffle-Exchange graph with dilation 2.
Proposition 3.7 For all One can embed the order n Cube-Connected-Cycles graph in
the order n Butterfly graph with dilation 2. One can embed the order n Butterfly graph in the
order n Cube-Connected-Cycles graph with dilation 2.
By Theorem 3.3, the average rate of the graphs of Proposition 3.6 (3.7) are equal up to a
constant factor of 2, provided that the processing times of corresponding processors have the
same distributions (regardless of what these distributions are).
3.2 Probability Distributions
3.2.1 Deterministic Processing Times
Now we compare networks, say G(V; E)and H(V; E), having the same (arbitrary) topology, but
operate with different distributions of the random variables - k (v). To that end, we assume that
the processing times - G
are independent and have finite mean E[- G
v .
We say that - v is the potential rate of v, as this would be the rate of v if it would not have
to wait for messages from its in-neighbors. The processing times in H are distributed as in
G except for a subset V 0 ' V of processors, for which the processing times are assumed to
be deterministic, i.e. - H
specific realization of the random variables in G. Again, it is assumed that the
processors are awakened at the same time in both networks.
Theorem 3.8 Under the above conditions we have that
for all processors v, and k - 0. The expectation is taken over the respective distributions of
processing times of processors of G in V 0 .
Proof: The proof is by induction on k. For the basis, observe that
for
for
The induction hypothesis is t H
k (v)], and we need to show that t H
for all
?From (1) we have that
for . Jensen's inequality implies
By the induction hypothesis,
since E[- G
Remark 4 Theorem 3.8 holds also if the processing times - H
k (v) of processors v of H in V 0 ,
are deterministic, but not necessarily the same for every k.
When all processing times in the network H are deterministic, the computation of the
network rate is no longer a stochastic problem, but a combinatorial one. Thus, a conclusion
of Theorem 3.8 is that in this case, the computation rate of H , obtained via combinatorial
techniques ([ER1] and [ER2]), yields an upper bound on the average rate of G. Furthermore,
if the times t H
k (v) are computed, they give a lower bound on E[t G
k (v)], for every k - 0.
3.2.2 More Variable Processing Times
More generally, we study the effect of substituting a random variable in the network (e.g. the
processing time of a given processor, for a given computational step) with a given distribution,
for a random variable with another distribution on the rate of the network, and define an
ordering among probability distributions.
Recall that a function h is convex if for all
distribution FX is said to be more variable than
a random variable Y with distribution F Y , denoted X- c Y or FX- c F Y , if E[h(X)] - E[h(Y )]
for all increasing convex functions h. The partial order - c is called convex order (e.g. [Ro83],
[S84]). Intuitively X will be more variable than Y if FX gives more weight to the extreme
values than F Y ; for instance, if E[X
convex function.
Here we compare networks, say G(V; E) and H(V; E) having the same arbitrary topology,
but some of the processing times in G are more variable than the corresponding processing
times in H , i.e., for some k's and some v's, - G
k (v), while all other processing times
have the same distributions in both graphs. When t G processing times in
G (H) are independent of each other, the following holds.
Theorem 3.9 Under the above conditions the following holds for all processors v, and k - 0
Proof: ?From Theorem 2.1 we have
where is a directed path of length k ending in v, and
?From the fact that the - 's are positive and max and
are convex increasing functions,
it follows that t k (v) is a convex increasing function of its arguments f-
(v)g. Now we can use Proposition 8.5.4 in [Ro83]:
Proposition 8.5.4: If are independent r.v., and Y are independent
r.v., and
increasing convex function g which are convex in each of its arguments.
The proof of the theorem now follows since by assumption the - 's in G are independent, the
- 's in H are independent, and - H
. Note that the random variables
are not independent.
Corollary 3.10 Under the above conditions N G
t (v), R G (v) - R H (v) and R G - R H .
In the next section we show that if the processing times are independent and have the same
exponential distribution with mean - \Gamma1 , then the rate of any network is at least -jV log jV j.
We conclude this subsection by characterizing a set of distributions for which the same lower
bound holds.
Assume that the expected time until a processor finishes a processing step given that it
has already been working on that step for ff time units is less or equal to the original expected
processing time for that step. Namely, we assume that the distributions of the processing
times - k (v), for all are new better than used in expectation (NBUE) (e.g. [Ro83],
[S84]), so that if - is a processing time, then
Let G d (V; E) be a network with deterministic processing times, let G e (V; E) be a network
with corresponding processing times with the same mean, but independent, exponentially
distributed, and let G(V; E) be a network with corresponding processing times with the same
mean and independent, but with any NBUE distribution. The following theorem follows from
the fact that the deterministic distribution is the minimum, while the exponential distribution
is the maximum with respect to the ordering - c , among all NBUE distributions [Ro83], [S84].
Theorem 3.11 For every holds that t Gd
(v).
Some examples of distributions which are less variable than the exponential (with appropriate
parameters) are the Gamma, Weibull, Uniform and Normal.
We should conclude this section by pointing out that the interested reader can find similar
results for rather general stochastic petri-nets in [Ba89] and [BL91].
In this section we assume that the processing times - k (v), k - 0, are independent and
exponentially distributed with mean - \Gamma1 . We first consider general topologies and derive upper
and lower bounds on the expected values of t k (v), and thus obtain upper and lower bounds on
the rate of the network. These bounds depend on the in-degrees and out-degrees of processors
in the network, but not on the number of processors itself. Then, exploring the Markov chain
of the underlying process, we derive the exact rates of two extreme topologies: the directed
ring and the fully connected (complete) network. For these two topologies we study also the
effect of having a single slower processor within the network.
4.1 Upper and Lower Bounds
Denote by d out (v) (d in (v)) the number of edges going out of (into) v in G, and let
d out
d in (v);
d out (v) ; ffi in = min v2V
d in (v):
Lemma 4.1 (Lower Bound)
(i) For every k - 0 there exists a processor v 2 V for which
(ii) For every k - 0, and every v 2 V , the following holds
log ffi in ]:
Proof: We present a detailed proof for part (i) only; the proof of part (ii) is discussed at the
end. We start by proving that for every k - 0, there exists a (not necessarily simple) path
, such that
We assume the statement holds for k - 0, and prove it for k + 1. The proof of the basis
is identical. Let v k+1 be the processor for which the processing time during the
computational step is maximum, among the out-neighbors of v k , i.e.,
not start the 1)st computational step before v k finishes the kth computational
step, we have that t k+1 (v k+1
to the maximum of at least ffi out independent and identically distributed exponential random
variables with mean - \Gamma1 . It is well known (e.g. [BT89], [D70]) that the mean of the maximum
of c such random variables is at least - \Gamma1 log c. It follows that
We can chose v 0 to be the one with latest waking time t(v 0 ), and thus E[t 0 (v
Therefore, for every k - 0, there exists a processor v such that
completing the proof of (i). The proof of part (ii) evolves along the same lines, except that we
start from v k and move backwards along a path.
Remark 5 ?From its proof, one can see that Lemma 4.1 holds for any distribution F of the
processing times, for which the expected value m c of the maximum of c independent r.v. with
distribution F exists. In this case it implies that R v - 1=m c , with
Remark 6 Lemma 4.1 implies that for the exponential case, the slowdown of the rate is at
least logarithmic in the maximum degree of G. By Remark 5, there are distributions (not
NBUE, by Theorem 3.11) for which the slowdown is larger; an example is F
which the slowdown is at least the square root of the maximum degree of G ([D70]
pp. 58).
Lemma 4.2 (Upper Bound)
(i) For every k - 1, for every processor v,
log \Delta in
(ii) For every k - 1, for every processor v,
Proof: Again we restrict ourselves to the proof of part (i). Recall that Theorem 2.1 states
that for every (v)). Also, for a path P
for the moment let
By Proposition D.2 of the Appendix,
Pr
ck
log \Delta in
ck
log \Delta in ;
for every c ? 4, since log 2= log \Delta in - 1. It follows that
Pr
ck
log \Delta in
in ck
log \Delta in = e \Gammak( c
log \Delta in ;
for every c ? 4, and
Z 4k
log
log \Delta in
e \Gammak( c
log \Delta in
log
Combining Lemma 4.1 and Lemma 4.2 we obtain:
Theorem 4.3
log
log
4.2 Exact Computations
Theorem 4.3 implies the following bounds for the rate of a directed cycle C n
of a complete graph K n is the number of processors:
0:36- R Cn (v) -;
4 log n
log n
In this section we shall compute the exact values for the rates of C n and K n . To that end
we consider the Markov chain associated with the network This Markov chain is denoted by
is the number of messages stored in the buffer
of edge i at time t, and m is the number of edges in the network. Note that a processor with
positive number of messages on each of its in-coming edges is in a processing state. When such
a processor completes its processing (after an exponential time), one message is deleted from
each of its in-coming edges and one message is put on each of its out-going edges. We denote
by s 0 the state in which X i m. Thus, the network can be represented as a
Marked Graph (e.g. [CHEP]).
The number of states in the Markov chain is finite, say N , because a transition of the chain
does not change the total number of messages in a circuit in the network. Moreover, if the
network is strongly connected, then the Markov chain is irreducible. Therefore, the limiting
probabilities of the states s i of the chain exist, they are all positive and their
sum is equal to 1 (e.g. [C67],[Ro83]). However, as we shall see, N can be exponential in n,
therefore it is infeasible to compute the rate by directly solving the Markov chain. Here we
show how to solve the Markov chain for two network classes, without having to produce the
entire chain. We hope this combinatorial approach could be applied to other networks as well.
Let GX denote the transition diagram (directed graph) of the Markov chain X . Consider a
BFS (breadth first search) tree of GX , rooted at s 0 . The level L(v) of a vertex v will be equal
to the distance from s 0 to v. Thus, L(s 0 0, the set of vertices at level
i, and by L the number of levels of GX .
4.2.1 A Simple Directed Cycle
We study the performance of a simple directed cycle of n processors C
It is not difficult to observe that the Markov chain associated with C n , corresponds
to that of a closed queuing network; we return to this approach later. Here we choose to use
a combinatorial approach.
Theorem 4.4
(i) All the states associated with C n , have the same limiting probability.
(ii) For any graph G which is not a simple directed cycle (i) does not hold.
Proof: (i) The proof follows from two observations. First, by symmetry, all the states in
one level have the same probability. Second, the indegree of any state in the transition diagram
is equal to its outdegree. Then a simple inductive argument can be used to prove part (i).
(ii) If G is not a cycle, then it has a node v, s.t. d in (v) ? 1. Let be two nodes with
edges to v. Consider the state s, reached from s 0 , by the processing completion (or in marked
graphs terminology, firing) of vertex v. The outdegree of s is equal to n \Gamma 1, because apart
from v, all vertices are still enabled. But the indegree of s is at most n \Gamma 2, because by the
firing of v 1 , or of v 2 it is not possible to reach s, since there are no messages on the edges from
to v, in s. Therefore, we have proved that d in (s) 6= d out (s).
Consider the balance equation that holds at state s: P
are the limiting probabilities of the states that have an edge to s,
is the limiting probability of s, and We have just proved that k 6= n \Gamma 1. It
follows that it is not possible that all the probabilities of the last equation are equal.
The next theorem states that each processor of C n works at least at half of its potential
rate -, regardless of the value of n.
Theorem 4.5 The rate R(v) of a processor in C n is
and the limiting probability of each state is 1=N , where N is the number of states in the
associated chain.
Proof: If M is the number of states in which at least one message is in an edge, going into
a processor, say v, then the running rate will be M=N times the expected firing rate. This
is because v will be enabled when it has more than 0 messages in its input edge, and since
all states have the same probability (Theorem 4.4), the percent of the time that is enabled is
simply, M=N .
The number of ways of putting n objects in k places is
It is not difficult to see that
which gives the desired results.
4.2.2 A Complete Graph
Let K n be a complete graph with n processors. Recall that N is the number of states in the
associated Markov chain, and let s 0 be the state in which each edge has one token. A state is
at level l, 0 - l - can be reached from s 0 by the firing of l processors. The limiting
probability of a state at level l is denoted by P (l).
Theorem 4.6 : The rate of a processor in K n is
log n
Proof: A simpler proof can be derived as in the proof of Theorem 4.10; here we give a
combinatorial proof which also yields the number and the limiting probabilities of the states
of the associated Markov chain.
We consider a Markov chain T , similar to the Markov chain associated with network K n .
The root of T , s 0 , is the state with a message in each edge. A state s will have one son for
each one of the enabled processors at state s; a son of s corresponds to the state arrived from
s by the firing (completion of a processing step) of one of the enabled processors in state s.
Note that in chain T there are several vertices corresponding to the same state of the chain
associated with K n .
In T , the number of states in level l is n!=(n \Gamma l)!, because each time a processor fires it
can not fire again until the rest of the processors have fired. Thus, the number N T , of states
in T is
The number of states in which a given processor is enabled at level l, en(l) (edges from level l
to level l + 1), is
because at level l there are n!=(n \Gamma l \Gamma 1)! enabled processors, and by symmetry, each processor
is enabled the same number of times at each level.
Let us denote by P T
l , the limiting probability of a state of T in level l. One can show that
It follows that the percent of time that a processor is enabled is
l , and its rate is - \Delta ut.
Corollary 4.7 For a network K n ,
Proof: As noted before, it may be that two states of T correspond to the same state, say s,
of K n . In fact, if a state of T is reached from s 0 by firing a sequence of processors of length k,
then all k! permutations of the processors in this sequence constitute a valid firing sequence,
which leads to the same state s. Thus, the limiting probability of a state s at level l is
The number of different states at level l is n!=l!(n \Gamma l)!, and the total number of different
states is
Corollary 4.8 Asymptotically, the rate of any network of n processors is between -n=2 and
-n= log n.
Observe that the best possible rate of a processor is 2=3 of the potential rate, in the case
of a cycle of two processors; adding more processors can only lower this rate, but not below
1=2. Yet, the rate of the network grows linearly with n. In the case of a complete graph, the
rate of a processor reduces as n grows, but also here the total number of computational steps
executed per unit time (n= log n) grows with n.
4.3 Bottlenecks
Suppose that the potential rate of all processors of a graph is -, except for one, which has a
lower rate -. We shall now show that such a bottleneck has a stronger effect in a network
which is a directed cycle, than in one which is a complete graph.
Consider the case of a simple directed cycle with n vertices CB n , where processors
have rate -, and one processor has rate -. Using standard techniques of Queuing Theory, we
prove the following.
Theorem 4.9 The rate of a processor in CB n is
ae n
be the number of messages in the buffer of the incoming edge
to processor i. The total number of messages in the cycle is equal to n. Since this is a
closed queueing system, we have that the limiting probability of the system being in state
given by the following product form [Ro]:
if
and is equal to 0 otherwise, where K is a normalization constant that guarantees that the sum
of all the above probabilities is equal to 1. Thus, the probability of having l messages on the
incoming edge to processor n is
lg. Hence,
where K 0 is the normalization factor determined by the condition
Finally,
ae l
Now, observe that the rate is simply as the rate of the processor is -
while there are messages in the incoming edge to processor n.
Several conclusions can be derived from Theorem 4.9. First, observe that the rate of the
cycle cannot exceed -n, thus the slow processor bounds the rate of the network. Moreover,
for a fixed n and a very slow processor (- ! 0 or ae ! 1), the rate of the network is
ae \Gamman ], namely, as ae increases, the rate approaches its upper bound -n.
Next, we consider the case where the graph is a complete graph KB n . We continue to
assume that the rate of processors is - and the n-th processor is slower, operating at
rate -. We shall show that, for fixed - and -, as the number of processors n grows to infinity,
the influence of the slow processor diminishes, and in the limit, the rate of the network is the
same as that of a network with all processors running with the same rate -.
Theorem 4.10 The rate of a processor in KB n is at least -
Proof: Suppose that the network is in state s 0 at a given time, and after some time T 1 it returns
to that state; then after some time T 2 it returns again, and so on. Then, fT
is a sequence of non-negative independent random variables with a common distribution F ,
and expected value E[T i ].
Denote by N(t) the number of events (returning to s 0 ) by time t. The counting process
is a renewal process. Therefore, with probability 1,
(See, for example [Ro83]). Moreover, since each time the process returns to s 0 , each processor
of the network has completed exactly one computational step, it follows that the rate of the
network is 1=E[T i ]. We proceed to bound E[T i ].
The expected time of T i , that takes to return to s 0 is of the form:
for some 1 - j - n, depending on when the slow processor completes a computational step. If
the system leaves s 0 because the slow processor completed a computational step, E[T i ] is ff 1 .
In general, if the j-th (1 - j - n) processor to complete a computational step, after leaving
is the slow processor, then E[T i ] is ff j .
The probability of E[T j ] being equal to ff j , is not necessarily the same for every j, but for
the case -, it holds that ff j ! ff j+1 . Thus,
gives an upper bound on the time E[T ] that takes to return to s 0 , and 1=ff n , is a lower bound
on the rate of a processor in the network.
We have
--
log n:
We see that E[T i
log n) and thus R(KB n ) is at least 1-
For fixed -, R v is \Theta(-= log n), but observe that the rate of the network cannot exceed
-. However, when the number of processors n increases to infinity, the rate of the network
decreases in proportion to 1= log n, as if the slower processor is not in the network.
We briefly discuss the case of non-negligible transmission delays. In this model the processing
times are random, as before, but the transmission delays are also random. Denote the transmission
delay of message M k , k - 0, along edge
It follows that the behavior of the system is described by the recursions
Note that this system is not equal to the one of [BT89], in which the processing times are
negligible , and the delays non-negligible, with a self-loop in each processor (to model its
processing delay).
v) be a path of length k. It is easy to see how to modify
the definition of T (P k
Thus a theorem similar to Theorem 2.1 holds, and the corresponding results for general distributions
Consider the case in which the processing times, as well as the transmission delays are
exponentially distributed, with the same mean, say 1. It is easy to see that Lemma 4.1 still
holds, and that Lemma 4.2 holds up to a factor of 2. Namely, by Theorem 3.9, a regular
network with non-negligible delays runs at the same rate that the same network, up to a
constant factor, provided that the delays are less or equal (in the convex order) than the
processing times. In [ER1] we show that for a network with negligible delays and deterministic
processing times equal to 1, the rate of any network is equal to 1. Thus, in this case, random
processing times degrade the rate by at most a logarithmic factor in the maximum degree of
a processor.
Now, consider the case in which all processing times have mean 1, but the delays have
exponentially distributed. The rate in the deterministic case is
equal to - [ER2], and thus, by Theorem 3.3, in our case the rate is at most -. One can prove
(using Proposition D.2 ), that also in the case of non-negligible delays, the rate is degraded
by at most a logarithmic factor in the maximum degree of a processor, with respect to the
(optimal) deterministic case, for any NBUE distribution.
As for the exact computations for networks with average processing times and delays exponentially
distributed with mean 1, the rate of a simple cycle can be computed using the
same tools of Queuing Theory that we used in the case of negligible delays. To compute the
rate of a complete network K n things are not as straightforward; the structure of the Markov
process is more complicated, but by the arguments above, we have that the rate is between
1=8 log n and 1= log n. However, using the ideas of embedding, let us show that the rate of K n ,
is at least 1=4 log n. Let K 0
n be a complete network with negligible delays. Construct G, from
n by inserting one vertex in each of its edges. By Theorem 3.1 (or also 3.9), the rate of any
processor in G is at leastlog(n
One can show that the rate of any processor v in K n is greater or equal than half the rate of
the corresponding processor in G, using using the fact that there is an embedding of K n into
G of dilation 2. Therefore, the rate of v in K n is at least 1=4 log n.
6 CONCLUSIONS
In this paper we have studied the behavior of synchronizers in networks with random transmission
delays and processing times. We attempted to present a self-contained, general study
of the synchronizer performance, from the view point of distributed algorithms, rather than
providing a deep mathematical study of the underlying stochastic process. In particular, we
were interested in comparing the behavior of synchronizers with random delays as opposed
to the usual approach of analyzing distributed algorithms with bounded delays. Our main
conclusion is that if the delays belong to the natural class of NBUE distributions, the rate of
the network is only degraded by a small, local (vertex degree) factor.
We presented several properties of the behavior of the synchronizer for general probability
distributions, and described techniques useful to compare the rate of the synchronizer running
in networks with different topologies.
For exponential distributions we showed that the expected duration of a round of computation
depends on the logarithm of a vertex degree, and hence, the rate of computation does
not diminishes with the number of processors in the network. We presented techniques to
prove upper and lower bounds on the rate, and to obtain exact computations. We hope the
combinatorial approach of these techniques, which was applied to rings, complete networks
and regular degree networks, will be used in the future to obtain results for other topologies
as well.



The following proposition (similar to pp. 672 in [BT89]) is used to prove the lower bounds on
the rate of a network.
Proposition 7.1 (D.2) Let X i be a sequence of independent exponential random variables
with mean - \Gamma1 . For every positive integer k and any c ? 4 log 2,
Pr
ck
Proof: Fix fi 2 (0; -), and let fl be a positive scalar. A direct calculation yields
Z 1e fi(x\Gammafl) -e \Gamma-x
In particular, we can choose fl sufficiently large so that E
\Theta

- 1. If
satisfies the last equation . Using the independence of the random variables X i ,
we obtain
e fi
Using the Markov inequality, we obtain
e fikm Pr
e fi
This in turn implies that
Pr
Pr
Pr
fi=2. For our choose of fi, we have 2.

Acknowledgments

We would like to thank Gurdip Singh and Gil Sideman for helpful comments.



--R

"Complexity of Network Synchronization,"
"Reducing Complexities of Distributed Max-Flow and Breadth-First- Search Algorithms by Means of Network Synchronization,"
"Network Synchronization with Polylogarithmic Over- head,"
"Sojourn Times in Cyclic Queues - the Influence of the Slowest Server,"
"Ergodic Theory of Stochastic Petri Networks,"
"Concurrency in Heavily Loaded Neighborhood- Constrained Systems,"
"Estimates of Cycle Times in Stochastic Petri Nets,"
"Comparison Properties of Stochastic Decision Free Petri Nets,"
"Queueing Models for Systems with Synchronization Constraints,"
"The Fork-Join Queue and Related Systems with Synchronization Constraints: Stochastic Ordering and Computable Bounds,"
"Acyclic Fork-Join Queueing Networks,"
"Investigations of Fault-Tolerant Networks of Computers,"
Parallel and Distributed Computation
Markov Chains With Stationary Transition Probabilities
"Marked Directed Graphs,"
"Distributed Snapshots: Determining Global States of Distributed Systems,"
Order Statistics
"Lack of Global Clock Does Not Slow Down the Computation in Distributed Networks,"
"The Use of a Synchronizer Yields Maximum Rate in Distributed Networks,"
"Tentative and Definite Distributed Computations: An Optimistic Approach to Network Synchronization,"
"Subadditive Ergodic Theory,"
"Stochastic Petri Nets: An Elementary Introduction,"
"Analysis of a Distributed Scheduler for Communication Networks,"
"Performance Analysis Using Stochastic Petri Nets,"
"Fast Bounds for Stochastic Petri Nets,"
"Generating a Global Clock in a Distributed System,"
"Graph Spanners,"
"An Optimal Synchronizer for the Hypercube,"
"Stochastic Bounds on Execution Times of Task Graphs,"
"Shuffle-Oriented Interconnection Networks,"
"Stochastic Marked Graphs,"
"Analysis of Distributed Algorithms based on Recurrence Relations,"

Comparison Methods for Queues and Other Stochastic Models
"The effect of Increasing Service Rates in a Closed Queueing Network,"
--TR
Complexity of network synchronization
Parallel and distributed computation: numerical methods
Investigations of fault-tolerant networks of computers
Acyclic fork-join queuing networks
Concurrency in heavily loaded neighborhood-constrained systems
An optimal synchronizer for the hypercube
Stochastic Petri nets: an elementary introduction
Unison in distributed networks
The use of a synchronizer yields maximum computation rate in distributed networks
Upper and lower bounds for stochastic marked graphs
Distributed snapshots
Fast Bounds for Stochastic Petri Nets
Analysis of Distributed Algorithms based on Recurrence Relations (Preliminary Version)
Tentative and Definite Distributed Computations
Analysis of a Distributed Scheduler for Communication Networks
Shuffle-Oriented Interconnection Networks

--CTR
Julia Lipman , Quentin F. Stout, A performance analysis of local synchronization, Proceedings of the eighteenth annual ACM symposium on Parallelism in algorithms and architectures, July 30-August 02, 2006, Cambridge, Massachusetts, USA
Omar Bakr , Idit Keidar, Evaluating the running time of a communication round over the internet, Proceedings of the twenty-first annual symposium on Principles of distributed computing, July 21-24, 2002, Monterey, California
Jeremy Gunawardena, From max-plus algebra to nonexpansive mappings: a nonlinear theory for discrete event systems, Theoretical Computer Science, v.293 n.1, p.141-167, 3 February
message passing;distributed computing;exponential distribution;synchronisation;graph theory;probabilitydistributions;parallel programming;marked graphs;compiler;asynchronous network;transmission delays;bottleneck processor;index termsprogram compilers;processing times;performance measure;synchronized programs;distributed networks;computational steps;random variables;performance evaluation;message transmissiondelays;synchronous network;randomprocessing times;synchronizer