US20030028858A1 - Evolution diagrams for debugging distributed embedded software applications - Google Patents

Abstract

Software development methods and tools are described to generate visual representations of a system's behavior over time, called “evolution diagrams,” to aid in debugging concurrent software systems. The diagrams take advantage of the exposure provided by coordination interfaces to present more complete views of system executions, explicitly showing events, message traffic between components, etc. The display is presented at a user-selectable hierarchical level of the system design, thus enabling a programmer to work at a design layer where the problem or its effect is easily recognized.

Description

RELATED APPLICATIONS
• This application is a continuation of U.S. Provisional Application No. 60/213,496 filed Jun. 23, 2000, incorporated herein in its entirety.[0001]
TECHNICAL FIELD
• The present invention relates to software development tools and, more specifically, relates to creation and use of graphical displays in connection with debugging concurrent software systems.[0002]
BACKGROUND OF THE INVENTION
• A system design and programming methodology is most effective when it is closely integrated and coheres tightly with its corresponding debugging techniques. In distributed and embedded system methodologies, the relationship between debugging approaches and design methodologies has traditionally been one-sided in favor of the design and programming methodologies. Design and programming methodologies are typically developed without any consideration for the debugging techniques that will later be applied to software systems designed using that design and programming methodology. While these typical debugging approaches attempt to exploit features provided by the design and programming methodologies, the debugging techniques will normally have little or no impact on what the design and programming features are in the first place. This lack of input from debugging approaches to design and programming methodologies serves to maintain the role of debugging as an afterthought, even though in a typical system design, debugging consumes a majority of the design time.[0003]
• Concurrence, distributed hardware architectures, real-time constraints, and physical disparity between development and execution environments complicate the debugging of complex embedded systems. Researchers have noted that designers are most productive in debugging systems when they have a robust mental model of the systems' correct behavior. The preceding factors make it both more important for designers to use robust mental models and more difficult to form and maintain them. Distributed systems have no system-wide schedule of events, and the interleaving of coherent event sequences from individual components can be counter-intuitive and often surprising. Intercomponent relationships are complex, and the bookkeeping required to track debugging information can be phenomenal. Debugging tools that complement human ability, assuming tasks that require bookkeeping rather than creativity or intuition, are an absolute necessity. These tools must also present tracked information in a form that designers can quickly understand.[0004]
SUMMARY OF THE INVENTION
• Evolution diagrams can be used to graphically display operation of a distributed or concurrent software system to a programmer to aid in debugging. A preferred diagram explicitly shows selected events, message traffic between software components, changes in component behavior, and correlations between local behavior changes. In one embodiment of such a display, each selected component is represented by a corresponding trace, interface states are displayed by corresponding traces (for example, extending generally parallel to the component traces), and events are made explicit by graphical symbols spanning the space affected by the event. Messages, represented by arrows, present explicit dependencies, while indirect or implicit dependencies such as those implemented by coordinator constraints and actions, are indicated by diagonal lines or the like between the relevant events. See page 78.[0005]
• “Selective focus,” similar to scrolling the display over time (not real time but “consistent cut” time) enables examination of a particular event or sequence of interest to the programmer. Importantly, the user can select a hierarchical level or layer at which to examine an evolution diagram. This powerful concept allows studying the execution at the design layer where the problem or its effect is recognized; thereby identifying the specific component that requires modification. Thus debugging of complex concurrent systems is made relatively fast and easy, and initial identification of the offending component or interface can be done without delving “into the code”.[0006]
• The present invention leverages a coordination-centric design methodology to improve complex embedded system debugging. We draw upon:[0007]
• The behavioral exposure provided by coordination interfaces to generate rich temporal visualizations of system behavior;[0008]
• The hierarchical system models to maximize the utility of computer/designer Bandwidth; and[0009]
• The formal relationships between design elements to examine and abstract behavior.[0010]
• Additional aspects and advantages of this invention will be apparent from the following detailed description of preferred embodiments thereof, which proceeds with reference to the accompanying drawings.[0011]
BRIEF DESCRIPTION OF THE DRAWINGS
• FIG. 1 is a component of a distributed software system.[0012]
• FIG. 2 is the component of FIG. 1 further having a set of coordination interfaces.[0013]
• FIG. 3A is a prior art round-robin resource allocation protocol with a centralized controller.[0014]
• FIG. 3B is a prior art round-robin resource allocation protocol implementing a token passing scheme.[0015]
• FIG. 4A is a detailed view of a component and a coordination interface connected to the component for use in round-robin resource allocation in accordance with the present invention.[0016]
• FIG. 4B depicts a round-robin coordinator in accordance with the present invention.[0017]
• FIG. 5 shows several typical ports for use in a coordination interface in accordance with the present invention.[0018]
• FIG. 6A is a unidirectional data transfer coordinator in accordance with the present invention.[0019]
• FIG. 6B is a bidirectional data transfer coordinator in accordance with the present invention.[0020]
• FIG. 6C is a state unification coordinator in accordance with the present invention.[0021]
• FIG. 6D is a control state mutex coordinator in accordance with the present invention.[0022]
• FIG. 7 is a system for implementing subsumption resource allocation having components, a shared resource, and a subsumption coordinator.[0023]
• FIG. 8 is a barrier synchronization coordinator in accordance with the present invention.[0024]
• FIG. 9 is a rendezvous coordinator in accordance with the present invention.[0025]
• FIG. 10 depicts a dedicated RPC system having a client, a server, and a dedicated RPC coordinator coordinating the activities of the client and the server.[0026]
• FIG. 11 is a compound coordinator with both preemption and round-robin coordination for controlling the access of a set of components to a shared resource.[0027]
• FIG. 12A is software system with two data transfer coordinators, each having constant message consumption and generation rules and each connected to a separate data-generating component and connected to the same data-receiving component.[0028]
• FIG. 12B is the software system of FIG. 12A in which the two data transfer coordinators have been replaced with a merged data transfer coordinator.[0029]
• FIG. 13 is a system implementing a first come, first served resource allocation protocol in accordance with the present invention.[0030]
• FIG. 14 is a system implementing a multiclient RPC coordination protocol formed by combining the first come, first served protocol of FIG. 13 with the dedicated RPC coordinator of FIG. 10.[0031]
• FIG. 15 depicts a large system in which the coordination-centric design methodology can be employed having a wireless device interacting with a cellular network.[0032]
• FIG. 16 shows a top-level view of the behavior and components for a system for a cell phone.[0033]
• FIG. 17A is a detailed view of a GUI component of the cell phone of FIG. 16.[0034]
• FIG. 17B is a detailed view of a call log component of the cell phone of FIG. 16.[0035]
• FIG. 18A is a detailed view of a voice subsystem component of the cell phone of FIG. 16.[0036]
• FIG. 18B is a detailed view of a connection component of the cell phone of FIG. 16.[0037]
• FIG. 19 depicts the coordination layers between a wireless device and a base station, and between the base station and a switching center, of FIG. 15.[0038]
• FIG. 20 depicts a cell phone call management component, a master switching center call management component, and a call management coordinator connecting the respective call management components.[0039]
• FIG. 21A is a detailed view of a transport component of the connection component of FIG. 18B.[0040]
• FIG. 21B is a CDMA data modulator of the transport component of FIG. 18B.[0041]
• FIG. 22 is a detailed view of a typical TDMA and a typical CDMA signal for the cell phone of FIG. 16.[0042]
• FIG. 23A is a LCD touch screen component for a Web browser GUI for a wireless device.[0043]
• FIG. 23B is a Web page formatter component for the Web browser GUI for the wireless device.[0044]
• FIG. 24A is a completed GUI system for a handheld Web browser.[0045]
• FIG. 24B shows the GUI system for the handheld Web browser combined with the connection subsystem of FIG. 18B in order to access the cellular network of FIG. 15.[0046]
• FIG. 25 is a typical space/time diagram with space represented on a vertical axis and time represented on a horizontal axis.[0047]
• FIG. 26 is a space/time diagram depicting a set of system events and two different observations of those system events.[0048]
• FIG. 27 is a space/time diagram depicting a set of system events and an ideal observation of the events taken by a real-time observer.[0049]
• FIG. 28 is a space/time diagram depicting two different yet valid observations of a system execution.[0050]
• FIG. 29 is a space/time diagram depicting a system execution and an observation of that execution take by a discrete lamport observer.[0051]
• FIG. 30 is a space/time diagram depicting a set of events that each include a lamport time stamp.[0052]
• FIG. 31 is a space/time diagram illustrating the insufficiency of scalar timestamps to characterize causality between events.[0053]
• FIG. 32 is a space/time diagram depicting a set of system events that each a vector time stamp.[0054]
• FIG. 33 depicts a display from a partial order event tracer (POET).[0055]
• FIG. 34 is a space/time diagram depicting two compound events that are neither causal nor concurrent.[0056]
• FIG. 35 is a POET display of two convex event clusters.[0057]
• FIG. 36 is a basis for distributed event environments (BEE) abstraction facility for a single client.[0058]
• FIG. 37 is a hierarchical tree construction of process clusters.[0059]
• FIG. 38A depicts a qualitative measure of cohesion and coupling between a set of process clusters that have heavy communication or are instantiated from the same source code.[0060]
• FIG. 38B depicts a qualitative measure of cohesion and coupling between a set of process clusters that do not have heavy communication or are not instances of the same source code.[0061]
• FIG. 38C depicts a qualitative measure of cohesion and coupling between an alternative set of process clusters that have heavy communication or are instantiated from the same source code.[0062]
• FIG. 39 depicts a consistent and an inconsistent cut of a system execution on a space/time diagram.[0063]
• FIG. 40A is a space/time diagram depicting a system execution.[0064]
• FIG. 40B is a lattice representing all possible consistent cuts of the space/time diagram of FIG. 40A.[0065]
• FIG. 40C is a graphical representation of the possible consistent cuts of FIG. 40B.[0066]
• FIG. 41A is a space/time diagram depicting a system execution.[0067]
• FIG. 41B is the space/time diagram of FIG. 41A after performing a global-step.[0068]
• FIG. 41C is the space/time diagram of FIG. 41A after performing a step-over.[0069]
• FIG. 41D is the space/time diagram of FIG. 41A after performing a step-in.[0070]
• FIG. 42 is a space/time diagram depicting a system that is subject to a domino effect whenever the system is rolled back in time to a checkpoint.[0071]
• FIG. 43 is a coordinator evolution diagram for an RPC interaction.[0072]
• FIG. 44 illustrates top-level event types useful for evolution diagrams.[0073]
• FIG. 45 illustrates primitive state types useful for evolution diagrams.[0074]
• FIG. 46 is an evolution diagram of mobile unit call initiation.[0075]
• FIGS.[0076]47A-47B are evolution diagrams illustrating local control failure and distributed control failure, respectively, of the call initiation transaction.
• FIG. 48 is an expanded view of the voice subsystem aspect of an execution diagram illustrating selective focus in debugging.[0077]
• FIG. 49 illustrates source code for three components highlighting the sections of code implicated in suspect behavior.[0078]
• FIG. 50 shows an evolution diagram illustrating a bug that manifests itself in interactions among the several components of FIG. 49.[0079]
• FIGS.[0080]51A-51B illustrate a token-preemptor coordinator mapped to a distributed architecture that causes unanticipated delays.
• FIGS.[0081]52A-52B are evolution diagrams illustrating model simulation and actual execution, respectively, of the combined token-ring/preempt coordinator of FIG. 51.
• FIGS.[0082]53A-53B are conceptual diagrams illustrating a design hierarchy and a designer's desired view, respectively, of the GUI model.
• FIG. 54 illustrates component, event and state clusters in evolution diagrams to reduce clutter.[0083]
• FIG. 55A illustrates a portion of an evolution diagram before filtering.[0084]
• FIG. 55B illustrate the diagram of FIG. 55A after filtering to hide behavioral clutter.[0085]
DETAILED DESCRIPTION OF PREFERRED EMBODIMENTS
• Coordination-Centric Software Design[0086]
• FIG. 1 is an example of a[0087]component100, which is the basic software element within the coordination-centric design framework, in accordance with the present invention. With reference to FIG. 1,component100 contains a set ofmodes102. Eachmode102 corresponds to a specific behavior associated withcomponent100. Eachmode102 can either be active or inactive, respectively enabling or disabling the behavior corresponding to thatmode102.Modes102 can make the conditional aspects of the behavior ofcomponent100 explicit. The behavior ofcomponent100 is encapsulated in a set ofactions104, which are discrete, event-triggered behavioral elements within the coordination-centric design methodology.Component100 can be copied and the copies ofcomponent100 can be modified, providing the code-sharing benefits of inheritance.
• [0088]Actions104 are enabled and disabled bymodes102, and hence can be thought of as effectively being properties ofmodes102. An event (not shown) is an instantaneous condition, such as a timer tick, a data departure or arrival, or a mode change.Actions104 can activate and deactivatemodes102, thereby selecting the future behavior ofcomponent100. This is similar to actor languages, in which methods are allowed to replace an object's behavior.
• In coordination-centric design, however, all possible behaviors must be identified and encapsulated before runtime. For example, a designer building a user interface component for a cell phone might define one mode for looking up numbers in an address book (in which the user interface behavior is to display complete address book entries in formatted text) and another mode for displaying the status of the phone (in which the user interface behavior is to graphically display the signal power and the battery levels of the phone). The designer must define both the modes and the actions for the given behaviors well before the component can be executed.[0089]
• FIG. 2 is[0090]component100 further including afirst coordination interface200, asecond coordination interface202, and a third coordination interface204. Coordination-centric design'scomponents100 provide the code-sharing capability of object-oriented inheritance through copying. Another aspect of object-oriented inheritance is polymorphism through shared interfaces. In object-oriented languages, an object's interface is defined by its methods. Although coordination-centric design'sactions104 are similar to methods in object-oriented languages, they do not define the interface forcomponent100. Components interact through explicit and separate coordination interfaces, in thisfigure coordination interfaces200,202, and204. The shape ofcoordination interfaces200,202, and204 determines the ways in whichcomponent100 may be connected within a software system. The way coordination interfaces200,202, and204 are connected tomodes102 andactions104 withincomponent100 determines how the behavior ofcomponent100 can be managed within a system. Systemwide behavior is managed through coordinators (see FIG. 4B and subsequent).
• For our approach to be effective, several factors in the design of software elements must coincide: packaging, internal organization, and how elements coordinate their behavior. Although these are often treated as independent issues, conflicts among them can exacerbate debugging. We handle them in a unified framework that separates the internal activity from the external relationship of[0091]component100. This lets designers build more modular components and encourages them to specify distributable versions of coordination protocols. Components can be reused in a variety of contexts, both distributed, andsingle processor1.
• 1. Introduction to Coordination[0092]
• Within this application, coordination refers to the predetermined ways by which components interact. Consider a common coordination activity: resource allocation. One simple protocol for this is round-robin: participants are lined up, and the resource is given to each participant in turn. After the last participant is served, the resource is given back to the first. There is a resource-scheduling period during which each participant gets the resource exactly once, whether or not it is needed.[0093]
• FIG. 3A is prior art round-robin resource allocation protocol with a[0094]centralized controller300, which keeps track of and distributes the shared resource (not shown) to each ofsoftware elements302,304,306,308, and310 in turn. With reference to FIG. 3A,controller300 alone determines whichsoftware element302,304,306,308, or310 is currently allowed to use the resource and which has it next. This implementation of a round-robin protocolpermits software elements302,304,306,308, and310 to be modular, becauseonly controller300 keeps track of the software elements. Unfortunately, when this implementation is implemented on a distributed architecture (not shown),controller300 must typically be placed on a single processing element (not shown). As a result, all coordination requests must go through that processing element, which can cause a communication performance bottleneck. For example, consider the situation in whichsoftware elements304 and306 are implemented on a first processing element (not shown) andcontroller300 is implemented on a second processing element.Software element304 releases the shared resource and must send a message indicating this tocontroller300.Controller300 must then send a message tosoftware element306 to informsoftware element306 that it now has the right to the shared resource. If the communication channel between the first processing element and the second processing element is in use or the second processing element is busy, then the shared resource must remain idle, even though both the current resource holder and the next resource holder (software elements304 and306 respectively) are implemented on the first processing element (not shown). The shared resource must typically remain idle until communication can take place andcontroller300 can respond. This is an inefficient way to control access to a shared resource.
• FIG. 3B is a prior art round-robin resource allocation protocol implementing a token passing scheme. With reference to FIG. 3B, this system consists of a shared resource[0095]311 and a set ofsoftware elements312,314,316,318,320, and322. In this system alogical token324 symbolizes the right to access resource311, i.e., when a software element holds token324, it has the right to access resource311. When one ofsoftware elements312,314,316,318,320, or322 finishes with resource311, it passes token324, and withtoken324 the access right, to a successor. This implementation can be distributed without a centralized controller, but as shown in FIG. 3B, this is less modular, because it requires each software element in the set to keep track of a successor.
• Not only must[0096]software elements312,314,316,318,320, and322 keep track of successors, but each must implement a potentially complicated and error-prone protocol for transferring token324 to its successor. Bugs can cause token324 to be lost or introducemultiple tokens324. Since there is no formal connection between the physical system and complete topology maps (diagrams that show how each software element is connected to others within the system), some software elements might erroneously be serviced more than once per cycle, while others are completely neglected. However, these bugs can be extremely difficult to track after the system is completed. The protocol is entangled with the functionality of each software element, and it is difficult to separate the two for debugging purposes. Furthermore, if a few of the software elements are located on the same machine, performance of the implementation can be poor. The entangling of computation and coordination requires intrusive modification to optimize the system.
• 2. Coordination-Centric Design's Approach to Coordination[0097]
• The coordination-centric design methodology provides an encapsulating formalism for coordination. Components such as[0098]component100 interact using coordination interfaces, such as first, second, and third coordination interfaces200,202, and204, respectively. Coordination interfaces preserve component modularity while exposing any parts of a component that participate in coordination. This technique of connecting components provides polymorphism in a similar fashion to subtyping in object-oriented languages.
• FIG. 4A is a detailed view of a[0099]component400 and a resourceaccess coordination interface402 connected tocomponent400 for use in a round-robin coordination protocol in accordance with the present invention. With reference to FIG. 4A, resourceaccess coordination interface402 facilitates implementation of a round-robin protocol that is similar to the token-passing round-robin protocol described above. Resourceaccess coordination interface402 has a single bit of control state, called access, which is shown as an arbitratedcontrol port404 that indicates whether or notcomponent400 is holding a virtual token (not shown).Component400 can only use asend message port406 onaccess coordination interface402 when arbitratedcontrol port404 is true.Access coordination interface402 further has a receivemessage port408.
• FIG. 4B show a round-[0100]robin coordinator410 in accordance with the present invention. With reference to FIG. 4B, round-robin coordinator410 has a set of coordinator coordination interfaces412 for connecting to a set ofcomponents400. Eachcomponent400 includes a resourceaccess coordination interface402. Eachcoordinator coordination interface412 has a coordinator arbitratedcontrol port414, an incomingsend message port416 and an outgoing receivemessage port418.Coordinator coordination interface412 in complimentary to resourceaccess coordination interface402, and vice versa, because the ports on the two interfaces are compatible and can function to transfer information between the two interfaces.
• The round-robin protocol requires round-[0101]robin coordinator410 to manage the coordination topology. Round-robin coordinator410 is an instance of more general abstractions called coordination classes, in which coordination classes define specific coordination protocols and a coordinator is a specific implementation of the coordination class. Round-robin coordinator410 contains all information about howcomponents400 are supposed to coordinate. Although round-robin coordinator410 can have a distributed implementation, nocomponent400 is required to keep references to any other component400 (unlike the distributed round-robin implementation shown in FIG. 3B). All required references are maintained by round-robin coordinator410 itself, andcomponents400 do not even need to know that they are coordinating through round-robin. Resourceaccess coordination interface402 can be used with any coordinator that provides the appropriate complementary interface. A coordinator's design is independent of whether it is implemented on a distributed platform or on a monolithic single processor platform.
• 3. Coordination Interfaces[0102]
• Coordination interfaces are used to connect components to coordinators. They are also the principle key to a variety of useful runtime debugging techniques. Coordination interfaces support component modularity by exposing all parts of the component that participate in the coordination protocol. Ports are elements of coordination interfaces, as are guarantees and requirements, each of which will be described in turn.[0103]
• A. Ports[0104]
• A port is a primitive connection point for interconnecting components. Each port is a five-tuple (T; A; Q; D; R) in which:[0105]
• T represents the data type of the port. T can be one of int, boolean, char, byte, float, double, or cluster, in which cluster represents a cluster of data types (e.g., an int followed by a float followed by two bytes).[0106]
• A is a boolean value that is true if the port is arbitrated and false otherwise.[0107]
• Q is an integer greater than zero that represents logical queue depth for a port.[0108]
• D is one of in, out, inout, or custom and represents the direction data flows with respect to the port.[0109]
• R is one of discard-on-read, discard-on-transfer, or hold and represents the policy for data removal on the port. Discard-on-read indicates that data is removed immediately after it is read (and any data in the logical queue are shifted), discard-on-transfer indicates that data is removed from a port immediately after being transferred to another port, and hold indicates that data should be held until it is overwritten by another value. Hold is subject to arbitration.[0110]
• Custom directionality allows designers to specify ports that accept or generate only certain specific values. For example, a designer may want a port that allows other components to activate, but not deactivate, a mode. While many combinations of port attributes are possible, we normally encounter only a few. The three most common are message ports (output or input), state ports (output, input, or both; sometimes arbitrated), and control ports (a type of state port). FIG. 5 illustrates the visual syntax used for several common ports throughout this application. With reference to FIG. 5, this figure depicts an exported[0111]state port502, an importedstate port504, an arbitratedstate port506, anoutput data port508, and aninput data port510.
• 1. Message Ports[0112]
• Message ports (output and input)[0113]data ports508 and510 respectively) are either send (T; false; 1; out; discard-on-transfer) or receive (T; false; Q; in; discard-on-read). Their function is to transfer data between components. Data passed to a send port is transferred immediately to the corresponding receive port, thus it cannot be retrieved from the send port later. Receive data ports can have queues of various depths. Data arrivals on these ports are frequently used to trigger and pass data parameters into actions. Values remain on receive ports until they are read.
• 2. State Ports[0114]
• State ports take one of three forms:[0115]
• 1. (T; false; 1; out; hold)[0116]
• 2. (T; false; 1; in; hold)[0117]
• 3. (T; true; 1; inout; hold)[0118]
• State ports, such as exported[0119]state port502, importedstate port504, and arbitratedstate port506, hold persistent values, and the value assigned to a state port may be arbitrated. This means that, unlike message ports, values remain on the state ports until changed. When multiple software elements simultaneously attempt to alter the value of arbitratedstate port506, the final value is determined based on arbitration rules provided by the designer through an arbitration coordinator (not shown).
• State ports transfer variable values between scopes. In coordination-centric design, all variables referenced by a component are local to that component, and these variables must be explicitly declared in the component's scope. Variables can, however, be bound to state ports that are connected to other components. In this way a variable value can be transferred between components and the variable value achieves the system-level effect of a multivariable.[0120]
• 3. Control Ports[0121]
• Control ports are similar to state ports, but a control port is limited to having the boolean data type. Control ports are typically bound to modes. Actions interact with a control port indirectly, by setting and responding to the values of a mode that is bound to the control port.[0122]
• For example, arbitrated[0123]control port404 shown in FIG. 4A is a control port that can be bound to a mode (not shown) containing all actions that send data on a shared channel. When arbitratedcontrol port404 is false, the mode is inactive, disabling all actions that send data on the channel.
• B. Guarantees[0124]
• Guarantees are formal declarations of invariant properties of a coordination interface. There can be several types of guarantees, such as timing guarantees between events, guarantees between control state (e.g., state A and state B are guaranteed to be mutually exclusive), etc. Although a coordination interface's guarantees reflect properties of the component to which the coordination interface is connected, the guarantees are not physically bound to any internal portions of the component. Guarantees can often be certified through static analysis of the software system. Guarantees are meant to cache various properties that are inherent in a component or a coordinator in order to simplify static analysis of the software system.[0125]
• A guarantee is a promise provided by a coordination interface. The guarantee takes the form of a predicate promised to be invariant. In principle, guarantees can include any type of predicate (e.g., x>3, in which x is an integer valued state port, or t[0126]_ea−t_eb<2 ms). Throughout the remainder of this application, guarantees will be only event-ordering guarantees (guarantees that specify acceptable orders of events) or control-relationship guarantees (guarantees pertaining to acceptable relative component behaviors).
• C. Requirements[0127]
• A requirement is a formal declaration of the properties necessary for correct software system functionality. An example of a requirement is a required response time for a coordination interface—the number of messages that must have arrived at the coordination interface before the coordination interface can transmit, or fire, the messages. When two coordination interfaces are bound together, the requirements of the first coordination interface must be conservatively matched by the guarantees of the second coordination interface (e.g., x<7 as a guarantee conservatively matches x<8 as a requirement). As with guarantees, requirements are not physically bound to anything within the component itself. Guarantees can often be verified to be sufficient for the correct operation of the software system in which the component is used. In sum, a requirement is a predicate on a first coordination interface that must be conservatively matched with a guarantee on a complementary second coordination interface.[0128]
• D. Conclusion Regarding Coordination Interfaces[0129]
• A coordination interface is a four-tuple (P; G; R; I) in which:[0130]
• P is a set of named ports.[0131]
• G is a set of named guarantees provided by the interface.[0132]
• R is a set of named requirements that must be matched by guarantees of connected interfaces.[0133]
• I is a set of named coordination interfaces.[0134]
• As this definition shows, coordination interfaces are recursive.[0135]Coordinator coordination interface412, shown in FIG. 4B, used for round-robin coordination is called AccessInterface and is defined in Table 1.

  Constituent	Value
  Ports	P =
  	{access: StatePort, s: outMessagePort, r: inMessagePort}
  Guarantees	G ={ access => s.gen }
  Requirement	R = Ø
  interfaces	I = Ø

