On randomized and deterministic schemes for routing and sorting on fixed-connection networks

Torsten Suel

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    Abstract

    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.

    Original languageEnglish (US)
    Title of host publicationParallel 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
    EditorsJose Rolim
    PublisherSpringer Verlag
    Pages384-386
    Number of pages3
    ISBN (Print)3540643591, 9783540643593
    DOIs
    StatePublished - 1998
    Event10 Workshops held in conjunction with 12th International Parallel Symposium and 9th Symposium on Parallel and Distributed Processing, IPPS/SPDP 1998 - Orlando, United States
    Duration: Mar 30 1998Apr 3 1998

    Publication series

    NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
    Volume1388
    ISSN (Print)0302-9743
    ISSN (Electronic)1611-3349

    Other

    Other10 Workshops held in conjunction with 12th International Parallel Symposium and 9th Symposium on Parallel and Distributed Processing, IPPS/SPDP 1998
    CountryUnited States
    CityOrlando
    Period3/30/984/3/98

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • Computer Science(all)

    Fingerprint Dive into the research topics of 'On randomized and deterministic schemes for routing and sorting on fixed-connection networks'. Together they form a unique fingerprint.

  • Cite this

    Suel, T. (1998). On randomized and deterministic schemes for routing and sorting on fixed-connection networks. In J. Rolim (Ed.), 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 (pp. 384-386). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1388). Springer Verlag. https://doi.org/10.1007/3-540-64359-1_711