{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,29]],"date-time":"2022-03-29T16:14:33Z","timestamp":1648570473744},"reference-count":0,"publisher":"World Scientific Pub Co Pte Lt","issue":"02","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Parallel Process. Lett."],"published-print":{"date-parts":[[1995,6]]},"abstract":"<jats:p> A parallel algorithm exhibits a fixed-processor communication-time tradeoff if lower bounds on communication and time cannot be simultaneously realized by any schedule using p processors. For unrestricted schedules, lower bounds on communication are trivial, so all researchers in this area have made assumptions about what kinds of schedules to consider. The usual restriction is that all processors perform approximately equal work. The problem with this restriction is that it can overstate the number of processors that are needed to realize the claimed time and communication bounds. Since the communication and time bounds are expressed as a function of p, using an inflated value for p can lead us to believe that there is a tradeoff when none exists. In this paper we reexamine previously published communication results for several algorithms and show that the existence of tradeoffs is still an open question. We also introduce the concept of effective schedules, and argue that both tight communication bounds and fixed-processor communication-time tradeoffs are only meaningful for effective schedules. <\/jats:p>","DOI":"10.1142\/s0129626495000291","type":"journal-article","created":{"date-parts":[[2004,11,10]],"date-time":"2004-11-10T11:14:37Z","timestamp":1100085277000},"page":"311-320","source":"Crossref","is-referenced-by-count":0,"title":["DO FIXED-PROCESSOR COMMUNICATION-TIME TRADEOFFS EXIST?"],"prefix":"10.1142","volume":"05","author":[{"given":"DAVID R.","family":"LUTZ","sequence":"first","affiliation":[{"name":"AT&amp;T Bell Laboratories, 6200 East Broad Street, Columbus, Ohio 43213, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"D. N.","family":"JAYASIMHA","sequence":"additional","affiliation":[{"name":"Department of Computer and Information Science, The Ohio State University, 2015 Neil Ave, Columbus, Ohio 43210\u20131277, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2011,11,21]]},"container-title":["Parallel Processing Letters"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129626495000291","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T16:17:36Z","timestamp":1565108256000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129626495000291"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995,6]]},"references-count":0,"journal-issue":{"issue":"02","published-online":{"date-parts":[[2011,11,21]]},"published-print":{"date-parts":[[1995,6]]}},"alternative-id":["10.1142\/S0129626495000291"],"URL":"https:\/\/doi.org\/10.1142\/s0129626495000291","relation":{},"ISSN":["0129-6264","1793-642X"],"issn-type":[{"value":"0129-6264","type":"print"},{"value":"1793-642X","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995,6]]}}}