• Related to coordination interfaces is a recursive coordination interface descriptor, which is a five-tuple (P[0136]_a; G_a; R_a; I_d; N_d) in which:
• P[0137]_ais a set of abstract ports, which are ports that may be incomplete in their attributes (i.e., they do not yet have a datatype).
• G[0138]_ais a set of abstract guarantees, which are guarantees between abstract ports.
• R[0139]_ais a set of abstract requirements, which are requirements between abstract ports.
• I[0140]_dis a set of coordination interface descriptors.
• N[0141]_dis an element of Q×Q, where Q={∞}∪Z+ and Z+ denotes the set of positive integers. N_dindicates the number or range of numbers of permissible interfaces.
• Allowing coordination interfaces to contain other coordination interfaces is a powerful feature. It lets designers use common coordination interfaces as complex ports within other coordination interfaces. For example, the basic message ports described above are nonblocking, but we can build a blocking coordination interface (not shown) that serves as a blocking port by combining a wait state port with a message port.[0142]
• 4. Coordinators[0143]
• A coordinator provides the concrete representations of intercomponent aspects of a coordination protocol. Coordinators allow a variety of static analysis debugging methodologies for software systems created with the coordination-centric design methodology. A coordinator contains a set of coordination interfaces and defines the relationships the coordination interfaces. The coordination interfaces complement the component coordination interfaces provided by components operating within the protocol. Through matched interface pairs, coordinators effectively describe connections between message ports, correlations between control states, and transactions between components.[0144]
• For example, round-[0145]robin coordinator410, shown in FIG. 4B, must ensure that only onecomponent400 has itscomponent control port404's value, or its access bit, set to true. Round-robin coordinator410 must further ensure that thecorrect component400 has itscomponent control port404 set to true for the chosen sequence. This section presents formal definitions of the parts that comprise coordinators: modes, actions, bindings, action triples, and constraints. These definitions culminate in a formal definition of coordinators.
• A. Modes[0146]
• A mode is a boolean value that can be used as a guard on an action. In a coordinator, the mode is most often bound to a control port in a coordination interface for the coordinator. For example, in round-[0147]robin coordinator410, the modes of concern are bound to acoordinator control port414 of eachcoordinator coordination interface412.
• B. Actions[0148]
• An action is a primitive behavioral element that can:[0149]
• Respond to events.[0150]
• Generate events.[0151]
• Change modes.[0152]
• Actions can range in complexity from simple operations up to complicated pieces of source code. An action in a coordinator is called a transparent action because the effects of the action can be precomputed and the internals of the action are completely exposed to the coordination-centric design tools.[0153]
• C. Bindings[0154]
• Bindings connect input ports to output ports, control ports to modes, state ports to variables, and message ports to events. Bindings are transparent and passive. Bindings are simply conduits for event notification and data transfer. When used for event notification, bindings are called triggers.[0155]
• D. Action Triples[0156]
• To be executed, an action must be enabled by a mode and triggered by an event. The combination of a mode, trigger, and action is referred to as an action triple, which is a triple (m; t; a) in which:[0157]
• m is a mode.[0158]
• t is a trigger.[0159]
• a is an action.[0160]
• The trigger is a reference to an event type, but it can be used to pass data into the action. Action triples are written: mode : trigger : action.[0161]
• A coordinator's actions are usually either pure control, in which both the trigger and action performed affect only control state, or pure data, in which both the trigger and action performed occur in the data domain. In the case of round-[0162]robin coordinator410, the following set of actions is responsible for maintaining the appropriate state:
• access_i: −access_i: +access_{(i+1)mod n}
• The symbol “+” signifies a mode's activation edge (i.e., the event associated with the mode becoming true), and the symbol “−” signifies its deactivation edge. When any[0163]coordinator coordination interface412 deactivates its arbitratedcontrol port404's, access bit, the access bit of the nextcoordinator coordination interface412 is automatically activated.
• E. Constraints[0164]
• In this dissertation, constraints are boolean relationships between control ports. They take the form:[0165]
• Condition

  

  Effect
• This essentially means that the Condition (on the left side of the arrow) being true implies that Effect (on the right side of the arrow) is also true. In other words, if Condition is true, then Effect should also be true.[0166]
• A constraint differs from a guarantee in that the guarantee is limited to communicating in-variant relationships between components without providing a way to enforce the in-variant relationship. The constraint, on the other hand, is a set of instructions to the runtime system dealing with how to enforce certain relationships between components. When a constraint is violated, two corrective actions are available to the system: (1) modify the values on the left-hand side to make the left-hand expression evaluate as false (an effect termed backpressure) or (2) alter the right-hand side to make it true. We refer to these techniques as LHM (left-hand modify) and RHM (right-hand modify). For example, given the constraint x[0167]

  

  

  y and the value x^ y, with RHM semantics the runtime system must respond by disabling y or setting y to false. Thus the value of

  

  y is set to true.
• The decision of whether to use LHM, to use RHM, or even to suspend enforcement of a constraint in certain situations can dramatically affect the efficiency and predictability of the software system. Coordination-centric design does not attempt to solve simultaneous constraints at runtime. Rather, runtime algorithms use local ordered constraint solutions. This, however, can result in some constraints being violated and is discussed further below.[0168]
• Round-[0169]robin coordinator410 has a set of safety constraints to ensure that there is never more than one token in the system:
• access_i

  

  ∀_j≠i

  

  access_j
• The above equation translates roughly as access[0170]_iimplies not access_jfor the set of all access_jwhere j is not equal to i. Even this simple constraint system can cause problems with local resolution semantics (as are LHM and RHM). If the runtime system attempted to fix all constraints simultaneously, all access modes would be shut down. If they were fixed one at a time, however, any duplicate tokens would be erased on the first pass, satisfying all other constraints and leaving a single token in the system.
• Since high-level protocols can be built from combinations of lower-level protocols, coordinators can be hierarchically composed. A coordinator is a six-tuple (I; M; B; N; A; X) in which:[0171]
• I is a set of coordination interfaces.[0172]
• M is a set of modes.[0173]
• B is a set of bindings between interface elements (e.g., control ports and message ports) and internal elements (e.g., modes and triggers).[0174]
• N is a set of constraints between interface elements.[0175]
• A is a set of action triples for the coordinator.[0176]
• X is a set of subcoordinators.[0177]
• FIGS. 6A, 6B,[0178]6C, and6D show a few simple coordinators highlighting the bindings and constraints of the respective coordinators. With reference to FIG. 6A, a unidirectionaldata transfer coordinator600 transfers data in one direction between two components (not shown) by connecting incoming receivemessage port408 to outgoing receivemessage port418 with a binding602. With reference to FIG. 6B, bidirectionaldata transfer coordinator604 transfers data back and forth between two components (not shown) by connecting incoming receivemessage port408 to outgoing receivemessage port418 with binding602 and connecting sendmessage port406 to incomingsend message port416 with a second binding602. Unidirectionaldata transfer coordinator600 and bidirectionaldata transfer coordinator604 simply move data from one message port to another. Thus each coordinator consists of bindings between corresponding ports on separate coordination interfaces.
• With reference to FIG. 6C,[0179]state unification coordinator606 ensures that a state port a608 and astate port b610 are always set to the same value.State unification coordinator606 connects state port a608 tostate port b610 with binding602. With reference to FIG. 6D, controlstate mutex coordinator612 has afirst constraint618 and asecond constraint620 as follows:
• c

  

  

  d and  (1)
• d

  

  

  c.  (2)
• [0180]Constraints618 and620 can be restated as follows:
• (1) A[0181]state port c614 having a true value implies that astate port d616 has a false value, and
• (2)[0182]State port d616 having a true value implies thatstate port c614 has a false value.
• A coordinator has two types of coordination interfaces: up interfaces that connect the coordinator to a second coordinator, which is at a higher level of design hierarchy and down interfaces that connect the coordinator either to a component or to a third coordinator, which is at a lower level of design hierarchy. Down interfaces have names preceded with “˜”. Round-[0183]robin coordinator410 has six down coordination interfaces (previously referred to as coordinator coordination interface412), with constraints that make the turning off of any coordinator control port414 (also referred to as access control port) turn on thecoordinator control port414 of the nextcoordinator coordination interface412 in line. Table 2 presents all constituents of the round-robin coordinator.

  Constituent	Value
  Coordination interfaces	I = AccessInterface1-6
  Modes	M = access1-6
  Bindings	B =
  	∀1≦i≦6(˜AccessInterfacei,access,accessi) ∪
  Constraints	N = ∀1≦i≦6(∀(1≦j≦6)^ (i≠j)accessi=> accessj)
  Actions	A =
  	∀1≦i≦6accessi: −accessi: +access(i+1)mod 6
  Subcoordinators	X = Ø

