Appendix A

Mirage & Shannon

In developing a new model for communication protocol analysis, we should examine the seminal work in the area, by C. Shannon. His work explains the operation of many communication models. This is a comparison of Mirage to it. It is also hoped that the Mirage model will reduce to Shannon’s, in the case where latency is negligible relative to the other communication parameters.

A.1. The channel

Shannon’s mathematical model of communication defines channel bandwidth and capacity, and analyzes the capacity of the channel under the constraint of transmission error [Sh63]. In his model, nodes are connected by channels characterized by bandwidth alone (latency is ignored). His analysis determines the amount of information transmitted across a channel, given the transmission errors of that channel.

In this model, the channel can viewed as a pipe between the communicating nodes (Figure A.1). Bandwidth is a unit of volume of flow in this pipe – bits wide times signal duration. Note that the propagation (latency) of this volume as it traverses the pipe is ignored – Mirage adds this factor, in its extension of this model.

Figure A.1

Shannon’s communication channel

Mirage adds a spatial measure to the connectivity measure of Shannon’s communication theory. In addition to width, the connecting channel thus has a length (Figure A.2).

Figure A.2

Mirage’s communication channel

One the test of the Mirage model is that it reduce to Shannon’s where latency is negligible. Mirage adds a latency measure to the channel characterization, but this can be ignored if the state transformation equations ignore the latency measure, so the reduction holds.

A.2. State transformations

Shannon’s model is based on a denoting the state of a node as a point in state space, implying that the values at the node are known precisely at remote nodes. This is implicit in the communication model, which attempts to emulate the transitions of the transmitter by equivalent transitions in the receiver (Figure A.3).

The communication is based on a model of the channel as it corrupts information that traverses it. Each action of a participant alters the state space point by moving it to a new point. Sending and receiving data are both modeled as motions of single points in state space. The elapsing of time is not modeled in this scheme.

Figure A.3

State space point transformation

In Mirage, the sender models the receiver as a set of points in state space. The endpoints of the channel are considered, rather than the channel itself. Each node in the system models each other, to some extent. These models are sets of points, which, in an appropriately transformed space, comprise a volume. Transformations on that volume represent the functions of the communicating system (Figure A.4). When a node sends a message, its model of the state of the destination of that message expands; when a node receives a message, its model of the source of that message contracts. Time causes the model of the remote node to expand, reflecting the increased uncertainty in the knowledge of the remote state.

Figure A.4

Visualization of state space volume transformations

A.3. Levels of communication

In the introduction to Shannon’s work, W. Weaver describes three levels of communication [Sh63]. These levels define the layering of the communication problem, each level being dependent on the successful communication of information at the previous level. Associated with each level is a problem, which determines the extent to which the communication at that level can succeed (Table A.1).

The first level is called the PRECISION level, and it is associated with the technical problem of determining the transmitted symbol from the received signal. Communication at this level assures that a mapping is established between the signals on the opposite ends of the channel. The extent to which the symbol association is repeatable determines the most fundamental limit of communication.

The second level is called the ACCURACY level, and it is associated with the semantic problem of identifying the meaning of the symbol received. This determines the correctness of the received information, relative to the intended information sent.

The third level is called the BEHAVIORAL level, and it is associated with the effectiveness of the communicated message. Effective communication is correlated with the desired behavior of the receiver, i.e., if the receiver acts as if it received the correct information, then we infer that it has.

Level Name	Defined Characteristic	Net result on communication
technical	precision	repeatable
semantic	accurate	correct
effective	correlate to desired behavior	reaction

Table A.1

Weaver’s 3 levels of communication

Shannon’s work focuses on the technical problems at the precision level, although there are applications of his theory to the other levels as well. Each of these levels is concerned with errors in communication, either in reliability, correctness, or resulting behavior.

A.3.1. Extensions for time

In Mirage we are interested in extending Shannon’s theory to its application in high speed, wide area networks. We have already discussed that the major effort here is to sensitize the problem to communication latency, as such, we consider how to extend Shannon’s model to account for latency, as it already accounts for error.

One constraint of our extension is that, where latency is negligible, it collapses to the original model; thus it will be an extension to the model. Other constraints are that the model be useful, i.e., that it describes the new domain effectively and that it enables the derivation of protocols that account for this increased latency. We also prefer the model to exhibit these characteristics by an extension that is minimal, but this is not addressed here.

A.3.2. Time vs. error

One of the fundamental results of Shannon’s theory is that any amount of channel error (below 100%) can be removed by sufficient encoding. Given encodings over arbitrarily long sequences of transmitted symbols, the effective error of the channel can be reduced as low as desired (but never removed completely). The effect of error compensation and reduction is to require encoding, which requires delaying the symbol stream by the length over which encoding is performed. As such, error reduction is traded for an increase in propagation delay.

Mirage examines the complement of this, where latency is reduced by increasing the error across the channel; the error will be exhibited by the imprecision of information about remote nodes in the network. Error and latency are thus conjugate spaces, where each may be traded for the other, and some minimal product persists. The error thus introduced will be constrained, in a ‘well-behaved’ way, which represents the evolution of imprecision of information caused by elapsed time and other causes.

We define three additional levels of communication, associated with the introduction of measured latency in the channels, called lag and stability. The lag level is associated with the timeliness problem, or how to communicate some amount information within some time delay. The stability level is associated with the synchronization problem, or whether two sets of information can be synchronized to within some error in the given time lag (Table A.2). Each level has a corresponding Weaver level, as shown.

Level Name	Defined Characteristic	Net result on communication	Corresponding Weaver level
timeliness	effect within Dt	lag	Technical (repeatable)
synchrony	synchronize to within Dt	stability	Effectiveness (reaction)

Table A.2

Mirage’s 2 levels of latency

A.4. Observations

This gives a hint at the justification for seeking additional models for protocol analysis. Current models yield situations in the emerging high speed, wide-area domains where utilization of the communication capacity can be low. New models may explain this phenomenon more precisely, and perhaps indicate methods that alleviate such degradation.

In Mirage, there are three forms of communication: real, virtual direct, and virtual indirect. Real communication corresponds to Shannon’s communication, where information is transmitted, and the intent of the sender is decrypted by the receiver. Virtual indirect communication is derived information about a set of nodes, given global constraints on the state spaces of all nodes combined with real communication from some other set of nodes. This is also known as inferred or derived communication, and corresponds to common knowledge.

Mirage uses a third form of communication, that of virtual indirect. This is information derived from local constraints about the state evolution of a node and the absence of other communication from that node. Virtual indirect information is contained in the state evolution function of a node’s individual perception, i.e., in the time transformation function of Mirage.

Appendix B

Mirage & Physics

Mirage was originally conceived of in terms of quantum physics analogs [To89]. These analogies helped develop the Mirage model, so it is useful to present some of these discussions here, for historical purposes.

B.1. Origins of the analogy

The origins of Mirage began with discussions of state space evolution, and with the imprecisions in that space introduced by communication latency. This latency corresponds to a latency of interaction, which governs the degree of coupling of systems separated in time. This is loosely analogous to particle interaction by force-carrier exchange. Mirage is an attempt to integrate ideas from particle interaction of quantum physics and information theoretic analysis to develop a communication protocol model, as depicted in Figure B.1.

Figure B.1

Mirage’s relationship to other sciences

B.1.1. Field interaction as communication

A protocol can be considered analogous to field interaction as explained by particle exchange in quantum physics (Table B.1). In this analogy, a field is communication, i.e., action at a distance. The mechanism of interaction is field quantum exchange, analogous to packet exchange. Traditional particles in the field are nodes, thus emphasizing the blurred distinction between particles and field quantum, i.e., between data packets and nodes. Uncertainty of particle interaction corresponds to latency of interaction, and the effects of high speed extend the model of interaction, in the manner of relativistic effects.

Physics	Protocol / Network
field	communication
field quantum	packet
particles	nodes
relativistic effects	high speed
uncertainty	latency

Table B.1

Physics analogs of protocol components

In physics, interaction between particles is accomplished by the exchange of other, force-carrying particles. A matter particle emits a force particle by creating it from nothingness (and is recoiled as a result); that force particle is absorbed, causing an impulse where absorbed. If the force particle has high mass, it is hard to exchange over long distances, due to the high temporary energy debt cause by the creation of the force particle. Force particles are thus virtual, i.e., measurable only by their effect. This is discussed in further detail in [Ha88b].

B.1.1.1. Four physical forces

There are, in physics, four forces: electromagnetism, the strong nuclear and weak nuclear forces, and gravity. The strength of the force and distance over which it acts is governed by the mass of the force-carrying particle. Electromagnetism is effective over infinite distances, but affects only charged particles. Photons carry the electromagnetic force, and are bosons (spin-0).

The weak nuclear force governs radioactivity, and is effective over very small (nuclear) distances, and affects only matter particles (fermions, i.e., spin-1/2 particles, not bosons, i.e., integral spin particles). This force is carried by spin-1 vector bosons.

The strong nuclear force holds the nucleus together, and is thus effective over only nuclear distances. It is carried by gluons, which are bosons.

Gravity affects all particles, is weak, and effective over infinite ranges. Further, it is always attractive. Gravitons, which are bosons, are proposed to carry the gravitational force.

