Approaching simple and powerful service-computing¹

Abstract

Service-computing is the computing paradigm that utilises services as building blocks for developing applications or solutions. Because simplicity of services, applications and their interaction are critical for low cost and high productivity of service-computing, this paper tries to explore a proper bound of the simplicity. By proving that any Turing machine is equivalent to the interaction product of three generalised finite automata, we show that the services can be as simple as generalised finite automata and their interaction can be as simple as interaction product. Since generalised finite automata are equivalent to finite automata which are intuitively very simple, and interaction product is an interaction mechanism imposing few constraints on its components, this result is generally helpful in distributed-system design for achieving low cost and high productivity.

Keywords:

• service-computing
• interaction complexity
• automaton
• computability

Keywords:

• 68M07
• 68Q05

Acknowledgements

This work is supported in part by the National Natural Science Foundation of China (Grant No. 90412010, 60603004) and China's National Basic Research and Development 973 Program (2005CB321807).