• This tuple describes an implementation of a round-robin coordination protocol for a particular system with six components, as shown in round-[0184]robin coordinator410. We use a coordination class to describe a general coordination protocol that may not have a fixed number of coordinator coordination interfaces. The coordination class is a six-tuple (Ic; Mc; Bc; Nc; Ac; Xc) in which:
• Ic is a set of coordination interface descriptors in which each descriptor provides a type of coordination interface and specifies the number of such interfaces allowed within the coordination class.[0185]
• Mc is a set of abstract modes that supplies appropriate modes when a coordination class is instantiated with a fixed number of coordinator coordination interfaces.[0186]
• Bc is a set of abstract bindings that forms appropriate bindings between elements when the coordination class is instantiated.[0187]
• Nc is a set of abstract constraints that ensures appropriate constraints between coordination interface elements are in place as specified at instantiation.[0188]
• Ac is a set of abstract action triples for the coordinator.[0189]
• Xc is a set of coordination classes (hierarchy).[0190]
• While a coordinator describes coordination protocol for a particular application, it requires many aspects, such as the number of coordination interfaces and datatypes, to be fixed. Coordination classes describe protocols across many applications. The use of the coordination interface descriptors instead of coordination interfaces lets coordination classes keep the number of interfaces and datatypes undetermined until a particular coordinator is instantiated. For example, a round-robin coordinator contains a fixed number of coordinator coordination interfaces with specific bindings and constraints between the message and state ports on the fixed number of coordinator coordination interfaces. A round-robin coordination class contains descriptors for the coordinator coordination interface type, without stating how many coordinator coordination interfaces, and instructions for building bindings and constraints between ports on the coordinator coordination interfaces when a particular round-robin coordinator is created.[0191]
• 5. Components[0192]
• A component is a six-tuple (I; A; M; V; S; X) in which:[0193]
• I is a set of coordination interfaces.[0194]
• A is a set of action triples.[0195]
• M is a set of modes.[0196]
• V is a set of typed variables.[0197]
• S is a set of subcomponents.[0198]
• X is a set of coordinators used to connect the subcomponents to each other and to the coordination interfaces.[0199]
• Actions within a coordinator are fairly regular, and hence a large number of actions can be described with a few simple expressions. However, actions within a component are frequently diverse and can require distinct definitions for each individual action. Typically a component's action triples are represented with a table that has three columns: one for the mode, one for the trigger, and one for the action code. Table 3 shows some example actions from a component that can use round-robin coordination.[0200]

  	Mode	Trigger	Action
  	Access	tick	AccessInterface.s.send(“Test message”);
  			−access;
  	access	tick	waitCount ++;

• A component resembles a coordinator in several ways (for example, the modes and coordination interfaces in each are virtually the same). Components can have internal coordinators, and because of the internal coordinators, components do not always require either bindings or constraints. In the following subsections, various aspects of components are described in greater detail. Theses aspects of components include variable scope, action transparency, and execution semantics for systems of actions.[0201]
• A. Variable Scope[0202]
• To enhance a component's modularity, all variables accessed by an action within the component are either local to the action, local to the immediate parent component of the action, or accessed by the immediate parent component of the action via state ports in one of the parent component's coordination interfaces. For a component's variables to be available to a hierarchical child component, they must be exported by the component and then imported by the child of the component.[0203]
• B. Action Transparency[0204]
• An action within a component can be either a transparent action or an opaque action. Transparent and opaque actions each have different invocation semantics. The internal properties, i.e. control structures, variable, changes in state, operators, etc., of transparent actions are visible to all coordination-centric design tools. The design tools can separate, observe, and analyze all the internal properties of opaque actions. Opaque actions are source code. Opaque actions must be executed directly, and looking at the internal properties of opaque actions can be accomplished only through traditional, source-level debugging techniques. An opaque action must explicitly declare any mode changes and coordination interfaces that the opaque action may directly affect.[0205]
• C. Action Execution[0206]
• An action is triggered by an event, such as data arriving or departing a message port, or changes in value being applied to a state port. An action can change the value of a state port, generate an event, and provide a way for the software system to interact with low-level device drivers. Since actions typically produce events, a single trigger can be propagated through a sequence of actions.[0207]
• 6. Protocols Implemented with Coordination Classes[0208]
• In this section, we describe several coordinators that individually implement some common protocols: subsumption, barrier synchronization, rendezvous, and dedicated RPC.[0209]
• A. Subsumption Protocol[0210]
• A subsumption protocol is a priority-based, preemptive resource allocation protocol commonly used in building small, autonomous robots, in which the shared resource is the robot itself.[0211]
• FIG. 7 shows a set of coordination interfaces and a coordinator for implementing the subsumption protocol. With reference to FIG. 7, a[0212]subsumption coordinator700 has a set of subsumption coordinator coordination interfaces702, which have a subsume arbitratedcoordinator control port704 and an incomingsubsume message port706. Eachsubsume component708 has a subsumecomponent coordination interface710. Subsumecomponent coordination interface710 has a subsume arbitratedcomponent control port712 and an outgoingsubsume message port714.Subsumption coordinator700 and eachsubsume component708 are connected by their respective coordination interfaces,702 and710. Each subsumptioncoordinator coordination interface702 insubsumption coordinator700 is associated with a priority. Eachsubsume component708 has a behavior that can be applied to a robot (not shown). At any time, anysubsume component708 can attempt to assert its behavior on the robot. The asserted behavior coming from thesubsume component708 connected to the subsumptioncoordinator coordination interface702 with the highest priority is the asserted behavior that will actually be performed by the robot.Subsume components708 need not know anything about other components in the system. In fact, eachsubsume component708 is designed to perform independently of whether their asserted behavior is performed or ignored.
• [0213]Subsumption coordinator700 further has a slavecoordinator coordination interface716, which has an outgoingslave message port718. Outgoingslave message port718 is connected to an incomingslave message port720. Incomingslave message port720 is part of aslave coordination interface722, which is connected to aslave730. When asubsume component708 asserts a behavior and that component has the highest priority,subsumption coordinator700 will control slave730 (which typically controls the robot) based on the asserted behavior.
• The following constraint describes the basis of the[0214]subsumption coordinator700's behavior:${\mathrm{subsume}}_p\Rightarrow \stackrel{p-1}{\underset{i=1}{}}{\mathrm{subsume}}_i$

  
• This means that if any[0215]subsume component708 has a subsume arbitratedcomponent control port712 that has a value of true, then all lower-priority subsume arbitratedcomponent control ports712 are set to false. An important difference between round-robin and subsumption is that in round-robin, the resource access right is transferred only when surrendered. Therefore, round-robin coordination has cooperative release semantics. However, in subsumption coordination, asubsume component708 tries to obtain the resource whenever it needs to and succeeds only when it has higher priority than anyother subsume component708 that needs the resource at the same time. A lower-priority subsume component708 already using the resource must surrender the resource whenever a higher-priority subsume component708 tries to access the resource. Subsumption coordination uses preemptive release semantics, whereby eachsubsume component708 must always be prepared to relinquish the resource.
• Table 4 presents the complete tuple for the subsumption coordinator.[0216]

  Constituent	Value
  Coordination interfaces	I = (Subsume1−n) ∪ (Output)
  Modes	M = subsum1−n
  Bindings	B = ∀1≦i≦n(Subsumei,subsume,subsumei) ∪
  Constraints	N = ∀1≦i≦n(∀1≦j≦i)subsumei=> subsumej)
  Actions	A = Ø
  Subcoordinators	X = Ø

• B. Barrier Synchronization Protocol[0217]
• Other simple types of coordination that components might engage in enforce synchronization of activities. An example is barrier synchronization, in which each component reaches a synchronization point independently and waits. FIG. 8 depicts a[0218]barrier synchronization coordinator800. With reference to FIG. 8,barrier synchronization coordinator800 has a set of barriersynchronization coordination interfaces802, each of which has a coordinator arbitratedstate port804, named wait. Coordinator arbitratedstate port804 is connected to a component arbitratedstate port806, which is part of acomponent coordination interface808.Component coordination interface808 is connected to acomponent810. When allcomponents810 reach their respective synchronization points, they are all released from waiting. The actions for a barrier synchronization coordinator with n interfaces are:$\underset{0\le i<n}{\mathrm{<figure-callout\; label="\Lambda "\; filenames="US20030028858A1-20030206-D00014.png,US20030028858A1-20030206-D00028.png"\; state="\{\{state\}\}">\Lambda </figure-callout>}}{\mathrm{wait}}_i::{\forall }_{0\le j<n}-{\mathrm{wait}}_j$

  
• In other words, when all wait modes (not shown) become active, each one is released. The blank between the two colons indicates that the trigger event is the guard condition becoming true.[0219]
• C. Rendezvous Protocol[0220]
• A resource allocation protocol similar to barrier synchronization is called rendezvous. FIG. 9 depicts a[0221]rendezvous coordinator900 in accordance with the present invention. With reference to FIG. 9,rendezvous coordinator900 has arendezvous coordination interface902, which has a rendezvous arbitratedstate port904. A set ofrendezvous components906, each of which may perform different functions or have vastly different actions and modes, has a rendezvouscomponent coordination interface908, which includes a component arbitratedstate port910.Rendezvous components906 connect to rendezvouscoordinator900 through their respective coordination interfaces,908 and902.Rendezvous coordinator900 further has a rendezvousresource coordination interface912, which has a rendezvous resource arbitratedstate port914, also called available. Aresource916 has aresource coordination interface918, which has a resource arbitratedstate port920.Resource916 is connected to rendezvouscoordinator900 by their complementary coordination interfaces,918 and912 respectively.
• With rendezvous-style coordination, there are two types of participants:[0222]resource916 and several resource users, here rendezvouscomponents916. Whenresource916 is available, it activates its resource arbitratedstate port920, also referred to as its available control port. If there are any waitingrendezvous components916, one will be matched with the resource; both participants are then released. This differs from subsumption and round-robin in thatresource916 plays an active role in the protocol by activating itsavailable control port920.
• The actions for[0223]rendezvous coordinator900 are:
• available_i^ wait_j: :−available_i, −wait_j
• This could also be accompanied by other modes that indicate the status after the rendezvous. With rendezvous coordination, it is important that only one component at a time be released from wait mode.[0224]
• D. Dedicated RPC Protocol[0225]
• A coordination class that differs from those described above is dedicated RPC. FIG. 10 depicts a dedicated RPC system. With reference to FIG. 10, a[0226]dedicated RPC coordinator1000 has an RPCserver coordination interface1002, which includes an RPC server importedstate port1004, an RPC serveroutput message port1006, and an RPC serverinput message port1008.Dedicated RPC coordinator1000 is connected to aserver1010.Server1010 has aserver coordination interface1012, which has a server exportedstate port1014, a server input data port1016, and a serveroutput data port1018.Dedicated RPC coordinator1000 is connected toserver1010 through their complementary coordination interfaces,1002 and1012 respectively.Dedicated RPC coordinator1000 further has an RPCclient coordination interface1020, which includes an RPC client importedstate port1022, an RPC clientinput message port1024, and an RPC clientoutput message port1026.Dedicated RPC coordinator1000 is connected to aclient1028 by connecting RPCclient coordination interface1020 to a complementaryclient coordination interface1030.Client coordination interface1030 has a client exportedstate port1032, a client output message port1034, and a clientinput message port1036.
• The dedicated RPC protocol has a client/server protocol in which[0227]server1010 is dedicated to a single client, in thiscase client1028. Unlike the resource allocation protocol examples, the temporal behavior of this protocol is the most important factor in defining it. The following transaction listing describes this temporal behavior:
• [0228]Client1028 enters blocked mode by changing the value stored at client exportedstate port1032 to true.
• [0229]Client1028 transmits an argument data message toserver1010 via client output message port1034.
• [0230]Server1010 receives the argument (labeled “a”) data message via server input data port1016 and enters serving mode by changing the value stored in server exportedstate port1014 to true.
• [0231]Server1010 computes return value.
• [0232]Server1010 transmits a return (labeled “r”) message toclient1020 via serveroutput data port1018 and exits serving mode by changing the value stored in server exportedstate port1014 to false.
• [0233]Client1028 receives the return data message via clientinput message port1036 and exits blocked mode by changing the value stored at client exportedstate port1032 to false.
• This can be presented more concisely with an expression describing causal relationships:[0234]
• T_RPC=+client.blocked→client.transmits→
• +server.serving→server.transmits→
• (−server.serving∥client.receives)→−client.blocked
• The transactions above describe what is supposed to happen. Other properties of this protocol must be described with temporal logic predicates.[0235]
• server.serving[0236]

  

  client.blocked
• server.serving[0237]

  

  F(server.r.output)
• server.a.input[0238]

  

  F(server.serving)
• The r in server.r.output refers to the server[0239]output data port1018, also labeled as the r event port on the server, and the a in serving.a.input refers to server input data port1016, also labeled as the a port on the server (see FIG. 10).
• Together, these predicates indicate that (1) it is an error for[0240]server1010 to be in serving mode ifclient1028 is not blocked; (2) afterserver1010 enters serving mode, a response message is sent or else an error occurs; and (3)server1010 receiving a message means thatserver1010 must enter serving mode. Relationships between control state and data paths must also be considered, such as:
• (client.a

  

  client.blocked)
