Rebel Science News
11/28/2012
Jeff Hawkins Is Close to Something Big
 
8/26/2012
The Myth of the Bayesian Brain
 
8/23/2012
The Second Great AI Red Herring Chase
 
8/15/2012
Rebel Speech Recognition Theory
 
8/8/2012
Rebel Speech Update
 

The COSA Operating System

Non-Algorithmic Synchronous Parallel Software Objects

 

 

 
Rebel Science Home
Why Software Is Bad
Project COSA
Operating System
Software Composition
Parallel QuickSort
The Devil's Advocate
COSA Discussion Forum
Not Associated with V.S. Merlot, Inc.
Contact Me

 

Abstract
Introduction
Execution Kernel
  Cell Processor
  Data Objects
  Cells
  Synapses
  Sensors
  Logic Detectors
  Sequence Detectors
  Effectors
The Cell Processor
  Single Execution Thread
  Exceptions to the Single Thread Rule
  Two Update Lists
  COSA-Optimized Processors
  Signals
  Virtual Master Clock
  Real Time Processing
  Time Slicing
  Verification
Cells
  Synapses
  Sensors
  Comparison Sensors
  The Principle of Sensor Coordination
  Effectors
  Hybrid Effectors
  The Principle Of Motor Coordination
  Effector-Sensor Associations
  Message Effectors
  Granularity
  Atomicity

The Automatic Elimination of Blind Code

The COSA Reliability Principle
Logic Detectors
  AND
  OR
  XOR
Sequence Detectors
  Time-Based Sequence Detectors
  Rank-Based Sequence Detectors
  Temporal Order Invariance
  Timer Cells
  Real-Time Watchdogs
COSA Innovations
   

Abstract: This page contains a description of the COSA operating system. COSA is an alternative software construction and execution environment designed to improve software productivity by several orders of magnitude. In addition, COSA will enable the creation of bug-free software applications of arbitrary complexity. It is based on the premise that the primary reason that computer programs are unreliable is the age-old practice of using the algorithm as the basis of software construction. Switch to a synchronous, signal-based model and the problem will disappear. Please refer to the previous articles (Silver Bullet, Project COSA) in the series for important background information.

Introduction

COSA is a complete operating system. It consists of two major subsystems, the execution kernel and the support system. The latter consists of common service components that are needed for a modern operating system. Note that there is no clear distinction between a system service component and a user application other than the convenience of labeling them as such. Every application is seen as an extension of the operating system. Thus, every COSA system can be custom-tailored for a given purpose. That is to say, if, for examples, the application requirements do not call for file I/O and graphics capabilities, the file and graphics components are simply left out.

Execution Kernel

The execution kernel is the part of COSA that runs everything. It consists of the cell processor, the cells proper, and the data objects. The term "cell" is borrowed directly from neurobiology because biological neurons are similar to the elementary processors used in COSA, as explained below. Components are high-level objects which are made of cells and data objects or other components. Components are not considered part of the execution kernel. They are explained in detail in the Software Composition page. The following is a short listing of the items that comprise the execution kernel.

Cell Processor

The cell processor is an elementary object processor. It runs everything in COSA including applications and services.

Data Objects

Data objects are also called passive objects or properties because they do not do anything of themselves. They are operated on by cells (active objects). A data object can be either a variable or a constant, or a collection of properties.

Cells

Cells are active synchronous objects that reside in computer memory. A cell communicates with other cells via signals. There are two types of cells: sensors and effectors. Sensors detect changes or patterns of changes and effectors execute changes. Together with data (passive objects) cells comprise the basic building blocks of every COSA application.

Synapses

A synapse is part of a cell. It is a small data structure which is used to connect one cell to another.

Sensors

A sensor is a type of cell that detects change. Sensors detect changes either in data or in the external environment.

Logic Detectors

A logic detector is a special sensor that detects a logical combination of events.

Sequence Detectors

A sequence detector is a special sensor that detects a pattern of events (changes) occurring over time.

Effectors

An effector is a type of cell that operates on data variables and/or the external environment.

The Cell Processor