B.1.1.2. Communication forces

Communication is also effected by an exchange. Intuition is that the larger the packet of an exchange, the smaller the effective distance of the data of the packet, because interaction is restricted by latency. Larger packets incur higher latencies.

B.1.2. Further references

The analogies between fields and communication have been examined before, in the Computational Field Model (CFM) [To90b], as also discussed as Prior Work in Chapter 3. CFM equates a distributed system with a field and particles, context-switch overhead with inertia, and communication bandwidth with force. It is used to develop a self-optimizing process migration system. Mirage differs from CFM by using physics analogies to guide protocol design, where the analogy ‘homomorphism’ is given semantic justification.

With regard to the remainder of the discussion, there are a few notable references. First, [Kl75] contains a good description of the difference between probability density and distribution functions. A good overview of quantum concepts is contained in [Re91], [Ha91], [Sh88]. Original discussions of the Many-Worlds principle are contained in [De73], and an introduction to this principle is given in [Ha91]. An overview of quantum principles for non-scientists is given in [Ga65]. Lastly, an excellent historical overview and presentations on quantum principles are given in [Pe89], although this book is more commonly presented as a discussion of the ‘mental’ capabilities of discrete systems.

B.2. Existing analogies from physics

The existing analogies between communication and physics include similarities between entropy and information, uncertainty and stability, and the Hamiltonian function and state change functions.

B.2.1. Entropy

Entropy in physics is related to information in communication, as first noted by John von Neumann [Ha28]. The two are inverses, so that the negative of entropy is proportional to information; information is thus sometimes also called ‘negentropy.’ Both are proportional to the logarithm of possible state space, and are additive where systems are combined. The use of entropy in communications has thus become common.

Some discussions consider physics entropy and information entropy similar but otherwise unrelated, whereas others consider the two identical. We consider them identical for the following reason.

In physics, specifically thermodynamics, entropy is a measure of disorder. The units are calories/degree. Calories are a measure of work, energy, or heat (equivalently). Temperature is defined as energy per degree of freedom, i.e., a measure of energy extracted when degrees of freedom are unified.

In information, entropy is a measure of the log of the number of possible states, or the average number of bits required to specify a state within a partition. Entropy thus measures imprecision of state, or disorder among elements of a partition that information removes.

In both cases, entropy measures disorder, and the amount of ‘work’ required to compensate for the disorder. In physics, ‘work’ is work, heat, or energy, whereas in communication ‘work’ is information, or bits. Thus we consider physics entropy equivalent to communication entropy because we consider work equivalent to information. The only difference is that in physics the degrees of freedom are continuous[1], and in information they are binary.

B.2.2. Uncertainty

One result of the true equivalence between physics entropy and information entropy observation concerns uncertainty. The Heisenberg uncertainty principle is characterized by units of ‘action.’ [Gr84] An ‘action’ is defined as energy*time, or work*time; in communication, this is bits*time, or bit-latency, the unit of ‘distance’ in Mirage. Uncertainty is a measure of imprecision of state in physical systems, and bit-latency governs the imprecision of state in communicating systems.

Further, ‘actions’ share a property with entropy – that of observer invariance [Gr84]. In relativistic physics, some measures are not observer invariant; the length of an object depends on the relative velocity between the observer and the object. Time-of-traversal, or distance/time is invariance, because the object shortening is always coupled with a corresponding decrease in the relative time frames.

B.2.3. Hamiltonian function

The Hamiltonian function describes the state transformation of a physical system [Pe89]. The quantum equivalent of the Hamiltonian is the wave-function. In Newtonian (conventional) state space, the Hamiltonian of object location and velocity is denoted by a pair of partial derivatives, Eqs. B.1 and B.2.

Equation B.1:

Equation B.2:

‘H’ denotes the Hamiltonian, ‘p’ denotes the momentum, and ‘x’ denotes the position. The Hamiltonian encodes both the position and momentum. This will be augmented in the quantum description of the equivalent of the Hamiltonian. The pair of equations obey the Heisenberg uncertainty principle, in which the error in position times the error in momentum is always larger than a fixed constant (Eq. B.3).

Equation B.3:

B.3. Quantum analogies

Although there are some analogies between Newtonian physics and telecommunications, there are others involving quantum physics which have not yet been exploited.

B.3.1. State sets / multiple worlds

In quantum physics, the state space of a system has a single dimension for each system variable, and is called a phase space. One point in phase space thus denotes an entire configuration of the system; multiple points denote copies (or possible copies) of versions of entire systems [Pe89]. This latter phenomenon has evoked the title Multiple-Worlds, in which each world contains one system [Gr84]. In Mirage, a node models a remote state as a set of possible states, or worlds.

One implication of having multiple simultaneous possible states is that of state collapse, in which a single definite state among the possible is denoted. The denotation occurs because of some external event. In Mirage, this event is the reception of a message from the remote state being modeled.

The canonical physics example of simultaneous state is Schrödinger’s Cat experiment [Gr84]. In this experiment a delayed choice is modeled in one of two possible ways – either there are two possible worlds in which the cat is correspondingly dead and alive, or the state of the cat (dead, alive) is superimposed in the single world of the experimenter. In the former case, the state of the cat is known precisely in whatever world exists; it is the lack of information in the experimenter that causes the confusion in the choice of the correct world. In the latter, so-called Copenhagen interpretation, the cat exists in two superimposed states, and the delayed opening of the box causes the state vector to collapse.

Mirage is based on the Multiple-Worlds interpretation of quantum interaction, although we often denote the choice of the correct world as ‘state collapse’, because we model state as an expanding set that message reception collapses. The distinction is that the collapse occurs in the mind of the observer only in Multiple-Worlds, whereas that collapse is a property of the actual state of the system in the Copenhagen interpretation.

One interesting characteristic of the Multiple-Worlds interpretation is that the state of the system can be determined by the actions of the observer, in certain cases. When physical experiments were designed that emit particles (i.e., light quanta), and then the experimental apparatus is modified while the quanta are in transit, the results of the experiment change. The answer depends on the questions.

Compare the observer-creation of results with a game of Twenty-Questions, in which the participants agree not to select a goal object. The participants create replies that are random, but necessarily consistent with previous replies and some possible object. The result is that the random choices and the questions asked determine the final object, delaying the choice of the goal object (as in the delayed-choice cat experiment).

B.3.2. State set collapse

The collapse of the state set occurs in the perception of the observer or in the actual system state. In either case, the evolution of the state space set is governed by the so-called wave-function, y, and the Hamiltonian describing this evolution in Newtonian physics becomes Schrödinger’s wave equation, Eq. B.4. In this equation, the partial of the wave-function with respect to time is the same as the Hamiltonian of the wave-function [Pe89] (with appropriate constants).

Equation B.4:

The wave-function thus denotes the evolution of the system over time, even when a set of states describes the possible system states. The wave-function describes the Time Transformation of Mirage.

B.3.3. Virtual pairs

One model for interaction in quantum physics uses virtual particles. A particle is virtual if it can be measured only indirectly, through its effect on other, real (directly measurable) particles. One form of virtual particle is a member of a virtual pair, a particle and its negative image, which can be temporarily created in a vacuum by creating a temporary energy debt in the vacuum.

A second form of virtual pair denotes the two possible paths of a single particle in space. Consider the canonical double-slit experiment, using electrons rather than light. A single electron is a real particle, that should go through only one of the two slits, by Newtonian laws.

In quantum physics, the real electron becomes a set of virtual, mutually-exclusive electrons. These virtual particles travel through all paths in space-time from the emitter to the detector. Two of these paths go through the two slits. The virtual electron going through one slit interacts with the virtual electron going through the other slit, forming an interference pattern. The seeming paradox is that a single real, measurable particle apparently must go through two paths in space-time simultaneously for the interference pattern to occur.

“Any other situation in quantum mechanics, it turns out, can always be explained by saying, ‘You remember the case of the experiment with the two holes? It’s the same thing.’”

- Feynman, quoted in [Gr84]

In Mirage, this latter form of virtual, mutually-exclusive particles corresponds to the possible paths in state-space-time. These virtual paths and particles are denoted more explicitly in the application of Mirage to Petri Nets, in Appendix F.

B.3.4. Feynman path integrals

Real particle paths are the integral of the mutually-exclusive virtual particle paths and interactions therein. Richard Feynman described these path integrals in quantum physics [Gr84].

In quantum interactions, the virtual splitting is not restricted, so a real particle path is described by the integral of an infinite number of virtual particle paths. This introduces an infinity that can be removed by Feynman’s technique of renormalization.

Mirage uses a direct analog of Feynman paths in the description of the computation function governing Time Transformations, i.e., in the wave-equation. Mirage does not require renormalization, because the remote state being modeled is equivalent to a Turing Machine (TM). Over a finite time interval, a fixed number of TM state changes occur, and each state change is finitely bounded, so the resulting number of possible state paths of the TM is also bounded. This prevents the need for renormalization, because infinite path lengths and numbers are not possible.

B.4. Observations from the analogy

There are a few useful observations from these analogies between physics and communication, and particularly involving quantum interactions. Some of these observations have been presented in the Mirage model description (Chapter 2), in Prior Work (Chapter 3), and in the Mirage extension of Petri Nets (Appendix F). Other observations include the relationship between error and latency, and the interpretation of stability as denoted by these analogies.

