1 Introduction

A common way to interpret self-* in autonomic systems (ASs) is to say that self-* actions are running on ASs. Triggers of self-* actions from self-* can be performed concurrently to transform one AS state into another. A first rule for self-* actions is this: the performance of a sequence of several self-* actions is itself the performance of a self-* action - a more complex self-* action, but a self-* action nonetheless. Algebraic objects called monoids are tasked with encoding the self-* action’s perspective in all this, i.e. what the self-* action can do, and what happens when different self-* actions are done in succession. A monoid can be construed as a set of self-* actions, together with a formula that encodes how a sequence of self-* actions is itself considered a self-* action. In this paper we concentrate on monoids.

2 Outline

The paper is a reference material for readers who already have a basic understanding of ASs and are now ready to know the novel approach for formalizing self-* in ASs using algebraic language.

Formalization is presented in a straightforward fashion by discussing in detail the necessary components and briefly touching on the more advanced components. Several notes explaining how to use the algebraic structures, including justifications needed in order to achieve the particular results, are presented.

We attempt to make the presentation as self-contained as possible, although familiarity with the notions of self-* in ASs is assumed. Acquaintance with the algebra and the associated notion of algebraic structures is useful for recognizing the results, but is almost everywhere not strictly necessary.

The rest of this paper is organized as follows: Section 3 includes some major work related directly to the content of the paper. In Section 4, AC is described as self-*. Section 5 presents algebraic objects called monoids to be tasked with encoding the self-* action’s perspective. In Section 6, we specify monoid self-* actions. Section 7 presents monoid homomorphisms. Finally, a short summary is given in Section 8.

3 Related work

The topic of AC has seen a number of developments through various research investigations following the IBM initiative such as AC paradigm in [1–5]; different approaches and infrastructures in [6–10] for enabling autonomic behaviors [11–14]; core enabling systems, technologies, and services in [15–20] to support the realization of self-* properties in autonomic systems and applications; specific realizations of self-* properties in autonomic systems and applications in [21–27]; architectures and modeling strategies of autonomic networks in [28–30]; middleware and service infrastructure as facilitators of autonomic communications in [31–33]; approaches in [34–36] to equipping current networks with autonomic functionality for migrating this type of networks to autonomic networks.

Moreover, AC has also been intensely studied by various areas of engineering including artificial intelligence, control systems and human orientated systems [37–40]. Autonomic computing has been set as an important requirement for systems devised to work in new generation global networked and distributed environments like wireless networks, P2P networks, Web systems, multi-agent systems, grids, and so on [41–45]. Such systems pose new challenges for the development and application of autonomic computing techniques, due to their special characteristics including: nondeterminism, context-awareness and goal- and inference-driven adaptability [37, 46–48].

Finally, the choice of the underlying formalization requires a close look at models for AC. Hence, our interest centers on formal approach to AC taking advantage of category theory [46]. In fact, categories were first described by Samuel Eilenberg and Saunders Mac Lane in 1945 [49], but have since grown substantially to become a branch of modern mathematics. Category theory spreads its influence over the development of both mathematics and theoretical computer science. The categorical structures themselves are still the subject of active research, including work to increase their range of practical applicability.

4 Autonomic computing as self-*

Autonomic computing (AC) imitates and simulates the natural intelligence possessed by the human autonomic nervous system using generic computers. This indicates that the nature of software in AC is the simulation and embodiment of human behaviors, and the extension of human capability, reachability, persistency, memory, and information processing speed [50]. AC was first proposed by IBM in 2001 where it is defined as

“Autonomic computing is an approach to self-managed computing systems with a minimum of human interference. The term derives from the body’s autonomic nervous system, which controls key functions without conscious awareness or involvement” [51].

AC is generally described as self-*. Formally, let self-* be the set of self-_’s. Each self-_ to be an element in self-* is called a self-* action. That is,

$$ \text{self-*} = \{\text{self-}\_\!\_{\parallel} \text{self-}\_\!\_{\text{ is a self-* action}}\} $$
(1)