The cell processor is a highly optimized interpreter. It is the part of the COSA operating system that handles the reactive logic for the entire system. The processor’s function is to emulate parallelism by performing an operation for every cell which is in need of processing. It should be viewed as a necessary evil. It is needed only because software objects in a von Neumann machine cannot process themselves. The cell processor is designed to be completely transparent to the application developer.

In COSA, every computation is considered to be a form of either input or output processing. For example, detecting a change in a data variable (a comparison operation) is just as much a sensory event as a key-press or a button-down signal. Likewise, incrementing a counter variable is no less a motor action than sending a character to the printer. The following elaborates on various aspects of the cell processor.

Single Execution Thread

An ideal COSA operating system would have no algorithmic processes whatsoever as all objects would be self-processing and would communicate via direct connection pathways, not unlike biological neurons. Unfortunately, the architecture of von Neumann computers is such that a software system must have at least one algorithmic thread (a set of CPU instructions). As a result, communication pathways between objects are virtual.

In COSA, there is a single loop thread called the execution thread which runs the entire system, including applications and services. The cell processor is essentially a virtual machine similar to a FORTH interpreter or the Java™ virtual machine. It is designed to be completely transparent to the software designer. It is the only directly executable code in the entire system. No new executable code is allowed, not even for traditional system services such as file I/O, memory management, device drivers, etc...

Software construction is achieved by connecting elementary cells together using simple signal connectors called synapses. Cells can be combined into larger modules or plug-compatible components. This is mostly for the benefit of the application designer because the cell processor sees only the cells, their synapses and assigned data operands, if any. Nothing else.

Exceptions to the Single Thread Rule

There are a few exceptions to the single thread rule. Every operating system must be able to handle hardware interrupts in real time. Interrupts are, in essence, sensory events indicating that something important has happened which needs immediate handling. Examples are mouse, keyboard, network card or hard drive events. COSA uses small interrupt service routines to modify relevant data/message structures and mark appropriate sensors for updating by the cell processor at the earliest opportunity. Neither applications nor services have permission to access interrupts directly. Indeed they cannot do so since no new native (directly executable) code is allowed in COSA. All possible interrupt eventualities must be handled by the operating system and, if the need arises, corresponding sensors are provided for use by applications and services. This eliminates a lot of headaches, especially in safety-critical domains.

Another exception has to do with copying memory buffers. Sometimes, it is imperative that such tasks be executed as rapidly as possible. It would be best to delegate them to a dedicated DMA or graphics hardware chip. However, this may not always be possible. The alternative is to use a super-optimized assembly language thread. To the software designer, a buffer-copy component would be no different than any other COSA service component. It would have an input connector for service request messages and an output connector for acknowledging when a task is completed. (See the next article in the series for more information on components and connectors).

Two Update Lists

The job of the cell processor is to update all cells that need updating at every tick of the master clock. This is done with the help of two update lists, one for input processing and the other for output processing. The lists contain pointers to all objects that need updating at any given time. As one list is processed, the other is filled. The reason for using two lists instead of one is to prevent signal racing conditions that would otherwise arise.

During every cycle, the lists are processed one after the other starting with the input list. During input processing, the cell processor performs a primitive operation on behalf of every cell in the input list according to the cell’s type. The cell is stamped with an integer value representing the time of activation (I shall explain later why this is important). After each operation is performed, the cell is placed in the output list for subsequent output processing. The input list is emptied after processing is completed. Output processing is much simpler. It consists of placing the destination targets of every cell currently in the output list into the input list. After completion, the output list is emptied, the master clock is incremented and the cycle begins anew. Of course, in order for any processing to occur, cells must first be placed in the input list. This normally happens when an application or component is loaded into memory and started or when a sensor detects a change in the hardware.

COSA-Optimized Processors

Unfortunately for the COSA software model, current microprocessors are optimized for conventional algorithmic software. As I mentioned elsewhere on this site, this is an old tradition that has its roots in Charles Babbage's and Lady Lovelace's ideas for the analytical engine which was built more than one hundred and sixty-two years ago out of metal gears and rotating shafts! The use of the algorithm as the basis of computing may have been a necessity in the early days of the modern computer era when clock speeds were measured in kilohertz and computer memory was at a premium, but with the advent of megahertz and gigahertz CPUs, there is no longer any excuse for processor manufacturers to continue doing business as usual.