B.4.1. Error and latency as conjugates

Error and latency are conjugates, in which the units of the product of such conjugates are ‘actions’, as described before [Gr84]. The limitation of the product in communication is the bit-latency of the channel. This limit determines the smallest error in stability, in the absence of other constraint information.

B.4.2. Stability

Stability in Mirage consists of either traditional stability, or entropic stability (Chapter 2). Traditional stability guarantees constraint of state evolution over time to a fixed subset of possible states. Entropic stability guarantees the evolution of the size of the possible states over time, but doesn’t restrict the state values to a fixed set. The Time Transformation indicates the evolution of the state space over time.

In physics, the Hamiltonian function denotes each point in phase space as a vector to the subsequent point, i.e., ‘H’ defines a vector field on phase space. Stability exists when a phase space region is closed with respect to the vector field, i.e., no vector exits the region [Pe89].

The Liouville theorem indicates that the volume of a region of phase space remains constant, but permits the size of the region to grow. The volume of a region is a measure of the number of possible states in the region, whereas the size of the region is a measure in relation to the extremes of the dimensions. The components in the region can disperse throughout phase space, but the total number of components cannot decrease; this latter view is described as the incompressibility of the vector field flow.

By the Liouville theorem, if no vector exits a region, no vector can enter either. This implies that stability violates the theorem. An example of this paradox is shown in the Hawking box.

A Hawking box is a box in thermal equilibrium, containing one black hole [Pe89]. The Hamiltonian in the box has vectors converging in the hole, i.e., there is a confluence (compression, merging) of flow lines. By the Liouville theorem, there must be a corresponding divergence of flow lines, because flow lines remain constant in overall number (incompressible flow of the Hamiltonian).

Hawking himself noted that, “I am indeed claiming that it is an objective (sic) quantum-mechanical process of state-vector reduction…which causes the flow lines to bifurcate…”[Pe89] – implying that flow lines can converge (lose information) or diverge (create alternatives).

This may seem contradictory with Mirage’s interpretation of information creation as divergence, and information reception (state-vector reduction) as convergence. This states that state vector-reduction causes flow lines in the Hamiltonian to bifurcate, whereas we claim that the reduction causes state alternatives to collapse (reducing the entropy of the state).

Divergence of flow lines corresponds to a collapse of the state space, because 1 previous state with imprecision becomes one of 2 with precision, i.e., 1 large space becomes 1 of 2 small spaces. The large ® small transformation represents the collapse of the space and the increase in information (decrease in entropy). The 1 to 1 of 2 transformation corresponds to the bifurcation of the flow lines.

Mirage thus resolves the paradox with the creation of information by an external party, i.e., the user. A similar paradox removal involves the introduction of information to a formerly closed system by biological participants [Ja55].

Appendix C

Upper Bound

This is an analysis of the comparison of the exact and continuous channel utilization formulae from Chapter 2. It will show that the complete discrete formula of channel utilization under finite branching of the message stream (Equation C.1, as repeated below) is bounded by the continuous form (Equation C.2, also as repeated below). We claim that the continuous form is an upper bound for the complete discrete form.

Equation C.1:

Equation C.2:

In order for Equation C.2 to be an upper bound to Equation C.1, Equation C.3 must hold. This simplifies (via Eqs. C.4, C.5) to Equation C.6. If Equation C.6 holds under the domain of the original formula, then the upper bound is proven.

Equation C.6 has at least two zeroes, at the endpoints (x=0, x=1) of the domain. It is also positive at arbitrary points within the domain, and continuous within the domain. Its derivative (Equation C.7) has only one zero, i.e., there is only one zero of the slope in the domain. Equation C.6 has two zeroes at the endpoints, is continuous, positive between those endpoints, and its slope has only one zero (a maximum), thus we conclude that it holds for all points in the interior of the domain.

Equation C.3:

Equation C.4:

Equation C.5:

Equation C.6:

where x Î [0,1)

D ³ 2

Equation C.7:

Equation C.6 is presented graphically below (Figure C.1), denoting the difference between the upper bound and the exact formula. ‘Fraction’ denotes FRAC(tree-depth); note that as branch degree increases from 2, the deviation increases, and the upper bound becomes less exact, especially for larger values of FRAC(tree-depth).

Figure C.1

Error between upper bound and exact channel utilization

Appendix D

The Liouville Theorem

The Liouville theorem is a result of statistical mechanics, which states constraints on the temporal evolution of state space volumes in models of closed systems [Hi56]. The terminology used here is different from that of statistical mechanics (SM), where the theorem is usually presented. What Mirage call state space, SM calls phase space. Mirage refers to a volume in that state space as representing a subset of that space that denotes a set of possible system values; SM refers to the probability density function as describing this set, and its distribution in phase space.

In our notation, the Liouville theorem states that the volume of state space representing the local state of a node cannot add or delete points. The theorem claims that every point in the original state space lies on a unique trajectory of points, of a system as it evolves in time. A system’s trajectory is completely described by one such point, because other constraints on the system completely determine its subsequent state from its current.

This indicates that, whereas the points in the original volume may later spread out in space, the overall number of points (the integral of this volume) remains constant. If the integral were to decrease or increase, it would imply that two trajectories merged, indicating that the system had been incompletely described by the state space variables and transformation rules. A closed system is permitted to move through state space, but never to bifurcate into two system instances. Volumes in the state space represent ‘competing’ instances of a system, but only one actually exists. Each system instance has its own unique trajectory, so whereas the volume can move through state space (by translation or deformation) the integral (number of possible state values in the volume) must remain constant.

The theorem applies only to closed systems; the integral of the volume of state space representing remote nodes is not part of such a system, and it thus is not a violation to speak of that volume as expanding (increasing the integral) or collapsing (decreasing the integral). The theorem is meant to convey the notion that information, in a closed system, is neither created nor destroyed over the long term. Within a node, however, information can be created. This occurs whenever I/O occurs at the node, such that the state of the system is now enhanced by external information.

The quantum aspect of this phenomenon is necessitated by the discrete values of the variables in our system – the integral is more properly a (discrete) summation. The theorem applies to the quantum domain in a similar, though distinct fashion. The implications of maintaining this theorem as it applies to Mirage will be discussed more completely in subsequent research.

Appendix E

Mirage in Set Notation

Mirage uses state space volumes to describe the possible states of a remote node. One instance of this model is a description in terms of sets of states, so that each set represents a ‘volume’ in state space. This set notation can be extended by including a probability for each state. The continuous form of state sets with probabilities is a probability density function (pdf). The following is an elaboration of the definition of the state space volume description of Mirage from Chapter 2, in terms of sets.

E.1. Definitions

Consider the set of nodes in the network. These nodes are herein completely connected, each pair (i,j) connected with a finite maximum communication bandwidth () and a finite minimum communication delay (). The following definitions will be used; the ‘equations’ below represent these definitions.

denotes a node’s finite storage. This storage is used both to denote the node’s dedicated local storage and perceptions of the storage of remote nodes.

denotes the local state of the node i, the local component of its storage.

denotes node i’s perception of node j, which is some subset of the set of all states of node j, namely (Eq. E.1).

denotes node i’s view of the network, comprised of its own local state and the set of perceptions of the other nodes (j) in the network (Eq. E.2).

The only constraint thus far is that the size of the node be sufficient to store its view (Eq. E.3). Note also that mutually recursive knowledge is permitted, provided that the recursion is bounded and finite, as required by the fixed size of local storage at each node.

Equation E.1:

Equation E.2:

Equation E.3:

E.2. Time Transform

Time transforms the perception by expanding it, thus reducing the precision in the knowledge of the state of the remote node. The temporal transformation of a perception of a remote node P over the interval is denoted by a function ; this function describes the known bounds on the state space evolution as a function of time. A node’s view thus changes over time as its local state changes, and as the time transformations of its perceptions change (Eq. E.4).

Equation E.4:

The extent to which the remote node is correctly modeled depends on the precision of this function, as characterized by the amount of state space expansion per unit time, a form of induced entropy[2], E. The ratio of the volumes describes the expansion, equivalent to the entropy increase (Eq. E.5). The imprecision describes the difference between node j’s actual state and node i’s model of that state. The entropy change per unit time is a measure of the minimum bandwidth required to compensate for the entropy change (Eq. E.6).

Equation E.5:

Equation E.6:

The computation function, C, which describes the evolution of the space over time as viewed at a distance, is a combination of the remote space evolving over time and the messages that it can receive over that time. Analysis of this function can be complex, since all possible permutations of messages and computing intervals must be accounted for. The computation function encodes known internal computation at the node j, known bounds on the information received by node j, and known message emissions from node j (i.e., all known constraints on node j).

The formula is derived by taking the union over all possible time intervals (so we include inaction over the remainder of each interval), of the way in which any point (union over all points p in P) can be transformed by any computation function c in C, such that the computation function can occur in the specified interval (Eq. E.7).

Equation E.7:

