TY - GEN
T1 - On randomized and deterministic schemes for routing and sorting on fixed-connection networks
AU - Suel, Torsten
PY - 1998
Y1 - 1998
N2 - We give a high-level description of some fundamental randomized and deterministic techniques for routing and sorting on fixedconnection networks such as meshes, hypercubes or point-to-point networks. On the randomized side, we focus on the techniques of randomized routing and random sampling and their use in many algorithms, while our presentation of deterministic algorithms uses the example of the Columnsort algorithm to highlight techniques such as local sorting and deterministic sampling. We then demonstrate that there is a close relationship between the randomized and deterministic techniques presented, and illustrate how this relationship can be used to transform randomized into deterministic algorithms and vice versa. Our main objective here is to provide a more unified perspective on many of the algorithms in the literature, and we do not attempt to provide a complete survey of routing and sorting problems on parallel machines.
AB - We give a high-level description of some fundamental randomized and deterministic techniques for routing and sorting on fixedconnection networks such as meshes, hypercubes or point-to-point networks. On the randomized side, we focus on the techniques of randomized routing and random sampling and their use in many algorithms, while our presentation of deterministic algorithms uses the example of the Columnsort algorithm to highlight techniques such as local sorting and deterministic sampling. We then demonstrate that there is a close relationship between the randomized and deterministic techniques presented, and illustrate how this relationship can be used to transform randomized into deterministic algorithms and vice versa. Our main objective here is to provide a more unified perspective on many of the algorithms in the literature, and we do not attempt to provide a complete survey of routing and sorting problems on parallel machines.
UR - http://www.scopus.com/inward/record.url?scp=84947447898&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84947447898&partnerID=8YFLogxK
U2 - 10.1007/3-540-64359-1_711
DO - 10.1007/3-540-64359-1_711
M3 - Conference contribution
AN - SCOPUS:84947447898
SN - 3540643591
SN - 9783540643593
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 384
EP - 386
BT - Parallel and Distributed Processing - 10 IPPS/SPDP 1998 Workshops Held in Conjunction with the 12th International Parallel Processing Symposium and 9th Symposium on Parallel and Distributed Processing, Proceedings
A2 - Rolim, Jose
PB - Springer Verlag
T2 - 10 Workshops held in conjunction with 12th International Parallel Symposium and 9th Symposium on Parallel and Distributed Processing, IPPS/SPDP 1998
Y2 - 30 March 1998 through 3 April 1998
ER -