Preface
In this framework, by asynchronicity we mean that the coordinate functions of a function are computed independently on each other, asynchronously. Synchronicity is that special case of asynchronicity when are computed at the same time, synchronously. It is of special interest to study the iterations of which can be asynchronous or synchronous.
Our project "Topics in asynchronicity" has been thought of having two parts, part I: Boolean functions and part II: Boolean systems. While working we took the decision to split it in two books.
The source of inspiration is represented by the asynchronous circuits from electronics that can be modeled by Boolean functions iterating their coordinates in arbitrary time, independently on each other, i.e. asynchronously. The uncertainties related with the behavior of the circuits and their models are generated by technology and also by temperature variations and voltage supply variations.
In order to understand the dynamics of these systems, we give the example of the function from Table 1, whose state portrait was drawn in Figure 1 (we have adopted the terminology of state portrait, by analogy with the phase portraits of the dynamical systems theory; such drawings might be called in engineering and elsewhere state transition graphs or state transition diagrams).
Table 1 An example.
In Figure 1, the arrows show the increase of time. We have underlined in the tuples these coordinates, called unstable (or excited, or enabled), for which these are the coordinates that are about to switch, but the time instant and the order in which these switches happen are not known. In this model, each present value of the state may be followed by several possible values in the future, giving nondeterminism and also branching time in the future.
Figure 1 Dependence on the order in which are computed.
is an isolated fixed point of (a fixed point is also called equilibrium point, or rest position, or final state), where the system stays indefinitely long; it has no underlined coordinates. Unlike it, is a fixed point that is not isolated, since a transfer to it exists, from
The transition consists in the computation of even if we do not know when it happens, we know that it happens and the system, if it is in surely gets to sometime. And the transitions are similar.
The interesting behavior is in if is computed first, or if are computed simultaneously, the system gets to sometime, with a possible intermediate state; but if is computed first, then the state is reached and, as it is a fixed point of (no coordinate is underlined) the system rests there indefinitely long.
In the previous discussion:
(a) a system is identified with a function in the sense that contains all the information that gives the behavior of the system. This justifies our definitions of the Boolean functions via state portraits and, in fact, this is the motivation situated behind writing this book;
(b) the system that we refer to is Boolean (this vaguely refers at ), universal (the state space is all of ), regular (a generator function exists), asynchronous ( are not computed at the same time, but the fact that these coordinates are computed independently on each other also shows that the structure of the system is variable), nondeterministic ( have unknown durations of computation), autonomous (no input), noninitialized;
(c) the durations of computation of are subject to no restriction (this is the unbounded delay model of computation of the Boolean functions);
(d) time is discrete or continuous.
The topics that are common for the Boolean functions and the Boolean systems include morphisms and antimorphisms, invariant sets, the conditions of proper operation (race-freedom) and time-reversal, with the symmetry that it generates.
The concept of isomorphism is easily understood by looking at Figure 2, where the state portrait of a function which is isomorphic with the function from Figure 1 was drawn. To each point from Figure 1, the vector was added modulo 2 coordinatewise and the result expressed by Figure 2 is that the transitions from the first case become transitions translated with in the second case. Note the arrows and the underlined coordinates of the two functions: the behavior is the same. The morphisms present under a more general form this transfer of properties from a function to another one and this is observed by taking a look at Figure 3, representing a function that accepts a morphism from it to both functions, from Figures 1 and 2. The morphism of this example forgets the computations of .
Figure 2 This function is isomorphic with the function from Figure 1.
Figure 3 A morphism exists from this function to the functions from Figure 1 and Figure 2: the computation of is forgotten.
A nonempty set is invariant ( is kept in mind) if, whenever a computation starts in it ends in some point and two types of invariance are situated behind this intuition. We can think, looking at Figure 2, that the fixed points give the invariant sets (where the computation starts in and ends in etc.). But the set is also invariant. From the previous sets, are attractors.
The functions from Figures 1 and 2 suggest the problem of finding sets of Boolean functions where, even if we do not know the time instants and the order in which their coordinates are computed, we know that for any the values are computed sometime, in this order. Thus, the behavior of the (asynchronous) systems that we are looking for reproduces in a certain way the behavior of the (synchronous, usual) dynamical systems in their Boolean version, and this is considered to be "nice", in a context with many unknown parameters. We get the "proper operation" properties of the Boolean functions/systems. The functions from Figures 1 and 2 do not fulfill such a property, for example in Figure 2 it is not sure that is really computed, since the computation of first produces the transfer of the system from to where it rests indefinitely long. The functions from Figures 3 and 4 fulfill the proper operation property.
Figure 4 Function that accepts time reversal.
Time reversal means, roughly speaking, reversing the arrows of a state portrait. The function from Figure 2 does not accept this, since reversing the arrows that point to to arrows that start from is impossible, but the function from Figure 4 does accept. We have inserted an arrow from to The time-reversed symmetrical function of the function from Figure 4 is the function from Figure 5.
Figure 5 The time-reversed symmetrical function of the function from Figure 4.
The book is structured into chapters, sections, paragraphs, and the chapters have a short introduction and/or summary. The paragraphs are definitions, notations, remarks and also theorems, lemmas, corollaries with their proofs. We have added two appendixes containing the definition of the category whose objects are functions, and the notations respectively.
In Chapter 1, we introduce the binary Boole algebra and we give some preliminaries on Boolean functions (such as duality, iterates, state portraits, ). We sketch how the asynchronous circuits are modeled by Boolean functions.
Chapter 2 is dedicated to the affine spaces defined by two points Their meaning consists in the fact that, given the set contains the points that may be accessed when is computed asynchronously; for example, looking at Figure 4, we have and also
Chapters 3 and 3 introduce the morphisms and the antimorphisms of Boolean functions. Intuitively, the morphisms from to presume that the succession of the cause and the effect is the same, time flows in the same sense when are computed (from the past to the future, or from the future to the past); and the antimorphisms act as if for and time flows in opposite senses.
The invariant sets are treated in Chapters 5 and 5. The concept is taken from the dynamical systems theory and it is brought in this timeless framework, where we discuss as well symmetry relative to translations, maximality and minimality, disconnectedness, etc. The path connected sets are treated in Chapter 7: the visual meaning of a path connecting with is given by the existence in the state portrait of the points such that an arrow exists from to and and an arrow exists from to . Chapter 8 introduces the attractors, the nonempty subsets of satisfying a strong version of invariance together with one of: topological transitivity, minimality, and path connectedness.
Four concepts of proper...
