On bufferless routing of variable-length messages in leveled networks

S. N. Bhatt, G. Bilardi, G. Pucci, A. Ranade, A. L. Rosenberg, E. J. Schwabe

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

2 Scopus citations

Abstract

We study the most general communication paradigm on a multiprocessor wherein each processor has a distinct message (of possibly distinct lengths) for each other processor. We study this paradigm, which we call chatting, on multiprocessors that do not allow messages once dispatched ever to be delayed on their routes. By insisting on oblivious routes for messages we convert the communication problem to a pure scheduling problem. We introduce the notion of a virtual chatting schedule, and we show how efficient chatting schedules can often be produced from efficient virtual chatting schedules. We present a number of strategies for producing efficient virtual chatting schedules on a variety of network topologies.

Original languageEnglish
Title of host publicationAlgorithms ESA 1993 – 1st Annual European Symposium, Proceedings
EditorsThomas Lengauer
Pages49-60
Number of pages12
DOIs
StatePublished - 1993
Event1st Annual European Symposium on Algorithms, ESA 1993 - Bad Honnef, Germany
Duration: 30 Sep 19932 Oct 1993

Publication series

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

Conference

Conference1st Annual European Symposium on Algorithms, ESA 1993
Country/TerritoryGermany
CityBad Honnef
Period30/09/932/10/93

Fingerprint

Dive into the research topics of 'On bufferless routing of variable-length messages in leveled networks'. Together they form a unique fingerprint.

Cite this