Equation E.7 denotes the computation constraint in terms of state space volume transformation. In the case where the time transformation is expressed by a probability density function (pdf), this function reduces to a convolution of the entire set of remote nodes (p’s) over the set of probability density functions (pdfs) of the transformations of individual messages that can be received (c’s) and the a time transformation pdf (Equation E.8). This reduction to convolutions requires that the time transformation is time invariant, i.e., it depends on the interval of elapsed time, but not the absolute time at which the interval occurs (Equation E.9).

Equation E.8:

Equation E.9:

E.3. Receive Transform

Receiving information collapses the perception of a remote node to a subspace of its former volume. denotes a message sent from node k, when it is received (i.e., this notation is used only within the node receiving that message).

affects node i’s perception of node k, denoted by . The total view of node i is affected only in the perception of the source of the message, so that the effect of on node i’s view contains the unchanged local state and other perceptions, and the transformed perception of the message source (Eq. E.10).

Once constraint on the receive transform is that the transformed perception is a subset of the original perception, otherwise the perception was in error (Eq. E.11).

There is a limit to the amount to which the message can reduce the volume of the perception (Eq. E.12) (on average), since the volume reduction caused by the incoming information is bounded by the information content of that message, since volume reduction is equivalent to reduction in entropy.

Equation E.10:

Equation E.11:

Equation E.12:

E.4. Send Transform

Sent messages expand the state of the message source by expanding the volume of the source’s perception of the recipient of the message. A transmitted message is denoted as , i.e., as a message transmitted to node k. This notation is used in the context of the source of the message, i.e., within node i.

affects a node’s view by transforming the perception of the remote node it is sent to (Eq. E.13), using notation similar to that of received messages. Again, the information contained in the sent message is limited by the transformation it effects, in terms of the relative volumes of state spaces indicated (i.e., entropy) (Eq. E.14).

Equation E.13:

Equation E.14:

E.5. Observations

The set notation interpretation of the abstract Mirage model is largely composed of additional notational constructions. The result of this exercise supplants this notation with formal relationships among bandwidth, message length, and the volume ratios of the original and transformed components of the state spaces. The description of the time transformation in terms of a computation function emphasizes the dependence communication on the application-layer semantics of the function of the remote node. The computation function description also led to the observation that the probability density function analog of the time transformation is pdf convolution, if the time transformation is time-offset invariant.

Appendix F

Mirage & Petri Nets

To introduce the effects of the Mirage model on protocol analysis, we demonstrate its effect on the Timed Petri Net model. The Mirage model suggests a version of Petri Nets where tokens replicate, and later annihilate each other, similarly to the interactions of virtual pairs of particle in quantum physics.

F.1. Petri Net Analogs

As another instance of the Mirage model’s application, we have selected Timed Petri Nets [Me76]. Here these nets are extended to describe the state expansion and collapse that is integral to Mirage, while preserving the graphical/formal properties of the original network.

A Petri Net is a network of nodes, called places and transitions, and arcs. The net is bipartite with respect to the sets of places and transitions; arcs connect places to transitions or transitions to places. Nodes are depots for objects called tokens, and transitions denote rules for the movement of tokens from places at the input arcs to places at the output arcs. A transition can move tokens if it is enabled, if there is at least one token matching the source of each input arc to the transition. Once enabled, the transition consumes these enabling tokens, and places a token at the places indicated by the output arcs [Pe77], [Pe62]. Timed Petri Nets include temporal constraints on the persistence of enabled transitions and the propagation of tokens along arcs [Me76].

To compose a Petri net analog of the Mirage state space subset model, consider the Petri Net (PN) normally associated with a protocol in a node. Places in this net represent conditions in the protocol, and the transitions represent transformation of sets of conditions into other conditions (Figure F.1). A marking of this net represents a particular, unique state of the node operating that protocol (Figures F.2A-E).

Figure F.1

Petri Net (unmarked)

Figure F.2

Petri Net markings

Mirage needs to represent subsets of states, i.e., more than just single states. For a particular protocol PN, there is an associated finite state machine, called a token machine (TM) of that net (Figure F.3). The states of the TM correspond to the unique markings, and the transitions in the TM represent the transformation of one marking into another, by action of the movement of tokens associated with the firing of active transitions of the PN. The state space of a Petri Net is the set of markings of that net.

Figure F.3

Token machine of a Petri Net

Consider now the PN whose places correspond to the states of the TM, and whose transitions correspond to the arcs of the TM (Figure F.4). This is also a valid model of the protocol; we call this a meta-Petri net, or MPN.

Figure F.4

Meta-Petri Net of a Token Machine

The protocol would begin in a single marking in the original PN, so there would be one token in the initial marking of the MPN, indicating that marking. Tokens in the MPN thus indicate entire markings in the original PN, which denoted states of the protocol. Note that in taking the TM of a PN into a MPN, the number of tokens of the MPN must be conserved after each firing in the MPN, because a PN firing results in only one resulting PN marking, even though the choice of which firing occurs from a given marking can be nondeterministic.

The conservation of tokens results from the construction of the machine. No transition contains more than one output, so tokens are never replicated.

For these diagrams, we consider only markings where a place is in one of two states – marked, containing a token, or unmarked, empty, a binary Petri Net. This simplifies the diagrams; Petri Net places normally are defined to contain an any number of tokens, in which case a different net could be developed which observes token conservation after some point, which this does not. In the (binary) example, state C goes to state D only once; the conventional (non-binary) PN would go to a next state that was a version of C with two tokens in the lowermost place, which is distinct from marking C.

Mirage implements transformations on the MPN that will enable the MPN to model multiple PN markings, by allowing it to violate the token conservation, under certain conditions. In the Mirage MPN, the number of tokens in the marking of a MPN reflects the entropy of the state of the node that the MPN is modeling.

F.1.1 Communication channel

So far, a Petri Net is considered a model of the entire network. In designing the Mirage-based transformations on the Meta-PN, the nodes are considered as separate subnets in the original Petri Net. One way of separating the network Petri Net is to consider a partition of the MPN into node nets and communication channel nets (Figure F.5).

Figure F.5

Network MPN partitioned into channels and nodes

In partitioning the MPN, the resulting partial MPNs are incomplete, as they have input and output arcs which are not connected. The input and output arcs of the node MPN’s are their interface to the communication channel. One of the simplest partitionings results in a channel MPN consisting of only transitions (i.e., having no places) (also Figure F.5).

The partitioning is required so that we may differentiate the state of a node from the its communication with other nodes; the reason for this difference will be shown later. Tokens in the node MPN denote the state of the node, whereas tokens in the channel MPN denote communication among the nodes.

F.1.1.1 Basic block

Further manipulation of the MPN requires the use of some definitions. We define a basic block as a subgraph of a MPN that is completely within the subgraph of a node, and which has one entry for tokens from that node, and one exit for tokens to that node (Figure F.6). It can have any number of token entries and exits to the communication channels to other nodes. The conservation of state tokens represents the point transformation model in Shannon’s theory, where one point in state space (i.e., a single token in a single place in the MPN) is transformed into another point. Communication tokens have no similar constraint.

Figure F.6

Basic block

F.1.1.2 Virtual tokens

Mirage uses a MPN where indeterminism exists, where an advantage can be gained by running the MPN into the ‘future’, with virtual tokens. A virtual token is one of a set created which causes indeterminism in a MPN. Rather than having a one token continue on a single path, a virtual token is created for each path possible (Figure F.7). These tokens then belong to a codependent set. At some later time, if any of these tokens is to be considered real, all codependents of that tokens set and all ancestors of all tokens in that set must be destroyed (Figure F.8). A token is real if it is the lone token in a MPN.

Figure F.7

Token virtualization

Figure F.8

Token realization

In token virtualization and realization, and the definition of removal of codependents is similar in principle to the visual process of a Feynman diagram. This is not a coincidence, as these operations were patterned after concepts from quantum physics. The number of simultaneous virtual tokens is also related to the size of the partition K in the Mirage stability criterion.

Token virtualization and realization can be introduced by a graph transformation in the MPN. This transformation introduces two tokens for each entering token, yet allows only one token to be emitted. In this way, virtualization and realization are implemented in the MPN.

The transformation works by the following principle. There exists a nondeterministic bifurcation into two basic blocks before the transformation (Figure F.9). After the transformation, two tokens, X and Y, are created. They affect their respective basic blocks, and exit the blocks accordingly. At that point, they are virtual tokens. They enter a mechanism that permits the first virtual token to pass, and be ‘measured’ (acted on by the rest of the T-MPN). That passage creates the measurable ‘hat’ token, and creates a token of the complement. The complement annihilates the opposite codependent token, thus maintaining the singular realization constraint (Figure F.10).

Figure F.9

MPN subgraph (before transform)

For example, if Y gets to the gate mechanism first, it passes, creating Y-hat, and X-bar. X-bar annihilates the next X token to reach the gate, causing the codependent virtual token to be destroyed. The rest of the T-MPN is permitted to act on the ‘hat’ tokens only. The feedback mechanism permits only one pair of virtual tokens from participating in the gate at one time.

Note that the messages emitted in the transformed MPN are guarded messages, where the conditional label on the message indicates which of the virtual tokens caused that message. Guarded messages are denoted by the form X:A, where X is a guard condition and A is a message.