A specially designed COSA-optimized processor could maintain both update lists in the processor's on-chip cache, obviating the need to access main memory to read and write to them, thus saving processing time. And since COSA cells are concurrent objects, they can be dispatched to available execution cores within a single multicore processor for simultaneous processing. Vector processing techniques can be used extensively to increase performance. It should even be possible to keep copies of the most often used cells in cache memory in order to further improve performance. In addition, the processor should have intimate knowledge of every cell type. As with FORTH processors, this would eliminate the need for a software interpreter or microkernel. The CPU itself would be the cell processor. These optimizations, among others, could bring performance to a level on a par with or better than that of RISC processors. See How to Design a Fine-Grain, Self-Balancing, Multicore CPU.

One of the advantages of the COSA model is that it is a change-based computing environment. As a result, a comparison test is made only once, i.e., when a related change occurs. Contrast this with algorithmic software where unnecessary comparison operations are often performed every time a subroutine is called. Sooner or later, the computer industry will come to its senses and recognize the soundness of the synchronous software model. The traditional algorithmic microprocessor will then join the slide rule and vacuum-tube computer as mere historical curiosities.

Signals

In a COSA program, there are obviously no tangible signals--comparable to the changes of potential in a digital circuit--that travel from one cell to another. There are no physical pathways between cells. Signals are virtual and signal "travel" time is always one cycle. The mere placement of a cell in an update list means that it has either received or is on the verge of transmitting a signal. This is a plus for software because the signal racing conditions that commonly occur in hardware are non-existent. It should be noted that signals do not carry any information in COSA. Particularly, a signal does not have a Boolean value. A signal is a simple temporal marker that indicates that some phenomenon just occurred. The nature or origin of the phenomenon cannot be determined by examining the signal.

There is a difference between a signal and a message in COSA. As explained above, a signal is an abstract temporal marker. With regard to effector cells (see below), it always marks either the end of an elementary operation or the beginning of another or both. With regard to sensor cells it marks either a positive or negative change in the environment. Signals are always processed synchronously (i.e., immediately) by the cell processor.

A message, on the other hand, is a data structure that can be placed in a queue (FIFO) or a stack (LIFO) and assigned a priority level. Messages are shared data structures between two or more components and are associated with a set of male and female connectors. Message queuing and stacking are not handled directly by the execution kernel. That is the job of the message server, one of the many service components in COSA (this will be explained further in a future article).

Virtual Master Clock

One of the most important aspects of using a master clock is that every elementary operation lasts exactly one execution cycle. An uncompromising consistency in the relative order of signals and operations must be maintained at all costs. Logically speaking, it does not matter whether the durations of the clock cycles are not equal. As long as the master clock (really an integer count) is incremented once every cycle and as long as it serves as the reference clock for timing purposes, logical order consistency is maintained. This is because coincidence and sequence detection are based on the master clock, not on a real-time clock. Thus all concurrent operations execute synchronously between heartbeats or clock ticks. Because of this deterministic concurrency, COSA can be said to belong to a class of software systems known as synchronous reactive systems.

The temporal deterministic nature of cell activation is maintained even though the heart rate of a COSA system is non-deterministic relative to real time: each cycle lasts only as long as necessary. This is not entirely unlike the digital processor design approach known as 'clockless computing.' There is no need to waste time waiting for an external clock tick if one does not have to. This does not mean that a COSA system cannot react in real-time. It can. In fact, the software designer will have ample flexibility to tweak message priorities to handle the most demanding environments. The important thing is that the temporal integrity of cell activations is maintained relative to the virtual clock.

Real Time Processing

Sometimes (e.g., simulation systems, parallel computing, etc...) it is necessary to synchronize a COSA program with an external clock. The best way to achieve this is to use the clock ticks emitted by one of the system's interrupt-driven sensors as reference signals. In such cases, all operations must execute within the fixed interval allotted between real-time ticks. In the event that the execution time exceeds the clock interval, the application designer has several options: a) use a slower real-time clock; b) use a faster CPU; c) split long operations into shorter ones; d) lower the priority of some message servers; or e) lighten CPU load by adding more CPUs to the system and redistributing the load.

