A series of case studies

Complexity of English text

English text is linear, sequential. That is, it is intended for sequential access by human readers. As a result, the complexity measure could ignore temporal decomposition but focus on spatial. The simplest form would ignore relationships between structural components, i.e., word, sentence, and paragraph, but focus on the properties of the components themselves.

If we allow a deeper analysis, especially into the semantics, or meaning of the text, more complex structures may be revealed: one paragraph may cite another; understanding one section may depend on another. With this, we will now have to consider the relationships between components. Nevertheless, this is still spatial decomposition

Complexity of software

Unlike English text, software can be nonlinear, with many paths of execution. It is better decomposed into a control flow graph. Then the complexity can be assessed based on the graph. A control flow graph is a temporal decomposition.

Complexity of interaction

Interaction between two systems can be characterized by protocols, which can often be represented by two interacting finite-state machines. Both machines change states according to input (from the outside world and the other machine). The complexity can be measured by properties of these two state machines. The two interacting state machines constitute a large state machine whose properties can also been used to quantify the interaction complexity. Note that the states here are the states of the interaction/protocol. The systems may well have other states not related to the interaction.

An important class of protocols (interactions) has no state in at least one side of the interaction, or stateless protocols. In a client-server model, a stateless protocol often has no state in at least one party. For example, HTTP and Internet Procotol (IP) are stateless protocols. In these protocols, each request from a client to the server is processed independent of previous requests. There are no states for the HTTP interaction in either the client and the server.

It is important to emphasize that when we say ''no state'' above, we are talking about the state of the interaction as characterized by the protocol. The server may well have states about its interactions with the client, characterized by other protocols. For example, when you shope at Amazon.com, the URL in the browser may appear like http://www.amazon.com/gp/huc/view.html?ie=UTF8&newItems=C2LS0F3O9TM8YQ. Note that the server has no state for the HTTP interaction but it does track the state of your shopping session, i.e., by newItems=C2LS0F3O9TM8YQ.

If we go deeper with the Amazon example above, one will realize that the web service implemented by Amazon on top of HTTP itself is an interaction protocol that is an example of RESTful API. Many of today's web services, including Amazon.com, are built using such RESTful APIs. In a RESTFul service, the client (say your web browser) does not maintain any state of the service. Each time a human user clicks a URL on the webpage, the URL, as generated by the server, includes the state of the service that the server needs to go further. From this perspective, a RESTful service has state only in the server but not in the client.