In the pre-transformed subgraph, it is assumed that the inputs to the basic blocks have not yet arrived, so the token waits at the root (top) of the graph, and no further communication ensues. The transformation permits the messages to be sent in anticipation with appropriate guards. Later, the inputs match the virtual tokens at the meet points, where token realization is modeled. The inputs arriving first permit realization of the virtual token on their side of the subgraph.

Figure F.10

MPN subgraph (after transform)

F.1.2 Equivalences to Mirage transformations

Now we show the equivalent transformations on the MPN of time, transmission, and reception of information in the network.

F.1.2.1 Time

Time is simply the token virtualization of a subgraph of a MPN of a particular node, representing the state of the remote node. This indicates that, as far as the state of the local node is concerned, the remote node is seen as being in multiple states at once. This reflects the increase in entropy of a system when information about the state of that system is absent, and the system is known to evolve over time.

Note that the only restriction imposed by Mirage on the virtualization is that the virtual tokens remain in the MPN representing a single remote node. As soon as any of these tokens interacts with a token from the representation of another node, or the state of the local node, it must be realized, and all codependents of the virtual disappear. Local interactions involve real tokens, but remote node knowledge looks into the future with virtual tokens.

The other restriction of time virtualization is the existence of indeterminism in the MPN graph. This requires a structure as was shown for the virtualization process above. The increase in the number of tokens in the MPN indicates the increase in entropy of the state of a node, due to the increase in the state space of the perception of a remote node.

F.1.2.2 Send

Sending information similarly causes token virtualization, due to the possible loss of the transmitted message. The node sending the information must operate under the dual assumptions that the message has been correctly received and also that it has been lost (considering non-Byzantine errors only). This involves a recursive form of token virtualization, where one virtual token remains where the original real token was, and the codependent token flows through the graph ahead (Figure F.11). The virtualization is called recursive because one of the virtual tokens is placed where the original real token had been, and that virtual token is in a position of being re-virtualized (although this is possible, there may be other considerations).

Figure F.11

Sending introduces virtualization

This form of virtualization does not require indeterminism in the MPN; it introduces it to account for the potential loss of information by the channel. The basic block must have at least one output, to describe the information sent into the channel. Before the transformation, a simple message would be sent; after the transform, a guarded message is sent instead.

One consequence of this transformation is that certain PN models of protocols are changed into machines that continually emit guarded messages. This is especially true in request/reply protocols based on finite databases, whose MPN is a very shallow, highly branched tree of such basic blocks. This may hint at an analytic justification for the efficiency of ‘blasting’ protocols in such domains, where continual emission of the database is preferable to an explicit request/reply.

F.1.2.3 Receive

Reception of information causes collapse of the state space of a remote node, from which information was received. This implies that the MPN of the representation of the remote node contained a set of virtual tokens, and that these tokens are meeting the arriving messages. When a message arrives, the state of the remote node is realized, and virtual tokens disappear (Figure F.12).

The decrease of the number of tokens caused by realization indicates the reduction in entropy caused by the reception of information. This decrease affects the entropy of the perception of the node from which information was received.

Figure F.12

Reception causes realization

F.2. Capacity in a PN

Even though we can define a communication channel as a PN, the notion of channel capacity has a time dimension, so we must use Timed Petri Nets, where there are temporal constraints on the maximum and minimum times that conditions may persist at a transition before it fires, with similar bounds on the firing action itself. The definition of channel capacity would then be a function of the number of unique markings of this PN, in a given amount of time.

One definition of the maximum channel capacity involves operations on the MPN. The MPN can be extended into a Timed-MPN by analysis on the time conditions of the original net. The bandwidth of the T-MPN is related to the average number of branches in a cycle in the T-MPN, divided by the time to complete the cycle. The number of branches indicates the communication choices in the cycle, a measure of its information capacity. This capacity, over the time taken to communicate it, defines the bandwidth. The MPN must have been initiated from any of the possible markings of the input to the channel.