• In other words,[0241]client1028 must be in blocked mode whenever it sends an argument message.
• The first predicate takes the same form as a constraint; however, since[0242]dedicated RPC coordinator1000 only imports the client:blocked and server:serving modes (i.e., through RPC client importedstate port1022 and RPC server importedstate port1004 respectively),dedicated RPC coordinator1000 is not allowed to alter these values to comply. In fact, none of these predicates is explicitly enforced by a runtime system. However, the last two can be used as requirements and guarantees for interface type-checking.
• 7. System-Level Execution[0243]
• Coordination-centric design methodology lets system specifications be executed directly, according to the semantics described above. When components and coordinators are composed into higher-order structures, however, it becomes essential to consider hazards that can affect system behavior. Examples include conflicting constraints, in which local resolution semantics may either leave the system in an inconsistent state or make it cycle forever, and conflicting actions that undo one another's behavior. In the remainder of this section, the effect of composition issues on system-level executions is explained.[0244]
• A. System Control Configurations[0245]
• A configuration is the combined control state of a system—basically, the set of active modes at a point in time. In other words, a configuration in coordination-centric design is a bit vector containing one bit for each mode in the system. The bit representing a control state is true when the control state is active and false when the control state is inactive. Configurations representing the complete system control state facilitate reasoning on system properties and enable several forms of static analysis of system behavior.[0246]
• B. Action-Trigger Propagation[0247]
• Triggers are formal parameters for events. As mentioned earlier, there are two types of triggers: (1) control triggers, invoked by control events such as mode change requests, and (2) data flow triggers, invoked by data events such as message arrivals or departures. Components and coordinators can both request mode changes (on the modes visible to them) and generate new messages (on the message ports visible to them). Using actions, these events can be propagated through the components and coordinators in the system, causing a cascade of data transmissions and mode change requests, some of which can cancel other requests. When the requests, and secondary requests implied by them, are all propagated through the system, any requests that have not been canceled are confirmed and made part of the system's new configuration.[0248]
• Triggers can be immediately propagated through their respective actions or delayed by a scheduling step. Recall that component actions can be either transparent or opaque. Transparent actions typically propagate their triggers immediately, although it is not absolutely necessary that they do so. Opaque actions typically must always delay propagation.[0249]
• 1. Immediate Propagation[0250]
• Some triggers must be immediately propagated through actions, but only on certain types of transparent actions. Immediate propagation can often involve static precomputation of the effect of changes, which means that certain actions may never actually be performed. For example, consider a system with a coordinator that has an action that activates mode A and a coordinator with an action that deactivates mode B whenever A is activated. Static analysis can be used to determine in advance that any event that activates A will also deactivate B; therefore, this effect can be executed immediately without actually propagating it through A.[0251]
• 2. Delayed Propagation[0252]
• Trigger propagation through opaque actions must typically be delayed, since the system cannot look into opaque actions to precompute their results. Propagation may be delayed for other reasons, such as system efficiency. For example, immediate propagation requires tight synchronization among software components. If functionality is spread among a number of architectural components, immediate propagation is impractical.[0253]
• C. A Protocol Implemented with a Compound Coordinator[0254]
• Multiple coordinators are typically needed in the design of a system. The multiple coordinators can be used together for a single, unified behavior. Unfortunately, one coordinator may interfere with another's behavior.[0255]
• FIG. 11 shows a combined[0256]coordinator1100 with both preemption and round-robin coordination for controlling access to a resource, as discussed above. With reference to FIG. 11,components1102,1104,1106,1108, and1110 primarily use round-robin coordination, and each includes acomponent coordination interface1112, which has a component arbitratedcontrol port1114 and a componentoutput message port1116. However, when apreemptor component1120 needs the resource,preemptor component1120 is allowed to grab the resource immediately.Preemptor component1120 has a preemptorcomponent coordination interface1122. Preemptorcomponent coordination interface1122 has a preemptor arbitratedstate port1124, a preemptoroutput message port1126, and a preemptorinput message port1128.
• All[0257]component coordination interfaces1112 and preemptorcomponent coordination interface1122 are connected to a complementary combinedcoordinator coordination interface1130, which has a coordinator arbitratedstate port1132, a coordinatorinput message port1134, and a coordinatoroutput message port1136. Combinedcoordinator1100 is a hierarchical coordinator and internally has a round-robin coordinator (not shown) and a preemption coordinator (not shown). Combinedcoordinator coordination interface1130 is connected to a coordination interface to round-robin1138 and a coordination interface to preempt1140. Coordinator arbitratedstate port1132 is bound to both a token arbitratedcontrol port1142, which is part of coordination interface to round-robin1138, and to a preempt arbitratedcontrol port1144, which is part of coordination interface to preempt1140. Coordinatorinput message port1134 is bound to an interface to a round-robinoutput message port1146, and coordinatoroutput message port1136 is bound to an interface to round-robininput message port1148.
• Thus preemption interferes with the normal round-robin ordering of access to the resource. After a preemption-based access, the resource moves to the component that in round-robin-ordered access would be the successor to[0258]preemptor component1120. If the resource is preempted too frequently, some components may starve.
• D. Mixing Control and Data in Coordinators[0259]
• Since triggers can be control-based, data-based, or both, and actions can produce both control and data events, control and dataflow aspects of a system are coupled through actions. Through combinations of actions, designers can effectively employ modal data flow, in which relative schedules are switched on and off based on the system configuration.[0260]
• Relative scheduling is a form of coordination. Recognizing this and understanding how it affects a design can allow a powerful class of optimizations. Many data-centric systems (or subsystems) use conjunctive firing, which means that a component buffers messages until a firing rule is matched. When matching occurs, the component fires, consuming the messages in its buffer that caused it to fire and generating a message or messages of its own. Synchronous data flow systems are those in which all components have only firing rules with constant message consumption and generation.[0261]
• FIG. 12A shows a system in which a[0262]component N11200 is connected to acomponent N31202 by adata transfer coordinator1204 and acomponent N21206 is connected tocomponent N31202 by a seconddata transfer coordinator1208.Component N31202 fires when it accumulates three messages on aport c1210 and two messages on aport d1212. On firing,component N31202 produces two messages on aport o1214. Coordination control state tracks the logical buffer depth for these components. This is shown with numbers representing the logical queue depth of each port in FIG. 12.
• FIG. 12B shows the system of FIG. 12A in which[0263]data transfer coordinator1204 and seconddata transfer coordinator1208 have been merged to form a mergeddata transfer coordinator1216. Merging the coordinators in this example provides an efficient static schedule for component firing. Mergeddata transfer coordinator1216fires component N11200 three times andcomponent N21206 twice. Mergeddata transfer coordinator1216 then firescomponent N31202 twice (to consume all messages produced bycomponent N11200 and component N21206).
• Message rates can vary based on mode. For example, a component may consume two messages each time it fires in one mode and four each time it fires in a second mode. For a component like this, it is often possible to merge schedules on a configuration basis, in which each configuration has static consumption and production rates for all affected components.[0264]
• E. Coordination Transformations[0265]
• In specifying complete systems, designers must often specify not only the coordination between two objects, but also the intermediate mechanism they must use to implement this coordination. While this intermediate mechanism can be as simple as shared memory, it can also be another coordinator; hence coordination may be, and often is, layered. For example, RPC coordination often sits on top of a TCP/IP stack or on an IrDA stack, in which each layer coordinates with peer layers on other processing elements using unique coordination protocols. Here, each layer provides certain capabilities to the layer directly above it, and the upper layer must be implemented in terms of them.[0266]
• In many cases, control and communication synthesis can be employed to automatically transform user-specified coordination to a selected set of standard protocols. Designers may have to manually produce transformations for nonstandard protocols.[0267]
• F. Dynamic Behavior with Compound Coordinators[0268]
• Even in statically bound systems, components may need to interact in a fashion that appears dynamic. For example, RPC-style coordination often has multiple clients for individual servers. Here, there is no apparent connection between client and server until one is forged for a transaction. After the connection is forged, however, the coordination proceeds in the same fashion as dedicated RPC.[0269]
• Our approach to this is to treat the RPC server as a shared resource, requiring resource allocation protocols to control access. However, none of the resource allocation protocols described thus far would work efficiently under these circumstances. In the following subsections, an appropriate protocol for treating the RPC as a shared resource will be described and how that protocol should be used as part of a complete multiclient RPC coordination class—one that uses the same RPC coordination interfaces described earlier—will be discussed.[0270]
• 1. First Come/First Serve Protocol (FCFS)[0271]
• FIG. 13 illustrates a first come/first serve (FCFS) resource allocation protocol, which is a protocol that allocates a shared resource to the requester that has waited longest. With reference to FIG. 13, a[0272]FCFS component interface1300 for this protocol has arequest control port1302, anaccess control port1304 and a componentoutgoing message port1306. AFCFS coordinator1308 for this protocol has a set ofFCFS interfaces1310 that are complementary toFCFS component interfaces1300, having a FCFS coordinatorrequest control port1312, a FCFScoordinator access port1314, and a FCFS coordinatorinput message port1316. When acomponent1318 needs to access aresource1320, it assertsrequest control port1302. When granted access,FCFS coordinator1308 asserts the appropriate FCFScoordinator access port1314, releasing FCFS coordinatorrequest control port1312.
• To do this,[0273]FCFS coordinator1308 uses a rendezvous coordinator and two round-robin coordinators. One round-robin coordinator maintains a list of empty slots in which a component may be enqueued, and the other round-robin coordinator maintains a list showing the next component to be granted access. When an FCFS coordinatorrequest control port1312 becomes active,FCFS coordinator1308 begins a rendezvous access to a binder action. When activated, this action maps theappropriate component1318 to a position in the round-robin queues. A separate action cycles through one of the queues and selects the next component to access the server. As much as possible,FCFS coordinator1308 attempts to grant access toresource1320 to theearliest component1318 having requestedresource1320, with concurrent requests determined based on the order in the rendezvous coordinator of therespective components1318.
• 2. Multiclient RPC[0274]
• FIG. 14 depicts a[0275]multiclient RPC coordinator1400 formed by combiningFCFS coordinator1308 withdedicated RPC coordinator1000. With reference to FIG. 14, a set ofclients1402 have a set ofclient coordination interfaces1030, as shown in FIG. 10. In addition,multiclient RPC coordinator1400 has a set of RPCclient coordination interfaces1020, as shown in FIG. 10. For each RPCclient coordination interface1020, RPC clientinput message port1024, of RPCclient coordination interface1020, is bound to the componentoutgoing message port1306 ofFCFS coordinator1308.Message transfer action1403 serves to transfer messages between RPC clientinput message port1024 and componentoutgoing message port1306. For coordinating the actions ofmultiple clients1402,multiclient RPC coordinator1400 must negotiate accesses to a server1404 and keep track of the values returned by server1404.
• G. Monitor Modes and Continuations[0276]
• Features such as blocking behavior and exceptions can be implemented in the coordination-centric design methodology with the aid of monitor modes. Monitor modes are modes that exclude all but a selected set of actions called continuations, which are actions that continue a behavior started by another action.[0277]
• 1. Blocking Behavior[0278]
• With blocking behavior, one action releases control while entering a monitor mode, and a continuation resumes execution after the anticipated response event. Monitor mode entry must be immediate (at least locally), so that no unexpected actions can execute before they are blocked by such a mode.[0279]
• Each monitor mode has a list of actions that cannot be executed when it is entered. The allowed (unlisted) actions are either irrelevant or are continuations of the action that caused entry into this mode. There are other conditions, as well. This mode requires an exception action if forced to exit. However, this exception action is not executed if the monitor mode is turned off locally.[0280]
• When components are distributed over a number of processing elements, it is not practical to assume complete synchronization of the control state. In fact, there are a number of synchronization options available as detailed in Chou, P “Control Composition and Synthesis of Distributed Real-Time Embedded Systems”, Ph.D. dissertation, University of Washington, 1998.[0281]
• 2. Exception Handling[0282]
• Exception actions are a type of continuation. When in a monitor mode, exception actions respond to unexpected events or events that signal error conditions. For example,[0283]multiclient RPC coordinator1400 can bind

  

  client.blocked to a monitor mode and set an exception action on +server. serving. This will signal an error whenever the server begins to work when the client is not blocked for a response.
• 8. A Complete System Example[0284]
• FIG. 15 depicts a large-scale example system under the coordination-centric design methodology. With reference to FIG. 15, the large scale system is a bimodal digital[0285]cellular network1500.Network1500 is for the most part a simplified version of a GSM (global system for mobile communications) cellular network. This example shows in greater detail how the parts of coordination-centric design work together and demonstrates a practical application of the methodology.Network1500 has two different types of cells, a surface cell1502 (also referred to as a base station1502) and asatellite cell1504. These cells are not only differentiated by physical position, but by the technologies they use to sharenetwork1500.Satellite cells1504 use a code division multiple access (CDMA) technology, andsurface cells1502 use a time division multiple access (TDMA) technology. Typically, there are seven frequency bands reserved for TDMA and one band reserved for CDMA. The goal is for as much communication as possible to be conducted through the smaller TDMA cells, here surfacecells1502, because power requirements for a CDMA cells, heresatellite cell1504, increase with the number of users in the CDMA cell.Mobile units1506, or wireless devices, can move betweensurface cells1502, requiring horizontal handoffs betweensurface cells1502.Several surface cells1502 are typically connected to aswitching center1508.Switching center1508 is typically connected to a telephone network or theInternet1512. In addition to handoffs betweensurface cells1502, the network must be able to hand off between switching centers1508. Whenmobile units1506 leave the TDMA region, they remain covered bysatellite cells1504 via vertical handoffs between cells. Since vertical handoffs require changing protocols as well as changing base stations and switching centers, they can be complicated in terms of control.
• Numerous embedded systems comprise the overall system. For example,[0286]switching center1508 and base stations,surface cells1502, are required as part of the network infrastructure, but cellular phones, handheld Web browsers, and othermobile units1506 may be supported for access throughnetwork1500. This section concentrates on the software systems for two particular mobile units1506: a simple digital cellular phone (shown in FIG. 16) and a handheld Web browser (shown in FIG. 24). These examples require a wide variety of coordinators and reusable components. Layered coordination is a feature in each system, because a function of many subsystems is to perform a layered protocol. Furthermore, this example displays how the hierarchically constructed components can be applied in a realistic system to help manage the complexity of the overall design.
• To begin this discussion, we describe the cellular phone in detail, focusing on its functional components and the formalization of their interaction protocols. We then discuss the handheld Web browser in less detail but highlight the main ways in which its functionality and coordination differ from those of the cellular phone. In describing the cellular phone, we use a top-down approach to show how a coherent system organization is preserved, even at a high level. In describing the handheld Web browser, we use a bottom-up approach to illustrate component reuse and bottom-up design.[0287]
• A. Cellular Phone[0288]
• FIG. 16 shows a top-level coordination diagram of the behavior of a[0289]cell phone1600. Rather than using a single coordinator that integrates the components under a single protocol, we use several coordinators in concert. Interactions between coordinators occur mainly within the components to which they connect.
• With reference to FIG. 16,[0290]cell phone1600 supports digital encoding of voice streams. Before it can be used, it must be authenticated with a home master switching center (not shown). This authentication occurs through a registered master switch for each phone and an authentication number from the phone itself. There are various authentication statuses, such as full access, grey-listed, or blacklisted. Forcell phone1600, real-time performance is more important than reliability. A dropped packet is not retransmitted, and a late packet is dropped since its omission degrades the signal less than its late incorporation.
• Each component of[0291]cell phone1600 is hierarchical. AGUI1602 lets users enter phone numbers while displaying them and query anaddress book1604 and alogs component1606.Address book1604 is a database that can map names to phone numbers and vice versa.GUI1602 usesaddress book1604 to help identify callers and to look up phone numbers to be dialed.Logs1606 track both incoming and outgoing calls as they are dialed. Avoice component1608 digitally encodes and decodes, and compresses and decompresses, an audio signal. Aconnection component1610 multiplexes, transmits, receives, and demultiplexes the radio signal and separates out the voice stream and caller identification information.
• Coordination among the above components makes use of several of the coordinators discussed above. Between[0292]connection component1610 and aclock1612, and betweenlogs1606 andconnection component1610, are unidirectional data transfercoordinators600 as described with reference to FIG. 6A. Betweenvoice component1608 andconnection component1610, and betweenGUI1602 andconnection component1610, are bidirectional data transfercoordinators604, as described with reference to FIG. 6B. Betweenclock1612 andGUI1602 is astate unification coordinator606, as described with reference to FIG. 6C. BetweenGUI1602 andaddress book1604 is adedicated RPC coordinator1000 as described with reference to FIG. 10, in whichaddress book1604 hasclient1028 andGUI1602 hasserver1010.
• There is also a custom GUI/[0293]log coordinator1614 betweenlogs1606 andGUI1602. GUI/log coordinator1614 letsGUI1602 transfer new logged information through an routput message port1616 on a GUI coordination interface1618 to an rinput message port1620 on alog coordination interface1622. GUI/log coordinator1614 also letsGUI1602 choose current log entries through a pair of coutput message ports1624 on GUI coordination interface1618 and a pair of cinput message ports1626 onlog coordination interface1622.Logs1606 continuously display one entry each for incoming and outgoing calls.
• 1. GUI Component[0294]
• FIG. 17A is a detailed view of[0295]GUI component1602, of FIG. 16. With reference to FIG. 17A,GUI component1602 has two inner components, akeypad1700 and a text-basedliquid crystal display1702, as well as several functions of its own (not shown). Each time a key press occurs, it triggers an action that interprets the press, depending on the mode of the system. Numeric presses enter values into a shared dialing buffer. When a complete number is entered, the contents of this buffer are used to establish a new connection throughconnection component1610. Table 5 shows the action triples forGUI1602.

  Mode	Trigger	Action
  Idle		numBuffer.append(keypress.val)
  	Send	radio.send(numBuffer.val) +
  		outgoingCall
  	Disconnect	Nil
  	Leftarrow	AddressBook.forward() +
  		lookupMode
  	Rightarrow	log.lastcall() +
  		outlog
  LookupMode	Leftarrow	AddressBook.forward()
  	Rightarrow	AddressBook.backward()