Note that the symbol ∥ is read as “so that” in the paper. We see that self-CHOP is composed of four self-* actions of self-configuration, self-healing, self-optimization and self-protection. Hence, self-CHOP is a subset of self-*. That is, self-CHOP = {self-configuration, self-healing, self-optimization, self-protection}\(\subset \) self-*. Every self-* action must satisfy some certain criteria, so-called self-* properties. In [6], T.D. Wolf and T. Holvoet classified the self-* properties in autonomic networks.

In its AC manifesto, IBM proposed eight actions setting forth an AS known as self-awareness, self-configuration, self-optimization, self-maintenance, self-protection (security and integrity), self-adaptation, self-resource- allocation and open-standard-based [51]. Kinsner pointed out that these actions indicate that IBM perceives AC is a mimicry of human nervous systems [52]. In other words, self-awareness (consciousness) and non-imperative (goal-driven) behaviors are the main features of ASs [50].

5 Monoids of self-*

A monoid of self-* is a sequence (S E L F-∗, s k i p,∣), where S E L F-∗ is a set of self-* actions, s k i p ∈ S E L F-∗ is an action, and \(\mid : SELF\text {-}* \times SELF\text {-}* \rightarrow SELF\text {-}*\) is a concurrence, such that the following conditions hold for all s e-m, s e-n, s e-p ∈ S E L F-∗:

  • s e-m∣s k i p = s e-m,

  • s k i p∣s e-m = s e-m, and

  • (s e-m∣s e-n)∣s e-p = s e-m∣(s e-n∣s e-p)

The way they are written here is called infix notation. We refer to skip as the identity action and to ∣ as the concurrence formula for the monoid. We call the first two rules identity laws and the third rule the associativity law for monoids.

Alternatively, the rules of identity and associativity can be stated

  • ∣(s e-m, s k i p) = s e-m,

  • ∣(s k i p, s e-m) = s e-m, and

  • ∣(∣(s e-m, s e-n), s e-p) = ∣(s e-m,∣(s e-n, s e-p))

The way they are written above is called prefix notation. Note that we often use infix notation without mentioning it. That is, given a concurrence \(\mid : SELF\text {-}* \times SELF\text {-}* \rightarrow SELF\text {-}*\), we may write s e-a∣s e-b rather than ∣(s e-a, s e-b).

There is a monoid with only one action, ({s k i p}, s k i p,∣ ) where \(\mid :\{skip\} \times \{skip\} \rightarrow \{skip\}\) is the unique concurrence. We call this monoid the trivial monoid, and sometimes denote it \(\underline {1}\).

In monoid (S E L F-∗, s k i p,∣), given actions s e-m 1, s e-m 2, s e-m 3, s e-m 4 there are five different ways to parenthesize the concurrence s e-m 1∣s e-m 2∣s e-m 3∣s e-m 4, and the associativity law for monoids will show them all to be the same. We have

$$\begin{array}{@{}rcl@{}} ((se\text{-}m_{1} \mid se\text{-}m_{2}) \mid se\text{-}m_{3}) \mid se\text{-}m_{4} &=& (se\text{-}m_{1} \mid se\text{-}m_{2}) \mid (se\text{-}m_{3} \mid se\text{-}m_{4}) \\ &=& (se\text{-}m_{1} \mid (se\text{-}m_{2} \mid se\text{-}m_{3})) \mid se\text{-}m_{4} \\ &=& se\text{-}m_{1} \mid (se\text{-}m_{2} \mid (se\text{-}m_{3} \mid se\text{-}m_{4})) \\ &=& se\text{-}m_{1} \mid ((se\text{-}m_{2} \mid se\text{-}m_{3}) \mid se\text{-}m_{4}) \end{array} $$

In fact, the concurrence of any list of monoid self-* actions is the same, regardless of parenthesization. Therefore, we can unambiguously write s e-m 1∣s e-m 2∣s e-m 3∣s e-m 4 rather than any given parenthesization of it. This is known as the coherence theorem and can be found in [53].

5.1 Free monoids of self-*

