Bounds on fundamental problems in parallel and distributed computation

摘要: Bounds on fundamental problems are obtained in four general models of parallel and distributed computing. In the RAM model Fortune Wiley, processors completely reliable communicate through a common memory. In this model, bounds given for computation simple functions, such as logical OR n Boolean inputs. The "intuitive" lower bound log(,2)n steps is proved false; it beaten by multiplicative factor. However, shown to require (OMEGA)(log n) steps. The transaction commitment broadcasting studied environment with bounded processor communication asynchrony. Processors not assumed reliable. popular belief that nonblocking protocols have inherently greater message complexity than blocking disproved exhibiting single protocol achieves both classes. This also proved, so tight. Two types broadcast (consistency) examined. Still another myth disproved: interactive consistency (consistency among operational processors) exactly same total all processors, failed operational). Consensus examined several other models. Sharp boundaries exist between resilience arbitrary numbers benign failures impossibility even one or two failures. An intuitive explanation why can be presented. Conservative nonconservative oblivious matrix transposition networks A tight edge/depth tradeoff conservative case. interesting question whether apply case still open, although they depth at most 3.