The computational complexity of a parallel algorithm can be measured by the time it takes and the work it does. The work done by a parallel algorithm is the product of the time required and the processors used. Often,...
详细信息
We present a new paradigm for efficient randomized parallelalgorithms that needs ō(log' n) time, where Ō(x) means 'O(Z) expected'. It leads to: (1) constructing a perfect hash function for n elements in...
详细信息
The problem of online job scheduling on various parallelarchitectures is studied. An O((log log n)1/2)-competitive algorithm for online dynamic scheduling on an n × n mesh is given. It is proved that this algori...
详细信息
ISBN:
(纸本)0818624450
The problem of online job scheduling on various parallelarchitectures is studied. An O((log log n)1/2)-competitive algorithm for online dynamic scheduling on an n × n mesh is given. It is proved that this algorithm is optimal up to a constant factor. The algorithm is not greedy, and the lower bound proof shows that no greedy-like algorithm can be very good. The upper bound result can be generalized to any fixed-dimensional meshes. Competitive scheduling algorithms for other architectures are given.
The proceedings contain 28 papers. The topics discussed include: practical uses of synchronized clocks undistributed systems;randomized wait-free concurrent objects;efficient parallelalgorithms on restartable fail-st...
ISBN:
(纸本)0897914392
The proceedings contain 28 papers. The topics discussed include: practical uses of synchronized clocks undistributed systems;randomized wait-free concurrent objects;efficient parallelalgorithms on restartable fail-stop processors;resiliency of interactive distributed tasks;how to withstand mobile virus attacks;on the value of information in distributed decision-making;optimal space distributed move-to-front lists;compact deterministic distributed dictionaries;a theory of relaxed atomicity;real-time sequence transmission problem;and consensus in the presence of timing uncertainty: omission and byzantine failures.
Surprisingly simple corollaries from the Courant-Fischer rninimax characterization theorem enable us to devise a very effective algorithm for the evaluation of a set S interleaving the set E of the eigenvalues of a re...
详细信息
A certificate for the k-vertex connectivity of a graph G = (V, E) is a subset E' of E such that (V, E') is k-vertex connected iff G is k-vertex connected. Let n = IV[ and m = IEI. A certificate is called spars...
详细信息
We consider efficient parallelalgorithms for the evaluation of game trees. We prove an inherent limitation on the speedup achievable, and give an algorithm that achieves its best performance bounds on trees of the so...
详细信息
We will show that Lovasz number of graphs may be computed using interior-point methods. This technique will require O(√|V|) iterations, each consisting of matrix operations which have polylog parallel time complexity...
详细信息
We give a parallel algorithm for the problem of computing the row minima of a totally monotone two-dimensional matrix. Whereas the previous best CREW-PRAM algorithm for this problem ran in O(log n log log n) time with...
详细信息
parallel programs display two fundamentally different kinds of execution behavior: synchronous and asynchronous. Some methodologies, such as distributed data structures, are best suited to the construction of asynchro...
详细信息
暂无评论