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 synchronous network into a program that runs in an asynchronous network. The behaviour of a simple synchronizer, which also represents a basic mechanism for distributed computing and for the analysis of m arked graphs, was studied by Even and Rajsbaum under the assumption th at message transmission delays and processing times are constant. In t his paper, we study the behavior of the simple synchronizer when proce ssing times and transmission delays are random. Our main performance m easure is the rate of a network, i.e., the average number of computati onal steps executed by a processor in the network per unit time. We an alyze the effect of the topology and the probability distributions of the random variables on the behavior of the network. For random variab les with exponential distribution, we provide tight (i.e., attainable) bounds and study the effect of a bottleneck processor on the rate.