Wallace Markov pictorial language(ID:7342/wal003)

A Syntax of the Pictorial Language

2.1 Pictorial Languages

Formal representations of Markovian systems in diagram form are actually expressions in a graphical language.  More precisely, it is two- dimensional pictorial language, to use W.  R.  Sutherland's¹ term.  It is a means of conveying precise meaning through pictorial symbols and syntax.  Because the representations are descriptive of a problem to be solved rather than of the means of solution, such a language is also called a problem-oriented pictorial language.  The chief utility of pictorial languages arises from their compactness and from the high degree of instant recognition possible compared with textual languages.

2.1.1 An Example

Consider, for example, the diagram of Figure 2.1.  With suitable definitions, the symbols and syntax of this diagram could have the following meaning: Poisson arrivals of tasks, having mean rate of occurrence , are accepted into a queue, with up to a maximum of n₁ tasks present in the queue at any one time.  A server removes tasks from the queue and processes them for independent, exponentially distributed intervals of time having mean _l. Whenever the two other queues have less than a total of n₅ tasks present at the time of a completion, the completed task is randomly assigned to the upper queue (with probability p) or the lower queue (with probability 1- p). Otherwise the service is restarted and the server held for another exponentially distributed interval of time.  Tasks assigned to the upper queue are removed from the queue and processed, one at a time, by a server which is held for an independent exponentially distributed period of time having ₂. Upon completion of this holding, the task exits from the system and a new task is immediately drawn from the upper queue, if the queue is not empty.  Tasks assigned to the lower queue go to any of n₄ servers whenever one of them is vacant.  These servers are each held for independent exponentially distributed intervals with mean ₃. Every completion produces an exit of a task from the system, and a new task is immediately drawn from the lower queue into the vacated server, if the queue is not empty.
 

2.1.2 The Need for a New Language

That, briefly, is the meaning which can be assigned to the diagram of Figure 2.1.  In some senses, that description is incomplete because of the difficulty of systematically conveying all possible conditions and actions in English prose (i.e., textually). It will be seen later than any questions arising from the ambiguities of the description can be answered when the symbols are adequately defined.  The main issue here is that the diagram is clearly a means of description which is superior to prose.  It is compact and easy to visualize.

At present, no generally accepted pictorial language for the purpose of describing Markovian systems exists.  As used by queueing theorists and analysts, diagrams are used as discussion aids rather than as complete symbolic representations.  It is not uncommon, for example, for textbooks to use the same diagram for two different systems the difference being drawn out in the discussion.  Thus, these diagrams are usually ambiguous and can't be formally used as prototypes for a picture language.  The block-diagram representations used by some simulator programs² are unambiguous, but lack both the conciseness and the flexibility desired.  They also are more general than necessary, since they can usually be used to describe many non-Markovian systems.

It is necessary, therefore, to define a pictorial language here which can be used for the purpose.  However, rather than define a particular language, a class of languages which differ from one another only in their vocabulary will be defined.  In other words, it will not be assumed that fixed set of symbols will be used.  Rather, only the means of defining the symbols, and the form of the basic construction of expressions will be prescribed.  In this way a "living language" is constructed.  Of more practical significance, conciseness is preserved over wide ranges of application when special purpose symbols and syntactic constructions can be invented by a user as needed. This will obviate much of the awkwardness found in the simulation languages, and permit the abbreviation of frequently used constructions.

2.2 A PROPOSED SYNTAX

A network diagram (which is an expression in the picture language) will be characterized by a set of distinct symbols with lines between them. Each symbol has a characteristic shape and a number of special connection points physically located on it.  Each connecting point is the end-point of at most one connecting line, and has a specific orientation on the symbol, which identifies it.  (Points in Figure 2.1 which appear to have more than one connecting line are actually small symbols with more than one connecting point.) Each connecting line has a type (dotted, solid, etc.) and joins exactly two connecting points.

