Subject: Re: Wegner
From: "William J. Rapaport" <rapaport@buffalo.edu>
Date: Wed, 24 Mar 2010 11:34:05 -0400 (EDT)

A student wrote:
"I am reading the article by Wegner, and he wrote that Milner, in 1975,
noticed that concurrent processes cannot be expressed by sequential
algorithms. But I thought that it was proven that sequential processing
can simulate parallel processing. Am I mistaken?"

I had mentioned that I asked my colleague Prof. Russ Miller,
whose research area is parallel algorithms, about this. He tells me that
> typically one assumes that a sequential simulation can be written for a
> parallel computation, especially when considering pros and cons of Amdahl's Law.
> In practice, however, simulation very much depends on
> the parallel model of computation and the parallel algorithm itself.
> For example, in terms of an apriori approach to simulation,
> race conditions in shared memory systems cannot be
> simulated sequentially, nor can data dependent computations.
> Worse yet, is considering the entire computational system and not just
> the algorithm running in isolation. For example, other jobs being run
> on the machine, utilization of interconnection networks by other
> users, and system resources, etc.