Time Slicing

There is no need for multi-threaded applications in COSA. The performance overhead and latency problems associated with context switching is nonexistent. In COSA, every cell is its own tiny task or process, so to speak. This does not mean that the cells are always running. Since the system is driven by change, only the cells that are directly affected by events need to be processed during any given cycle. This makes for a very efficient approach to concurrency because only a relatively small percentage of the cells in a system are active at any one time. As a result, a single-CPU COSA operating system can easily support tens of thousands and even millions of concurrent cells.

Priority processing is controlled at the message server level, not at the kernel level. The kernel never processes messages directly. High-priority messages are immediately placed at the head of their queues. In addition, all message servers automatically stop serving low-priority messages while any high-priority message is still in a queue. This technique ensures that time-critical tasks always get a disproportionate share of processor runtime. Please refer to the Software Composition page for more details on this topic.

Verification

As mentioned above, one of the things that distinguishes concurrent COSA objects from concurrent algorithms is that all COSA objects perform their assigned elementary operations within one execution cycle. This uniformity of execution lends itself to the creation of verification tools and techniques for both static and dynamic analysis. For example, it is easy to determine at run time whether or not a given data operand is being accessed concurrently for modification and/or reading by multiple effectors and/or sensors. It is also possible to determine statically--by counting and analyzing convergent decision pathways--whether the potential exists for conflicting data access. In addition, since COSA program is a condition-driven behaving system and since all conditions are explicit in the design, it is easy to create tools that automatically test every condition before deployment. This is part of the mechanism that guarantees the reliability of COSA programs.

Cells

A COSA cell is a primitive concurrent object. Cells communicate with one another via simple connectors called synapses, to borrow a term from neurobiology. The function of cells is to provide a general purpose set of basic behavioral objects which can be combined in various ways to produce high-level components and/or applications. There is no computational problem that can be solved with a general purpose algorithmic language that cannot also be solved with a combination of COSA cells.

The number of input synapses a cell may have depends on its type. The number of output synapses is unlimited. Comparison sensors, for example, do not have input synapses. Internally, a cell is just a data structure that contains the cell's type, a list of synapses and pointers to data operands, if any. When a cell is processed by the execution thread during input processing, an elementary operation is performed on its behalf according to the cell's type. After processing, the cell immediately emits an output signal to any destination cell it may be connected to.

COSA cells are divided into two complementary categories: sensors and effectors. The latter operate on data while the former detect changes or patterns of changes. What follows is a discussion of various topics related to cells and their operations.

Synapses

A synapse is a simple data structure that serves as a connector between two cells. It contains two addresses, one for the source cell and another for the destination cell. A synapse is an integral part of its source cell. It is used by the cell processor to effect communication between cells. When two cells are connected, they share a synapse together. Note that, even though cells are graphically depicted as being connected via signal pathways, internally however, there are no pathways. There are only the cells and their synapses. Still, it is beneficial to think of a source and a destination cell as communicating over a unidirectional pathway. The pathway is considered an essential part of the source cell, similar to the axon of a neuron.

All synapses maintain a strength variable at least during the development phase. The variable is incremented every time a signal arrives at the synapse. Synaptic strength is an indication of usage and/or experience. It can serve as a powerful debugging aid. In case of failure, the culprit is almost invariably a young or rarely exercised synapse. From the point of view of reliability, it is important to verify that every signal pathway has seen activity at least once. Since all signals must pass through synapses, the use of synaptic strengths can be used to ensure total coverage of all decision pathways during testing. This is a tremendous asset in failure diagnosis (blame assignment).

Sensors

Sensors have no input synapses (except Logic and Sequence detectors) but they can have as many output synapses as necessary. Their function is to detect specific changes or state transitions, either in the computer's hardware or in data variables in memory. When a change is detected, a sensor immediately sends a signal to all its destination cells. A sensor should be thought as being always active in the sense that it is always ready to fire upon detection of a change. Every sensor in COSA has a complement or opposite. The following table lists several examples of sensors and their complements:

mouse-button-up mouse-button-down
key-up key-down
greater-than not-greater-than
less-than not-less-than
equal not-equal
bit-set bit-clear