• An “Addr Coord”[0296]coordinator1704 includes an address book mode (not shown) in which arrow key presses are transformed into RPC calls.
• 2. Logs Component[0297]
• FIG. 17B is a detailed view of[0298]logs component1606, which tracks all incoming and outgoing calls. With reference to FIG. 17B, bothGUI component1602 andconnection component1610 must communicate withlogs component1606 through specific message ports. Those specific message ports include a transmittednumber message port1720, a receivednumber message port1722, a change current receivedmessage port1724, a change currenttransmitted message port1726, and twostate ports1728 and1729 for presenting the current received and current transmitted values, respectively.
• [0299]Logs component1606 contains two identical single-log components: asend log1730 for outgoing calls and a receivelog1740 for incoming calls. The interface oflogs component1606 is connected to the individual log components by a pair of adapter coordinators,Adap11750 andAdap21752.Adap11750 has an adapter receiveinterface1754, which has a receive importedstate port1756 and a receiveoutput message port1758.Adap11750 further has anadapter send interface1760, which has a send importedstate port1762 and a sendoutput message port1764. Within Adap1,state port1728 is bound to receive importedstate port1756, change currentreceived message port1724 is bound to receiveoutput message port1758, receivednumber message port1722 is bound to a received interfaceoutput message port1766 on a receivednumber coordination interface1768, change currenttransmitted message port1726 is bound to sendoutput message port1764, andstate port1729 is bound to Up.rc is bound to send importedstate port1762 .
• 3. Voice Component[0300]
• FIG. 18A is a detailed view of[0301]voice component1608 of FIG. 16.Voice component1608 has acompression component1800 for compressing digitized voice signals before transmission, adecompression component1802 for decompressing received digitized voice signals, andinterfaces1804 and1806 to analog transducers (not shown) for digitizing sound to be transmitted and for converting received transmissions into sound.Voice component1608 is a pure data flow component containing sound generator1808 which functions as a white-noise generator, a ring tone generator, and which has a separate port for each on sound generator interface1810, and voice compression functionality in the form ofcompression component1800 anddecompression component1802.
• 4. Connection Component[0302]
• FIG. 18B is a detailed view of[0303]connection component1610 of FIG. 16. With reference to FIG. 18B,connection component1610 coordinates withvoice component1608, logscomponent1606,clock1612, andGUI1602. In addition,connection component1610 is responsible for coordinating the behavior ofcell phone1600 with a base station that owns the surface cell1502 (shown in FIG. 15), a switching center1508 (shown in FIG. 15), and all other phones (not shown) withinsurface cell1502.Connection component1610 must authenticate users, establish connections, and perform handoffs as needed—including appropriate changes in any low-level protocols (such as a switch from TDMA to CDMA).
• FIG. 19 depicts a set of communication layers between[0304]connection component1610 ofcell phone1600 andbase station1502 or switchingcenter1508. With reference to FIG. 19, has several subcomponents, or lower-level components, each of which coordinates with an equivalent, or peer, layer on eitherbase station1502 or switchingcenter1508. The subcomponents ofconnection component1610 include a cellphone call manager1900, a cellphone mobility manager1902, a cell phone radio resource manager1904, a cell phonelink protocol manager1906, and a cellphone transport manager1908 which is responsible for coordinating access to and transferring data through the shared airwaves TDMA and CDMA coordination. Each subcomponent will be described in detail including how each fits into the complete system.
• [0305]Base station1502 has acall management coordinator1910, a mobility management coordinator1912, a radio resource coordinator1914 (BSSMAP1915), a link protocol coordinator1916 (SCCO1917), and a transport coordinator1918 (MTP1919).Switching center1508 has a switchingcenter call manager1920, a switchingcenter mobility manager1922, (aBSSMAP1924, aSCCP1926, and anMTP1928.
• a. Call Management[0306]
• FIG. 20 is a detailed view of a[0307]call management layer2000 consisting of cellphone call manager1900, which is connected to switchingcenter call manager1920 bycall management coordinator1910. With reference to FIG. 20,call management layer2000 coordinates the connection betweencell phone1600 and switchingcenter1508.Call management layer2000 is responsible for dialing, paging, and talking.Call management layer2000 is always present incell phone1600, though not necessarily in Internet appliances (discussed later). Cellphone call manager1900 includes a set of modes (not shown) for call management coordination that consists of the following modes:
• Standby[0308]
• Dialing[0309]
• RingingRemote[0310]
• Ringing[0311]
• CallInProgress[0312]
• Cell[0313]phone call manager1900 has a cell phonecall manager interface2002. Cell phonecall manager interface2002 has a port corresponding to each of the above modes. The standby mode is bound to a standby exportedstate port2010. The dialing mode is bound to a dialing exportedstate port2012. The RingingRemote mode is bound to a RingingRemote importedstate port2014. The Ringing mode is bound to a ringing importedstate port2016. The CallInProgress mode is bound to a CallInProgress arbitratedstate port2018.
• Switching[0314]center call manager1920 includes the following modes (not shown) for call management coordination at the switching center:
• Dialing[0315]
• RingingRemote[0316]
• Paging[0317]
• CallInProgress[0318]
• Switching[0319]center call manager1920 has a switching center callmanager coordination interface2040, which includes a port for each of the above modes within switchingcenter call manager1920.
• When[0320]cell phone1600 requests a connection,switching center1508 creates a new switching center call manager and establishes acall management coordinator1910 betweencell phone1600 and switchingcenter call manager1920.
• b. Mobility Management[0321]
• A mobility management layer authenticates[0322]mobile unit1506 orcell phone1600. When there is asurface cell1502 available,mobility manager1902 contacts theswitching center1508 forsurface cell1502 and transfers a mobile unit identifier (not shown) formobile unit1506 to switchingcenter1508.Switching center1508 then looks up a home motor switching center formobile unit1506 and establishes a set of permissions assigned tomobile unit1506. This layer also acts as a conduit for the call management layer. In addition, the mobility management layer performs handoffs betweenbase stations1502 and switchingcenters1508 based on information received from the radio resource layer.
• C. Radio Resource[0323]
• In the radio resource layer, radio resource manager[0324]1904, chooses thetarget base station1502 and tracks changes in frequencies, time slices, and CDMA codes. Cell phones may negotiate with up to 16 base stations simultaneously. This layer also identifies when handoffs are necessary.
• d. Link Protocol[0325]
• The link layer manages a connection between[0326]cell phone1600 andbase station1502. In this layer,link protocol manager1906 packages data for transfer tobase station1502 fromcell phone1600.
• e. Transport[0327]
• FIG. 21A is a detailed view of[0328]transport component1908 ofconnection component1610.Transport component1908 has two subcomponents, a receivecomponent2100 for receiving data and a transmitcomponent2102 for transmitting data. Each of these subcomponents has two parallel data paths aCDMA path2104 and a TDMA/FDMA path2106 for communicating in the respective network protocols.
• FIG. 21B is a detailed view of a[0329]CDMA modulator2150, which implements a synchronous data flow data path.CDMA modulator2150 takes the dot-product of an incoming data signal alongpath2152 and a stored modulation code forcell phone1600 alongpath2154, which is a sequence of chips, which are measured time signals having a value of −1 or +1.
• [0330]Transport component1908 uses CDMA and TDMA technologies to coordinate access to a resource shared amongseveral cell phones1600, i.e., the airwaves.Transport components1908 supersede the FDMA technologies (e.g., AM and FM) used for analog cellular phones and for radio and television broadcasts. In FDMA, a signal is encoded for transmission by modulating it with a carrier frequency. A signal is decoded by demodulation after being passed through a band pass filter to remove other carrier frequencies. Eachbase station1502 has a set of frequencies—chosen to minimize interference between adjacent cells. (The area covered by a cell may be much smaller than the net range of the transmitters within it.)
• TDMA, on the other hand, coordinates access to the airwaves through time slicing.[0331]Cell phone1600 on the network is assigned a small time slice, during which it has exclusive access to the media. Outside of the small time slice,cell phone1600 must remain silent. Decoding is performed by filtering out all signals outside of the small time slice. The control for this access must be distributed. As such, each component involved must be synchronized to observe the start and end of the small time slice at the same instant.
• Most TDMA systems also employ FDMA, so that instead of sharing a single frequency channel,[0332]cell phones1600 share several channels. The band allocated to TDMA is broken into frequency channels, each with a carrier frequency and a reasonable separation between channels. Thus user channels for the most common implementations of TDMA can be represented as a two-dimensional array, in which the rows represent frequency channels and the columns represent time slices.
• CDMA is based on vector arithmetic. In a sense, CDMA performs inter-cell-phone coordination using data flow. Instead of breaking up the band into frequency channels and time slicing these, CDMA regards the entire band as an n-dimensional vector space. Each channel is a code that represents a basis vector in this space. Bits in the signal are represented as either 1 or −1, and the modulation is the inner product of this signal and a basis vector of[0333]mobile unit1506 orcell phone1600. This process is called spreading, since it effectively takes a narrowband signal and converts it into a broadband signal.
• Demultiplexing is simply a matter of taking the dot-product of the received signal with the appropriate basis vector, obtaining the original 1 or −1. With fast computation and the appropriate codes or basis vectors, the signal can be modulated without a carrier frequency. If this is not the case, a carrier and analog techniques can be used to fill in where computation fails. If a carrier is used, however, all units use the same carrier in all cells.[0334]
• FIG. 22 shows TDMA and CDMA signals for four[0335]cell phones1600. With reference to FIG. 22, for TDMA, eachcell phone1600 is assigned a time slice during which it can transmit.Cell phone1 is assigned time slice t0,cell phone2 is assigned time slice t1,cell phone3 is assigned time slice t2, andcell phone4 is assigned time slice t3. For CDMA, eachcell phone1600 is assigned a basis vector that it multiplies with its signal.Cell phone1 is assigned the vector:$\left(\begin{array}{c}-1\\ 1\\ -1\\ 1\end{array}\right)\hspace{1em}$

  
• [0336]Cell phone2 is assigned the vector:$\left(\begin{array}{c}1\\ -1\\ 1\\ -1\end{array}\right)\hspace{1em}$

  
• [0337]Cell phone3 is assigned the vector:$\left(\begin{array}{c}1\\ 1\\ -1\\ -1\end{array}\right)\hspace{1em}$

  
• [0338]Cell phone4 is assigned the vector:$\left(\begin{array}{c}-1\\ -1\\ 1\\ 1\end{array}\right)\hspace{1em}$

  
• Notice that these vectors form an orthogonal basis.[0339]
• B. Handheld Web Browser[0340]
• In the previous subsection, we demonstrated our methodology on a cell phone with a top-down design approach. In this subsection, we demonstrate our methodology with a bottom-up approach in building a handheld Web browser.[0341]
• FIG. 23A is a LCD[0342]touch screen component2300 for a Web browser GUI (shown in FIG. 24A) for awireless device1506. With reference to FIG. 23A, a LCDtouch screen component2300, has anLCD screen2302 and atouch pad2304.
• FIG. 23B is a Web[0343]page access component2350 for fetching and formatting web pages. With reference to FIG. 23B,web access component2350 has a page fetchsubcomponent2352 and apage format subcomponent2354.Web access component2350 reads hypertext markup language (HTML) from aconnection interface2356, sends word placement requests to adisplay interface2358, and sends image requests to theconnection interface2356.Web access component2350 also has a character input interface to allow users to enter page requests directly and to fill out forms on pages that have forms.
• FIG. 24A shows a completed handheld[0344]Web browser GUI2400. With reference to FIG. 24A, handheldWeb browser GUI2400, has LCDtouch screen component2300,web access component2350, and a penstroke recognition component2402 that translates pen strokes entered ontouch pad2304 into characters.
• FIG. 24B shows the complete component view of a[0345]handheld Web browser2450. With reference to FIG. 24B,handheld Web browser2450 is formed by connecting handheldWeb browser GUI2400 toconnection component1610 of cell phone1600 (described with reference to FIG. 16) with bi-directional data transfer coordinator604 (described with reference to FIG. 6B).Handheld Web browser2450 is an example ofmobile unit1506, and connects to the Internet through the cellular infrastructure described above. However,handheld Web browser2450 has different access requirements than doescell phone1600. Forhandheld Web browser2450, reliability is more important than real-time delivery. Dropped packets usually require retransmission, so it is better to deliver a packet late than to drop it. Real-time issues primarily affect download time and are therefore secondary. Despite this,handheld Web browser2450 must coordinate media access withcell phones1600, and so it must use the same protocol ascell phones1600 to connect to the network. For that reason,handheld Web browser2450 can reuseconnection component1610 fromcell phone1600.
• Debugging Techniques[0346]
• In concept, debugging is a simple process. A designer locates the cause of undesired behavior in a system and fixes the cause. In practice, debugging—even of sequential software—remains difficult. Embedded systems are considerably more complicated to debug than sequential software, due to factors such as concurrence, distributed architectures, and real-time concerns. Issues taken for granted in sequential software, like a schedule that determines the order of all events (the program), are nonexistent in a typical distributed system. Locating and fixing bugs in these complex systems requires many factors, including an understanding of the thought processes underpinning the design.[0347]
• Prior art research into debugging distributed systems is diverse and eclectic and lacks any standard notations. This application uses a standardized notation both to describe the prior art and the present invention. As a result of this standardized notation, the principles in the prior art follow those published in the referenced works. However, the specific notation, theorems, etc., may differ.[0348]
• The two general classes of debugging techniques are event-based debugging and state-based debugging. Most debugging techniques for general-purpose distributed systems are event based. Event-based debugging techniques operate by collecting event traces from individual system components and causally relating those event traces. These techniques require an ability to determine efficiently the causal ordering among any given pair of events. Determining the causal order can be difficult and costly.[0349]
• Events may be primitive, or they may be hierarchical clusters of other events. Primitive events are abstractions of individual local occurrences that might be important to a debugger. Examples of primitive events in sequential programs are variable assignments and subroutine entries or returns. Primitive events for distributed systems include message send and receive events.[0350]
• State-based debugging techniques are less commonly used in debugging distributed systems. State-based debugging techniques typically operate by presenting designers with views or snapshots of a process state. Distributed systems are not tightly synchronized, and so these techniques traditionally involve only the state of individual processes. However, state-based debugging techniques can be applied more generally by relaxing the concept of an “instant in time” so that it can be effectively applied to asynchronous processes.[0351]
• 1. Event-Based Debugging[0352]
• In this section, prior art systems for finding and tracking meaningful event orderings, despite limits in observation, are described. Typical ways in which event orderings are used in visualization tools through automated space/time diagrams are then described.[0353]
• A. Event Order Determination and Observation[0354]
• The behavior of a software system is determined by the events that occur and the order in which they occur. For sequential systems, this seems almost too trivial to mention; of course, a given set of events, such as[0355]
• {x:=2, x:=x*2, x:=5, y:=x},
• arranged in two different ways may describe two completely different behaviors. However, since a sequential program is essentially a complete schedule of events, ordering is explicit. Sequential debugging tools depend on the invariance of this event schedule to let programmers reproduce failures by simply using the same inputs. In distributed systems, as in any concurrent system, it is neither practical nor efficient to completely schedule all events. Concurrent systems typically must be designed with flexible event ordering.[0356]
• Determining the order in which events occur in a distributed system is subject to the limits of observation. An observation is an event record collected by an observer. An observer is an entity that watches the progress of an execution and records events but does not interfere with the system. To determine the order in which two events occur, an observer must measure them both against a common reference.[0357]
• FIG. 25 shows a typical space/time diagram[0358]2500, with space represented on avertical axis2502 and time represented on ahorizontal axis2504. With reference to FIG. 25, space/time diagram2500 provides a starting point for discussing executions in distributed systems. Space/time diagram2500 gives us a visual representation for discussing event ordering and for comparing various styles of observation. A set ofhorizontal world lines2506,2508, and2510 each represent an entity that is stationary in space. The entities represented byhorizontal world lines2506,2508, and2510 are called processes and typically represent software processes in the subject system. The entities can also represent any entity that generates events in a sequential fashion. The spatial separation in the diagram, alongvertical axis2502, represents a virtual space, since several processes might execute on the same physical hardware. Adiagonal world line2512 is called a message and represents discrete communications that pass between two processes. Asphere2514 represents an event. In subsequent figuresvertical axis2502 andhorizontal axis2504 are omitted from any space/time diagrams, unlessvertical axis2502 andhorizontal axis2504 provide additional clarity to a particular figure.
• FIG. 26 shows a space/time diagram[0359]2600 of two different observations of a single system execution, taken by afirst observer2602 and asecond observer2604. With reference to FIG. 26,first observer2602 andsecond observer2604 are entities that record event occurrence.First observer2602 andsecond observer2604 must each receive distinct notifications of each event that occurs and each must record the events in some total order.First observer2602 andsecond observer2604 are represented in space/time diagram2600 as additional processes, or horizontal world lines. Each event recorded requires a signal from its respective process to bothfirst observer2602 andsecond observer2604. The signals from anevent x2606 on aprocess2608 to bothfirst observer2602 andsecond observer2604 are embodied inmessages2610 and2612, respectively.First observer2602 records event x2606 as preceding anevent y2614. However,second observer2604records event y2614 as precedingevent x2606. Such effects may be caused by nonuniform latencies within the system.
• However, the observations of[0360]first observer2602 andsecond observer2604 are not equally valid. A valid observation is typically an observation that preserves the order of events that depend on each other.Second observer2604 records the receipt of amessage2616 before that message is transmitted. Thus the observation fromsecond observer2604 is not valid.
• FIG. 27 shows a space/time diagram[0361]2700 for a special, ideal observer, called the real-time observer (RTO)2702. With reference to FIG. 27,RTO2702 can view each event immediately as it occurs. Due to the limitations of physical clocks, and efficiency issues in employing them, it is usually not practical to implementRTO2702. However,RTO2702 represents an upper bound on precision in event-order determination.
• FIG. 28 shows a space/[0362]time graph2800 showing two valid observations of a system taken by two separate observers:RTO2702 and athird observer2802. With reference to FIG. 28, there is nothing special about the ordering of the observation taken byRTO2702. Events d2804,e2806, and f2808 are all independent events in this execution. Therefore, the observation produced byRTO2702 and the observation produced bythird observer2802 can each be used to reproduce equivalent executions of the system. Any observation in which event dependencies are preserved is typically equal in value to an observation byRTO2702. However, real-time distributed systems may need additional processes to emulate timing constraints.
• FIG. 29 is a space/time diagram[0363]2900 of a methodological observer, called the discrete Lamport Observer (DLO)2902, that records each event in a set of ordered bins. With reference to FIG. 29,DLO2902 records anevent2904 in an orderedbin2906 based on the following rule: each event is recorded in the leftmost bin that follows all events on which it depends.DLO2902 views events discretely and does not need a clock.DLO2902 does, however, require explicit knowledge of event dependency. To determine the bin in which each event must be placed,DLO2902 needs to know the bins of the immediately preceding events. The observation produced byDLO2902 is also referred to as a topological sort of the system execution's event graph.
• In the following, E is the set of all events in an execution. The immediate predecessor relation,[0364]

  

  

  E×E, includes all pairs (e_a, e_b) such that:
• a) If e[0365]_aand e_bare on the same process, e_aprecedes e_bwith no intermediate events.
• b) If e[0366]_bis a receive event, e_ais the send event that generated the message. Given these conditions, e_ais called the immediate predecessor of e_b.
• Each event has at most two immediate predecessors. Therefore,[0367]DLO2902 need only find the bins of at most two records before each placement. The transitive closure of the immediate predecessor relation forms a causal relation. The causal relation,

  

  

  E×E, is the smallest transitive relation such that e_i→e_j

  

  

  e_j.
• This relation defines a partial order of events and further limits the definition of a valid observation. A valid observation is an ordered record of events from a given execution, i.e., (R,[0368]

  

  ), where eεE

  

  (record(e))εR and

  

  is an ordering operator. A valid observation has:
• e_i; e_jεE, e_i

  

  e_j

  

  record(e_i)

  

  record(e_j)
• The dual of the causal relation is a concurrence relation. The concurrence relation, E×E, includes all pairs (e[0369]_a, e_b) such that neither e_a

  

  e_bnor e_b

  

  e_a. While the causal relation is transitive, the concurrence relation is not. The concurrence relation is symmetric, while the causal relation is not.
• B. Event-Order Tracking[0370]
• Debugging typically requires an understanding of the order in which events occur. Above, observers were presented as separate processes. While that treatment simplified the discussion of observers it is typically not a practical implementation of an observer. When the observer is implemented as a physical process, the signals to indicate events would have to be transformed into physical messages and the system would have to be synchronized to enable all messages to arrive in a valid order.[0371]
• FIG. 30 depicts a space/[0372]time graph3000 with each event having alabel3002. With reference to FIG. 30,DLO2902 can accurately place event records in their proper bins—even if received out of order—as long as it knows the bins of the immediate predecessors. If we know the bins in which events are recorded, we can determine something about their causality. Fortunately, it is easy to label each event with the number of its intended bin.Labels3002 are analogous to time and are typically called Lamport timestamps.
• A Lamport timestamp is an integer t associated with an event e[0373]_isuch that
• e_i

  

  e_j

  

  t(e_i)<t(e_j)
• Lamport timestamps can be assigned as needed, provided the labels of an event's immediate predecessors are known. This information can be maintained with a local counter, called a Lamport clock (not shown), t[0374]_Pi, on each process, P_i. The clock's value is transmitted with each message M_jas t_Mj. Clock value t_Ptis updated with each event, as follows:$\mathrm{tpi}=\left\{\begin{array}{cc}\max \left(\mathrm{tMj},\mathrm{tpi}\right)+1;& \mathrm{if}e\mathrm{is}a\mathrm{receive}\mathrm{event}\\ \mathrm{tpi}+1;& \mathrm{otherwise}\end{array}\right\}$

  
• A labeling mechanism is said to characterize the causal relation if, based on their labels alone, it can be determined whether two events are causal or concurrent. Although Lamport timestamps are consistent with causality (if t(e[0375]_i)≧t(e_i), then e_i

  

  e_j), they do not characterize the causal relation.
