Journal Article @Article Artikel in Fachzeitschrift
 Show entries of: this year (2020) | last year (2019) | two years ago (2018) | Notes URL
 Action: login to update Options: Goto entry point

 Author, Editor(s)
 Author(s): Sanders, Peter Solis-Oba, Roberto dblp dblp
 BibTeX cite key*: SanSol2001

 Title
 Title*: How Helpers Hasten h-Relations

 Journal
 Journal Title*: Journal of Algorithms Journal's URL: Download URL for the article: http://www.idealibrary.com/servlet/doi/10.1006/jagm.2001.1169 Language: English

 Publisher

 Vol, No, pp, Date
 Volume*: 41 Number: Publishing Date: 2001 Pages*: 86-98 Number of VG Pages: 25 Page Start: Page End: Sequence Number: DOI:

 Note: (LaTeX) Abstract: We study the problem of exchanging a set of messages among a group of processors, where messages may consist of different numbers of packets. We consider the model of half-duplex communication. Let $\Lmax$ denote the maximum number of packets that a processor must send and receive. If all the packets need to be delivered directly, at least $\frac{3}{2}\Lmax$ communication steps are needed to solve the problem in the worst case. We show that by allowing forwarding, only $\frac{6}{5}\Lmax + \Oh{1}$ time steps are needed to exchange all the messages, and this is optimal. Our work was motivated by the importance of irregular message exchanges in distributed-memory parallel computers, but it can also be viewed as an answer to an open problem on scheduling file transfers posed by Coffmann, Garey, Johnsson, and LaPaugh in 1985. URL for the Abstract: Categories, Keywords: HyperLinks / References / URLs: Copyright Message: Personal Comments: Download Access Level:

 Correlation
 MPG Unit: Max-Planck-Institut für Informatik MPG Subunit: Algorithms and Complexity Group Audience: experts only Appearance: MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort

BibTeX Entry:

@ARTICLE{SanSol2001,
AUTHOR = {Sanders, Peter and Solis-Oba, Roberto},
TITLE = {How Helpers Hasten h-Relations},
JOURNAL = {Journal of Algorithms},