If we restrict a channel to a set of transitions, the capacity of the channel is defined as the number of patterns (N#transitions – for Boolean PNs this becomes 2#trans) divided by the sum of times of transition for each pattern. The time of transition for a pattern is defined as the time of the slowest enabled transition in the pattern.

The channel has input and output patterns, the capacity of the channel can be determined by considering the unique output patterns derived from the set of unique input patterns. These input/output sets can be analyzed by conventional Shannon techniques.

Appendix G

The TreeStack

The TreeStack is an abstract data structure that combines the characteristics of a stack and a tree into a monolithic entity. It was developed to facilitate the m‑Net description (Chapter 5), but may have more general application. We have not investigated the TreeStack as a formal data structure, nor have we determined whether it is novel; such investigations will be included in future work.

This is a description of the TreeStack as a formal data structure. Basic operations that define access to the structure are enumerated. One defining characteristic of the TreeStack is that it reduces a conventional tree or a conventional stack, under particular constraints.

G.1. Components

A TreeStack consists of three basic elements: a binary node, a unary node, and a leaf (Figure G.1). Binary nodes represent branchings, unary nodes represent stack elements, and leaves are the only terminal elements.

Binary Node	Unary Node	Leaf

Figure G.1

TreeStack components

G.2. Operations

The operations of the TreeStack consist of the operations on a stack (Push, Pop) and the operations on a tree (Branch, Select Subtree). If Push and Pop operations are prohibited, then a conventional binary tree results. If Branch and Select Subtree operations are prohibited, then a conventional stack structure results.

G.2.1. Push

The Push operation indicates a recursion entry point, whose exit is the corresponding later Pop. A Push operation replaces a leaf with a unary node copy of that leaf, and places the leaf as a child of the unary node (Figure G.2). A Push is defined only as a transformation on a leaf. The cost of a Push is .

Before Push	After Push

Figure G.2

TreeStack Push operation

G.2.2. Pop

A Pop operation indicates the exit of a recursion. Pops are defined only on subtrees terminating in a unary node & leaf pair. The leaf is discarded, and the unary nodes internal value is used to create a new replacement leaf, which is attached where the pair had been (Figure G.3). The cost of a Pop is .

Before Pop	After Pop

Figure G.3

TreeStack Pop operation

G.2.3. Branch

A Branch operation allows equivalent alternates to be represented in the data structure. A Branch replaces a leaf with a binary node, whose two children are two new leaves which are copies of the replaced leaf (Figure G.4). The cost of a Branch is .

Before Branch	After Branch

Figure G.4

TreeStack Branch operation

G.2.4. Select subtree

Subtree selection indicates a substructure of the TreeStack, which contains all the equivalent alternates of the children of the selected internal node of the structure. In a conventional tree a subtree is selected. In a TreeStack, a selection (i.e., the X in Figure G.5) indicates the extraction of the superior tree (i.e., children, indicated by the dotted oval), along with a path of unary nodes back to the root (the dotted path). This path denotes the recursion return information encoded in the TreeStack, such that the resulting extracted substructure is self-contained. The cost of a Branch is between and , where N is the number of overall elements in the tree, depending on whether the TreeStack is dominated by (respectively) binary or unary nodes.

Subtree selection indicated	Subtree selection extracted

Figure G.5

TreeStack Subtree Selection operation

G.2.5. Equivalence transforms - Twinning and UnTwinning

It is possible that a TreeStack structure evolves to a state where a Pop cannot be executed, even though a corresponding Push exists. Consider the case where a Push is followed by a Branch. The subsequent Pop on either leaf of the binary node is not defined. There is an equivalence between TreeStack substructures which permits a Pop to occur, given some intermediate transformations.

A unary node whose child is a binary node is equivalent to a binary node whose children are two identical copies of that unary node (Figure G.6). Conversion from the unary node/binary child to a binary node/pair of unary children is called Twinning, and the reverse transformation (where possible) is called UnTwinning. The cost of either transform is .

UnTwinned	Twinned

Figure G.6

TreeStack Twinning and UnTwinning

G.2.6. Canonical forms

There are two canonical forms of the TreeStack, one that is maximally Twinned, the other that is maximally UnTwinned. A Twinned TreeStack is efficient at Push and Pop operations, but has a high Branch cost and is inefficient in its space requirements, whereas an UnTwinned Stack is efficient in its use of space, Push, and Branch operations, but costly for Pop operations. The costs for Subtree Selection are equivalent in either form.

G.2.6.1. Twinned TreeStack

The result of Twinning is to move the binary nodes closer to the root, eventually becoming a tree of binary nodes originating at the root. The ‘leaves’ of the binary node tree are strings of unary nodes, terminating in leaves. The binary tree structure represents an encoding of the choices of alternates, i.e., alternate worlds, and the unary strings represent a conventional stack local to each world. Thus the composite structure of the TreeStack can be transformed into a conventional tree of conventional stacks (Figure G.7). The cost of transforming an arbitrary TreeStack to canonical form is at most , i.e., if the original structure is a stack of trees.

Figure G.7

TreeStack canonical form - maximally Twinned

A Twinned TreeStack is inefficient in its use of space, because stack elements are replicated among the tree alternates, to maintain strict independence among the alternates. A Pop operation costs because Twinning transformations are not required at the time of the Pop, but Branch operations are very costly, i.e., where k is the depth of the individual stacks of the alternates. In that case the entire recursion stack must be replicated in its entirety, even though much of it may never be accessed independently of other alternates.

G.2.6.2. UnTwinned TreeStack

Twinning is costly, because stack components may be unnecessarily replicated. In the case where the operations consist of a sequence of Pushes, followed by a sequence of Branches, the structure becomes a stack whose top element is a tree. Conversion of this structure to canonical form replicates elements exponentially in the depth of the stack. If the structure is left in original form, replication of internal unary nodes occurs only where Pops require them, and so some economy of time and space is achieved. UnTwinning (to the extent possible) decreases the cost of access and storage of the TreeStack (Figure G.8).

Figure G.8

TreeStack form - maximally UnTwinned

An UnTwinned TreeStack is efficient in its use of space, because the stacks of overlapping alternates are maintained as a single structure until Twinning is required. Branch operations cost , but Pop operations cost where k is the depth of the path back to the root, because of the Twinning required back along that path.

G.2.7. The Graft transform

One optimization uses an alternate storage method. In the TreeStack described thus far, a stack whose last element is a tree can cause unnecessary replication when one leaf of the tree Pops multiple levels of recursion, but where the other leaves do not Pop (Figure G.9). In the equivalence transformation, a set of k Pops would cost in space and time replication (Figure G.10). Space optimization would suggest that the equivalent structure that was not accessed should be UnTwinned (Figure G.11).

Figure G.9

Multiple Pops in max-Twinned TreeStack (before Pops)

Figure G.10

Multiple Pops after Twinning and Pops

Figure G.11

Multiple Pops after subsequent UnTwinning

Rather than performing the transformations only to undo some portion of them later, we have developed an equivalent encoding for a Pop through binary nodes, called a Graft. A leaf of an arbitrary TreeStack is Popped by traversing the TreeStack back towards the root, through binary nodes, stopping at the first unary node found. That node is then preceded by a binary node, whose one child is the unary node, and whose other child is a leaf copied from the data of the unary node (Figure G.12). The leaf where the Pop occurred is considered a null unary node (lined out in the figure), whose child is the leaf thus grafted in (the arrow in the figure). The cost of a Graft is , due to the search for the unary node.

Figure G.12

A Graft

The Graft has the advantage of permitting a Pop to occur while retaining the original branching structure that led to the leaf that popped, so that a Select Subtree can choose a subtree within that popped structure. The null unary node permits the grafted leaf to appear as a child within the selected subtree, even though that leaf is actually an alternate on a path back to the root that would normally have been removed in the subtree selection (Figure G.13). The disadvantage is that the entire tree remains after all leaves have popped, thus relying on the Select Subtree operation to prune the TreeStack structure down to its currently accessible elements. We have not analyzed the increased cost of a Grafted TreeStack subtree selection operation, or the reduction in cost due to the omission of equivalence transformations.

Graft with selection indicated	Extracted subtree selection

Figure G.13

A Graft Subtree Selection

Appendix H

m‑Scope Methods

Measurements were required to analyze the m‑Net variations, to specify parameters of the branching stream model and to determine the requirements for reasonable implementations. These measurements included limb length, recursion depth, and opcode type distributions. Existing tools performed only some of these measurements, so a method was devised to perform all the required measurements in a single environment.

H.1. Existing Tools

There are several tools that could have been used for some of these measurements. They can be grouped into four basic classes, as listed below:

• Hardware

• Software emulation

• Block tagging

• Opcode interleaving

Hardware methods were considered initially for these measurements. Most current microprocessors provide sufficient internal status on external pins that opcodes can be distinguished from other information on the data bus. A device can be designed which monitors the bus and these signal pins, and increments local counters as required. A design that does not affect performance can be implemented with existing PLA technology. The advantage to this method is that all opcodes executed are measured, the measurements are done in real time, and any executable code can be measured. The disadvantage was that our existing hardware base did not support student hardware access, and that reasonable software schemes would be more portable and more quickly implemented.

Software emulation was not possible, because of the size of the benchmarks to be tested. Software emulation reduces execution time by a factor of 50-200 (approximately), and some benchmarks used required several minutes of direct execution time. Emulation would have required hours of CPU time, which was not available here. Further, measurements we required would have necessitated modification of any existing emulator, or the design of an entire new emulator. The former was precluded by the lack of access to the source code of commercial emulators, such as Shadow[3], and the latter was precluded by time limitations.

Current opcode measurement techniques have focused on block tagging methods. In these schemes, basic blocks are determined by a preprocessor, and opcodes are inserted which measure the execution of the basic blocks only. After execution of the tagged code, statistics on individual opcode types are computed from block execution statistics and the opcode listings of each basic block. This technique adds only 10-20% to the execution time and code size of the measured program. Block tagging measurement tools include Pixie[4] and SpixTools[5]; the former was not used because we had only one DecStation 5100[6] computer, and the latter was not publicly available[7].

Another version of block tagging is called Abstract Execution (AE) [La90]. AE both saves execution time of the measured code, adding 50-80% to the execution time, and compresses measured data by several orders of magnitude. In AE, ‘interesting’ events are measured during an initial execution of the program. This trace is used to direct more detailed measurement of ‘interesting’ portions of the original program; the final measurements are scaled according to the trace proportions to produce the final output. AE thus focuses detailed measurements on statistically significant components of the original program. It was not used here because opcode interleaving provided sufficient measurements with tolerable degradation. AE’s major benefit is that unlikely portions of the source code don’t waste measurement resources, and that huge amounts of measured data are compressed. We are not concerned with resource optimization, and do not measure data address access, so we do not require trace data compression.

Block tagging was insufficient to perform the measurements we require. Block delineation is performed by static code analysis, where destinations of branch, jump, and call opcodes determine block beginnings, and any control transfer (branch, call, jump, or return) determines a block end. Dynamic opcodes are not analyzed in this method, because the destination of dynamic control transfers (call, jump, branch) cannot be predicted before runtime without additional assumptions. Further, the basic block defines the limb length; its measurement cannot be sufficiently modified to accommodate basic blocks whose interiors contain jumps, calls, or returns, as some of our measurements required.

Instruction interleaving was the final classification of measurement methods. Interleaving can be static, i.e., by modification a-priori of the object code, or dynamically, using software interrupts.

Software interrupts can be used dynamically to interleave the opcode stream with execution of the measurement code. In a SPARC the dual instruction pointers can be used to replace the next opcode with a trap instruction, where the software interrupt caused by the trap causes the measurement code to execute. This method also slows execution by two orders of magnitude.

We chose static instruction interleaving on a Sun SPARCstation, due to accessibility of the workstation (five were used for these experiments). The method was chosen to permit measurement of limb length statistics under various definitions of basic block delineations, and to perform more conventional opcode occurrence statistics in a dynamic instruction sequence.

H.2. The method

m‑Scope (i.e., MicroScope) is a sequence of steps that performs dynamic opcode traces on a SPARC CPU. The current method is designed any language, provided that intermediate SPARC assembler code is accessible by m‑Scope.

If the source code is in C, the MSCOPE.h C-language file is included at the beginning of the source code, to prevent warning messages; equivalent assembler directives could have been determined from this C-code and included in the final assembler output.

The SPARC assembler output is passed through two AWK scripts. The first script, INSERT_SYMBOLS, adds temporary placeholders for various measured opcode types and limb sequences. Every type of opcode measured is followed by a placeholder. Limb lengths are measured by inserting limb length calculation placeholders whenever an opcode occurs which terminates a limb of a particular type. For example, branches cause all types of limbs to terminate, whereas returns cause only some categories of limb measurements to indicate a limb end. The placeholders are pseudocodes for operations, which include increment, increment by 2, decrement, and index; the latter pseudocode increments a value at some offset in an array (with bounds checking).

The second script, INSERT_OPCODES, replaces inserted placeholders with SPARC assembler that tabulates measurements as indicated. Opcode type occurrences cause global counters to increment, whereas limb length occurrences cause an increment in a histogram of limb lengths of the type of limb terminated, and a resetting of that limb length counter. The limb counters allow limb lengths to be calculated across calls, subroutines, and jumps, as some types of limb measurements required. Opcode type occurrences add 3 opcodes for every opcode occurrence; limb occurrences add up to 16 opcodes for each limb end occurrence. In the benchmarks we measured, these two scripts added an average of 7 to 10 opcodes for each original opcode, i.e., the object code was increased by 7-10x, and execution time was similarly increased.

This method of opcode interleaving was proposed independently, but is a specific example of a general technique of source code debugging and measurement. We noted an identical method published concurrently with our development [Ka91]; we then contacted the authors of this work, who provided us with extensive source of their tools. These tools and AWK scripts were used to debug and verify our techniques. Our scripts are believed more efficient and compact, and perform types of measurements of particular interest herein, whereas their scripts measure other data not required here. We use their compensation for SPARC “annulled” instructions in our method.

The final SPARC assembler code contains all measurements code inline with the original opcodes, and a final call to the output routine is also included. This routine is written in C-language code (MSCOPE.c), and is compiled separately, and linked after the assembly of the SPARC code. It computes and outputs the statistics in the desired format.

Other files developed included an AWK script to measure the static opcode distributions of SPARC assembler (STATIC_COUNT), and various scripts to take given dynamic and static output files and merge the statistics. These latter scripts were written on a personal computer, in a script not suitable for linear ASCII output, and are not included here.

H.3. Observations

There were several observations made in the process of the development of m‑Scope. First, the entire technique required approximately two weeks of programming, and the resulting measurements increased static code sizes and execution times each by 7-10x. The largest file was the GNU C compiler, which took approximately 10 hours of SPARC CPU time on our workstations, which was reduced to 2.5 hours by distribution of the process across 5 CPUs (parallelization was not evenly distributed due to quantization of the compilation phases). The original C compiler object code was 1 Megabyte in size, whereas the self-measuring object code was 8 Megabytes.

Static opcode distributions were compared to dynamic opcode distributions, and were nearly equivalent. We attribute this equivalence to size of the selected benchmarks, such that initialization code did not unduly skew the static distributions in comparison, and to the uniformity of the dynamic executions in traversing a uniform distribution of component blocks of static opcodes.

Indirect opcodes occurred less than 0.3% in the dynamic opcode measurements, and not at all in some of the benchmarks. Inspection of the SPARC assembler code indicated that the GNU C compiler (an unmodified version of which is the usual compiler on our systems) generated indirect opcodes only where C source code required a subroutine to return a C-language data structure rather than a conventional predefined C-language data type. Indirect calls were used there; the SPARC has no indirect branches, and indirect jumps were not found in any benchmark.

The UNIMP SPARC opcode, representing unimplemented instructions, was also generated by the compiler in response to the same condition. The UNIMP instruction was inserted to force a software interrupt when the destination of the indirect instruction failed to modify the executable code; this device permitted detection of the use of a non-standard C-language feature in environments that may not have supported it. A sufficient supporting environment would overwrite the UNIMP instruction, thus preventing the interrupt, whereas a deficient environment would result in a software failure.

Finally, the use of “annulled” instructions complicated the design of m‑Scope substantially. These architectural methods, along with internal pipelining, inhibit measurements of this kind. Future architectures that include hardware for direct measurement of opcode streams would be useful, and have been proposed, but unfortunately have not affected consumer-level CPU designs.

H.4. AWK scripts and C-language code listings

The following are the AWK scripts and C-language code listings. They are available from the author for research use.

H.4.1. MSCOPE.h - C-language ‘include’ file

/* Joe Touch 5/11/91 - added for tracing */

#include <stdio.h>

extern long JTbranch;

extern long JTjump;

extern long JTret;

extern long JTcall;

extern long JTjumpI;

extern long JTcallI;

extern long JTreccall;

extern long JTtotal;

extern long JToldall;

extern long JToldbcr;

extern long JToldb;

extern long JTlinearall[1024];

extern long JTlinearbcr[1024];

extern long JTlinearb[1024];

extern long JTcalldepth;

extern long JTcallall[256];

extern long JTretall[256];

/* Joe Touch -end */

H.4.2. INSERT_SYMBOLS - AWK, inserts signals in SPARC assembler

# branches (always direct)

/^ b((n?(e|z))|((g|l)e?u?)|((c|v)(c|s))|(n|pos)|(neg)),a / {

branch = 1;

annul = 1;

}

/^ b((n?(e|z))|((g|l)e?u?)|((c|v)(c|s))|(n|pos)|(neg)) / {

branch = 1;

}

/^ fb((u?(g|l)e?)|(n?(e|z))|(ue?)|(n|o|lg)),a / {

branch = 1;

annul = 1;

}

/^ fb((u?(g|l)e?)|(n?(e|z))|(ue?)|(n|o|lg)) / {

branch = 1;

}

/^ cb((0?1?2?3?)|(n)),a / {

branch = 1;

annul = 1;

}

/^ cb((0?1?2?3?)|(n)) / {

branch = 1;

}

# jumps

/^ ((jmp)|((f|c)?)b(a?)),a / {

jump = 1;

ba_annul = 1;

}

/^ ((jmp)|((f|c)?)b(a?)) / {

jump = 1;

}

# calls

/^ (call|jumpl) / {

call = 1;

}

#/\#PROLOGUE\# 0/ {

# local_call = 1;

# }

# returns

/^ ret((l|t)?)/ {

ret = 1;

}

/^ call \.stret4/ {

call = 0; # cancel call

ret = 1; # treat as a return

}

/\.proc/ {

new_proc = 1;

# insert local call code after the next label

}

(new_proc == 1) && /.+\:/ {

new_proc = 0;

print $0;

printf "JT_OP inc _JTreccall\n";

printf "JT_OP inc _JTcalldepth\n";

printf "JT_INDEX _JTcalldepth ZERO _JTcallall 0xFF\n";

next;

}

# check for indirect calls and jumps

((jump == 1) || (call == 1)) {

if ($0 ~ /\%[gGlLiIoO]?[0-9]+.*/)

indirect = 1;

}

# use the following flags instead of repeating elaborate conditionals

(branch == 1) || (call == 1) || (ret == 1) || (jump == 1) {

delaynext = 1;

}

(branch == 1) || (call == 1) || (ret == 1) || (jump == 1) {

resetALL = 1;

}

(branch == 1) || (call == 1) || (ret == 1) || (indirect == 1) {

resetBCR = 1;

}

(branch == 1) || (indirect == 1)) {

resetB = 1;

}