• FIG. 31 is a space/[0376]time graph3100 that demonstrates the inability of scalar timestamps to characterize causality between events. With reference to FIG. 31, space/time graph3100 showsevent e₁3102,event e₂3104, andevent e₃3106.e₁3102 causese₂3104, and alsoe₁3102 is concurrent with e₃3106e₂3104 is concurrent withe₃3106 and it can be shown thate₃3106 appears, when scalar timestamps are used, concurrent with bothe₁3102 ande₂3104. However, since e₁3102

  

  e₂3104 it is not possible fore₃3106 to be concurrent with both.
• Event causality can be tracked completely using explicit event dependence graphs, with directed edges from each event to its immediate predecessors. Unfortunately, this method cannot store enough information with each record to determine whether two arbitrarily chosen events are causally related without traversing the dependence graph.[0377]
• Other labeling techniques, such as vector timestamps, can characterize causality. The typical formulation of vector timestamps is based on the cardinality of event histories. A basis for vector timestamp is established based on the following definitions and theorems. An event history, H(e[0378]_j), of an event e_jis the set of all events, e_i, such that either since e_i

  

  e_jor e₁

  

  e_i=e_j. The event history can be projected against specific processes. For a process P_j: the P_jhistory projection of H(e_i), H_Pj(e_i), is the intersection of H(e_i) and the set of events local to P_j. The event graph represented by a space/time diagram can be partitioned into equivalence classes, with one class for each process. The set of events local to P_jis just the P_jequivalence class.
• The intersection of any two projections from the same process is identical to at least one of the two projections. Two history projections from a single process, Hp(a) and Hp(b), must satisfy one of the following:[0379]
• a) Hp(a)⊂Hp(b)[0380]
• b) Hp(a)=Hp(b)[0381]
• c) Hp(a)⊃Hp(b)[0382]
• The cardinality of H[0383]_Pj(e_i) is thus the number of events local to P_jthat causally precede e_iand e_iitself. Since local events always occur in sequence, we can uniquely identify an event by its process and the cardinality of its local history.
• For events e[0384]_a; e_bwith e_a≠e_b, H_Pea(e_a)

  

  H_Pea(e_b)

  

  e_a

  

  e_b
• FIG. 32 shows a space/time diagram[0385]3200 with vector timestamped events. Avector timestamp3202 is a vector label, t_e, assigned to each event, eεE, such that the i^thelement represents [H_Pi(e)]. Given two events, e₁and e₂, we can determine their causal ordering: if vector t_eihas a smaller value for its own process's entry than the other, t_ej, has at that same position, then ei

  

  ej. If both vectors have larger values for their own process entries, then e_i∥e_j. It is not possible for both events to have smaller values for their own entries because for events e_aand e_b, e_a

  

  e_bimplies H_Pea(e_a)

  

  H_Pea(e_b). It is not necessary to know the local processes of events to determine their causal order using vector timestamps.
• The causal order of two vector timestamped events, e[0386]_aand e_b, from unknown processes can be determined with an element-by-element comparison of their vector timestamps:$\underset{i=1}{\stackrel{n}{}}t_{\mathrm{ea}}\left[i\right]\le t_{\mathrm{ea}}\left[i\right]\Rightarrow e_a\to e_a$$\underset{i=1}{\stackrel{n}{}}t_{\mathrm{ea}}\left[i\right]\le t_{\mathrm{eb}}\left[i\right]\underset{i=1}{\stackrel{n}{}}t_{\mathrm{eb}}\left[i\right]\le t_{\mathrm{ea}}\left[i\right]\Rightarrow e_ae_b$

  
• Thus vector timestamps both fully characterize causality and uniquely identify each event in an execution.[0387]
• Computing vector timestamps at runtime is similar to Lamport timestamp computation. Each process (P[0388]_s) contains a vector clock ({circumflex over (t)}_Ps) with elements for every process in the system, where {circumflex over (t)}_Ps[s] always equals the number of events local to P_s. Snapshots of this vector counter are used to label each event, and snapshots are transmitted with each message. The recipient of a message with a vector snapshot can update its own vector counter ({circumflex over (t)}_Pr) by replacing it with sup({circumflex over (t)}_Ps, {circumflex over (t)}_Pr), the element-wise maximum of {circumflex over (t)}_Psand {circumflex over (t)}_Pr.
• This technique places enough information with each message to determine message ordering. It is performed by comparing snapshots attached to each message. However, transmission of entire snapshots is usually not practical, especially if the system contains a large number of processes.[0389]
• Vector clocks can however be maintained without transmitting complete snapshots. A transmitting process, P[0390]_s, can send a list that includes only those vector clock values that have changed since its last message. A recipient, P_r, then compares the change list to its current elements and updates those that are smaller. This requires each process to maintain several vectors: one for itself and one for each process to which it has sent messages. However, change lists do not contain enough information to independently track message order.
• The expense of maintaining vector clocks can be a strong deterrent to employing them. Unfortunately, no technique with smaller labels can characterize causality. It has been proven that the dimension of the causal relation for an N-process distributed execution is N, and hence N-element vectors are the smallest labels characterizing causality.[0391]
• The problem results from concurrence, without which Lamport time would be sufficient. Concurrence can be tracked with concurrency maps, where each event keeps track of all events with which it is concurrent. Since the maps characterize concurrency, adding Lamport time lets them also characterize causality (the concurrency information disambiguates the scalar time). Unfortunately, concurrency maps can only be constructed after-the-fact, since doing so requires an examination of events from all processes.[0392]
• In some situations, distinguishing between concurrency and causality is not a necessity, but merely a convenience. There are compact labeling techniques that allow better concurrence detection than Lamport time. One such technique uses interval clocks in which each event record is labeled with its own Lamport time and the Lamport time of its earliest successor. This label then represents a Lamport time interval, during which the corresponding event was the latest known by the process. This gives each event a wider region with which to detect concurrence (indicated by overlapping intervals).[0393]
• In cases in which there is little or no cross-process causality (few messages), interval timestamps are not much better than Lamport timestamps. In cases with large numbers of messages, however, interval timestamps can yield better results.[0394]
• C. Space/Time Displays in Debugging Tools[0395]
• Space/time diagrams have typically proven useful in discussing event causality and concurrence. Space/time diagrams are also often employed as the user display in concurrent program debugging tools.[0396]
• The Los Alamos parallel debugging system uses a text based time-process display, and Idd uses a graphic display. Both of these, however, rely on an accurate global real-time clock (impractical in most systems).[0397]
• FIG. 33 shows a partial order event tracer (POET)[0398]display3300. The partial order event tracer (POET) system supports several different languages and run-time environments, including Hermes, a high-level interpreted language for distributed systems, and Java. With reference to FIG. 33,POET display3300 distinguishes among several types of events by shapes, shading, and alignment of corresponding message lines.
• A Distributed Program Debugger (DPD) is based on a Remote Execution Manager (REM) framework. The REM framework is a set of servers on interconnected Unix machines in which each server is a Unix user-level process. Processes executing in this framework can create and communicate with processes elsewhere in the network as if they were all on the same machine. DPD uses space/time displays for debugging communication only, and it relies on separate source-level debuggers for individual processes.[0399]
• 2. Abstraction in Event-Based Debugging[0400]
• Simple space/time displays can be used to present programmers with a wealth of information about distributed executions. Typically, however, space/time diagrams are too abstract to be an ultimate debugging solution. Space/time diagrams show high-level events and message traffic, but they do not support designer interaction with the source code. On the other hand, simple space/time diagrams may sometimes have too much detail. Space/time diagrams display each distinct low-level message that contributes to a high-level transaction without support for abstracting the transaction.[0401]
• FIG. 34 is a space/time diagram[0402]3400 having afirst compound event3402 and asecond compound event3404. With reference to FIG. 34, even though a pair of primitive events are either causally related or concurrent, first andsecond compound events3402 and3404, or any other pair of compound events, might be neither causally related nor concurrent. Abstraction is typically applied across two dimensions—events and processes—to aid in the task of debugging distributed software. Event abstraction represents sequences of events as single entities. A group of events may occasionally have a specific semantic meaning that is difficult to recognize, much as streams of characters can have a meaning that is difficult to interpret without proper spacing and punctuation. Event abstraction can in some circumstances complicate the relationships between events.
• Event abstraction can be applied in one of three ways: filtering, clustering, and interpretation. With event filtering, a programmer describes event types that the debugger should ignore, which are then hidden from view. With clustering, the debugger collects a number of events and presents the group as a single event. With interpretation, the debugger parses the event stream for event sequences with specific semantic meaning and presents them to a programmer.[0403]
• Process abstraction is usually applied only as hierarchical clustering. The remainder of this section discusses these specific event and process abstraction approaches.[0404]
• A. Event Filtering and Clustering[0405]
• Event filtering and clustering are techniques used to hide events from a designer and thereby reduce clutter. Event filters exclude selected events from being tracked in event-based debugging techniques. In most cases, this filtering is implicit and cannot be modified without changing the source code because the source code being debugged is designed to report only certain events to the debugger. When deployed, the code will report all such events to the tool. This approach is employed in both DPD and POET, although some events may be filtered from the display at a later time.[0406]
• An event cluster is a group of events represented as a single event. The placement of an event in a cluster is based on simple parameters, such as virtual time bounds and process groups. Event clusters can have causal ambiguities. For example, one cluster may contain events that causally precede events in a second cluster, while other events causally follow certain events in the second cluster.[0407]
• FIG. 35 shows a[0408]POET display3500 involving a firstconvex event cluster3502 and a secondconvex event cluster3504. POET uses a virtual-time-based clustering technique that represents convex event clusters as single abstract events. A convex event cluster is a set of event instances, C, such that for events
• a, b, cεE with a, cεC, a

  

  b^ b

  

  c

  

  bεC
• Convex event clusters, unlike generic event clusters, cannot overlap.[0409]
• B. Event Interpretation (Specific Background for Behavioral Abstraction)[0410]
• The third technique for applying event abstraction is interpretation, also referred to as behavioral abstraction. Both terms describe techniques that use debugging tools to interpret the behavior represented by sequences of events and present results to a designer. Most approaches to behavioral abstraction let a designer describe sequences of events using expressions, and the tools recognize the sequence of events through a combination of customized finite automata followed by explicit checks. Typically, matched expressions generate new events.[0411]
• 1. Event Description Language (EDL)[0412]
• One of the earliest behavioral abstraction technique was Bates's event description language (EDL), in which event streams are pattern-matched using shuffle automata. A match produces a new event that can, in turn, be part of another pattern. Essentially, abstract events are hierarchical and are built from the bottom up.[0413]
• This approach can recognize event patterns that contain concurrent events. There are, however, several weaknesses in this approach. First, shuffle automata match events from a linear stream, which is subject to a strong observational bias. In addition, even if the stream constitutes a valid observation, interleaving may cause false intermediates between an event and its immediate successor. Finally, concurrent events appear to occur in some specific order.[0414]
• Bates partially compensates for these problems in three ways. First, all intermediates between two recognized events are ignored—hence, false intermediates are skipped. Unfortunately, true intermediates are also skipped, making error detection difficult. Second, the shuffle operator, Δ, is used to identify matches with concurrent events. Unfortunately, shuffle recognizes events that occur in any order, regardless of whether they are truly ordered in the corresponding execution. For example, e[0415]₁Δe₂can match with either e₁

  

  e₂or e₂

  

  e₁in the event stream, but this means the actual matches could be: e₁

  

  e₂, e₂

  

  e₁, in addition to the e₁∥e₂that the programmer intended to match. Third, the programmer can prescribe explicit checks to be performed on each match before asserting the results. However, the checks allowed do not include causality or concurrence checks.
• 2. Chain Expressions[0416]
• Chain expressions, used in the Ariadne parallel debugger, are an alternate way to describe distributed behavior patterns that have both causality and concurrence. These behavioral descriptions are based on chains of events (abstract sequences not bound to processes), p-chains (chains bound to processes), and pt-chains (composed p-chains). The syntax for describing chain expressions is fairly simple, with <a b > representing two causally related events and |[a b]| representing two concurrent events.[0417]
• The recognition algorithm has two functions. First, the algorithm recognizes the appropriate event sequence from a linear stream, using a nondeterminate finite automaton (NFA). Second, the algorithm checks the relationships between specific events.[0418]
• For example, when looking for sequences that match the expression <|[a b]|c> (viz., a and b are concurrent, and both causally precede c), Ariadne will find the sequence a b c and then verify the relationships among them. Unfortunately, the fact that sequences are picked in order from a linear stream before relationships are checked can cause certain matches to be missed. For example, |[a b]| and |[b a]| should have the same meaning, but they do not cause identical matches. This is because Ariadne uses NFAs as the first stage in event abstraction. In the totally ordered stream to which an NFA responds, either a will precede b, preventing the NFA for the second expression from recognizing the string, or b will precede a, preventing the NFA for the first expression from recognizing the string.[0419]
• 3. Distributed Abstraction[0420]
• The behavioral abstraction techniques described so far rely on centralized abstraction facilities. These facilities can be distributed, as well. The BEE (Basis for distributed Event Environments) project is a distributed, hierarchical, event-collection system, with debugging clients located with each process.[0421]
• FIG. 36 show a Basis for distributed Event Environments (BEE)[0422]abstraction facility3600 for a single client. With reference to FIG. 36, event interpretation is performed at several levels. The first is anevent sensor3602, inserted into the source of the program under test and invoked whenever a primitive event occurs during execution. The next level is anevent generator3604, where information—including timestamps and process identifiers—is attached to each event.Event generator3604 uses an event table3606 to determine whether events should be passed to anevent handler3608 or simply dropped.Event handler3608 manages event table3606 withinevent generator3604.Event handler3608 filters and collects events and routes them to appropriate event interpreters (not shown). Event interpreters (not shown) gather events from a number of clients (not shown) and aggregate them for presentation to a programmer. Clients and their related event interpreters are placed together in groups managed by an event manager (not shown). A weakness of this technique is that it does not specifically track causality. Instead, this technique relies on the real-timestamps attached to specific primitive or abstract events. However, as discussed above these timestamps are not able to characterize causality.
• C. Process Clustering[0423]
• Most distributed computing environments feature flat process structures, with few formally stated relationships among processes. Automatic process clustering tools can partially reverse-engineer a hierarchical structure to help remove spurious information from a debugger's view. Intuitively, a good cluster hierarchy should reveal, at the top level, high-level system behavior, and the resolution should improve proportionally with the number of processes exposed. A poor cluster hierarchy would show very little at the top level and would require a programmer to descend several hierarchical levels before getting even a rough idea about system behavior. Process clustering tools attempt to identify common interaction patterns—such as client-server, master-slave, complex server, layered system, and so forth. When these patterns are identified, the participants are clustered together. Clusters can then serve as participants in interaction patterns to be further clustered. These cluster hierarchies are strictly trees, as shown in FIG. 37, which depicts a hierarchical construction of[0424]process clusters3700. With reference to FIG. 37, asquare node3702 represents a process (not shown) and around node3704 represents a process cluster (not shown).
• Programmers can choose a debugging focus, in which they specify the aspects and detail levels they want to use to observe an execution. With reference to FIG. 37, a representative debugging focus that includes nodes I, J, E, F, G, and H is shown. One drawback of this approach is that when a parent cluster is in focus, none of its children can be. For example, if we wanted to look at process K in detail, we would also need to expose at least as much detail for processes E and L and process cluster D.[0425]
• Each process usually participates in many types of interactions with other processes. Therefore, the abstraction tools must heuristically decide between several options. These decisions have a substantial impact on the quality of a cluster hierarchy. In “Abstract Behaviour of Distributed Executions with Applications to Visualization,” Ph.D. thesis, Technische Hochschule Darmstadt, Darmstadt, Germany, May 1994, by T. Kunz, the author evaluates the quality of his tool by measuring the cohesion, which though expressed quantitatively is actually a qualitative measurement (the higher the better) within a cluster and the coupling, a qualitative measure of the information clusters must know about each other (the higher the worse), between clusters. For a cluster P of m processes, cohesion is quantified by:[0426]$\mathrm{Cohesion}\left(P\right)=\frac{\sum _{i<j}{\mathrm{Sim}}_f\left(p_i,p_j\right)}{m\left(m-1\right)/2}$

  
• where Sim[0427]_f(P₁, P₂) is a similarity metric that equals:${\mathrm{Sim}}_f=\frac{A〈{\hat{C}}_{{\mathrm{<figure-callout\; label="P"\; filenames="US20030028858A1-20030206-D00000.png,US20030028858A1-20030206-D00001.png"\; state="\{\{state\}\}">P</figure-callout>}}_1}{\hat{C}}_{{\mathrm{<figure-callout\; label="P"\; filenames="US20030028858A1-20030206-D00000.png,US20030028858A1-20030206-D00001.png"\; state="\{\{state\}\}">P</figure-callout>}}_2}〉}{{\hat{C}}_{{\mathrm{<figure-callout\; label="P"\; filenames="US20030028858A1-20030206-D00000.png,US20030028858A1-20030206-D00001.png"\; state="\{\{state\}\}">P</figure-callout>}}_1}·{\hat{C}}_{{\mathrm{<figure-callout\; label="P"\; filenames="US20030028858A1-20030206-D00000.png,US20030028858A1-20030206-D00001.png"\; state="\{\{state\}\}">P</figure-callout>}}_2}}$

  
• Here, <â|{circumflex over (b)}> denotes the scaler product of vectors â and {circumflex over (b)}, and ∥â∥ denotes the magnitude of vector â. C[0428]_P1and C_P2are process characteristic vectors—in them, each element contains a value between 0 and 1 that indicates how strongly a particular characteristic manifests itself in each process. Characteristics can include keywords, type names, function references, etc. A is a value that equals 1 if any of the following apply:
• P[0429]₁and P₁are instantiations of the same source.
• P[0430]₁and P₂are unique instantiations of their own source.
• P[0431]₁and P₂communicate with each other.
• A equals 0 if none of these is true (e.g., P[0432]₁and P₂are nonunique instantiations of separate source that do not communicate with each other). Coupling is quantified by:$Coupling\left(P\right)=\frac{\sum _{\mathrm{ij}}Sim_f\left(p_i,q_j\right)}{mn}$

  
• where q[0433]_jεQ, Q is the complement of P, and n=|Q|. The quality of a cluster is quantified as its Coupling minus its Cohesion. In many cases, these metrics match many of the characteristics that intuitively differentiate good and poor clusters, as shown in FIGS. 38A, B, and C. With reference to FIGS. 38A and C, Cohesion is high where clusters correspond to heavy communication and where clusters correspond to processes instantiated from the same source code. Coupling is shown to be low in each of the above cases. With reference to FIG. 38B, Coupling is high when clusters do not correspond to heavily communicating processes or to instances of the same source code. It is not clear, however, that the cluster in FIG. 38C should be assigned the same quality value as the cluster in FIG. 38A. Using these metrics, Kunz achieved qualities of between :15 and :31 for his clustering techniques. However, it is hard to tell what this means in terms of cluster usefulness.
• 3. State-Based Debugging[0434]
• State-based debugging techniques focus on the state of the system and the state changes caused by events, rather than on events themselves. The familiar source-level debugger for sequential program debugging is state-based. This source-level debugger lets designers set breakpoints in the execution of a program, enabling them to investigate the state left by the execution to that point. This source-level debugger also lets programmers step through a program's execution and view changes in state caused by each step.[0435]
• Concurrent systems have no unique meaning for an instant in execution time. Stopping or single-stepping the whole system can unintentionally, but substantially, change the nature of interactions between processes.[0436]
• A. Consistent Cuts and Global State[0437]
• In distributed event-based debugging, the concept of causality is typically of such importance that little of value can be discussed without a firm understanding of causality and its implications. In distributed state-based debugging, the concept of a global instant in time is equally important.[0438]
• Here again, it may seem intuitive to consider real-time instants as the global instants of interest. However, just as determining the real-time order of events is not practical or even particularly useful, finding accurate real-time instants makes little sense. Instead, a global instant is represented by a consistent cut. A consistent cut is a cut of an event dependency graph representing an execution that (a) intersects each process exactly once and (b) points all dependencies crossing the cut in the same direction. Like real-time instants, consistent cuts have both a past and a future. These are the subgraphs on each side of the cut.[0439]
• FIG. 39 shows that consistent cuts can be represented as a jagged line across the space/time diagram that meets the above requirements. With reference to FIG. 39, a space/[0440]time graph3900 is shown having afirst cut3902 and asecond cut3904. All events to the left of eitherfirst cut3902 orsecond cut3904 are in the past of each cut, and all events to the right are in the future of each cut, respectively. First cut3902 is a consistent cut because no message travels from the future to the past.Second cut3904, however, is not consistent because amessage3906 travels from the future to the past.
• FIGS. 40A, B, and C show that a distributed execution shown in a space/time diagram[0441]4000 can be represented by a lattice ofconsistent cuts4002, in which

  

  is the start of the execution and ⊥ is system termination. With reference to FIGS. 40A, B, and C, lattice ofconsistent cuts4002 represents the global statespace traversed by a single execution. Since lattice ofconsistent cuts4002's size is on the order of |E|^|P|, it, unlike space/time diagrams, is never actually constructed. In the remainder of this chapter, to describe properties of consistent cut lattices, the symbol

  

  relates cuts such that one immediately precedes the other and

  

  relates cuts between which there is a path.
