We study the routing of messages with multiple destinations on an n-node square mesh (one-to-many routing). The obvious approach of simply replicating each message into the appropriate number of point-to-point messages and routing these independently does not generally yield optimal performance. A standard argument proves that (Ω √ n + cm) time is required to route m ⪇ n messages, where each message is generated by a distinct node and at most c messages must be delivered to any individual node. The lower bound does not depend on the number of destinations per message. We provide both randomized and deterministic algorithms for one-to-many routing, which use constant-size buffers at each node. The randomized algorithm attains optimal performance, while the deterministic algorithm is slower by a factor of Ο (log2 n). We also describe an optimal deterministic algorithm that, however, requires large buffers of size Ο (c).

A quantitative comparison of the BSP and LogP models for parallel computation is developed.Very efficient cross simulations between the two models are derived, showing their substantial equivalence for algorithmic design guided by asymptotic analysis.It is also shown that the two models can be implemented with similar performance on most point-to-point networks.In conclusion, within the limits of our analysis that is mainly of asymptotic nature, BSP and LogP can be viewed as closely related variants within the bandwidth-latency framework for modeling parallel computation.BSP seems somewhat preferable due to greater simplicity and portability, and slightly greater power.

The problem of simulating a PRAM with n processors and memory size $m \geqslant n$ on an n-node bounded degree network is considered. A deterministic algorithm is presented that simulates an arbitrary PRAM step in $O(({{\log n\log m)} / {\log \log n)}}$ time in the worst case on an expander-based network. By extending a previously established lower bound, it is shown that the proposed simulation is optimal whenever $\Omega (n^{1 + \epsilon } ) \leqslant m \leqslant O(2^{(\log n)^\alpha } )$ for some positive real constants $ \epsilon $ and $\alpha $.

Consider a set of packets distributed unevenly among the nodes of a bounded degree network of processors. The Token Distribution Problem involves redistributing these packets so that each node holds the same number. Token distribution algorithms underlie several efficient routing algorithms. Peleg and Upfal formulated this problem and presented a communication-efficient solution. In this paper we refine their techniques to provide a solution that is efficient with respect to both communication and local computation.

The problem of representing a set.tr k (2~1,. . . .II,,} of read-write variables on an n-node distribut,ed memory pa.rallel computer is considered.It is shown that, Cr can be represented among the n nodes of a variant. of tlie mesh-of-t,rees using O((?n/77)polyIoy( )??/)I)) storage per node such tha.tany n-tuple of variables ma.y be accessed in O(log n(10glogn)~) time in t,he worst ca.se for m polynomial in n.

The problem of simulating a parallel random-access machine (PRAM) with n processors and memory size m>or=n on an n-node bounded degree network (BDN) is considered. Since many of the more efficient PRAM algorithms use an amount of shared memory not much larger than the number of processors, the case in which m=o(n/sup 1+ epsilon /) is considered, and a deterministic solution to the simulation problem is presented. For m=n(log n)/sup /O/sup (1)/ the running time of O(log n log log n) is within a factor of O(log log n) of the lower bound imposed by the diameter of the network.>