The connecting points also have types, which determine what connections can legally be made.  There are four types in use in Figure 2.1:
1) task transfer-input;
2) task transfer-output;
3) contents sensing; and
4) value collecting
Others are possible, and this is one of the syntactic variables of the language.  In the language of Figure 2.1, corrections are only permitted between a point of type (1) and a point of type (2), or between a point of type (3) and a point of type (4). The former connection is shown solid, the latter dotted.  For simplicity: only this connection syntax will be used in this report.

Finally, each symbol has a set of locations for parameters.  The orientation of the parameter identifies it and its range (integer, real, etc.) The parameter may be supplied as any algebraic expression of appropriate range.

It will be evident in the next section that the connection syntax is irrelevant to the algebraic model or its translator.  It provides only a protection against unintended constructions. An algebraic meaning for the connecting line will always exist, regardless of the point-types involved, but it may represent nonsense if the connection syntax is invalid.
 

1. Sutherland, W.  R., "The On-Line Graphical Simplification of Computer Procedures, Ph.D.  thesis, Electrical Engineering Department, Massachusetts Institute of Technology, January 1966.

2. Gordon, G., "A General Purpose Systems Simulation Program, Proc. Eastern Joint Computer Conference, Washington, D.  C., December 1961.

Semantics of the Pictorial Language

Having established a syntax, which defines+ the form which Markovian network diagrams may legally take, the meaning which the diagram conveys must be described.  This meaning can be awkwardly conveyed in English, as the description of Figure 2.1 testifies. However, our purpose is to describe this meaning in a formal algebraic form, to enable systematic transfer of this meaning to the description of a Markov chain.  In this sense, set and function concepts are used as a meta-language with which to define the picture language expressions. The English descriptions will be used to gain insight into the forms which the algebraic descriptions must take.
 

3.1 An Assumption - Meaning Independent of Context

One important property of the language which must be assumed is that each symbol have a definable meaning independent of its position (or context) in a network diagram. It will be seen in this section that each of the symbols used in Figure 2.19 as well as many others which can be invented, can be so described in English.  Since this is the case, our plan to seek to do so also in formal algebraic terms appears reasonable.

In order to distinguish between language elements are the things they represent, it will be noticed that separate terms are used.  Thus diagrams represent networks, whereas symbols represent elements, connecting lines represent connections, and connection points represent ports. (The phrase "The meaning of a language element" is synonymous to the phrase "a description of the thing represented by the language element.")

3.1.1 An Example

To give an example of a verbal, context-independent definition of a symbol, consider the following definition of a queue.  The queue has an input port, an output port, and a contents sensing port.  (For simplicity, the operation of the contents-sensing port will not be treated here.) It has a parameter, represented here by the symbol N, which indicates the maximum number of waiting tasks which can be allowed in the queue.  Let the number of waiting tasks be represented here by s.  This queue is affected whenever tasks are offered by the element connected at its input. If y₁ tasks are offered at the input, and x₂ tasks are acceptable to the element connected at the output, then s+y₁ tasks will be offered at the output.  The number of tasks actually sent to the output will be smaller of s+y₁ and x₂. The number of waiting tasks is changed to N if s+y₁- x₂ >N;to zero if s+y₁- x₂<0; and to s+y₁-x₂ otherwise.  The number of tasks acceptable to the queue, at its input is N-s+x₂. The number actually taken at the input is the smaller of N-s+x₂ and y₁.

The queue is also affected whenever tasks are requested by the element connected at its output port.  If y₂ tasks are requested at the output, and x₁ tasks are available from the element connected at the input, then y₂+N-s tasks will be requested by the queue from the element connected at its input.  The number of tasks actually taken at the input will be smaller if y₂+N-s and x₁. The number of waiting tasks is changed to N if  s+x₁- y₂>N; to zero if s+x₁- y₂<0; and to s+x₁-y₂ otherwise.  The number of tasks sent to the output is s+x₁ if s+x₁-y₂>0.

3.2 A Framework for Semantic Description of Symbols

The verbal definition of the queue is very wordy and somewhat repetitious.  The verbal description of the meaning of Figure 2.1 was also.  The key to reducing this wordiness, or at least putting it in some perspective, lies in attempting to observe the entities which all elements have in common.  Then, by naming these entities, the cumbersome phrases which describe them can be replaced by something more technical.