• B. Single Stepping in a Distributed Environment[0442]
• Controlled stepping, or single-stepping, through regions of an execution can help with an analysis of system behavior. The programmer can examine changes in state at the completion of each step to get a better understanding of system control flow. Coherent single-stepping for a distributed system requires steps to align with a path through a normal execution's consistent cut lattice.[0443]
• DPD works with standard single-process debuggers (called client debuggers), such as DBX, GDB, etc. Programmers can use these tools to set source-level break-points and single-step through individual process executions. However, doing so leaves the other processes executing during each step, which can yield unrealistic executions.[0444]
• Zernic gives a simple procedure for single-stepping using a post-mortem traversal of a consistent cut lattice. At each point in the step process, there are two disjoint sets of events: the past set, or events that have already been encountered by the stepping tool, and the future set, or those that have yet to be encountered. To perform a step, the debugger chooses an event, e,, from the future such that any events it depends on are already in the past, i.e., there are no future events, e[0445]_f, such that e_f

  

  e_i. This ensures that the step proceeds between two consistent cuts related by

  

  . The debugger moves this single event to the past, performing any necessary actions.
• To allow more types of steps, POET's support for single-stepping uses three disjoint sets: executed, ready, and nonready. The executed set is identical to the past set in “Using Visualization Tools to Understand Concurrency,” by D. Zernik, M. Snir, and D. Malki,[0446]IEEE Software9, 3 (1992), pp. 87-92. The ready set contains all events that are fully enabled by events in the future, and the contents of the nonready set have some enabling events in either the ready or nonready sets. Using these sets, it is possible to perform three different types of steps: global-step, step-over, and step-in. Global-step and step-over may progress between two consistent cuts not related

  

  (i.e., there may be several intermediate cuts between the step cuts).
• A global-step is performed by moving all events from the ready set into the past. Afterwards, the debugger must move to the ready set all events in the nonready set whose dependencies are in the executed set. A global-step is useful when the programmer wants information about a system execution without having to look at any process in detail.[0447]
• The step-over procedure considers a local, or single-process, projection of the ready and nonready sets. To perform a step, it moves the earliest event from the local projections into the executed set and executes through events on the other processes until the next event in the projection is ready. This ensures that the process in focus will always have an event ready to execute in the step that follows.[0448]
• Step-in is another type of local step. Unlike step-over, step-in does not advance the system at the completion of the step; instead, the system advance is considered to be a second step. FIGS. 41A, B, C, and D show a space/time diagram before a[0449]step4100 and a resulting space/time diagram after performing a global-step4102, a step-over4104, and a step-in4106.
• C. Runtime Consistent Cut Algorithms[0450]
• It is occasionally necessary to capture consistent cuts at runtime. To do so, each process performs some type of cut action (e.g., state saving). This can be done with barrier synchronization, which erects a temporal barrier that no process can pass until all processes arrive. Any cut taken immediately before, or immediately after, the barrier is consistent. However, with barrier synchronization, some processes may have a long wait before the final process arrives.[0451]
• A more proactive technique is to use a process called the cut initiator to send perform-cut messages to all other system processes. Upon receiving a perform-cut message, a process performs its cut action, sends a cut-finished message to the initiator, and then suspends itself. After the cut initiator receives cut-finished messages from all processes, it sends each of them a message to resume computation.[0452]
• The cut obtained by this algorithm is consistent: no process is allowed to send any messages from the time it performs its own cut action until all processes have completed the cut. This means that no post-cut messages can be received by processes that have yet to perform their own cut action. This algorithm has the undesirable characteristic of stopping the system for the duration of the cut. The following algorithms differ in that they allow some processing to continue.[0453]
• 1. Chandy-Lamport Algorithm[0454]
• The Chandy-Lamport algorithm does not require the system to be stopped. Once again, the cut starts when a cut initiator sends perform-cut messages to all of the processes. When a process receives a perform-cut message, it stops all work, performs its cut action, and then sends a mark on each of its outgoing channels; a mark is a special message that tells its recipient to perform a cut action before reading the next message from the channel. When all marks have been sent, the process is free to continue computation. If the recipient has already performed the cut action when it receives a mark, it can continue working as normal.[0455]
• Each cut request and each mark associated with a particular cut are labeled with a cut identifier, such as the process ID of the cut initiator and an integer. This lets a process distinguish between marks for cuts it has already performed and marks for cuts it has yet to perform.[0456]
• 2. Color-Based Algorithms[0457]
• The Chandy-Lamport algorithm works only for FIFO (First In First Out) channels. If a channel is non-FIFO, a post-cut message may outrun the mark and be inconsistently received before the recipient is even aware of the cut, i.e., it is received in the cut's past. The remedy to this situation is a color-based algorithm. Two such algorithms are discussed below.[0458]
• The first is called the two-color, or red-white, algorithm. With this algorithm, information about the cut state is transferred with each message. Each process in the system has a color. Processes not currently involved in a consistent cut are white, and all messages transmitted are given a white tag. Again, there is a cut initiator that sends perform-cut messages to all system processes. When a process receives this request, it halts, performs the cut action, and changes its color to red. From this point on, all messages transmitted are tagged with red to inform the recipients that a cut has occurred.[0459]
• Any process can accept a white message without consequence, but when a white process receives a red message, it must perform its cut action before accepting the message. Essentially, white processes treat red messages as cut requests. Red processes can accept red messages at any time, without consequence.[0460]
• A disadvantage of the two-color algorithm is that the system must reset all of the processes back to white after they have completed their cut action. After switching back, each process must treat red messages as if they were white until they are all flushed from the previous cut. After this, each process knows that the next red message it receives signals the next consistent cut.[0461]
• This problem is addressed by the three-color algorithm, which resembles the two-color algorithm in that every process changes color after performing a cut; it differs in that every change in color represents a cut. For colors zero through two, if a process with the color c receives a message with the color (c−1)[0462]mod3, it registers this as a message-in-flight (see below). On the other hand, if it receives a message with the color (c+1)mod3, it must perform its cut action and switch color to (c+1)mod3 before receiving the message. Of course, this can now be generalized to n-color algorithms, but three colors are usually sufficient.
• Programmers may need to know about messages transmitted across the cut, or messages-in-flight. In the two-color algorithm, messages-in-flight are simply white messages received by red processes. These can all be recorded locally, or the recipient can report them to the cut initiator. In the latter case, each red process simply sends the initiator a record of any white messages received.[0463]
• It is not safe to switch from red to white in the two-color algorithm until the last message-in-flight has been received. This can be detected by associating a counter with each process. A process increments its counter for each message sent and decrements it for each message received. When the value of this counter is sent to the initiator at the start of each process's cut action, the initiator can use the total value to determine the total number of messages-in-flight. The initiator simply decrements this count for each message-in-flight notification it receives.[0464]
• D. State Recovery—Rollback and Replay[0465]
• Since distributed executions tend to be nondeterministic, it is often difficult to reproduce bugs that occur during individual executions. To do so, most distributed debuggers contain a rollback facility that returns the system to a previous state. For this to be feasible, all processes in the system must occasionally save their state. This is called checkpointing the system. Checkpoints do not have to save the entire state of the system. It is sufficient to save only the changes since the last checkpoint. However, such incremental checkpointing can prolong recovery.[0466]
• DPD makes use of the UNIX fork system call to perform checkpointing for later rollback. When fork is called, it makes an exact copy of the calling process, including all current states. In the DPD checkpoint facility, the newly forked process is suspended and indexed. Rollback suspends the active process and resumes an indexed process. The problem with this approach is that it can quickly consume all system memory, especially if checkpointing occurs too frequently. DPD's solution is to let the programmer choose the checkpoint frequency through use of a slider in its GUI.[0467]
• Processes must sometimes be returned to states that were not specifically saved. In this case, the debugger must do additional work to advance the system to the desired point. This is called replay and is performed using event trace information to guide an execution of the system. In replay, the debugger chooses an enabled process (i.e., one whose next event has no pending causal requirements) and executes it, using the event trace to determine where the process needs to block for a message that may have arrived asynchronously in the original execution. When the process blocks, the debugger chooses the next enabled process and continues from there. In this way, a replay is causally identical to the original execution.[0468]
• Checkpoints must be used in a way that prevents domino effects. The domino effect occurs when rollbacks force processes to restore more than one state. Domino effects can roll the system back to the starting point. FIG. 42 shows a space time diagram[0469]4200 for a system that is subject to the domino effect during rollback. With reference to FIG. 42, if the system requests a rollback tocheckpoint c₃4202 ofprocess P₃4204, all processes in the system must roll back to c₁(i.e., roll back to P₃. c₂4206 requires a roll back to P₂. c₂4208, which requires a roll back to P₁. c₂4210, which requires a roll back to P₃. c₁4212, which requires a roll back to P₂. c₁4214, which requires a final roll back to P₁. c₁4216). The problem is caused by causal overlaps between message transfers and checkpoints. Performing checkpoints only at consistent cuts avoids a domino effect.
• E. Global State Predicates[0470]
• The ability to detect the truth value of predicates on global state yields much leverage when debugging distributed systems. This technique lets programmers raise flags when global assertions fail, set global breakpoints, and monitor interesting aspects of an execution. Global predicates are those whose truth value depends on the state maintained by several processes. They are typically denoted with the symbol φ. Some examples include (Σ[0471]₁c₁>20) and (c₁<20^ c₂5), where c_iis some variable in process P₁that stores positive integers. In the worst case (such as when (Σ₁c₁>20) is false for an entire execution), it may be necessary to get the value of all such variables in all consistent cuts. In the following discussion, we use the notation C_a|=Φ to indicate that Φ is true in consistent cut C_a.
• At this point, it is useful to introduce branching time temporal logic. Branching time temporal logic is predicate logic with temporal quantifiers, P, F, G, H, A, and E. PΦ is true in the present if Φ was true at some point in the past; FΦ is true in the present if Φ will be true at some point in the future; GΦ is true in the present if Φ will be true at every moment in the future; and HΦ is true in the present if Φ was true at every moment of the past. Notice that GΦ is the same as[0472]

  

  F

  

  Φ, and HΦ is the same as

  

  P

  

  Φ.
• Since global time passage in distributed systems is marked by a partially ordered consistent cut lattice rather than by a totally ordered stream, we need the quantifiers A, which precedes a predicate that is true on all paths, and E, which precedes a predicate that is true on at least one path. So, AFΦ is true in the consistent cut representing the present if Φ is true at least once on all paths in the lattice leaving this cut. EPΦ is true in the consistent cut representing the present if Φ is true on at least one path leading to this cut.[0473]
• A monotonic global predicate is a predicate Φ such that C[0474]_a|=Φ

  

  C_a|=AGΦ. A monotonic global predicate is one that remains true after becoming true. An unstable global predicate, on the other hand, is a predicate Φ such that C_a|=Φ

  

  C_a|=EG

  

  Φ. An unstable global predicate is one that may become false after becoming true.
