Interaction Complexity - A Computational Complexity Measure for Service-Oriented Computing

Service-oriented computing is gaining popularity, and interaction of services becomes a critical computational resource since several interacting services cooperating to solve a problem is now a common paradigm. However, little work has been done to measure the amount of interaction that must be involved in this paradigm. Using interaction product as basic computing model, this paper defines the interaction complexity of a language to capture the cost of interaction for recognizing the language in service- oriented computing. We prove the "robustness" of interaction complexity class, show that interaction complexity of a language is upper-bounded by exponential of its time complexity, present that time complexity is no more than a linear polynomial of interaction complexity, and propose that space complexity is no more than logarithm of interaction complexity.