Probabilistic load balancing for parallel graph reduction

An analysis is made of simple probabilistic implementations of (slightly restricted) parallel graph rewriting both on a shared memory architecture like a PRAM and a more realistic distributed memory architecture like a transputer network. Graph rewriting is executed in cycles where every cycle consists in the execution of all the tasks presently available in the graph. Assuming that there are p processors and N executable tasks in the cycle, it is shown that the PRAM can execute the cycle in (optimal) time O(N/p) with high probability provided N = Ω(p² log p), whereas a processor net can execute the cycle in time O(N/p log p) with high probability using chunks of messages of size O(N/p) if only N = Ω(p log p).