A Scheme for Fast Parallel Communication

DOI10.1137/0211027zbMath0478.94034OpenAlexW2107997203WikidataQ100759369 ScholiaQ100759369MaRDI QIDQ3936664

Leslie G. Valiant

Publication date: 1982

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0211027

zbMATH Keywords

randomizationMonte Carlo algorithmparallel computerscommunication networknetwork routingdistributed randomized algorithm

Mathematics Subject Classification ID

Stochastic network models in operations research (90B15) Circuits, networks (94C99) Theory of software (68N99) Software, source code, etc. for problems pertaining to information and communication theory (94-04)

Related Items (43)

Direct routing: Algorithms and complexity ⋮ A real-time algorithm for the \((n^{2}-1)\)-puzzle ⋮ Randomized routing on generalized hypercubes ⋮ Towards a better understanding of pure packet routing ⋮ A new look at fault-tolerant network routing ⋮ Communication-efficient parallel algorithms for distributed random-access machines ⋮ Distributed match-making ⋮ A nearly optimal parallel algorithm for constructing maximal independent set in planar graphs ⋮ A new digraphs composition with applications to de Bruijn and generalized de Bruijn digraphs ⋮ Communication aspects of networks based on geometric incidence relations ⋮ Efficient delay routing ⋮ Oblivious bounds on the probability of boolean functions ⋮ Communication throughput of interconnection networks ⋮ Good permutation codes based on the shuffle-exchange network ⋮ Beyond the worst-case bisection bound: Fast sorting and ranking on meshes ⋮ Faster deterministic sorting through better sampling. ⋮ Randomized oblivious integral routing for minimizing power cost ⋮ Graph Sparsification, Spectral Sketches, and Faster Resistance Computation via Short Cycle Decompositions ⋮ Tiara: a self-stabilizing deterministic skip list and skip graph ⋮ Unnamed Item ⋮ Oblivious routing with limited buffer capacity ⋮ A fast distributed deadlock- detection algorithm for hypercube ⋮ Oblivious Routing for Sensor Network Topologies ⋮ On the theory of interconnection networks for parallel computers ⋮ Low time complexity algorithms for path computation in Cayley graphs ⋮ Optimal randomized parallel algorithms for computational geometry ⋮ Optimal routing algorithms for mesh-connected processor arrays ⋮ Analysis of minimal path routing schemes in the presence of faults ⋮ Parallel methods for initial value problems ⋮ Bounds on tradeoffs between randomness and communication complexity ⋮ Embedding grids into hypercubes ⋮ A data parallel finite element method for computational fluid dynamics on the Connection Machine system ⋮ Compromises and rewards: stable and non-manipulable probabilistic matching ⋮ On the benefit of supporting virtual channels in wormhole routers ⋮ Fast algorithms for bit-serial routing on a hypercube ⋮ Tight bounds for oblivious routing in the hypercube ⋮ Fast fault-tolerant parallel communication and on-line maintenance for hypercubes using information dispersal ⋮ Some permutation routing algorithms for low-dimensional hypercubes ⋮ Towards a scalable and robust DHT ⋮ Probabilistic NetKAT ⋮ Dynamic networks of finite state machines ⋮ Constructing disjoint paths on expander graphs ⋮ Bsp2omp: A Compiler For Translating Bsp Programs To Openmp

This page was built for publication: A Scheme for Fast Parallel Communication