time-space trade-offs for asynchronous parallel models (reducibilities and equivalences)
The question of relative efficiencies is studied in the context of a simple model of communicating aynchronous processes. The fundamental problem is whether a simple distributed system, with arbitrary size variables, is any more powerful than a system where only binary valued variables are permitted. The answer was (surprisingly) found to be negative, with an intuitive definition of the power of systems. The development of these notions required formalization of concepts such as equivalence of models, and the reduction of systems between models. It was discovered that requiring a strong definition of equivalence which decreased time apparently results in an increase in space. The trade-offs involved are seen to be tight in one approach to the problem.
timing asynchronicity parallel model efficiency context communication process distributed systems systems size variability power definition developer formalism concept reduction space relation