Let S E L F-∗ be a set of self-* actions. A list in S E L F-∗ is a pair (n, f) where n ∈ ℕ is a natural number (called the length of the list) and \(f : \underline {n} \rightarrow SELF\text {-}*\) is a function, where \(\underline {n} = \{1, 2,\ldots , n\}\). We may denote such a list by

$$(n,f) = [f(1),f(2),\ldots,f(n)]$$

The empty list is the unique list in which n = 0; we may denote it by []. Given a self-* action s e-x ∈ S E L F-∗ the singleton list on s e-x is the list [s e-x]. Given a list L = (n, f) and a number i ∈ ℕ with \(i \leqslant n\), the ith entry of L is the self-* action f(i) ∈ S E L F-∗.

Given two lists L = (n, f) and \(L^{\prime } = (n^{\prime },f^{\prime })\), define the concatenation of L and \(L^{\prime }\), denoted \(L \ddagger L^{\prime }\), to be the list \((n+n^{\prime }, f \ddagger f^{\prime })\), where \(f \ddagger f^{\prime } : \underline {n+n^{\prime }} \rightarrow SELF\text {-}*\) is given on \(i \leqslant n+n^{\prime }\) by

$$ (f \ddagger f^{\prime})(i) = \left\{\begin{array}{ll} f(i) & \quad\text{ if }i \leqslant n \\ f^{\prime}(i-n) &\quad\text{ if }i \geqslant n+1 \end{array}\right. $$
(2)

Let S E L F-∗ = {s e-a, s e-b, s e-c, … , s e-z}. The following are self-* actions of L i s t(S E L F-∗):

$$[se\text{-}a,se\text{-}b], [se\text{-}p], [se\text{-}p,se\text{-}a,se\text{-}a], \ldots $$

The concatenation of [s e-a, s e-b] and [s e-p, s e-a, s e-a] is [s e-a, s e-b, s e-p, s e-a, s e-a]. The concatenation of any list with [] is just itself.

A free monoid generated by S E L F-∗ is the sequence (L i s t(S E L F-∗),[], †), where L i s t(S E L F-∗) is the set of lists of self-* actions in S E L F-∗, where [] ∈ L i s t(S E L F-∗) is the empty list, and where ‡ is the operation of list concatenation. We refer to S E L F-∗ as the set of generators for the free monoid (L i s t(S E L F-∗), [], ‡).

A free monoid generated by \(\varnothing \) is the sequence \((List(\varnothing ), [], \ddagger )\) where \(List(\varnothing )\) consists only of the empty list. It is the trivial free monoid.

In the section below, we will define the monoid (L i s t(S E L F-∗), [], ‡) by specifying some generators and some relations. Lists of generators provide us all the possible ways to write self-* actions of (L i s t(S E L F-∗), [], ‡). The relations allow us to have two ways of writing the same self-* actions.

5.2 Presented monoids of self-*

Let S E L F-∗ be a finite set of self-* actions, let n ∈ ℕ be the number of relations we declare, and for each \(1 \leqslant i \leqslant n\), let m i and \(m^{\prime }_{i}\) be self-* actions of L i s t(S E L F-∗). The monoid presented by generators S E L F-∗and relations \(\{(m_{i},m_{i}^{\prime })\) where \(1 \leqslant i \leqslant n\}\) is the monoid (L i s t(S E L F-∗)/ ∼, [], ‡) defined fully when ∼ denotes the equivalence relation on (L i s t(S E L F-∗) generated by \(\{xm_{i}y \sim xm_{i}^{\prime }y\) where \(x, y \in List(SELF\text {-}*), 1 \leqslant i \leqslant n\}\).

Every free monoid (L i s t(S E L F-∗), [], ‡) is a presented monoid, because we can just take the set of relations to be empty.

Let S E L F-∗ = {s e-a, s e-b, s e-c, s e-d}. The idea of presented monoids is that you notice that list of self-* actions [s e-a, s e-a, s e-c] always gives the same result as list of self-* actions [s e-d, s e-d]. You also notice that list of self-* actions [s e-c, s e-a, s e-c, s e-a] is the same thing as doing nothing. In this case, we have m 1 = [s e-a, s e-a, s e-c], \(m_{1}^{\prime } = [se\text {-}d, se\text {-}d]\), and \(m_{2} = [se\text {-}c, se\text {-}a, se\text {-}c, se\text {-}a], m_{2}^{\prime } = []\) and relations \(\{(m_{1},m_{1}^{\prime }), (m_{2},m_{2}^{\prime })\}\). Really this means that we are equating m 1 with \(m_{1}^{\prime }\) and m 2 with \(m_{2}^{\prime }\), which for convenience we will write out [s e-a, s e-a, s e-c] = [s e-d, s e-d] and [s e-c, s e-a, s e-c, s e-a] = []. To see how this plays out, we give an example of a calculation in L i s t(S E L F-∗)/ ∼. Namely,

$$\begin{array}{@{}rcl@{}} [se\text{-}b, \underline{se\text{-}d, se\text{-}d}, se\text{-}a, se\text{-}c, se\text{-}a, se\text{-}a, se\text{-}c, se\text{-}d] &=& [se\text{-}b, se\text{-}a, \underline{se\text{-}a, se\text{-}c, se\text{-}a, se\text{-}c}, \\ &&se\text{-}a, se\text{-}a, se\text{-}c, se\text{-}d] \\ &=& [se\text{-}b, se\text{-}a, \underline{se\text{-}a, se\text{-}a, se\text{-}c}, se\text{-}d] \\ &=& [se\text{-}b, se\text{-}a, se\text{-}d, se\text{-}d, se\text{-}d] \end{array} $$

5.3 Cyclic monoids of self-*

A monoid is called cyclic if it has a presentation involving only one generator. Let s e-a be a self-* action; we look at some cyclic monoids generated by {s e-a}.

With no relations the monoid will be the free monoid on one generator, and will have underlying set {[], [s e-a], [s e-a, s e-a], [s e-a, s e-a, s e-a], …}, with identity list [] and concatenation such that [s e-a, s e-a] ‡ [s e-a] = [s e-a, s e-a, s e-a, s e-a] = s e-a 4. Note that s e-a 4 is shorthand for [s e-a, s e-a, s e-a, s e-a].

With the relation s e-a ∼ [] we will get the trivial monoid, a monoid having only one action. Consider the cyclic monoid with generator s e-a and relation s e-a 7 = s e-a 4. This monoid has seven actions

$$\{[]=se\text{-}a^{0}, se\text{-}a = se\text{-}a^{1}, se\text{-}a^{2}, se\text{-}a^{3}, se\text{-}a^{4}, se\text{-}a^{5}, se\text{-}a^{6} \} $$

and we know that

$$se\text{-}a^{6} \ddagger se\text{-}a^{5} = se\text{-}a^{7} \ddagger se\text{-}a^{4} = se\text{-}a^{4} \ddagger se\text{-}a^{4} = se\text{-}a^{7} \ddagger se\text{-}a = se\text{-}a^{5} $$

We can depict this monoid as follows

6 Actions of monoid of self-*

Let AS be a set of autonomic system states. A self-* action of monoid (S E L F-∗, s k i p,∣) on AS, or simply a self-* action of S E L F-∗ on AS or a S E L F-∗ action on AS, is a function

$$\circlearrowleft: SELF\text{-}* \times AS \rightarrow AS$$

such that the following conditions hold for all s e-m, s e-n ∈ S E L F-∗ and all s ∈ A S :

  • \(skip \circlearrowleft s = s \)

  • \(se\text {-}n \circlearrowleft (se\text {-}n \circlearrowleft s) = (se\text {-}n \mid se\text {-}n) \circlearrowleft s \)

Alternately, it is sometimes useful, we can rewrite \(\circlearrowleft \) as \(\alpha : SELF\text {-}* \times AS \rightarrow AS\) and restate the above conditions as

  • α(s k i p, s) = s

  • α(s e-n, α(s e-n, s)) = α(s e-n∣s e-n, s)

The following proposition expresses the notion of autonomic system in terms of free monoids and their actions on finite sets.

Proposition 1

Let SELF-∗ and AS be finite non-empty sets of self-* actions and autonomic system states, respectively. Giving a function \(\alpha : SELF\text {-}* \times AS \rightarrow AS\) is equivalent to giving an action of the free monoid List(SELF-∗) on AS.

Proof

We know that function \(\delta : List(SELF\text {-}*) \times AS \rightarrow AS\) constitutes an action of the monoid L i s t(S E L F-∗) on the set AS if and only if, for all s ∈ A S we have δ([], s) = s, and for any two actions \(m,m^{\prime } \in List(SELF\text {-}*)\) we have \(\delta (m,\delta (m^{\prime }, s)) = \delta (m \ddagger m^{\prime }, s) \). Let

$$A = \{ \delta: List(SELF\text{-}*) \times AS \rightarrow AS \parallel \delta\text{ constitutes an action} \}$$

We need to prove that there is an isomorphism of sets

$$\phi : A \stackrel{\cong}{\longrightarrow} \text{Hom}_{\textbf{Set}}(SELF\text{-}* \times AS, AS) $$

Given an element \(\delta : List(SELF\text {-}*) \times AS \rightarrow AS\) in A, define ϕ(δ) on an element (s e-a, s) ∈ S E L F-∗×A S by ϕ(δ)(s e-a, s) = d e f δ([s e-a], s), where [s e-a] is the one-element list.

We now define \(\psi : \text {Hom}_{\textbf {Set}}(SELF\text {-}* \times AS, AS) \rightarrow A\). Given an element f ∈ Hom Set (S E L F-∗×A S, A S) define \(\psi (f): List(SELF\text {-}*) \times AS \rightarrow AS\) on a pair (L, s) ∈ L i s t(S E L F-∗)×A S, where L = [δ 1, … , δ n ] as follows. By induction, if n = 0, put ψ(f)(L, s) = s; if \(n \geqslant 1\), let \(L^{\prime }=[\delta _{1},\ldots ,\delta _{n-1}]\) and put \(\psi (f)(L,s) = \psi (f)(L^{\prime },f(\delta _{n}, s))\).

We checks easily that ψ(f) satisfies the two rules of action above, making it an action of L i s t(S E L F-∗) on AS. It is also easy to check that ϕ and ψ are mutually inverse, completing the proof. □

It follows that an autonomic system is an action of a free monoid on a finite set.

7 Monoid homomorphisms

Let \(\mathcal {M}:(SELF\text {-}*,skip,\mid )\) and \(\mathcal {M}^{\prime }:(SELF\text {-}*',skip^{\prime },\mid ^{\prime })\) be monoids. A monoid homomorphism f from \(\mathcal {M}\) to \(\mathcal {M}^{\prime }\), denoted \(f : \mathcal {M} \rightarrow \mathcal {M}^{\prime }\), is a function \(f : SELF\text {-}* \rightarrow SELF\text {-}*'\) satisfying two conditions:

  • \(f(skip) = skip^{\prime }\)

  • \(f(se\text {-}a \mid se\text {-}b) = f(se\text {-}a) \mid ^{\prime } f(se\text {-}b)\), for all s e-a, s e-b ∈ S E L F-∗

The set of monoid homomorphisms from \(\mathcal {M}\) to \(\mathcal {M}^{\prime }\) is denoted Hom\(_{\textbf {Mon}}(\mathcal {M},\mathcal {M}^{\prime })\).

Let S E L F-∗ = {s e-a, s e-c, s e-g, s e-u} and let S E L F-∗′=S E L F-∗3, the set of triplets in S E L F-∗. Let \(\mathcal {M} = List(SELF\text {-}*)\) be the free monoid on S E L F-∗ and let \(\mathcal {M}^{\prime } = List(SELF\text {-}*')\) denote the free monoid on S E L F-∗′. There is a monoid homomorphism \(F : \mathcal {M}^{\prime } \rightarrow \mathcal {M}\) given by sending m = (s e-a, s e-b, s e-c) to the list [s e-a, s e-b, s e-c].

Given any monoids L i s t(S E L F-∗) there is a unique monoid homomorphism from L i s t(S E L F-∗) to the trivial monoid \(\underline {1}\). There is also a unique homomorphism \(\underline {1} \rightarrow List(SELF\text {-}*)\). These facts together have an upshot: between any two monoids L i s t(S E L F-∗) and L i s t(S E L F-∗′) we can always construct a homomorphism

$$List(SELF\text{-}*)\rightarrow \underline{1} \rightarrow List(SELF\text{-}*')$$

which we call the trivial homomorphism \(List(SELF\text {-}*) \rightarrow List(SELF\text {-}*')\). A morphism \(List(SELF\text {-}*) \rightarrow List(SELF\text {-}*')\) that is not trivial is called a nontrivial homomorphism.

Proposition 2

let F(SELF-∗):(List(SELF-∗), [], ‡) be the free monoid on SELF-∗, and let \(\mathcal {M}:(M, skip, \mid )\) be any monoid. There is a natural bijection

$$\text{Hom}_{\textbf{Mon}}(F(SELF\text{-}*), \mathcal{M}) \stackrel{\cong}{\longrightarrow} \text{Hom}_{\textbf{Set}}(SELF\text{-}*, M) $$

Proof

We provide a function \(\phi : \text {H\hspace *{.5pt}o\hspace *{.5pt}m\hspace *{.5pt}}_{\textbf {M\hspace *{.5pt}o\hspace *{.5pt}n\hspace *{.5pt}}}(F(SELF\text {-}*),\\ \mathcal {M}) \longrightarrow \text {Hom}_{\textbf {Set}}(SELF\text {-}*, M)\) and a function \(\psi : \text {Hom}_{\textbf {Set}}(SELF\text {-}*, M) \longrightarrow \text {Hom}_{\textbf {Mon}}(F(SELF\text {-}*), \mathcal {M})\) and show that they are mutually inverse. Let us first construct ϕ. Given a monoid homomorphism \(f : F(SELF\text {-}*)\\ \longrightarrow \mathcal {M}\), we need to provide ϕ(f) : S E L F-∗ → M. Given any s e-g ∈ S E L F-∗ we define ϕ(f)(s e-g) = d e f f[s e-g].

Now let us construct ψ. Given p : S E L F-∗ → M, we need to provide \(\psi (p) : List(SELF\text {-}*) \longrightarrow \mathcal {M}\) such that ψ(p) is a monoid homomorphism. For a list L = [s e-g 1, … , s e-g n ] ∈ L i s t(S E L F-∗), define ψ(p)(L) : p(s e-g 1)∣…∣p(s e-g n ) ∈ M. In particular, ψ(p)([]) = s k i p. It is not hard to see that this is a monoid homomorphism. It is also easy to see that ϕ; ψ(p) = p for all p ∈ Hom Set (S E L F-∗, M). We show that ψ; ϕ(f) = f for all \(f \in \text {Hom}_{\textbf {Mon}}(F(SELF\text {-}*),\mathcal {M})\). Choose L = [s e-g 1, … , s e-g n ] ∈ L i s t(S E L F-∗). Then

$$\begin{array}{@{}rcl@{}} \psi(\phi f)(L) &=& (\phi f)(se\text{-}g_{1}) \mid {\ldots} \mid (\phi f)(se\text{-}g_{n}) \\ &=& f[se\text{-}g_{1}] \mid {\ldots} \mid f[se\text{-}g_{n}] \\ &=& f([se\text{-}g_{1}, \ldots, se\text{-}g_{n}]) \\ &=& f(L) \end{array} $$

□

8 Conclusions

In this paper, based on algebraic objects called monoids, we have algebraically specified to autonomic computing (AC) from which some useful properties of AC emerge. Monoids are tasked with encoding the perspective of self-* action in all this, i.e. what the self-* action can do, and what happens when different self-* actions are done in succession. A monoid is construed as a set of self-* actions, together with a formula that encodes how a sequence of self-* actions is itself considered a self-* action.