Comparison Sensors

Comparison sensors--also called data sensors--must be associated with one or more effectors (see the discussion on sensor/effector associations below). Their function is to detect specific types of changes in their assigned data. As mentioned earlier, a signal-based system is a change-driven system.

As an example of how this works, let us say a given comparison sensor's job is to detect equality between two variables A and B. If A and B are equal both before and after an operation on either A or B, the sensor will do nothing. There has to be a change from not-equal to equal in order for the sensor to fire. The same change requirement applies to all sensors. COSA does not draw a process distinction between external (interrupts) and internal (changes in data) sensory phenomena.

Note: A cell's output synapses are always depicted as small red circles in order to distinguish them from input synapses which can be either white or black.

The Principle of Sensor Coordination

There is an implied logic to sensory signals, one which is assumed a priori. The logic is so obvious and simple as to be easily overlooked. Sensors react to specific phenomena or changes in the environment. The offset of a given phenomenon is assumed to follow the onset of the same phenomenon. This is what I call the principle of sensor coordination or PSC. It can be stated thus:

No phenomenon can start if it has already started or stop if it is already stopped.

As an example, if the intensity of a light source increases to a given level, it must first go back below that level in order to increase to that level again. The logical order of events is implicit in all sensory systems. That is to say, it is imposed externally (in the environment) and no special sensory mechanism is needed to enforce it. This may seem trivial but its significance will become clear when I discuss motor coordination and effectors below. As the principle of complementarity would have it, effector coordination is the exact mirror opposite of sensor coordination. That is, effector logic is the complementary opposite of sensory logic. I like to say that effecting is sensing in reverse.

It goes without saying that a complementary pair of sensors (e.g., button-up and button-down) should never fire simultaneously. If they do, something is obviously malfunctioning. An important corollary of the PSC is that positive and negative sensors always alternate. For example, a mouse-button-up signal cannot be followed by another mouse-button-up signal without an intervening mouse-button-down signal. The PSC can be used as a debugging aid during development and/or as part of a malfunction alert mechanism during normal operation.

Effectors

An effector is roughly analogous to a simple code statement in a conventional program. Usually, it performs a single operation on data such as (A = B + 1) or (A = B x C). An operation is any effect that modifies a passive object (a variable). Effectors operate on assigned data items using either direct, indirect or indexed addressing. Data types (integer, floating point, etc...) are specified at creation time.

Effectors are self-activating cells, not unlike the tonically active neurons found in the brain's motor system. What this means is that, once triggered, they will repeatedly execute their operation for a prescribed number of cycles. The left effector in the figure is preset to repeat an addition 10 times while the right effector is preset to perform 40 multiplications. The number of operations may range anywhere from 1 (for one-shot effectors) up to an indefinitely high value. For this reason, all effectors, except one-shot effectors, have two input synapses, one for starting and the other for stopping the activation.

Hybrid Effectors

In keeping with the principle of complementarity, an effector is defined as the opposite of a sensor. The complementarity is evident in the following table:

Sensor

Effector

Acted on by the environment Acts on the environment
No input connections One or more input connections
One or more output connections No output connections

It often turns out that one or more objects need to be notified whenever a given operation is performed. Normally, this calls for the use of a complementary activation sensor, one for every effector. However, rather than having two separate cells, it seems much more practical to combine the function of effector and sensor into a single hybrid cell, as seen in the figure below.

On receipt of a start signal, a hybrid effector performs its assigned operation and then emits an outgoing signal immediately afterwards. When creating a new effector, it is up to the software developer to choose between either the normal or the hybrid type.

The Principle of Motor Coordination

An effector may have any number of start and stop synapses. If an effector does not receive a stop command signal after initial activation, it will repeat its operation until it has run its course, at which time it will emit an output signal to indicate that it has finished its task. There is a strict rule that governs the manner in which start and stop command signals may arrive at an effector. I call it the Principle of Motor Coordination or PMC. The PMC is used to detect command timing conflicts as they happen.
 

No action can be started if it has already started, or stopped if it is already stopped.

