Top Up Prev Next Bottom Contents Index Search

10.4 The semantics of SR

An SR star must be well-behaved in the following mathematical sense to make SR systems deterministic. It must compute a monotonic function of its inputs, meaning that when it is presented with more-defined inputs, it must produce more-defined outputs. In particular, an output may only switch from undefined to either present or absent when one or more inputs do, but it may not change its value or become undefined.

The semantics of SR are defined as the least fixed point of the system, meaning the least-defined set of values on the communication channels that is consistent with all the stars' functions. That is, if any star were evaluated, it will not want to change its output---the value is already correct. The monotonicity constraint on the stars ensures that there is always exactly one least-defined set, and this is what the SR schedulers calculate.

There are two schedulers for the SR domain, default-SR and dynamic-SR. The dynamic scheduler is the easiest to understand. In each instant, it first initializes all the communication channels to "undefined" and then executes all the stars in the system until none of them try to change their outputs. The default scheduler is more shrewd. It uses the communication structure of the system to determine an execution order for the stars that will make them converge. This is based on a topological sort of the stars, but is made more complicated when there are feedback loops.



Top Up Prev Next Bottom Contents Index Search

Copyright © 1990-1997, University of California. All rights reserved.