For example, the definition of the queue made frequent reference to "the element connected to (a port)." Such a reference is to be expected in the definition of perhaps every element which has a port, unless the elements related by the connection are truly independent of one another.  Thus, the term associate will be used to refer to an element connected to the element under study.  The term associate at (a port) can be used when specification of the port is necessary.

3.2.1 State Variables

Less trivially, the phrase "the number of tasks waiting" describes the status of the element at any particular time. It is to be expected that there will be similar status variables for other elements, like the "number of tasks in service" for a multiple server element, or "the current phase of service" for servers with Erlang distributed holding times.¹ Such variables, when they are present in an element, will be referred to as state variables of the element, or sometimes as state components (for reasons that will be clear in the next section). There may be more than one such variable for a single element, for combinations of element should also be legal elements of a system.  To illustrate, Figure 3.1 demonstrates a possible equivalence, in diagram form, between a "holding server" and a queue and server connected together.  The state variables might well be jointly the "number waiting" and the "number in service.  "

The range of values which the state variable of an element can assume is a set which is distinctive of the element.  We call this set S the state set of the element.  It is also a property of the element, like the set P of ports of the element.  That is, an element e consists of a set P, a set S, and other things.  The members of S are either integers or integer vectors, depending on whether there is one, or more than one, state variable to the element.

Table I lists a set of useful symbols for a pictorial language for Markovian networks, along with their names, the semantics associated with their state variables, their state sets, and some other properties which will be described in subsections 3.2.2 and 3.2.3.  A verbal description of the meaning of some of these symbols will be given in section 3.3 and in section 5.

3.2.2 Parameters

The symbol N stood for "the maximum number of waiting tasks which can be allowed in the queue" in the definition of the queue.  This was an example of a parameter.  Parameters have many significances in elements.  Generally, they represent variables upon which the behavior of the element depends, but which do not change with the status of the element.  As far as this treatment is concerned; the parameters are constants.  Other uses of parameters are as mean values of probability distributions, probabilities of branches, etc.  Table I supplies the meanings of parameters, and the sets from which their values must be taken, for some symbols.

Because they are constants, parameters will be ignored in the remainder of this report.  Any property of an element can be treated, in general, as a function of the parameters of the element without difficulty.

3.2.3 Epochs

Sometimes, when a symbol is being defined it is necessary to refer to points in time when something occurs (according to a probabilistic rule). Such a time is called an epoch. To illustrate, the definition of a server having exponentially distributed holding times of mean will contain a statement to the effect "a service completion occurs with probability intensity, whenever a task is present," and other statements to the effect "whenever a service completion occurs…" The times of "service completions" are epochs.

If epochs are points in time at which something occurs, then epoch classes are sets of those points selected by some semantic identification. If the probabilistic rule determining whether or not a particular time t is a member of an epoch class is purely determined within an element, then that epoch class will be termed an autogenous (self-generated) epoch class of the element, and its members are autogenous epochs.  The semantics of autogenous epoch classes for the sample group of symbols are listed in a column of Table I.  They are all characterized by the fact that they can be thought to occur spontaneously within the element, and are not "triggered" from actions (or epochs) of the associates.

Such triggering epoch classes, which will be called exogenous epoch classes, will be discussed in the section 3.2.4.  Epochs and epoch classes will be defined more abstractly, in stochastic terms, in Section 6.

3.2.4 Port Variables

A rereading of the definition of the queue will recall a whole group of special phrases which refer to the influence of the associates of the queue. These phrases, like "the number of tasks acceptable to . . . ," "the number of tasks available from.  . ., " "the number of tasks requested by.  . . " or "the number of tasks offered by" represent variables sufficiently generalized that they continue to have meaning independently of the nature of the associate.  Indeed, it will be seen shortly that they will have a technical meaning whenever the connection to the associate is syntactically allowable.

These phrases are used to describe what is "seen" through a connection either when looking from the queue toward the associate or from the associate toward the queue.  The first two, "the number of tasks acceptable to . . . " and "the number of tasks available from. . . ", appear to play a role similar to that of the state variable when ". . . " is replaced by "the associate." Like state variables, they describe an observed condition of the element; but in this case the condition is external to the element.  Such a variable will be called an exocondition (short for exogenous condition: a condition having external origin) at the designated port.