# modes - branch, call, jump, ret, annul, delaynext, delayed, etc.

# early abort

/ unimp / {

print $0;

next;

}

($0 !~ /^ ?!/) && ($0 !~ /:/) &&

($0 !~ /^( |( ))*\./) && ($0 !~ /\=/) {

if (delayed == 1) {

print $0;

if (annul == 1)

printf "JT_OP dec _JTtotal\n";

if (ba_annul == 1)

printf "JT_OP inc _JTtotal\n";

ba_annul = 0;

annul = 0;

}

if (branch == 1) {

printf "JT_OP inc _JTbranch\n";

}

if (jump == 1) {

if (indirect == 1) {

printf "JT_OP inc _JTjumpI\n";

}

printf "JT_OP inc _JTjump\n";

}

if (call == 1) {

if (indirect == 1) {

printf "JT_OP inc _JTcallI\n";

}

printf "JT_OP inc _JTcall\n";

}

if (local_call == 1) {

printf "JT_OP inc _JTreccall\n";

printf "JT_OP inc _JTcalldepth\n";

printf "JT_INDEX _JTcalldepth ZERO _JTcallall 0xFF\n";

}

if (ret == 1) {

printf "JT_OP inc _JTret\n";

printf "JT_OP dec _JTcalldepth\n";

printf "JT_INDEX _JTcalldepth ZERO _JTretall 0xFF\n";

}

if (resetALL == 1) {

printf "JT_INDEX _JTtotal _JToldall _JTlinearall 0x3FF\n";

resetALL = 0;

}

if (resetBCR == 1) {

printf "JT_INDEX _JTtotal _JToldbcr _JTlinearbcr 0x3FF\n";

resetBCR = 0;

}

if (resetB == 1) {

printf "JT_INDEX _JTtotal _JToldb _JTlinearb 0x3FF\n";

resetB = 0;

}

if (delayed != 1) {

if ((delaynext == 1) && (ba_annul == 0))

printf "JT_OP add2 _JTtotal\n"

else

printf "JT_OP inc _JTtotal\n";

print $0;

}

delayed = delaynext;

delaynext = 0;

branch = 0;

call = 0;

jump = 0;

ret = 0;

local_call = 0;

indirect = 0;

next

}

# take care of comments, assembler directives...

{

print $0

}

H.4.3. INSERT_OPCODES - AWK, signals become SPARC assembler

/JT_OP/ {

# JT_OP $2=(inc|dec|add2) $3=counter

printf "\tsethi\t%%hi(%s),%%g7\n",$3;

printf "\tld\t[%%g7+%%lo(%s)],%%g6\n",$3;

if ($2 ~ /inc/)

printf "\tinc\t%%g6\n"

else if ($2 ~ /dec/)

printf "\tdec\t%%g6\n"

else if ($2 ~ /add2/)

printf "\tadd\t%%g6,0x2,%%g6\n";

printf "\tst\t%%g6,[%%g7+%%lo(%s)]\n",$3;

next

}

/JT_INDEX/ {

# JT_INDEX $2=current $3=old $4=array $5=boundmask

# insert code to increment the offset based on the current totals

printf "\tsethi\t%%hi(%s),%%g7\n",$2;

printf "\tld\t[%%g7+%%lo(%s)],%%g6\n",$2;

# suntract the previous value, if not ZERO

if (!($3 ~ /ZERO/)) {

printf "\tsethi\t%%hi(%s),%%g7\n",$3;

printf "\tld\t[%%g7+%%lo(%s)],%%g7\n",$3;

printf "\tsub\t%%g6,%%g7,%%g6\n";

}

# mask out the bound

printf "\tand\t%%g6,%s,%%g6\n",$5;

# multiply by the size of a long int

printf "\tsll\t%%g6,0x2,%%g6\n";

# g6 now has the length - add the base

printf "\tset\t%s,%%g7\n",$4;

printf "\tadd\t%%g7,%%g6,%%g7\n";

# g7 now has the index location - increment it

printf "\tld\t[%%g7],%%g6\n";

printf "\tinc\t%%g6\n";

printf "\tst\t%%g6,[%%g7]\n";

# insert code to reset the old total to the new total

# do if prev value not ZERO

if (!($3 ~ /ZERO/)) {

printf "\tsethi\t%%hi(%s),%%g7\n",$2;

printf "\tld\t[%%g7+%%lo(%s)],%%g6\n",$2;

printf "\tsethi\t%%hi(%s),%%g7\n",$3;

printf "\tst\t%%g6,[%%g7+%%lo(%s)]\n",$3;

}

next

}

