On saving space in parallel computation (Q1114403): Difference between revisions

The literature on parallel computing describes a number of algorithms whose space requirements exceed their time-processor product. Generalizing an idea by \textit{R. Cole} and \textit{U. Vishkin} [Approximate parallel scheduling II, Preprint (1987)] and combining it with a well known trick for avoiding initialization of memory areas, we show that in the CRCW PRAM model of computation, such anomalies can always be kept within bounds.