International Travel Support for Research in Resilient Parallel Computation: University of Paris, France: Oct- Dec 1992

研究人员建议为自动和有效的方法开发理论基础，将为理想的抽象共享内存并行机器编写的程序转换为更现实（但仍然抽象）的并行机器程序。在这种情况下，“现实”意味着机器的组件可能会出现故障，或者不同的组件可能以不同的速度运行。翻译的第一步是将为理想抽象机编写的并行程序分割成不同部分互不干扰的片断。每个这样的程序片段将被转换为更现实的机器上的程序，该机器快速执行该片段，但只是“暂时”执行；也就是说，结果只有在高概率下才是正确的。然后，现实机检查暂定计算是否正确。如果是，片段已经完成了它的执行，否则它的效果将被撤消，它将被重新执行。算法思想是从随机化和事务处理的文献中提取的。所提出的工作的意义在于，许多算法已经为理想的共享内存并行机器开发出来，因为它们易于编程和理解。该研究的成功将为将这些算法自动转换为在更现实的机器上有效执行的程序提供理论基础。

The investigators propose to develop theoretical foundations for automatic and efficient methods to translate programs written for ideal abstract shared-memory parallel machines to programs for more realistic (but still abstract) parallel machines. "Realistic" in this context means that components of the machines may suffer failures or that different components may execute at different speeds. The first step in the translation is to divide the parallel program written for the ideal abstract machine into fragments whose different portions do not interfere with one another. Each such program fragment will be transformed to a program on the more realistic machine, which executes the fragment fast but only "tentatively"; that is, the result is correct only with high probability. Then the realistic machine checks whether the tentative computation was correct. If so, the fragment has completed its execution, otherwise its effects will be undone and it will be re-executed. Algorithmic ideas are drawn from the literature on randomization and transaction processing. The significance of the proposed work is that many algorithms have been developed for ideal shared-memory parallel machines, since they are easy to program and understand. The success of the research will contribute to the theoretical foundation of the automatic translation of such algorithms to programs executing efficiently on more realistic machines.