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].