{

print $0

}

H.4.4. MSCOPE.c code - output desired statistics

/* Joe Touch 5/11/91 - added for tracing */

#include <stdio.h>

long JTbranch = 0;

long JTjump = 0;

long JTret = 0;

long JTcall = 0; /* all calls */

long JTreccall = 0; /* calls counted in recursion*/

long JTjumpI;

long JTcallI = 0;

long JTtotal = 0;

long JToldall = 0;

long JToldbcr = 0;

long JToldb = 0;

long JTlinearall[1024];

long JTlinearbcr[1024];

long JTlinearb[1024];

long JTcalldepth = 0;

long JTcallall[256];

long JTretall[256];

/* call with a string naming a file to be dumped into */

extern JT_dump();

/* Joe Touch -end */

/* Joe Touch - 5/11/91 added for tracing */

#include "JT.extern.h"

JT_dump(filename)

char *filename;

{

FILE *outfile;

int i;

double allsum, bcrsum, bsum;

double psumall = 0, psumbcr = 0, psumb = 0;

double callpsum = 0, retpsum = 0, retsum, callsum;

outfile = fopen(filename,"w");

bsum = JTbranch + JTjumpI + JTcallI;

bcrsum = JTbranch + JTcall + JTret + JTjumpI;

allsum = JTbranch + JTcall + JTret + JTjump;

#define JT_PERCENT(x) (((double)(x)) * 100.0 / ((double)(JTtotal)))

fprintf(outfile,"DYNAMIC CODE MEASUREMENTS\n");

fprintf(outfile,"Branches = %10d\t%7.3f%%\n",

JTbranch,JT_PERCENT(JTbranch));

fprintf(outfile,"Jumps = %10d\t%7.3f%%\n",

JTjump,JT_PERCENT(JTjump));

fprintf(outfile,"I- Jumps = %10d\t%7.3f%%\n",

JTjumpI,JT_PERCENT(JTjumpI));

fprintf(outfile,"Calls = %10d\t%7.3f%%\n",

JTcall,JT_PERCENT(JTcall));

fprintf(outfile,"I - Calls = %10d\t%7.3f%%\n",

JTcallI,JT_PERCENT(JTcallI));

fprintf(outfile,"Rec Calls = %10d\t%7.3f%%\n",

JTreccall,JT_PERCENT(JTreccall));

fprintf(outfile,"Returns = %10d\t%7.3f%%\n",

JTret,JT_PERCENT(JTret));

fprintf(outfile,"Others = %10d\t%7.3f%%\n",

JTtotal - (JTbranch + JTcall + JTret + JTjump),

JT_PERCENT(JTtotal - (JTbranch + JTcall + JTret + JTjump)));

fprintf(outfile,"INDIRECT = %10d\t%7.3f%%\n",

JTjumpI + JTcallI,JT_PERCENT(JTjumpI + JTcallI));

fprintf(outfile,"- ALL = %10d\t%7.3f%%\n",

JTbranch + JTcall + JTret + JTjump,

JT_PERCENT(JTbranch + JTcall + JTret + JTjump));

fprintf(outfile,"- BCRi = %10d\t%7.3f%%\n",

JTbranch + JTcall + JTret + JTjumpI,

JT_PERCENT(JTbranch + JTcall + JTret + JTjumpI));

fprintf(outfile,"- Bi = %10d\t%7.3f%%\n",

JTbranch + JTcallI + JTjumpI,

JT_PERCENT(JTbranch + JTcallI + JTjumpI));

fprintf(outfile,"Total = %10d\n",JTtotal);

if (allsum == 0.0)

allsum = 1e8;

if (bcrsum == 0.0)

bcrsum = 1e8;

if (bsum == 0.0)

bsum = 1e8;

callsum = JTreccall;

retsum = JTret;

for (i=0; i<255; i++) {

callpsum += JTcallall[i];

retpsum += JTretall[i];

}

fprintf(outfile,"depth partial sum - number greater/eq\n");

fprintf(outfile,"DEPTH\tCALL\tRET\tcall%%\tret%%\n");

for (i=0; i<255; i++) {

fprintf(outfile,"%d\t%d\t%d\t%5.1f\t%5.1f\n",i,

JTcallall[i], JTretall[i],

100 * callpsum / callsum,

100 * retpsum / retsum);

callpsum -= JTcallall[i];

retpsum -= JTretall[i];

}

fprintf(outfile,"\n\nlen partial sum - number less/eq\n");

fprintf(outfile,"Len\tALL\tBCR\tB\tALL%%\tBCR%%\tB%%\n");

for (i=0; i< 1024; i++) {

psumall += JTlinearall[i];

psumbcr += JTlinearbcr[i];

psumb += JTlinearb[i];

fprintf(outfile,"%d\t%d\t%d\t%d\t%5.1f\t%5.1f\t%5.1f\n",i,

JTlinearall[i],JTlinearbcr[i],JTlinearb[i],

100.0 * psumall / allsum,

100.0 * psumbcr / bcrsum,

100.0 * psumb / bsum);

}

fclose(outfile);

}

/* Joe Touch end */

H.4.5. STATIC_COUNT - get static SPARC opcode distributions

# branches - ALL SPARC branches are direct

/ b((n?(e|z))|((g|l)e?u?)|((c|v)(c|s))|(n|pos)|(neg))(,a)? / {

branch++

}

/ fb((u?(g|l)e?)|(n?(e|z))|(ue?)|(n|o|lg))(,a)? / {

branch++

}

/ cb((0?1?2?3?)|(n))(,a)? / {

branch++

}

# jumps can be direct or indirect

/ ((jmp)|((f|c)?)b(a?))(,a)? / {

jump++;

if ($0 ~ /\%[gGlLiIoO]?[0-9]+.*/) {

i_jump++;

print "I-JUMP: ",$0

}

}

# calls can be direct or indirect

/ (call|jumpl) / {

call++;

if ($0 ~ /\%[gGlLiIoO]?[0-9]+.*/) {

i_call++;

print "I-CALL: ",$0

}

}

# returns

/ ret((l|t)?)/ {

ret++;

}

($0 !~ /^!/) && ($0 !~ /:$/) && ($0 !~ /^ \./) {

total++;

}

END {

if (total != 0) {

all = branch + jump + call + ret;

bcr = branch + call + ret + i_jump;

b = branch + i_jump + i_call;

indirect = i_jump + i_call;

other = total - all;

printf "STATIC CODE MEASUREMENTS\n"

printf "Branches =\t%10d\t%7.3f%%\n",\

branch,branch/total*100;

printf "Jumps =\t%10d\t%7.3f%%\n",\

jump,jump/total*100;

printf "I- Jumps =\t%10d\t%7.3f%%\n",\

i_jump,i_jump/total*100;

printf "Calls =\t%10d\t%7.3f%%\n",\

call,call/total*100;

printf "I - Calls =\t%10d\t%7.3f%%\n",\

i_call,i_call/total*100;

printf "Returns =\t%10d\t%7.3f%%\n",\

ret,ret/total*100;

printf "Others =\t%10d\t%7.3f%%\n",\

other,other/total*100;

printf "INDIRECT =\t%10d\t%7.3f%%\n",\

indirect,indirect/total*100;

printf "- ALL =\t%10d\t%7.3f%%\n",\

all,all/total*100;

printf "- BCRi =\t%10d\t%7.3f%%\n",\

bcr,bcr/total*100;

printf "- Bi =\t%10d\t%7.3f%%\n",\

b,b/total*100;

printf "TOTAL =\t%10d\n",total;

}

}

---

[1]In thermodynamics, degrees of freedom are continuous-valued; in quantum physics, they are quantized, further blurring this distinction between information entropy and physics entropy.

[2]The notion that state reduction and volume ratios are related to entropy is not new; it has been discussed before, in [ShWe63] and [Ha28].

[3]Shadow is a SPARC emulator of Sun Microsystems. We requested access to Shadow from Sun in Feb. 1991, either in source or executable only form, and were told that Shadow is a commercial product, and so the source code was not available, even for educational uses with our offered nondisclosure.

[4]Pixie is a Digital Equipment Corporation program which does block tagging on MIPS object code.

[5]SpixTools is a program of Sun Microsystems, which performs block tagging on SPARC object code.

[6]The DecStation 5100 is a product of Digital Equipment Corporation.

[7]Again, Sun Microsystems was contacted in Feb. 1991 concerning access to SpixTools for these experiments. We were told that SpixTools had not yet been released as a product, and would not be available, even under a nondisclosure agreement, for our research. Because of ‘proprietary access’, we felt it inappropriate to compare our results to even published measurements made with this inaccessible tool, since such experiments are by definition “not repeatable.”