• 1. Detecting Monotonic Global Predicates[0475]
• Monotonic predicates can be detected any time after becoming true. One algorithm is to occasionally take consistent cuts and evaluate the predicate at each. In fact, it is not necessary to use consistent cuts, since any transverse cut whose future is a subset of the future of the consistent cut in which the predicate first became true will also show the predicate true.[0476]
• 2. Detecting Unstable Global Predicates[0477]
• Detecting arbitrary unstable global predicates can take at worst |E|[0478]^|P| time, where |E|^|P| is the size of an execution's consistent cut lattice, [E] is the number of events in the execution, and [P] is the number of processes. This is so, because it may be necessary to test for the predicate in every possible consistent cut. However, there are a few special circumstances that allow |E| time algorithms.
• Some unstable global predicates are true on only a few paths through the consistent cut lattice, while others are true on all paths. Cooper and Marzullo describe predicate qualifiers definitely Φ for predicates that are true on all paths (i.e.,[0479]

  

  |=A FΦ) and possibly Φ for those that are true on at least one path (i.e.,

  

  |=>E FΦ.
• The detection of possibly Φ for weak conjunctive predicates, or global predicates that can be expressed as conjunctions of local predicates, is Φ (|E|) The algorithm for this is to walk a path through the consistent cut lattice that aligns with a single process, P[0480]_t, until either (1) the process's component of Φ is true or (2) there is no way to proceed without diverging from P_t. In either case, the target process is switched and the walk continued. This algorithm continues until it reaches a state in which all components of the predicate are true or until it reaches ⊥. In this way, if there are any consistent cuts where all parts of the predicate simultaneously hold, the algorithm will encounter at least one.
• Detection of possibly Φ for weak disjunctive predicates, or global predicates that can be expressed as disjunctions of local predicates, is also φ (|E|); it is the same algorithm as above, except it halts at the first node where any component is true. However, weak conjunctive and disjunctive predicates constitute only a small portion of the types of predicates that could be useful in debugging distributed systems.[0481]
• 4. Conclusions[0482]
• Complicating the debugging of heterogenous embedded systems are designs composed of concurrent and distributed processes. Most of the difficulty in debugging distributed systems results from concurrent processes with globally unscheduled and frequently asynchronous interactions. Multiple executions of a system can produce wildly varying results—even if they are based on identical inputs. The two main debugging approaches for these systems are event based and state based.[0483]
• Event-based approaches are monitoring approaches. Events are presented to a designer in partially ordered event displays, called space/time displays. These are particularly good at showing inter-process communication over time. They can provide a designer with large amounts of information in a relatively small amount of space.[0484]
• State-based approaches focus locally on the state of individual processes or globally on the state of the system. Designers can observe individual system states, set watches for specific global predicates, step through executions, and set breakpoints based on global state predicates. These approaches deal largely with snapshots, considering temporal aspects only as differences between snapshots.[0485]
• As distributed systems increase in size and complexity, the sheer volume of events generated during an execution grows to a point where it is exceedingly difficult for designers to correctly identify aspects of the execution that may be relevant in locating a bug. For distributed system debugging techniques to scale to larger and faster systems, behavioral abstraction will typically become a necessity to help designers identify and interpret complicated behavioral sequences in a system execution. Finally, embedded systems must execute in a separate environment from the one in which they were designed and embedded systems may also run for long periods of time without clear stopping points. Debugging them requires probes to report debugging information to a designer during the execution. These probes inevitably alter system behavior, which can mask existing bugs or create new bugs that are not present in the uninstrumented system. While it is not possible to completely avoid these probe effects, they can be minimized through careful placement, or masked through permanent placement.[0486]
• Evolution Diagrams[0487]
• Evolution diagrams are visual representations of a system's behavior over time. They resemble the space/time diagrams discussed in[0488]Chapter 2, but they explicitly include information related to component behavior and changes in behavior caused by events. Evolution diagrams take advantage of the exposure provided by coordination interfaces to present more complete views of system executions than can be obtained from space/time diagrams.
• Evolution diagrams explicitly show events, message traffic between components, changes in component behavior, and correlations between local behavior changes. Through them, designers can easily spot transaction failures and components operating outside of their expected model. Essentially, evolution diagrams are event graphs interpreted in the context of the system being debugged. While evolution diagrams do not aid the debugging of individual lines of action code, they can help designers pinpoint the specific action to debug. In Section 4.5.2, we discuss how source-level debuggers can be integrated coherently with evolution diagrams.[0489]
• FIG. 43 portrays the evolution of a dedicated RPC transaction. It has traces for both components[0490]4310 (bars enclosed by dashed lines), interface states4312 (shown by solid horizontal bars), and events4314 (shown by vertical ovals spanning the space affected by the event). The figure displays all essential aspects of an RPC transaction.
• The remainder of this section describes event and state representations, event dependencies, the use of evolution diagrams with high-level simulation to detect transaction failures and inappropriate component behavior, and debugging issues that become evident at synthesis (“synthesis effects”).[0491]
• Event Representations[0492]
• Event representations display all event types described earlier (e.g., transmission and reception of data, changes in control state, and changes in more general shared state). Event representations have a name and can also have a visual cue, or icon, such as those shown in FIG. 44.[0493]
• The design methodology described above clearly identifies the types of events that can be generated by each component. Although there are many more specific types than shown in FIG. 44, each specific type must be derived from one of those shown. For example, both RPC.Client.argument.send and RPC.server.return.send are derived from the primitive send event.[0494]
• State Representations[0495]
• Modes and other types of state are displayed as horizontal bars annotated with the name of the state and, where appropriate, the value. These bars extend across the duration of the mode or the value. See FIG. 43. Through state views, designers can monitor component behavior changes over time.[0496]
• The types of state that can be displayed are the values of exported variables and control state. FIG. 45 shows illustrative primitive state types.[0497]
• Event Dependencies[0498]
• Events on different components may be connected explicitly by messages traveling between them or implicitly by coordinator constraints and actions, as described earlier. Explicit connections are displayed as arrows between transmit and receive events. Implicit connections are displayed as diagonal lines without arrows, where the event on the left side is the immediate predecessor of the event on the right side. These connections indicate dependencies in the underlying event graph. See the discussion above regarding FIG. 25, et seq.[0499]
• Debugging with Evolution Diagrams[0500]
• Evolution diagrams can be integrated with high-level simulation, letting designers fix many bugs before synthesis and mapping to a hardware architecture. FIG. 46 shows the evolution diagram of a correct lookup and an initiate call transaction for the mobile telephone example. This diagram shows the top level of the design hierarchy for the cell phone itself. The transaction begins when a user looks up a number in the address book. When the number is selected, the GUI sends it to the connection subsystem with a send action, which generates a send event[0501]4604. It then waits for the connection to go through. This demonstrates the use of design hierarchy to hide information; many aspects of the GUI and connection subsystem's interaction are hidden from view, but the information presented gives a general idea about what is going on inside the system. The connection subsystem then contacts the call recipient and starts the ring signal in the voice subsystem4608. When the recipient answers the phone, the GUI, the connection subsystem, and the voice subsystem all switch to the call-in-progress mode4610 and begin the corresponding behavior.
• If part of the transaction fails (for example, if the phone never plays a ring-back tone), the designer can often find the source of the problem in an evolution diagram. If the problem is caused by a control failure, the voice subsystem does not enter ringing mode, and designers would see something like the evolution diagrams shown in FIG. 47. FIG. 47A shows the results of a local control failure, where the voice subsystem receives the appropriate trigger[0502]4710 but does not respond appropriately by moving into ring mode. FIG. 47B shows the same transaction, except that the problem is in the distributed control structure.
• Selective Focus in Debugging[0503]
• Selective focus describes techniques by which designers can limit the data presented based on its relevance at any point in time. Selective focus plays an important role in debugging with evolution diagrams. For example, designers begin debugging the 47 problem needing only high-level information about the system's behavior. Once the high-level source of the problem is found, designers can descend the design hierarchy to pinpoint the cause. FIG. 48 shows an expanded view of the voice subsystem, where, at the point of failure, the sound coordinator fails to switch on the “ringing” mode. A designer can now investigate the specific action responsible for this. With selective focus, the designer can quickly bore into the affected region to help identify the bug's cause.[0504]
• Selective focus is also useful in debugging problems with layered coordination. Recall from FIG. 19 that there are several coordination layers between the call managers on the cell phone and the switching center, but that there is conceptual coordination between peer layers. This conceptual coordination enables a form of selective focus.[0505]
• Consider an example where designers discover that a cell phone drops calls at random moments. Using standard good troubleshooting procedure, they begin debugging at the layer nearest the detected problem: call management. Using evolution diagrams and selective focus, the designers can investigate the bug on the call management layer without requiring details from lower layers. They can review the progress of the phone call up until the moment of the drop.[0506]
• Assume the cause of the bug is elsewhere (for example, the radio resource layer sometimes fails when performing handoffs between cells), finding no specific problem in the call management layer, designers can proceed down the protocol stack to the mobility management layer and, finding no problem there, move on to the radio resource layer. At the radio resource layer, designers will find that, at the time of the drop off, the radio resource component was in the midst of executing a handoff, wherein the problem lies. Thus, they may immediately suspect that the cause of the problem was related to the handoff.[0507]
• Correlating Disparate Behaviors[0508]
• Consider a bug that manifests itself in interactions among several components. FIG. 49 shows the source code for components X, Y, and Network Interface, shading the aspects that participate in the bug. As shown, these participating sections of code are scattered across three files. Because of this scattering, and because the relevant sections of code do not execute at the same time, a designer is unlikely to spot the bug easily through source-level debugging techniques.[0509]
• FIG. 50 shows an evolution diagram of a bug from a system built with the present methodology. At the point of failure, the evolution diagram shows that the network interface's resource is taken, and that X is clearly holding the resource. Scrolling back, we find that when Y tried to obtain the resource, it could not because X was still holding it. Scrolling back further, we may find a number of such repeated attempts, each with similar failures. And finally, scrolling back to the beginning, we find that grabbed the resource before Y's first attempt, and that never released it. We now know that X was the primary cause of the problem, and the problem is now reduced to debugging a single component.[0510]
• Event Persistence[0511]
• In each of the examples described above, it was necessary to review portions of the system execution several times to track down a bug. For the ring failure bug, we needed to review the failure to obtain detailed information about the voice component's behavior. For the call dropping bug, we needed to review the execution at least three times to trace the bug through the call management, mobility management, and radio resource layers. For the resource allocation bug, we needed to examine the behavior of component X in the vicinity of the bug to determine why it never released the resource. Repeated executions of a concurrent system with the same inputs can produce greatly varying results. Specific interactions may differ on each new execution, preventing designers from making progress in debugging.[0512]
• To avoid this, and ensure that each execution is identical to the last, it is necessary to: (1) maintain a store of an execution's events and the relationships among them, and (2) provide our debugging tools with the means to traverse this store many times with differing perspectives. We can operate directly on this store, as described later.[0513]
• Synthesis Effects[0514]
• Designers inevitably make assumptions about relative timing that are not necessarily borne out by the implementation. Unfortunately, idealized simulation without regard for architectural issues can give designers a skewed perspective. It is only at synthesis that the actual timing between events and the relative timing between actions congeals. Solidifying timing concerns affects event orders and timing constraints. The synthesized system must be tested and validated by a designer.[0515]
• An example of synthesis effects can be seen in the use of the round-robin/preempt coordinator described earlier. In this protocol, components usually take turns with the resource, but one of the components is a preemptor that can take over without waiting for its turn. A potential source of problems is that after preemption, control always returns to the component that follows the preemptor in the ring, not to the component that was preempted. This may still be a reasonable design decision, since distributed tracking of the preempted component can be expensive. However, in the mapping shown in FIG. 51, this combined protocol performs poorly.[0516]
• As shown in FIG. 52A, before synthesis, this system approximates fair access to the resource. After synthesis, as shown in FIG. 52B, preemption seems to occur more frequently than expected. This results in components C, D, and E getting few or no chances to access the resource. In this case, a bug fix may be to alter the protocol so that it tracks the component that held the resource before preemption, to try different mappings to alter the situation so that preemption occurs less frequently, or to try different protocols altogether.[0517]
• Behavioral Perspectives[0518]
• Design hierarchy is a very important part of managing debugging complexity: it allows designers to observe what is happening in a system or component at a general level, and then further refine the view. Unfortunately, clusters that make sense for design purposes are not always the ones needed for debugging. FIG. 53A shows part of the design decomposition of the GUI module. To compare numbers generated by the keypad with packets sent out through the transport, designers need only be able to put the relevant parts into focus and represent the rest of the system as a cluster, as shown in FIG. 53B.[0519]
• Behavioral perspectives allow designers to tailor selective focus for their convenience. A behavioral perspective is a set of clusters and filters, some of which may be derived from the design hierarchy, while others may be specified by a designer when the design hierarchy is not sufficient. Special-purpose clusters and filters are described below.[0520]
• Special-purpose Clusters[0521]
• Designers use special-purpose clusters to help reduce the amount of clutter presented in a display without eliminating sources of information. There are three types of special-purpose clusters: component, event, and state. Component clusters combine several component traces into one; event clusters combine sequences of events on a single component into one; and state clusters combine several state traces into one. Designers can form clusters that are separate from the design hierarchy, as shown in FIG. 54.[0522]
• Clusters can be described in two ways: visually, through selection on an evolution diagram, or textually, through cluster lists (see[0523]Listing number 1, as follows):

  	Listing 1:

  ClusterComponent “C1, C2” {

  C1, C2

  	}
  	ClusterStates C1. “Z” {

  C1. Q, C1. P

  	}

• Special-purpose Filters[0524]
• Filters remove specific events, states, and even components from a designer's view. Using filters, designers can observe only the parts of an execution that pertain to a specific debugging objective. Filters work well with clusters to help a designer reduce the total noise in an evolution diagram.[0525]
• Like clusters, filters can be described both visually and textually. Filter lists can have the form ALL except <event list>. Thus, in cases where there are more event types to be filtered than passed, a designer can use the filter lists to specify only those events that should be shown.[0526]
• FIGS. 55A and 55B show before and after snapshots, respectively, of an evolution diagram using the filter description shown in[0527]Listing number 2, as follows:

  	Listing 2:
  	Filter {

  	Components {
  	C3
  	}
  	States {

  ALL except C1.Q, C2.S

  	}
  	Events {

  ALL except C1.a.send,

  	C1.r.rec, C2.a.rec,
  	C2.r. send

  }

  	}

• Event type names in this listing have the form:[0528]
• component_name.interface.specific_type.[0529]
• The result of applying this filter clarifies an RPC-like aspect of this coordination. Designers can also use filters to expose events and states that are not normally visible at a particular level of focus.[0530]
• It will be apparent to those having skill in the art that many changes may be made to the details of the above-described embodiment of this invention without departing from the underlying principles thereof. The scope of the present invention should, therefore, be determined only by the following claims.[0531]

Claims (30)

1. A method for debugging a distributed software system that includes first and second components and a coordinator that implements a desired interaction between the first and second components; each component and the said coordinator including coordination interfaces that expose events, and the debugging method comprising the steps of:

creating an event record in response to each exposed event that occurs during an execution of the distributed software system, each event record including identification of a component that generated the event and a local time stamp;

accumulating the event records into an event database; and then

displaying an evolution diagram for use by a developer in debugging the distributed software system, the evolution diagram including a graphical representation of at least a selected portion of the event database.

2. A method according toclaim 1 wherein said displaying step includes displaying at least a first selected event together with the identification of the component that generated the selected event.

3. A method according toclaim 1 wherein the displaying step includes presenting in the evolution diagram:

a first graphical display element representing a first component of the software system; and

a second graphical display element representing a first selected event generated by the first component;

the first and second graphical display elements being juxtaposed so as to visually indicate that the first selected event was generated by the first component.

4. A method according toclaim 1 wherein the displaying step includes presenting in the evolution diagram:

a first graphical display element representing a first event;

a second graphical display element representing a second event; and

a third graphical display element indicating a causal relationship between the first and second events.

5. A method according toclaim 4 wherein each of the first and second graphical display elements comprises an identifier of a component that generated the corresponding event.

6. A method according toclaim 4 wherein the causal relationship comprises sending a message as the first event and receiving the said message as the second event.

7. A method according toclaim 6 wherein the third graphical display element comprises an arrow extending from the first graphical display element to the second graphical display element.

8. A method according toclaim 4 wherein at least one of the first and second events consists of a control state change exposed at the coordination interface of one of the components.

9. A method according toclaim 4 wherein at least one of the first and second events consists of a message sent from a port at the coordination interface one of the components.

10. A visual display for use by a developer in debugging a distributed or concurrent software system, the visual display comprising an evolution diagram responsive to a predetermined set of event records generated during an execution of the subject software system; each event record reflecting a corresponding software system event.

11. A visual display according toclaim 10 wherein each of the event records is responsive to one of a timer tick, a data departure, a data arrival or a mode change.

12. A visual display according toclaim 10 wherein the evolution diagram includes:

a first graphical display element representing a first component of the software system; and

a second graphical display element representing a first event generated by the first component;

the first and second graphical display elements being juxtaposed in the visual display so as to cue the developer that the first event was generated by the first component.

13. A visual display according toclaim 12 wherein the first graphical element representing a first component of the software system comprises a generally horizontal bar and the second graphical display element comprises a generally vertical icon overlapping the horizontal bar.

14. A visual display according toclaim 10 wherein the evolution diagram includes:

a first graphical display element representing a first component of the software system;

a second graphical display element representing a second component of the software system; and

a third graphical display element representing an implicit message from the first component to the second component.

15. A visual display according toclaim 10 wherein the evolution diagram includes:

a first graphical display element representing a first component of the software system;

a second graphical display element representing a second component of the software system; and

a third graphical display element representing an explicit message from the first component to the second component.

16. A visual display according toclaim 10 wherein the evolution diagram includes:

a first graphical display element representing a first event;

a second graphical display element representing a second event; and

a third graphical display element representing a causal relationship between the first and second events.

17. A visual display according toclaim 16 wherein

the first graphical display element includes identification of a component that generated the said first event;

the first event is sending a message;

the second event is receipt of a message caused by the first event; and

the third graphical display element comprises an arrow having a tail positioned adjacent the first graphical display element and a head positioned adjacent the second graphical display element.

18. A visual display according toclaim 12 wherein the first graphical display element includes indicia identifying a control state of the first component and indicating its current value.

19. A visual display according toclaim 12 wherein the first graphical display element includes indicia identifying an exported variable of the first component and indicating its current value.

20. A method for debugging a distributed, hierarchical software system that includes a plurality of design levels, each design level comprising two or more components and a coordinator that implements desired interaction between the said components; each component and the coordinators with which it interacts including respective complementary coordination interfaces that expose events, and the debugging method comprising the steps of:

creating an event record in response to each exposed event that occurs during an execution of the distributed software system, each event record including identification of a component that generated the event and a local time stamp;

accumulating the event records into an event database;

partially ordering the event database based on the time stamps; and then

displaying an evolution diagram for use by a developer in debugging the distributed software system, the evolution diagram including a graphical representation of at least a selected portion of the event database.

21. A method according toclaim 20 wherein said displaying step includes selecting one of the design levels and displaying an evolution diagram corresponding to the selected design level including graphical indicia including events exposed at the coordination interfaces of components defined at the selected design level, thereby hiding subsystem interactions from view.

22. A method according toclaim 21 and further comprising selecting a temporal subset of the event database for inclusion in the displayed evolution diagram thereby selectively focusing on a region of interest to the developer.

23. A method according toclaim 20 wherein the execution is simulated.

24. A method according toclaim 20 wherein the execution is carried out on a target hardware platform.

25. A method according toclaim 20 wherein the software system is instrumented so as to generate event records at selected points in execution that are not events exposed at the coordination interface of a component.

26. A method according toclaim 20 wherein the execution is carried out on a distributed, embedded target hardware platform comprising a plurality of hardware subsystems, and the event records are collected from each hardware subsystem.

27. A method according toclaim 20 wherein said displaying the evolution diagram includes combining a selected sequence of events on a single component so as to form an event cluster, and then displaying the event cluster.

28. A method according toclaim 20 wherein said displaying the evolution diagram includes combining a selected group of components so as to form a component cluster, and then displaying a single trace representing the component cluster.

29. A method according toclaim 20 wherein said displaying the evolution diagram includes combining a selected group of state traces so as to form a state cluster, and then displaying a single trace representing the state cluster.

30. A method according toclaim 20 and further comprising filtering selected events, states or components from the evolution diagram.

Images