An exocondition of an element e is determined by the nature of the associate (call it e') of e, as a function of properties or conditions observed in the associate.  This function, as yet not identified, is a property of e'. Its value, for example, is "the number of tasks acceptable to e'." To e it is external, to e' it is internal.  We will call this function an endocondition (for endogenous condition: a condition proceeding from within) function of e', and its values will be called endoconditions.  Clearly, if e' is to have exoconditions, then conversely e must also have an endocondition function.

The fact that there is a single variable "seen through the port" which, in combination with those "seen through" the other ports, is all that needs to be known about the status of the rest of the network, is a very interesting one.  It is a property of networks which seems natural, but which is, in fact, an assumption to be made about queueing networks. This assumption will be made here.  It implies that all influences between elements are explicitly shown by the connections between them, and that influences from remote elements are achieved only through influences by them of the closer elements.  Networks having this property will be called explicit.  It appears that explicitness of a network is a necessary condition for the existence of a context-independent definition of elements.

Earlier we referred to epoch classes whose probabilistic rule of occurrence was external to the element under study.  An example of this is the time-point represented by the phrase "whenever tasks are offered by (the associate)" in the definition of a queue.  Such an epoch class is associated with a port and is called an exogenous epoch class (or exo-epoch class) at the port.  Obviously, the associate must define this epoch, which it does by an endogenous epoch class.  In English descriptions, one sees "whenever (epoch) and if (condition) then tasks will be offered."

Variables representing "the number of tasks offered by (the associate)," indicate an identifier of the specific interpretation attached to the action resulting from the epoch and will be called exocontrols for the element.  The exocontrol of the element is determined by an endocontrol for the associate, which is a value of an endocontrol function.  The "controls" always classify what is to happen when the corresponding epoch occurs.

It should be clearly noted that the two alternate phraseologies for each of our types of variables are distinctly associated with input and output ports (i.e., the "syntactic type" of the port), respectively.  This is made clear in Table II, which tabulates the semantics.  It is also clear from Table II that the endocondition of an input port of an element has the same meaning as the exocondition of an output port of its associate, and vice versa and that this similarly holds true for -controls and -epochs.  This indicates that when inputs are connected to outputs, the corresponding variables always have the same meaning, and that the eight variables (four for each port) in the connection reduce to just four distinctions.

In the syntactic description of section 2.2, two additional types of connection points were described, known as contents sensing and value collecting points.  These connection point types were used in Figure 2.1 as part of the mechanism for describing blocking.  They conceivably have other uses as well.  Since contents sensing ports can only be connected to value collecting ports, the semantics of their port variables are interrelated in the same manner as the input and output ports: endoconditions of an element meaning the same thing as the exoconditions of its associate, etc.  The semantics of these two port types are summarized in Table III.  The controls were omitted because only one action can result from the exo-epoch.  Thus the endocontrol and exocontrol have no role and can be considered to be always zero.  Similarly the cases indicated by a blank in Table III have no role to play in the sample vocabulary of the pictorial language; and are zero.  Of course an extension of the pictorial vocabulary to other symbols might display a necessity for these variables to play a role.

TABLE II SEMANTICS OF INPUT AND OUTPUT PORT VARIABLES

Term and Symbol/Port Type	Input Port	Output Port
Endocondition v	"The number of tasks acceptable to (the element)."	"The number of tasks available from (the element)."
Exocondition x	"The number of tasks available from (the associate)."	"The number of tasks acceptable to (the associate)."
Endocontrol w	"The number of tasks requested by (the element."	"The number of tasks offered by (the element)."
Exocontrol y	"The number of tasks offered by (the associate)."	"The number of tasks requested by (the associate),"
Endo-epoch	"When tasks are requested by (the element)."	"When tasks are offered by (the element)."
Exo- epoch	"When tasks are offered by (the associate)."	"When tasks are requested by (the associate)."

 
TABLE III SEMANTICS OF CONTENTS SENSING AND VALUE COLLECTING PORTS

Term and Symbol/Port Type	Contents Sensing Port	Value Collecting Port
Endocondition v	"The number of tasks represented by (the element)."
Exocondition x		"The number of tasks represented by (the associate)."
Endo- epoch	"When the number of tasks represented by (the element) changes."
Exoepoch		"When the number of tasks represented by (the associate) changes."

The exocondition, endocondition, exocontrol, and endocontrol at a port will be known as port variables.  If we designate them by x, v, y, and w respectively, their roles are suggested schematically by the arrows in Figure 3.2, where their port is represented as a short horizontal line, and the element as a box.  This representation will be a handy aid in later discussion.

In general, there will be no mathematical need to associate meanings like "number of tasks.  . . " with these variables in order to define what we mean by the word "element." We assume only that one always connects ports together whose variables have mutually compatible meanings.  Nevertheless, in illustrating an element-writing out its detailed characteristics the semantics are helpful to the person who writes them out. Also, in determining whether a certain connection should be allowed (i.e., in syntax checking of the picture language), the consistency of these semantics is all- important.  But in combining elements, forming new ones, and in writing out their formal mathematical descriptions the semantics are irrelevant.

Even the question of whether a port is an input or output port can be ignored.  The ability to write algebraic descriptions of elements and to combine them is the objective of this report, so that these semantic descriptions of the variables will assume a low importance.  They will be used only to illustrate, and sometimes to clarify.
 

3.2.5 Events

The verbal definition of the queue was expressed in two paragraphs.  The first paragraph described the action which resulted from an exogenous epoch at the input port, while the second paragraph described the action which resulted from an exogenous epoch at the output port.  The totality of action in an element known to occur when an exogenous epoch occurs will be called an exogenous event.  Similarly, the action in an element known to occur when an autogenous epoch occurs will be called an autogenous event.
 

3.3 A Description of Some Useful Element Types

It will be useful now to define, verbally, several more of the element types partially described in Table I.  This will clarify some of the fine points of behavior which might be confusing when these elements are used as illustrations of the algebraic network model.
 

3.3.1 The Exponential Server

A service completion occurs with probability intensity (the parameter; see Table 1) whenever the number of tasks in service is unity.  When this occurs (an autogenous epoch), and the number of tasks acceptable to the associate at the output is zero, the task simply resumes service and no further action results from this epoch until it completes again.  If the number of tasks acceptable to the output associate is non-zero, one task is offered to it.  If, in this case, a task is available from the input associate one task is requested and the state remains unchanged (it was at unity). If a task is not available, the state is set to zero.

Whenever tasks are offered at the input and the state is unity, the number of tasks acceptable to the server is zero and no further action results. If the state is zero, one task is acceptable to the server, and the state is increased to unity.

When tasks are requested by the output associate, no tasks are available from the server, and no action results.  The state remains unchanged.

3.3.2 The Poisson Arrival Element

An arrival occurs with probability intensity λ. When this occurs, one task is offered by the arrival element at the only port (which is an output). The state is always the same.  When tasks are requested by the associate, no tasks are available from the element, and no action results.

3.3.3 The Random Distributor

When tasks are offered by the input associate, they are offered at the outputs in a proportion determined as follows: A two-dimensional random walk experiment is conducted, with the probability of moving upward being p, and the probability of moving to the right being (1- p). Whenever the vertical coordinate reaches the number of tasks acceptable to the upper output associate, or the horizontal coordinate reaches the num ber of tasks acceptable to the lower output associate, or the sum of both coordinates reaches the number of tasks offered by the input associate, the experiment stops.  The coordinates indicate the number of tasks to be offered to the output associates.  If the process is resumed until one of the first two conditions are met, then the sum of the coordinates indicates the number of tasks acceptable to the element at the input.

A similar strategy determines the result of a request for tasks by one of the output associates.

3.3.4 The Exit

When tasks are offered at the input port, the number of tasks acceptable by the element is infinite.  No change in state occurs.
 

1. Morse, P. M., Queues Inventories and Maintenance, John Wiley and Sons, New  York, 1958.