In other words, a start signal must not follow another start signal and a stop signal must not follow another stop signal. The PMC further stipulates that an effector must not receive more than one signal at a time, regardless of type. The reason is that an effector must not be invoked for two different purposes simultaneously. In other words, one cannot serve more than one master at the same time. Bad timing invariably results in one or more signal arriving out of turn, which can lead to failures. During development or even during normal operation in mission-critical environments, the environment can be set to trigger an alert whenever the PMC is violated. In addition, it is possible to create analysis tools to determine whether or not the PMC can potentially be violated as a result of one or more combination of events. This can be done by analyzing all relevant signal pathways, event conditions and cells leading to a particular effector.

Effector-Sensor Association (ESA)

In a truly parallel system (such as an electronic circuit), every cell is its own processor. Since a hardware sensor is always active, it continually keeps watch on whatever change event it is designed to detect and fires upon detection. In a software system, however, sensors must be explicitly updated. Updating every sensor at every tick of the clock would be prohibitively time-consuming in anything but the simplest of applications. The reason is that a single main processor must do the work of many small processors.

But all is not lost. There is an easy and efficient technique for getting around the bottleneck. I call it dynamic pairing or coupling. It suffices to associate one or more comparison sensors with one's chosen effector (see figure above) and the cell processor does the rest. The dotted line shown in the figure indicates that the 100+ effector is associated with the != comparison sensor. In other words, the sensor does a comparison every time the effector performs an addition. This is taken care of automatically by the cell processor. The sensor shown in the example sends a stop signal to the very effector with which it is associated. This way, as soon as the comparison is satisfied, the sensor terminates the iteration. As will be seen in the Software Composition page, this arrangement can be used to implement simple traditional loops.

Note that, even though, underneath, the sensor does a comparison test immediately after the operation, both the operation and the comparison should be thought of as happening simultaneously, i.e., within one execution cycle. The idea is that the sensor immediately reacts to the change, as it happens. Note also that an indefinite number of comparison sensors may be associated with a given effector. This way, multiple related comparisons can be done every time an action is taken. Conversely, a given comparison sensor may be associated with more than one effector, that is, with any effector whose actions may potentially affect the sensor.

I originally conceived of the concept of dynamic pairing as a way to get around the problem of updating every sensor in a program at every tick of the master clock. I soon realized that the development system can be designed so that the programmer can be relieved of the burden of finding and creating associations by hand. The system can take care of it automatically. The result is that all data dependencies are resolved, thereby completely eliminating blind code!

Message Effectors (ME)

A message effector is a special hybrid effector that is used to effect message communication between components. An ME is an integral part of every message connector and is the only cell that is shared by two components: a sender and a receiver.

The sole restriction is that only the sender can start a ME and only the receiver can stop it. Remember that a hybrid cell emits a signal immediately at the end of its operation. The signal is interpreted by the sender component to mean that the message has been received and that the receiver is ready to receive another. Note that the effector pictured above stops automatically after 10 cycles. This way, the sender component can send a new message automatically every 10 cycles. It is up to the component designer to choose an appropriate interval.

Granularity

It is important to pick the right granularity level for basic effector operations. It must be neither too high nor too low. For example, a typical addition operation like A = B + C is performed in several steps by the CPU. First B is fetched from memory and then C is fetched. A binary addition is then performed and the result placed in a temporary register. Finally, the result is copied into A. Should each step be considered a separate action to be performed by a separate cell? The answer is no.

As mentioned earlier, a signal-based program is driven by change. The only relevant changes are changes in the data operands that reside in memory. Whichever method is used by the processor to effect a change is irrelevant to the program because it belongs to a level of abstraction that is below that of the program's reactive logic. In the addition example, the only operand that may have changed after the operation is the variable A. The changing of A is the only event that has the potential of affecting the behavior of the program. So the entire operation should be considered a single effect that takes place during a single execution cycle.

Atomicity

When an application designer creates an effector in COSA, he or she is presented with a choice of operations. For example one can choose between simple assignment (e.g.,  A = B), and complex assignment (A = B + C). Once an operation is chosen, one is given a choice of addressing modes for each variable, direct, indirect, indexed, etc... Here are some examples of possible effector operations:

