A simple and efficient algorithm is presented for the FIFO allocation of K identical resources among asynchronous processes which communicate via shared memory. The algorithm simulates a shared queue but uses exponentially fewer shared memory values, resulting in practical savings of time and space as well as program complexity. The algorithm is robust against processes failure through unannounced stopping, making it attractive also for use in an environment of processes ...
We present parallel algorithms to compute the determinant and characteristics polynomial of nxn-matrices and the gcd of polynomials of degree less than or equal n. The algorithms use parallel time O(log to the 2nd power n) and a polynomial number of processors. We also give a fast parallel Monte Carlo algorithm for the rank of matrices. All algorithms work over arbitrary fields. (Author)
This report is concerned with routing protocols in networks. The major result is a low bound for any oblivious routing strategy where the route of a packet depends only on the source and destination of the packet. We show that for any oblivious routing protocol for a network of n processors in which the maximum number of processors directly connected to any processor is d, there exists a permutation that ...
A variety of models have been proposed for the study of synchronous parallel computation. We review these models and study further some prototype problems. Within a spectrum of shared memory models, we show that loglog n is asymptotically optimal for n processors to merge two sorted lists containing n elements. (Author)
Reports by Author
