On mapping processes to processors in distributed systems

This paper is concerned with the implementation of parallel programs on networks of processors. In particular, we study the use of the network augmenting approach as an implementation tool. According to this approach, the capabilities of a given network of processors can be increased by adding some auxiliary links among the processors. We prove that the minimum set of edges needed to augment a line-like network so that it can accommodate a parallel program is determined by an optimal path cover of the graph representation of the program. Anoptimal path cover of a simple graphG is a set of vertex-disjoint paths that cover all the vertices ofG and has the maximum possible number of edges. We present a linear time optimal path covering algorithm for a class of sparse graphs. This algorithm is of special interest since the optimal path covering problem is NP-complete for general graphs. Our results suggest that a cover and augment scheme can be used for optimal implementation of parallel programs in line-like networks.A preliminary version of this paper was presented at the 6th IEEE Conference on Computer Communications (INFOCOM '87).This reseach is supported in part by National Semiconductor (Israel), Ltd.     

An equivalence theorem for labeled marked graphs

Petri nets and their languages are a useful model of systems exhibiting concurrent behavior. The sequential language associated with a given Petri net S consists of all possible firing sequences of S, where each element of a firing sequence is a single transition. The concurrent language associated with S consists of all possible concurrent firing sequences of S, where each element of a concurrent firing sequence is a set of transitions. The sequential language and the concurrent language associated with S are denoted by (L)(S) and (π)(S), respectively. In this paper, we consider an important special ease of Petri nets, called labeled marked graphs. The main result derived in this paper states that if Γ₁ and Γ₂ are two structurally deterministic labeled marked graphs, then (L)(Γ₁)=L(Γ₂)&rlhar2;π(Γ ₁)=π(Γ₂)     

Optimal distributed t-resilient election in completenetworks

The problem of distributed leader election in an asynchronous complete network, in the presence of faults that occurred prior to the execution of the election algorithm, is discussed. Failures of this type are encountered, for example, during a recovery from a crash in the network. For a network with n processors, k of which start the algorithm that uses at most O(n log k +n+kt) messages is presented and shown to be optimal. An optimal algorithm for the case where the identities of the neighbors are known is also presented. It is noted that the order of the message complexity of a t-resilient algorithm is not always higher than that of a nonresilient one. The t-resilient algorithm is a systematic modification of an existing algorithm for a fault-free network