1.  A = B;
2.  A = B + C;
3.  A[x] = B[y];
4.  A = A / 3.1416;
5.  A = B[x][y][z];

Note that every operation assigns a value to a target variable. This is the general form of all primitive COSA operations: one assignment and one arithmetic operation, if any. This is what is meant by an atomic operation: it cannot be divided any further while remaining within the application's level of abstraction.

The Automatic Elimination of Blind Code

A further advantage of ESA is that it allows the creation of tools that automatically identify and correct weak or missing data dependencies in an application. For example, let us say we create a comparison sensor to detect when variable A changes to a value greater than 0. As explained earlier, sensor A must be associated with one or more existing effectors. This could be left to the discretion of the developer but why leave anything to chance if it can be handled by the development system? At the moment of creation, the system should immediately find every effector that can potentially change variable A to a positive non-zero value and associate it with our sensor. This can be done automatically without any intervention from the programmer.

In sum, the system should enforce associations in such a way that every comparison sensor is associated with every effector that may potentially affect the comparison. This way, new additions (sensors and/or effectors) to an existing program will not introduce hidden side effects which are potentially catastrophic. The end result is extremely robust applications.

The COSA Reliability Principle (CRP)

Perhaps the most revolutionary consequence of the automatic elimination of blind code, as seen above, is what I call the COSA Reliability Principle or CRP. It can be stated thus:
 

All COSA programs are guaranteed to be free of internal defects regardless of their complexity.

Here, complexity is defined simply as the number of connections or synapses in the program. Why is the CRP true? The reason is simple. A COSA program obeys the same reactive principles as a logic circuit. If a logic circuit can be guaranteed to be free of defects, so can a COSA program. As an example, let us say a programmer creates a simple thermostat-based program that sends a signal A whenever it detects that integer variable T changes to a value greater than 70 and a signal B when T changes to a value less than 60. Does this mean that the programmer has to test every possible value of T in order to prove that the program is correct? Of course not. The programmer needs to test only the prescribed conditions. This is true regardless of the complexity of the program.

Note that a condition is not a state but a state transition. Since all signal activation pathways and all conditions in a COSA program are explicit, circuit analyzers can be created to exhaustively test every possible eventuality (i.e., every condition) before it happens. Thus, all potential conflicts can be resolved long before deployment.

As I wrote in the Silver Bullet article, the claim by Frederick P. Brooks and others that unreliability comes from the difficulty of enumerating and/or understanding all the possible states of a program is not a valid claim. The truth is that only the conditions (state changes) for which the program is designed to react to must be tested. All other conditions are simply ignored because they are irrelevant.

Logic Detectors

A logic detector is a special sensor that detects a logical combination of events. Logic detectors are not to be confused with logic gates. Whereas a logic gate operates on Boolean states, a logic sensor operates on transient signals. Like all sensors, logic detectors come in complementary pairs, positive or negative. A positive logic detector fires if it receives a combination of input signals that satisfy its function. Conversely, a negative detector fires if it receives a combination of signals that do not satisfy its function. There are three types of logic detectors in COSA: AND OR and XOR.

Note: The labels "AND", "OR", and "XOR" are used below only for their clear correspondence with the language (English) of the accompanying text. In an actual COSA development environment, they would be replaced with the more traditional and universal Boolean logic symbols.

AND

An AND detector is used to detect concurrency. It fires if all its input synapses fire at the same time.

The AND detector depicted above has three positive synapses (white) and one negative synapse (black). The cell is updated only when a signal arrives at a positive synapse. If the three positive signals arrive simultaneously, the cell fires. But if the negative signal arrives at the same time as the others, the cell will not fire. The principle of sensory coordination (PSC) is strictly enforced during development or even during normal operation (mission-critical environments). This means that the system will not allow the developer to create an AND cell that receive signals from complementary sensors unless, of course, the synapses are opposites.

OR

An OR sensor fires whenever a signal arrives at one or more of its positive inputs.

The OR cell shown above has three positive synapses and one negative synapse. It will not fire if a negative signal arrives alone or at the same time as a positive signal.

XOR

An XOR detector fires if it receives a single signal. It will not fire if it receives two or more signals simultaneously. Unlike Boolean XOR operators, a COSA XOR detector can have an unlimited number of input synapses.

Note that the XOR detector shown above has a negative synapse. Negative synapses are used only as a way to exclude other signals. They cannot cause the cell to fire.

Sequence Detectors

There are times when the temporal order of signals is important for decision making. This is the function of the sequence detector. All sequence detectors have a special input synapse which is called the master or reference synapse. The other synapses are called slaves. A sequence detector is updated only when a signal arrives at the master input. In order for a sequence detector to fire, its slave signals must arrive at their prescribed times relative to the master signal. The designer must specify whether the prescribed setting for each input connection represents a precise temporal interval relative to the master signal or just a relative order of arrival or rank. That is to say, there are two types of sequence detectors, time-based and rank-based.

Time-Based Sequence Detectors

In the figure above, the negative integer next to a slave is the precise timing value for the connection. It indicates the temporal position of the slave relative to the arrival time of the master. As with AND sensors, the system will enforce the principle of sensory coordination (PSC). This means that, if two slaves receive signals from complementary sensors, they cannot have equal temporal settings.

Rank-Based Sequence Detectors

If a sequence detector is rank-based, a slave setting represents the order of arrival relative to the other connections. In this case, if two slaves have equal settings, it does not mean that they must arrive concurrently. It only means that they must precede a connection with a higher setting or come after one with a lesser setting.

Rank-based detectors are perfect for the detection of key activation sequences. A good example is the Ctrl-Alt-Delete pattern used in the MS Windows™ operating system:

As seen in the above figure, for the detector to fire, the Ctrl-Down and the Alt-Down signals must arrive before the Del-Down signal. But the Alt key and the Ctrl key must not be released in between. The order in which the Alt and Ctrl keys are pressed is unimportant.

Temporal Order Invariance

All sequence detectors come in complementary pairs, positive and negative. A negative detector is just like its positive sibling, except that if fires if its prescribed temporal conditions are not met when the master signal arrives. It is sometimes a good idea to test for both eventualities. A good COSA-compliant design tool must be able to automatically create negative and positive detectors at the click of a mouse button.

In this light, it is easy to see how a pattern detector can be used as an alarm mechanism to enforce timing constraints. For example, a software designer may have reasons to expect certain events to always occur in a given temporal order called an invariant order. Conversely, there may be reasons to expect certain events to never occur in a particular temporal order. In such cases, a temporal cell can be used to sound an alarm or take an appropriate action whenever the expectation is violated.

Many catastrophic failures in software have to do with one or more violated assumptions about event timing. Adding as many error detectors as possible is a good way to detect problems that would otherwise go unnoticed until too late.

Timer Cells

A timer cell emits a signal a specified number of cycles after receiving a start signal. Like an effector, a timer- cell can have any number of start and stop input synapses. The arrival of a stop signal inhibits the cell's internal counter.

By default, a timer stops after it times out. However, the designer has the option of specifying that the timer resets itself automatically so as to emit a signal at regular intervals.

Real Time Watchdogs

The timer cell described above is called a virtual timer because its internal counter is synchronized to the virtual master clock. There is another type of timer cell called a 'real-time timer' which is synchronized to an external clock. It can be used, as part of a watchdog to enforce real time constraints. Sometimes, especially in embedded applications, it is imperative that a computation finishes within a predetermined interval. A watchdog cell can easily determine whether or not a given signal A arrived before a timer signal B and alert the user if necessary.

COSA Innovations

Reactive software is not a new idea but many of the concepts and principles explained here are new to reactive computing. False modesty aside, I consider several of them to be genuine advances because of their value to software reliability and productivity. I list some of the innovations below, not necessarily in order of importance:

The principle of complementarity (PC).

The principle of motor coordination (PMC).

The principle of sensor coordination (PSC).

The concept of effector-sensor association (ESA).

The automatic resolution of data dependencies at the cell level.

The separation of implementation details from organizational structure.

Self-activated effectors.

Comparisons as sensory processes.

No process distinction between internal and external sensory events.

No process distinction between internal and external effects.

Logical consistency. See this news item.

 

Next: Software Composition

 

©2004-2006 Louis Savain

Copy and distribute freely