This content was uploaded by our users and we assume good faith they have the permission to share this book. If you own the copyright to this book and it is wrongfully on our website, we offer a simple DMCA procedure to remove your content from our site. Start by pressing the button below!
> Q5 ; ... Q5 : = Queue . c r e a t e <... >( M a x C a p a c i t y . QUEUE ) ; CAD . b i n d D i s p a t c h i n g Q u e u e <... >(Q5 , 5 ) ; ... thread threadgroup5 () { P a i r . t y p e<EventHandlerEnum , CAD . Event > p a i r ; EventHandlerEnum h a n d l e r ; CAD . E v e n t e v e n t ;
}
l o c l o c 0 : l i v e { h a n d l e r , e v e n t } when Queue . s i z e <... >(Q5) > 0 do i n v i s i b l e { p a i r : = Queue . g e t F r o n t <... >(Q5 ) ; Queue . dequeue <... >(Q5 ) ; h a n d l e r : = P a i r . f i r s t <... >( p a i r ) ; e v e n t : = P a i r . s e c o n d <... >( p a i r ) ; } goto l o c 1 ; l o c l o c 1 : l i v e {} i n v i s i b l e i n v o k e v i r t u a l f ( h a n d l e r , e v e n t ) goto l o c 0 ;
Fig. 8. Bogor dispatch queue and thread model for ModalSP (excerpts).
the Bogor model, queues are modeled using Queue and Pair extensions. Figure 8 illustrates the 5 hertz rate queue of pending event dispatches and the thread, threadgroup5, that cyclically dequeues dispatch pairs and invokes the component event handler encoded in each pair (note that pair type declarations are elided (i.e., <...>) for improved readability). Each correlator is represented as a deterministic finite-state automaton whose transition function is encoded as a static transition table. For each correlator, there is a single state variable that holds the current correlator state. Since the structure of correlators is fixed for a given system, the transition tables are not held in the state vector. 5.4
Summary of Data Portion of State-Vector
To summarize the modeling strategy discussed above, we present the state vector components related to data state of Cadena systems. The observable state of a Cadena assembly is comprised of all non-fixed system data. As we have noted above, correlator transition tables, subscriber lists, and component connection information are all fixed and are not considered part of the observable state. Definition 1. Cadena Data States are tuples (c, r, a, t, p) where: c = (c1 , . . . , ck ) stores the data states of component instances, each of which is comprised of a, possibly empty, set of mode attributes as defined by ci ’s component type. r = (qr1 , . . . , qrn ) are rate-specific queues of pairs, (c, e), recording the dispatch of event e to port c. a = (a1 , . . . , al ) stores the current states of each of the event correlation recognition automata. t records an abstraction of time used to trigger timeouts. p records the priority of the current thread being executed.
Model-Checking Middleware-Based Event-Driven Real-Time
171
The initial state is defined to have instance modes set to their initial values, correlation automata set to their start state, rate specific queues to be empty, t = 0, and the priority variable is set to the highest priority. The values of local variables in component handlers and methods and in the implementation of push methods and rate-specific threads cannot be observed outside their method activation by other threads or by property observables and are also not considered part of the observable state. Local variable are held in the state vector, but only during the corresponding method activations. In addition to the data state described above, Bogor maintains control information in the form of a program counter and a method call-stack frame for each thread. 5.5
Strategies for Modeling Scheduling and Time
The behavior of Cadena systems is driven by the triggering of middleware timeouts as described in Section 4 and is controlled by the scheduling policies of the thread-pool in the real-time event channel. Finding an effective strategy for modeling these timeouts and thread-scheduling is a central issue in the construction of Cadena models. When analyzing concurrent systems, most model-checkers do not attempt to exploit knowledge of specific timing or scheduling strategies but instead explore all possible interleavings of concurrent actions. If we followed this approach, we would allow timeout events to occur non-deterministically between every system transition and we would allow actions from different threads to be interleaved non-deterministically without consideration of priorities or other scheduling constraints. While such a strategy is sound in that it covers all possible system behaviors, the number of states generated makes it impractical for all but the smallest systems. In the subsections below, we describe several strategies that we use to reduce infeasible interleavings. Each strategy incorporates constraints based on observations about priority scheduling and timeout policies implemented by the real-time middleware. Priority-based scheduling: Having the model-checker non-deterministically explore interleavings without considering thread priorities obviously introduces schedules that are infeasible in the actual system, e.g., a schedule that continues to execute transitions from a lower priority thread even though a higher-priority thread is enabled. Inter-rate-group timeout constraints: Having the model-checker nondeterministically generate timeout events introduces schedules that are infeasible in the actual system, e.g., a 5 Hz timeout event should not occur more frequently than a 20 Hz timeout event. We present strategies that reduce infeasible interleavings by taking into account the appropriate relative frequency of timeout events, i.e., by taking into account constraints that exist between timeouts of different rate groups. Intra-rate-group timeout constraints: Having the model-checker nondeterministically generate timeout events introduces infeasible schedules
172
X. Deng et al.
where a timeout for a rate group r occurs before all events in the current frame for r are dispatched or before the previous timeout from group r is even dispatched. We constrain the generation of time-out events to ensure that timeouts from the same rate group are not triggered “too quickly”. This strategy constrains the occurrence of timeouts by considering the relative lengths of the real-time frames and constrains scheduling by considering priority information. Lazy-time with priority scheduling: In addition to the techniques used in the strategy above, this strategy also considers timing estimates for system transition which allows additional infeasible schedules to be removed from consideration. 5.6
Representing Priority-Based Scheduling Information
Bold Stroke systems are priority scheduled based on the results of rate monotonic analysis of a set of harmonic rate groups. The CAD call connectEvent(), illustrated in Figure 7, assigns a rate, and hence a priority, to each component handler for a given event. The default non-deterministic scheduling policy in Bogor is implemented by a module that calculates the set of enabled transitions in a given state and passes that set to the state exploration module, which explores each possible outgoing transition. When reporting our experiments, we refer to models that use this strategy as priority-unaware. For Cadena models, a Bogor plugin is used that intercepts the set of enabled transitions in a given state, selects the transitions with the highest priority and passes these transitions on to the state exploration module. As expected, this yields dramatic reductions in the state space, as shown in Section 6, and also improves the precision of the state space since only infeasible schedules are eliminated (i.e., ones on which a lower-priority transition executes when a higher-priority transition is enabled). We refer to models that use this strategy as priority aware. Variations of this plugin are used in the following models to allow for interleaving of timeouts with the highest-priority enabled transition. 5.7
Representing Intra-rate-group Timing Constraints
The treatment of time, t, determines, in part, the fidelity of the model with respect to the real system’s behaviors. If detailed timing information is available one can keep track of time as component actions are executed and use that time value to trigger periodic events. However, even when timing information is not available, one can still reduce the occurrence of timeout events based on both intra- and inter-rate-group constraints. Intra-rate-group constraints that we consider involve the notion of frame overrun. A frame overrun occurs when a timeout event er for rate group r occurs before all events e triggered directly or indirectly by the previous timeout for r are processed by the rate group’s thread tr . In normal situations, a timeout er occurs and is dispatched, other events arrive in the event channel’s dispatch queues (including those associated with r), and thread tr becomes idle after all
Model-Checking Middleware-Based Event-Driven Real-Time
173
events associated with r have been dispatched. The time that tr remains idle waiting for the next r timeout is called slack time. If a system has a frame overrun error, a thread tr has no slack time – it is unable to finish all of its work before the next timeout er arrives. Note that exploring the state-space of systems where arbitrary frame overruns are modeled results in a huge number of additional system behaviors that would very likely be infeasible if actual timing data were considered (timing data would allow us to conclude that in most cases frame overruns do not occur). While frame overruns are a real source of bugs in Bold Stroke systems, engineers have other tools and methods for detecting these types of errors. Accordingly, we will reduce the state space that we explore using two strategies. The first strategy which we call no overruns assumes that no frame overruns occur at all. This is implemented by having the model-checker scheduler only emit a timeout event for rate group r if there are no enabled transitions associated with rate group r – which models the situation where tr has become idle because its associated dispatch queue is empty. The second strategy which we call limited overruns is implemented by having the model-checker scheduler only emit a timeout event er if there is no other timeout event remaining in the r dispatch queue (but other non-timeout events may still be waiting in the queue for dispatch). Intuitively, this model includes overruns that only spill over into the very next frame but does not include overruns where processing is ‘late’ by more than one additional frame. 5.8
Representing Inter-rate-group Timing Constraints
The strategies related to frame overrun in the previous section constrain timeout events by considering when they should occur relative to other timeouts from the same rate group. We now describe a strategy which we call the relativetime (RT) strategy that constrains the issuing of timeout events by considering when a timeout for r should occur relative to a timeout for a different rate group r . Specifically, we take advantage of the fact that in rate-monotonic scheduling theory (which is used in Bold Stroke systems), the frame associated with a rate can be evenly divided into some whole number of r -frames for each rate r that is higher than r. In the example system of Figure 3, the frame of the slowest rate (1 Hz) can be divided into 5 5 Hz frames, and each 5 Hz frame can be divided into 4 20 Hz frames. The longest frame/period (the frame associated with the lowest rate) is called the hyper-period. The relative-time model enforces the following constraints related to issuing of timeouts: – a single timeout is issued for the slowest rate group in the hyper-period, – timeouts for rate groups, ri and rj where ri > rj , are issued such that ri /rj timeouts of rate ri are issued in a rj frame. These constraints determine the total number and relative ordering of instances of timeouts that may occur in the hyper-period.
174
X. Deng et al.
CAD . Component Timer ; ... Timer : = CAD . c r e a t e C o m p o n e n t ( ” Timer ” ) ; CAD . d e c l a r e E v e n t S o u r c e P o r t <EventType >(Timer , ” timeOut5 ” , EventType . TimeOut ) ; ... thread timerThread () { l o c l o c 0 : l i v e {} when t r u e do { t i m e : = ( t i m e + 1 ) % 2 0 ; } goto l o c 0 ; } ... thread timeOutSenderThread ( ) { ... l o c l o c 1 : / / 5 Hz t i m e o u t c a s e when t i m e % ( 2 0 / 5 ) = = 0 do i n v i s i b l e { } goto l o c I n v o k e 5 ; when t i m e % ( 2 0 / 5 ) ! = 0 do i n v i s i b l e { } goto l o c 2 ; ... loc locInvoke5 : l i v e { localTime} i n v i s i b l e i n v o k e p u s h O f P r o x y ( Timer , ” timeOut5 ” , CAD . c r e a t e E v e n t <EventType > ( EventType . TimeOut ) ) goto l o c 2 ; ... l o c l o c 2 : / / 1 Hz t i m e o u t c a s e ... }
Fig. 9. Timer and TimeOutSender thread models for ModalSP (excerpts).
Figure 9 shows the Bogor code for two threads that are used to model this strategy. Thread timerThread increments an abstraction of time where each ’tick’ (i.e., each increment of the time variable) represents the passing of time corresponding to the shortest frame in the system (e.g., in the ModalSP, each tick represents a 20 Hz frame). The time variable wraps around every 20 ticks which corresponds to the fact that there are 20 Hz frames in the 1 Hz hyperperiod. Thread timeOutSenderThread models the behavior of the rate-specific timer threads in the middleware discussed in Section 4. This thread monitors time and when it observes a change in the time value, it passes through a case statement to see which timeout events should be dispatched at that point. Since a time tick represents the period of the shortest frame, a new timeout event for the fastest rate is issued on each pass through the case statement. In our example system, the 5 Hz timeout happens every fourth tick. To represent the occurrence of a timeout, the thread enqueues the timeout event through the standard push call. From the explanation above, it is clear that the RT model only establishes the occurrence of timeouts relative to each other – it does not relate timeout occurrences to the time required by component event handlers and method execution. Thus, it is now important to understand when timeout actions may occur with respect to actions that occur inside of component handlers, i.e., when can these actions be interrupted by timeouts. To see that the model safely approximates all interleavings of timeouts and component actions (given the constraint on no frame overruns) consider Figure 10. This figure illustrates four points during a system execution which contains 5 Hz and 10 Hz rate processing. The 10 Hz and 5 Hz timeouts are queued together (e.g., at the point 1) since they both have frames that begin at the
Model-Checking Middleware-Based Event-Driven Real-Time
10Hz and 5Hz
175
10Hz timeout
10Hz
10Hz execution step 5Hz timeout 5Hz execution step
10Hz priority delay interleaving
5Hz time 1
2
3
4
Fig. 10. Relative-time Environment.
same point. However, the 10 Hz timeout event is dispatched first due to its higher priority. Once the all the actions associated with 10 Hz component processing complete (e.g., at point 2), the model-checker scheduler begins consideration of lower priority actions and the 5 Hz timeout is dispatched leading to 5 Hz component processing. Our no overruns assumption entails that processing the 10 Hz component actions does not require more time than the period of the 10 Hz frame — thus, the next 10 Hz timeout cannot occur before point 2. Since we are not modeling the actual time required for carrying out component actions, it impossible to determine the relationship between the time required for 5 Hz component action processing (e.g., the duration from point 2 to 4) and the time until the next 10 Hz timeout (e.g., the duration from point 2 to 3). To safely cover all possibilities, we must allow for any relationship between these durations. To model all such relationships, we adapt Bogor’s standard scheduling module to consider all interleavings of enabled timeouts with the enabled transitions. On the right in Figure 10 the interleavings of the 10 Hz timeout and the enabled transitions performed during 5 Hz component processing are illustrated. The dark grey double circle represents the dispatching of the leftmost 10 Hz timeout event. This is followed by three dark grey circles representing transitions in 10 Hz component processing: the first branch point represents the choice between the next 10 Hz timeout (on the left) or dispatching the already queued 5 Hz timeout event (on the right). If 5 Hz processing is selected then the choice between the 10 Hz timeout and 5 Hz processing repeats for the next enabled 5 Hz transition illustrated as a light grey circle. 5.9
Lazily-Timed Components
In the relative-time model, timeouts are arranged in a proper order and ratio with respect to each other, but there are no constraints that guarantee that, e.g., the interval between time outs is appropriate for the correspond period. This means that the model may have interleavings in which a timeout, e.g., for ri , occurs prematurely with respect to an action sequence whose duration is less than period(ri ). For example, if the 5 Hz component processing (i.e., from point 2 to 4) in Figure 10 is guaranteed to be less than the time to the next
176
X. Deng et al. 10Hz
10Hz priority delay
5Hz time 1
2
3
Fig. 11. Lazily-timed Environment.
10 Hz timeout (i.e., point 4 comes before point 3) then the interleavings of 10 Hz timeouts with 5 Hz processing in the RT model will be infeasible. The lazilytimed (LT) component model addresses this by leveraging worst-case estimates of the running time of components; these will be available for Cadena systems to support rate monotonic analysis. This model can be configured for whatever granularity of timing information is available. Here we consider worst-case timing estimates for event handlers. Conceptually, the estimates are used to determine whether a handler can run without interruption before the next timeout occurs and, if not, the model non-deterministically interleaves action sequences from the handler with timeouts and higher-priority actions that follow from timeouts. This model modifies the data associated with time to record the intra-hyperperiod (IHP) time normalized by the least common factor of all handler durations and timeout periods, the guards in timeOutSenderThread from Figure 9 are adjusted accordingly, and each component handler is modified to include an increment of time. Figure 11 illustrates how these increments are performed. It shows the execution of 5 Hz component processing subsequent to completion of 10 Hz processing in a frame. There are two cases: (1) the worst-case time estimate of the 5 Hz processing (i.e., which runs up to point 2) is less than or equal to the next timeout (i.e., timeout occurs at point 3) or (2) it is not (i.e., timeout occurs at point 1 and interrupts the 5 Hz actions). In case (1), the IHP time is incremented by the worst-case timing estimate of the currently running 5 Hz event handler and the state space exploration algorithm proceeds; note that there is no branching in the state space for this case. In case (2), the IHP time is incremented to the next timeout (i.e., point 1), a non-deterministically chosen prefix of the currently running 5 Hz handler is executed, and then the 10 Hz timeout is performed. By choosing a prefix of the handler actions, we are modeling all possible distributions of timing across the actions of the handler. The remaining portion of the handler is left for the state-space exploration algorithm after the 10 Hz timeout, and subsequent 10 hertz processing is performed. The difference between point 2 and point 1 (i.e., the worst-case execution time of the handler remaining time of the 10 Hz frame) is assigned to that remaining portion as its duration. This model can be seen as a refinement of the RT model. It eliminates interleavings when the timing estimates guarantee that a group of highest-priority enabled transitions are guaranteed to complete before the next timeout. In the example in Figure 10, if the right-most three light-grey circles correspond to a
Model-Checking Middleware-Based Event-Driven Real-Time
177
5 Hz component handler body whose worst-case execution bound is less than the time to the next 10 Hz timeout, then there would be no branching in that portion of the state space (i.e., the lower two left outgoing arcs to 10 Hz timeouts are eliminated).
6
Experimental Results
Table 1 shows the results of evaluating our strategies using four example systems provided by Boeing engineers. As an example of how to read a system description, the ModalSP scenario that we have used as an example has three threads (for rate groups 1 Hz, 5 Hz, and 20 Hz), 8 components, an event correlation (e/c), and 125 events being generated per one second hyper-period (hp). For each scenario, we give data for five models that incorporate the modeling strategies presented in the previous section. – (R) is the reference model. There is no scheduling policy for the thread groups in the scenario (it is priority unaware and has no intra-rate-group timing constraints). Since a completely interleaved execution is infeasible to check, the relative time constraints are used though. – (RT-1) uses two policies: priority aware scheduling and the relative time environment where we implement the no frame overruns strategy for the highest-priority thread only. – (RT-2) is like (RT-1), but also assumes there are no frame overruns for all threads. – (LT) is like (RT-2) but uses the lazy time environment model. For each example, we collect the number of transitions trans, states, time, and memory consumption mem at the end of the search. The numbers of transitions and states are both listed because some of steps in the model are marked as invisible (atomic) for which Bogor will not save the states. The experiments were run on a Pentium 4 2.53 GHz with 1.5Gb RAM using the Java 2 Platform. Bogor’s collapse compression[17] and heap symmetry [18] and process symmetry [2] reductions are used in all of the experiments. Each of the experiments represents a complete exploration of the state-space of the system. From the table, the state space generally decreases from model (R), (RT-1), (RT-2), to (LT). This shows that by incorporating more knowledge (e.g., the scheduling policy) of the model that is being checked, less states need to be explored. For example, Medium, the largest scenario that we have, cannot be model checked using Bogor or our previous dSpin implementation [14] without employing the reduction strategies used in (RT-2) and (LT). For Basic the states are the same for model (RT-1) and (RT-2) because it only has a single thread (thus, there is no interleaving). Model (R) has a larger number of states because the lack of constraints allows the timeout to occur even when events associated with the current frame are still being dispatched. Model (LT) has two more states than (RT-2) due to the overhead introduced by the timing transitions. Bogor runs out of memory checking ModalSP (R) (at 3 million states) and Medium (RT-1) (at 13 million states). It is interesting that the states for ModalSP
178
X. Deng et al. Table 1. Experiment Data. Example System Basic Scenario Threads: 20Hz Components: 3 Events: 2 per .05sec hp Multi-Rate Scenario Threads: 20Hz, 40Hz Components: 6 Events: 6 per .05sec hp ModalSP Scenario Threads: 1Hz, 5Hz, 20Hz Components: 8 (e/c) Events: 125 per 1sec hp Medium Scenario Threads: 1Hz, 20Hz Components: 50 Events: 820 per 1sec hp
(R) trans 111 states 20 time .16 sec mem .51Mb trans 1.36M states .12M time 5 min mem 16Mb trans o.m. states 3M+ time o.m. mem o.m. trans o.m. states — time o.m. mem o.m.
(RT-1) 42 12 .11 sec .5Mb 7.5K 1.5K 1.9 sec .77Mb .92M 20.9K 20 sec 4.1Mb o.m. 13M+ o.m. o.m.
(RT-2) 42 12 .09 sec .5Mb .98K .1K .38 sec .61Mb 38.2K 9.1K 8.59 sec 1.61Mb 3.79M .74M 29 min 71.8 Mb
(LT) 44 14 .11 sec .51Mb .15K 33 .19 sec .61Mb 6.27K 1.56K 2.11 sec 1.45Mb .36M 74.5K 3 min 21.5Mb
(R) require more memory than the states for Medium (RT-1). This is an effect of the collapse compression that is used. Specifically, there are three threads in ModalSP (R), but only two threads in Medium (RT-1). In addition, ModalSP (R), which has fewer scheduling constraints, allows more interleaving than Medium (RT-1). Thus, the collapse compression can save more in Medium (RT-1) than ModalSP (R), because there are more similar state bit patterns in Medium (RT-1) than in ModalSP (R).
7
Related Work
Garlan and Khersonsky [11] describe an approach for checking publish-subscribe systems (which they refer to as implicit invocation systems) using SMV. We build on their key insights of factoring system models into two parts: (1) a reusable model of run-time event-delivery infrastructure, and (2) application dependent, user-specified component models. However, we support much more directly the forms of component structure and connections (i.e., CCM structures and object references) and event-delivery mechanisms (i.e., RT CORBA middleware) found in real systems. This advance is achieved by leveraging Bogor’s direct modeling of OO concepts (as compared to the SMV input language which provides very little support for modeling programming language features) and Bogor’s extension mechanism (which allows complex middleware behavior to be captured internally to the model-checker). In addition, [11] does not provide any performance data, nor does that work consider any state-space reductions based on priorities, scheduling, or timing constraints that seem critical for scaling to realistic applications.
Model-Checking Middleware-Based Event-Driven Real-Time
179
There has been a large body of work on timing and schedulability analysis for component-based systems (see also [12] in this volume). As these techniques have matured, they have been integrated into environments that support the development of real-time systems. For example, MetaH [25] and Geodesic [6] are frameworks that support the reuse of components written in Ada and Java, respectively, in real-time systems. These frameworks include a range of timing analyses and automatically generate infrastructure code that coordinates the execution of component code in a way that achieves the system’s timing requirements. Cadena is complementary to this work in that it targets logical properties of a system using both light-weight and heavy-weight analysis techniques. Ptolemy [20] is a framework that allows a wide variety of formal descriptions of components and their behavior to be integrated into a single system. User’s provide sufficient detail in these descriptions to allow implementations to be automatically generated. Ptolemy provides a run-time infra-structure to mediate between components that have different execution models. In contrast, Cadena models intentionally leave out detail in order to provide more abstract system descriptions that are amenable to analysis for large systems. While Cadena provides some code generation capabilities, we do attempt to generate component method implementations. Model checking [4] has become extremely popular as a technology for analyzing behavioral models of software artifacts. Researchers have extracted such models from source code (e.g., [15,5]), UML design artifacts (e.g., [21,19]) and architectural descriptions (e.g., [1]). The difficulty with all applications of model checking is scaling it up to apply to realistically large and complex systems. Recent years have seen an enormous amount of research on the systematic abstraction of models to enable more tractable reasoning. We take a different approach in Cadena by exploiting the natural abstractions that arise when developing high-level design models of systems.
8
Conclusions
We believe the idea of a flexible model-checking framework that allows domainspecific extensions (such as the ones that we have used for encoding models of CORBA communication layers) can be a very effective approach for modelchecking modern distributed system designs and implementations. We are currently working with Boeing engineers to incorporate other forms of domain information (e.g., common specification idioms) and other forms of light-weight checking (e.g., interface protocol checking, refinement checking) and static analysis into Cadena.
Acknowledgements Thanks to various members of the Boeing Bold Stroke team including David Sharp, Carol Sanders, Wendy Roll, and Dennis Noll for their comments on the work described in this paper.
180
X. Deng et al.
References 1. R. Allen and D. Garlan. A formal basis for architectural connection. ACM Transactions on Software Engineering and Methodology, July 1997. 2. D. Bosnacki, D. Dams, and L. Holenderski. Symmetric spin. In International Journal on Software Tools for Technology Transfer. Springer-Verlag, 2002. 3. G. Brat, K. Havelund, S. Park, and W. Visser. Java PathFinder – a second generation of a Java model-checker. In Proceedings of the Workshop on Advances in Verification, July 2000. 4. E. Clarke, O. Grumberg, and D. Peled. Model Checking. MIT Press, 2000. 5. J. C. Corbett, M. B. Dwyer, J. Hatcliff, S. Laubach, C. S. P˘ as˘ areanu, Robby, and H. Zheng. Bandera : Extracting finite-state models from Java source code. In Proceedings of the 22nd International Conference on Software Engineering, June 2000. 6. D. de Niz and R. Rajkumar. Geodesic - a reusable component framework for embedded real-time systems. Technical report, Carnegie Mellon University, 2002. 7. C. Demartini, R. Iosif, and R. Sisto. dspin : A dynamic extension of SPIN. In Theoretical and Applied Aspects of SPIN Model Checking (LNCS 1680), Sept. 1999. 8. W. Deng, M. Dwyer, J. Hatcliff, G. Jung, Robby, and G. Singh. Model-checking middleware-based event-driven real-time embedded software (extended version). Forthcoming – April 2003. 9. B. Doerr and D. Sharp. Freeing product line architectures from execution dependencies. In Proceedings of the Software Technology Conference, May 1999. 10. Eclipse Consortium. Eclipse website. http://www.eclipse.org, 2001. 11. D. Garlan and S. Khersonsky. Model checking implicit-invocation systems. In Proceedings of the 10th International Workshop on Software Specification and Design, Nov. 2000. 12. G. Goessler and J. Sifakis. Composition for component-based modeling. In Proceedings of the First International Symposium on Formal Methods for Components and Objects, volume (this volume) of Lecture Notes in Computer Science. Springer, 2002. 13. T. H. Harrison, D. L. Levine, and D. C. Schmidt. The design and performance of a real-time corba event service. In Proceedings of the 1997 ACM SIGPLAN conference on Object-oriented programming systems, languages and applications, pages 184–200. ACM Press, 1997. 14. J. Hatcliff, W. Deng, M. Dwyer, G. Jung, and V. Prasad. Cadena: An integrated development, analysis, and verification environment for component-based systems. In Proceedings of the 25th International Conference on Software Engineering (to appear), 2003. 15. K. Havelund and T. Pressburger. Model checking Java programs using Java PathFinder. International Journal on Software Tools for Technology Transfer, 1999. 16. G. J. Holzmann. The model checker SPIN. IEEE Transactions on Software Engineering, 23(5):279–294, May 1997. 17. G. J. Holzmann. State compression in SPIN: Recursive indexing and compression training runs. In Proceedings of Third International SPIN Workshop, Apr. 1997. 18. R. Iosif. Symmetry reduction criteria for software model checking. In Proceedings of Ninth International SPIN Workshop, volume 2318 of Lecture Notes in Computer Science, pages 22–41. Springer-Verlag, Apr. 2002.
Model-Checking Middleware-Based Event-Driven Real-Time
181
19. D. Latella, I. Majzik, and M. Massink. Automatic verification of a behavioural subset of UML statechart diagrams using the SPIN model-checker. Formal Aspects of Computing, 11(6):637–664, 1999. 20. E. A. Lee. Overview of the ptolemy project. Technical Report UCB/ERL M01/11, University of California, Berkeley, Mar. 2001. 21. J. Lilius and I. P. Paltor. vUML: A tool for verifying UML models. In Proceedings of the 14th IEEE International Conference on Automated Software Engineering, 1999. 22. Robby, M. B. Dwyer, and J. Hatcliff. Bogor: An extensible and highly-modular model checking framework. In Proceedings of the 2003 ACM Symposium on Foundations of Software Engineering (FSE 2003), 2003. 23. Robby, M. B. Dwyer, and J. Hatcliff. Bogor Website. http://www.cis.ksu.edu/bandera/bogor, 2003. 24. H. Sipma. Event correlation: A formal approach. Technical Report Draft, Stanford University, July 2002. 25. S. Vestal. Metah user’s manual. http://www.htc.honeywell.com/metah, 1998.
Equivalent Semantic Models for a Distributed Dataspace Architecture Jozef Hooman1,2 and Jaco van de Pol2 1
University of Nijmegen, Nijmegen, The Netherlands [email protected] http://www.cs.kun.nl/∼hooman/ 2 CWI, Amsterdam, The Netherlands [email protected] http://www.cwi.nl/∼vdpol/
Abstract. The general aim of our work is to support formal reasoning about components on top of the distributed dataspace architecture Splice. To investigate the basic properties of Splice and to support compositional verification, we have defined a denotational semantics for a basic Splice-like language. To increase the confidence in this semantics, also an operational semantics has been defined which is shown to be equivalent to the denotational one using the theorem prover PVS. A verification framework based on the denotational semantics is applied to an example of top-down development and transparent replication.
1
Introduction
The general aim of our work is to support the development of complex applications on top of industrial software architectures by means of formal methods. As a particular example, we consider in this paper components on top of the software architecture Splice [Boa93,BdJ97] which has been devised at Thales Nederland (previously called Hollandse Signaalapparaten). It is used to build large and complex embedded systems such as command and control systems, process control systems, and air traffic management systems. The main goal of Splice is to provide a coordination mechanism between loosely-coupled heterogeneous components. In typical Splice-applications it is essential to deal with large data streams from sensors, such as radars. Hence Splice should support real-time and high-bandwidth distribution of data. Another aim is to support fault-tolerance, e.g., it should be possible to replicate components transparently, i.e. without affecting the overall system behaviour. Splice is data-oriented, with distributed local databases based on keys. It uses the publish-subscribe paradigm to get loosely-coupled data producers and consumers. An important design decision is to have minimal overhead for data management, allowing a fast and cheap implementation that indeed allows huge data streams. For instance, Splice has no standard built-in mechanisms to ensure global consistency or global synchronization. If needed, this can be constructed for particular data types on top of the Splice primitives. Note that this is quite F.S. de Boer et al. (Eds.): FMCO 2002, LNCS 2852, pp. 182–201, 2003. c Springer-Verlag Berlin Heidelberg 2003
Equivalent Semantic Models for a Distributed Dataspace Architecture
183
different from Linda [Gel85] and JavaSpaces [FHA99], which have a central data storage. The latter also has a transaction mechanism to handle distributed access. Our aim is to reason about components of the distributed dataspace architecture Splice in a compositional way. This means that we want to deduce properties of the parallel composition of Splice-components using only the specifications of the externally visible behaviour of these components. Compositionality supports verification of development steps during the development process. Many examples in the literature show that it is convenient to specify components using explicit assumptions about the environment. Concerning Splice, in [HH02] we propose a framework with an explicit assumption about the quality of data streams published by environment and a similar commitment of the component about its produced data. When putting components in parallel, assumptions can be discharged if they are guaranteed by other components. Reasoning with assumption/commitment [MC81] or rely/guarantee [Jon83] pairs, however, easily leads to unsound reasoning. There is a danger of circular reasoning, two components which mutually discharge each others assumptions, leading to incorrect conclusions. Hence it is important to prove the soundness of the verification techniques. Correctness of compositional verification rules is usually based on a denotational semantics which assigns a meaning to compound constructs based on the meaning of its constituents. Earlier work on the verification of Splicesystems [HvdP02] was based on a complex semantics with environment actions and its correctness was not obvious. In this paper we define a denotational semantics for a simple Splice-like language which is more convenient as a basis for compositional reasoning using assumptions about the environment. It is, however, far from trivial that this semantics captures the intuitive understanding of the Splice architecture. Hence, we also provide a more intuitive operational semantics and prove formally that it is equivalent to the denotational one. Moreover, we show by a small example of transparent replication how the denotational framework can be used to support verification. Both versions of the semantics have been formulated in the language of the interactive theorem prover PVS [OSRSC01]. The equivalence result has been checked completely using PVS. Also the example application (transparent replication) has been verified in detail using PVS. Related to our semantic study is earlier work on the semantics of Splice-like languages such as a transition system semantics for a basic language of write and read statements (without query) [BKBdJ98] and a comparison of semantic choices using an operational semantics [BKBdJ98,BKZ99]. In previous work on a denotational semantics for Splice [BHdJ00] the semantics of local storages is not very convenient for compositional verification; it is based on process identifiers and a partial order of read and write events with complex global conditions. New in this paper is an operational semantics that deals with local time stamps and their use for updating local databases. We define an equivalent denotational semantics which includes assumptions about the environment of a
184
J. Hooman and J. van de Pol
application process
application process
...... read
read
write
write local database
local database
......
agent send
agent receive
send
receive
Fig. 1. Splice applications.
component. Moreover, we show that this denotational semantics forms the basis of a formal framework for specifying and verifying Splice applications. This paper is structured as follows. Section 2 contains a brief informal explanation of Splice. In Sect. 3 we present a formal syntax of the Splice primitives considered in this paper. The operational and denotational semantics of this language are defined in Sect. 4 and Sect. 5, respectively. The main outline of the equivalence proof can be found in Sect. 6. A framework for specification and verification is described in Sect. 7 and applied to an example with top-down design and transparent replication in Sect. 8. Finally, Sect. 9 contains a number of concluding remarks.
2
Informal Splice Introduction
The Splice architecture provides a coordination mechanism for concurrent components. Producers and consumers of data are decoupled. They need not know each other, and communicate indirectly via the Splice primitives; basically readand write- operations on a distributed dataspace. This type of anonymous communication between components is strongly related to coordination languages such as Linda [Gel85] and JavaSpaces [FHA99]. These languages, however, have a single shared dataspace, whereas in Splice each component has its own dataspace, see Fig. 1. Communication between components takes place by means of local agents. A data producer writes data records to the other dataspaces via its agent. A data consumer uses its agent to subscribe to the required types of data; only data which matches this subscription is stored. Data items may be delayed and re-ordered and sometimes may even get lost. It is possible to associate certain quality-of-service policies with data delivery and data storage. For instance, for a particular data type, delivery maybe guaranteed (each item is delivered at least once) or best effort (zero or more times). Data storage can be volatile, transient, or persistent.
Equivalent Semantic Models for a Distributed Dataspace Architecture
185
Each data item within Splice has a unique sort, specifying the fields the sort consists of and defining the key fields [BdJ97]. In each local dataspace, at most one data item is present for each key. Basically, a newly received data item overwrites the current item with the same key (if any). To avoid that old data items overwrite newer information (recall that data may be delayed and re-ordered), data records include a time stamp field. A time stamp of a data item is obtained from the local clock of the data producer when the item is published. At the local storage of the consumer, data items are only overwritten if their time stamp is smaller than that of a newly arrived item (with the same key). This overwriting technique reduces memory requirements and allows a decoupling of frequencies between producers and consumers. It also reduces the number of updates to be performed on the dataspace, as not all received records get stored. The timestamps improve the quality of the data stored, as no record can be overwritten by older data. To program components on top of Splice, a Splice API can be called within conventional programming languages such as C and Java. Splice provides, for instance, constructs for retrieving (reading) data from the local dataspace, and for publishing (writing) data. Read actions contain a query on the dataspace, selecting data items that satisfy certain criteria. Data has a life-cycle attribute, such as “read”, “unread”, “new”, and “update”, which may be used for additional filtering.
3
Syntax of a Simple Splice-Like Language
In this section we define the formal syntax of a very simple Splice-like language. We have embedded the basic Splice primitives in a minimal programming language to be able to high-light the essential features and to prove equivalences between various semantic definitions in a formal way. In Sect. 7.1 we show that it is easy to extend the language with, e.g. if-then-else and loop constructs. Lifecycle attributes are not included in the current version, because we detected some problems with the informal definition (as mentioned in Sect. 9). We consider only one sort. Let Data be some data domain, with a set KeyData of key data and a function key: Data → KeyData. Assume a given type LocalT ime to represent values of local clocks (in our PVS representation we choose the natural numbers). The type DataItems of time-stamped data items, consists of records with two fields: dat of type Data and ts of type LocalT ime. A record of type DataItems can be written as (#dat := ..., ts := ...#), following the PVS notation. Hence, for di ∈ DataItems, we have dat(di) ∈ Data and ts(di) ∈ LocalT ime. The function key is extended to DataItems by key(di) = key(dat(di)). Let SV ars be a set of variables ranging over sets of elements from DataItems. A data expression e yields an element from Data (dependent on the current value of the program variables). Henceforth we typically use the following variables ranging over the types mentioned above:
186
– – – – –
J. Hooman and J. van de Pol
d, d0 , d1 , . . . over Data lt, lt0 , lt1 , . . . over LocalT ime dati, dati0 , dati1 , . . . over DataItems diset, diset0 , diset1 , . . . over sets of DataItems x, x0 , x1 , . . . , y, y0 , y1 , . . . over SV ars
A query q ⊆ P(diset) specifies sets of (time-stamped) data items (it may also depend on program variables). A few examples: – q1 = {diset | for all dati ∈ diset: ts(dati) > 100} = 0} – q2 = {diset | for all dati ∈ diset: dat(dati) = ø and diset = x} – q2 = {diset | diset For simplicity, we do not give the syntax of data expressions and queries here. The syntax of our programming language is given in Table 1. Table 1. Syntax Programming Language. Sequential program S ::= Write(e) | Read(x, q) | S1 ; S2 Process
P ::= S | P1 P2
Informally, the statements of this language have the following meaning: – Write(e) publishes the data item with value e (in the current state) and the current time stamp (from the local clock). We model best effort delivery; a data item arrives 0 or more times at each process, where it might be used to update the local storage if there is no current value with the same key which has a larger or equal time stamp. – Read(x, q) assigns to x some set of data items from local storage that satisfies query q (if there are several sets satisfying q, the choice is non-deterministic). For instance, for query q1 above, we assign to x a set of data items from local storage such that each data item has time stamp greater than 100. If there are no such items in local storage, x becomes the empty set. Note that query q3 above does not allow the empty set; then the read statement blocks until the local storage contains a set of items satisfying the query. Hence a read statement may be blocking, depending on the query. – S1 ; S2 : sequential composition of sequential programs S1 and S2 . – P1 P2 : parallel composition of processes. A process is a sequential program or a parallel composition of processes. As a very simple example, consider a few producers and consumers of flight data. Let Data be a record with two fields: flightnr (a string, e.g. KL309) and pos a position in some form, here a natural number for simplicity. The flight number is the key, that is, key(dati) = flightnr(dati). Consider a producer of flight data
Equivalent Semantic Models for a Distributed Dataspace Architecture
187
P1 = Write((#flightnr := KL567, pos := 1#)) ; Write((#flightnr := LU 321, pos := 6#)) ; Write((#flightnr := KL567, pos := 2#)) ; Write((#flightnr := KL567, pos := 3#)) and two consumers: C1 = Read(x1 , true) ; Read(y1 , q1 ) ; Read(z1 , q1 ) C2 = Read(x2 , q1 ) ; Read(y2 , q2 ) whose queries are specified as follows: = ø and for all dati ∈ diset : flightnr(dati) = KL567} q1 = {diset | diset = ø and for all dati ∈ diset : flightnr(dati) = KL567 and q2 = {diset | diset for all dati1 ∈ x2 : ts(dati) > ts(dati1 )} Consider the process P1 C1 C2 and assume there are no other producers of data. Note that the producer does not specify the local time stamp explicitly; this is added implicitly. Recall that the items produced by P1 may arrive at a different order at the consumers, and they may arrive several times. Variable x1 may be empty (if no data item has been delivered yet – note that this read is not blocking) or a set with one or two elements, at most one for each flight number. For instance, it may contain position number 3 for KL567. Variable y1 will be a singleton, since the local storage contains at most one item with flight number KL567 and the second read is blocking (the query requires a non-empty set). If there is a position for KL567 in x1 , then the position in y1 will be greater or equal (lower values are produced earlier, hence have a smaller local clock value, and thus they cannot overwrite greater values). Similarly for z1 , where the position is greater or equal than the one in y1 . It is possible that z1 = y1 . For consumer C2 the second read action requires a newer time stamp, hence we always have y2 = x2 and the position in y2 is at least 2.
4
Operational Semantics
We define an operational semantics for a process S1 ... Sn of the syntax of Sect. 3. where the Si are sequential programs. We first define an operational status of a sequential process (Def. 1) and a configuration (Def. 3) which represents the state of affairs during operational execution of a process. Next computation steps are defined (Def. 5), leading to the operational semantics (Def. 6). Let DataBases be the type consisting of sets of data items with at most one item for each key, i.e. DataBases = {diset ⊆ DataItems | for all dati1 , dati2 ∈ diset: key(dati1 ) = key(dati2 ) → dati1 = dati2 } Definition 1 (Operational Status). An operational status of a sequential process, denoted os, os0 , os1 , .., is a record with three fields, st, clock and db: – st : SV ars → ℘(DataItems), represents the local state, assigning to each variable a set of data items; – clock ∈ LocalT ime, the value of the local clock;
188
J. Hooman and J. van de Pol
– db ∈ DataBases, the local database, a set of data items (at most one for each key) representing local storage. Definition 2 (Variant). The variant of local state st with respect to variable x ∈ SV ars and value diset ⊆ DataItems, denoted diset if y = x st[x := diset], is defined as (st[x := diset])(y) = st(y) if y =x Similarly, the variant of a record r with fields f1 . . . fm is defined by v if fi = f r[f := v](fi ) = =f fi (r) if fi Produced data items are sent to an underlying network. Here this is represented by N , a set of data items, i.e. N ⊆ DataItems. Note that we do not use a multiset, although a particular item might be produced several times. The use of a set is justified by the fact that data items may always be delivered more than once and hence are never deleted from N . Definition 3 (Configuration). The state of affairs of a process S1 ... Sn during execution is represented by a configuration: (S1 , os1 ), ..., (Sn , osn ), N It denotes for each sequential process Si , the status osi and the remaining part Si that still has to be executed, and the current contents N of the network. For convenience, we introduce the empty statement E indicating that the process has terminated. An execution of S1 ... Sn is represented by sequence of configurations C0 −→ C1 −→ C2 −→ ... where C0 = (S1 ; E, os1 ), ..., (Sn ; E, osn ), ø with, for all i, db(osi ) = ø. The idea is that each step in the sequence C0 −→ C1 −→ C2 −→ ... represents the execution of an atomic action by some process i. We define the update of a database. Definition 4 (Update Database). The update of database db using a new database db1 , denoted UpdateDb(db, db1 ) is defined by dati ∈ UpdateDb(db, db1 ) iff – either dati ∈ db and for all dati1 ∈ db1 with key(dati1 ) = key(dati) we have ts(dati1 ) ≤ ts(dati), – or dati ∈ db1 and for all dati0 ∈ db with key(dati0 ) = key(dati) we have ts(dati0 ) < ts(dati). Computation steps are defined formally as follows. Definition 5 (Computation Step). We have a step of process i, i.e., (S1 , os1 ), .., (Si , osi ), .., (Sn , osn ), N −→ (S1 , os1 ), .., (Si , osi ), .., (Sn , osn ), N iff one of the following clauses holds: = E and Si = Si , N = N , st(osi ) = st(osi ), clock(osi ) = (Update) Si clock(osi ), and there exists a database db1 ⊆ N that is used to update
Equivalent Semantic Models for a Distributed Dataspace Architecture
189
db(osi ) such that an element of db1 is added if its key is not yet present and, otherwise, it replaces an element of db(osi ) with the same key if its local time-stamp is strictly greater. Formally, using Def. 4, there exists a database db1 ⊆ N such that db(osi ) = UpdateDb(db(osi ), db1 ). For simplicity, we did not change the local clock (it is not needed), but alternatively we might require clock(osi ) ≥ clock(osi ). Note that the network has not been changed, since data items might be used several times for an update (modeling the fact that an item might be delivered by the network several times). (Write) Si = Write(e) ; Si , st(osi ) = st(osi ), db(osi ) = db(osi ), clock(osi ) > clock(osi ), and N = N ∪ {(v, clock(osi ))} where v is the value of e in the current state. Note that, given a syntax of expressions, it would be easy to define the values of expressions and queries in the current status (see, e.g. [dRdBH+ 01]). (Read) Si = Read(x, q); Si , N = N , db(osi ) = db(osi ), clock(osi ) = clock(osi ), and there exists a set of data items diset ⊆ db(osi ) satisfying query q and such that st(osi ) = st(osi )[x := diset], i.e. assigning diset to x. For two configurations C1 and C2 , define C1 −→k C2 , for k ∈ IN, by C1 −→0 C1 and C1 −→k+1 C2 iff there exists a configuration C such that C1 −→k C and C −→ C2 . Define C1 −→∗ C2 iff there exists a k ∈ IN such that C1 −→k C2 . Typically, the operational semantics yields some abstraction of the execution sequence, depending on what is observable. Here we postulate that only the set of produced data items in the last configuration of an execution sequence is (externally) observable. Definition 6 (Operational Semantics). The operational semantics of a program S1 ... Sn , given an initial operational status os0 , is defined by O(S1 ... Sn )(os0 ) = {N ⊆ DataItems | (S1 ; E, os0 ), .., (Sn ; E, os0 ), ø −→∗ (E, os1 ), .., (E, osn ), N , with db(os0 ) = ø } Thus the operational semantics of a program yields a set of sets of produced data items, where each set of produced data items represents a possible execution of the program. Example 1. Let 0 be the query specifying that the value 0 should be read, similarly for 1. Observe that, for any os0 , O((Read(x, 0) ; Write(1)) (Read(x, 1) ; Write(0)))(os0 ) = ø.
5
Denotational Semantics
We define the denotational semantics of a program, given an initial status, i.e. the state of affairs when execution starts. To support our aim to reason with assumptions about the items produced by the environment, such assumptions are
190
J. Hooman and J. van de Pol
included in the status. The semantics yields a set of statuses, each representing a possible execution of the program. To achieve compositionality and to describe a process in isolation, it is quite common that information has to be added to the status to express relations with the environment explicitly. Here we add, e.g. the set of written data items and the set of items that are assumed to be produced by the environment. Moreover, we need a way to represent causality between the written items. As shown below, this is needed to assign a correct meaning to the program (Read(x, 0); Write(1)) (Read(x, 1); Write(0)). Here this is achieved by the use of conceptual logical clocks that are added to the status of each process. They are updated similarly to Lamport’s logical clocks [Lam78], which ensures that there exists a global, total order on the produced items. Let T ime be the domain of logical clock values, here we use the natural numbers. We add a logical clock value to the data items produced. Type ExtDataItems, with typical variables edi, edi0 , edi1 , . . ., consists of records with two fields: – di of type DataItems, and – tm of type T ime. Field tm represents the logical moment of publication. It can be used to construct a global partial order on the produced data items that reflects causality. Field selector di is extended to remove the logical clock values from a set of extended data items. For a set ediset ⊆ ExtDataItems define di(ediset) = {di(edi) | edi ∈ ediset}. A status, typically denoted by s, s0 , s1 , .., representing the current state of affairs of a program, is a record with six fields. In addition to the three fields of the operational status: – st : SV ars → ℘(DataItems), the local state (values of variables); – clock ∈ LocalT ime, the value of the local clock; – db ∈ DataBases, the local database (a set of data items, unique per key); we have three new fields: – time ∈ T ime, the logical clock, to represent causality; – ownw ⊆ ExtDataItems, the set of extended data items written by the program itself in the past; – envw ⊆ ExtDataItems, the set of extended data items written by the environment of the program; this is an assumption about all items produced (including present and future). Below we define a meaning function M for programs by induction on their structure. The possible behaviour of a program prog, i.e. a set of statuses, is defined by M(prog)(s0 ), where s0 is the initial status at the start of program execution. Note that this includes an assumption about all data items that have been or will be produced by the environment. The semantics will be such that if s ∈ M(prog)(s0 ) then
Equivalent Semantic Models for a Distributed Dataspace Architecture
191
– ownw(s) equals the union of ownw(s0 ) and the items written by prog. – envw(s) = envw(s0 ); the field envw is only used by prog to update its local storage. Although all items are available initially, constraints on logical clocks prevent the use of items “too early”. Next we define M(prog) by induction on the structure of prog. Write. In the semantics of the write statement the published item, extended with the current value of the local clock, is added to the ownw field. The local clock is increased to ensure that subsequent written items get a later time stamp. In a similar way, a logical clock value has been added. M(Write(e))(s0 ) = {s | clock(s) > clock(s0 ), time(s) > time(s0 ), ownw(s) = ownw(s0 ) ∪ {(#di := dati, tm := time(s)#)}, where dati = (#dat := v, ts := clock(s0 )#), with v the value of e in s0 , and s equals s0 for the other fields (st, db and envw) } Read. To define the meaning of a read statement, we first introduce an auxiliary Update function which may update the local database with data items written (by the process itself or by its environment), using UpdateDb of Def. 4. Update(s0 ) = {s | there exists an ediset ⊆ ownw(s0 ) ∪ envw(s0 ) and a database db1 ⊆ di(ediset), such that db(s) = UpdateDb(db(s0 ), db1 ), time(s) >= time(s0 ), for all edi ∈ ediset, we have tm(edi) < time(s), and s equals s0 for the other fields (st, clock, ownw and envw) } Then the read statement Read(x, q) first updates the local storage and next assigns to x a set of data items that satisfies the query q. M(Read(x, q))(s0 ) = {s | exists s1 ∈ Update(s0 ) and diset ⊆ db(s1 ) such that diset satisfies query q and st(s) = st(s1 )[x := diset], and s equals s1 for the other fields (clock, db, time, ownw and envw) } Note that we only represent terminating executions; blocking has not been modeled explicitly. Sequential Composition. Since we only model terminating executions, the meaning of the sequential composition S1 ; S2 is defined by applying the meaning of S2 to any status that results from executing S1 . In Sect. 7.1 we show how this can be extended to deal with non-terminating programs. M(S1 ; S2 )(s0 ) = {s | exists s1 with s1 ∈ M(S1 )(s0 )∧ s ∈ M(S2 )(s1 )} Parallel Composition. To define parallel composition, let init(s0 ) be the condition db(s0 ) = ø ∧ ownw(s0 ) = ø. Moreover, we use s + ediset to add a set
192
J. Hooman and J. van de Pol
ediset ⊆ ExtDataItems to the environment writes of s, i.e. envw(s + ediset) = envw(s) ∪ ediset and all other fields of s remain the same. In the semantics of P1 P2 , starting in initial status s0 , the main observation is that envw(s0 ) contains only the data items produced outside P1 P2 . Hence the semantic function for P1 is applied to s0 where we add the items written by P2 to the environment writes. Similarly for P2 . Then parallel composition is defined as follows: M(P1 P2 )(s0 ) = {s | init(s0 ) and there exist s1 and s2 with s1 ∈ M(P1 )(s0 + ownw(s2 )), s2 ∈ M(P2 )(s0 + ownw(s1 )), ownw(s) = ownw(s1 ) ∪ ownw(s2 ), envw(s) = envw(s0 )} Example 2. Consider again the program of Example 1: (Read(x, 0) ; Write(1)) (Read(x, 1) ; Write(0)) Without using logical clocks, the semantics of parallel composition would allow for this program a status where envw = ø and ownw contains 0 and 1 (each component produces the item required by the other one). This, however, does not correspond to the operational semantics which yields the empty set. In the current version of the semantics, we can indeed show that, for any s0 , M((Read(x, 0) ; Write(1)) (Read(x, 1) ; Write(0)))(s0 ) = ø.
6
Equivalence of Denotational and Operational Semantics
In this section we first define what it means that the operational and the denotational semantics of Sect. 4 and 5, resp., are equivalent. Next we give an outline of how we proved this equivalence formally. Note that equivalence is far from trivial, since there a number of prominent differences: – The operational semantics allows updates of the local database at any point in time, whereas in the denotational semantics we minimized the number of updates to keep verification simple, allowing it only once, immediately before reading items. – The parallel composition of the denotational semantics is defined by a few recursive equations and it is not clear whether this indeed corresponds to operational execution. – The denotational semantics has additional fields in a status and the read statement contains an additional check on logical clock values. – The underlying network is modeled in different ways. Equivalence is based on what is externally observable, i.e. two semantics functions are equivalent if they assign the same observable behaviour to any program. For the denotational semantics, we choose the same notion of observable behaviour as has been used in the operational semantics, namely the set of published data items. For a set D of denotational statuses, define the observations
Equivalent Semantic Models for a Distributed Dataspace Architecture
193
by Obs(D) = {di(ownw(s)) | s ∈ D}. Define for an n-tuple (s1 , . . . , sn ) of statuses Obs(s1 , . . . , sn ) = di(∪i,1≤i≤n ownw(si )), and for a set T of such tuples Obs(T ) = {Obs(s1 , . . . , sn ) | (s1 , . . . , sn ) ∈ T }. To relate the operational and the denotational semantics, we use a function Ext to extend an operational status to a status of the denotational semantics; Ext(os) copies the fields st, clock, and db of os and it sets the fields time to 0 and ownw and envw to ø. This leads to the main theorem. Theorem 1. O(S1 ... Sn )(os) = Obs(M(S1 (S2 (... Sn )...))(Ext(os))) We give an outline of the proof that has been checked completely using the interactive theorem prover PVS. Below we only give the main steps, for instance, ignoring details about initial conditions. The proof uses three intermediate versions of the semantics and corresponding lemma’s: – M which is the same as M except that also the write-statement is preceded by an update action. Lemma 1. Obs(M(S1 (S2 (... Sn )...))(Ext(os))) = Obs(M (S1 (S2 (... Sn )...))(Ext(os))) Note that M and M are defined for the parallel composition of two processes. But we derive a similar formulation for n processes: Lemma 2. Obs(M (S1 (S2 (... Sn )...))(Ext(os))) = Obs({(s1 , . . . , sn ) | init(Ext(os)), envw(Ext(os)) = ø and for all i, 1 ≤ i ≤ n, si ∈ M (Si )(Ext(os)[envw := ∪j=i ownw(sj )]) }) – OD which extends the operational semantics O to the status of the denotational semantics (adding time, ownw and envw). Moreover, the network N is removed. This is achieved by defining the atomic steps of a single sequential process as (S, s) −→ediset (S , s ), where ediset represents the set of items written in the step (a singleton if S starts with a write statement, the empty set otherwise). This also includes update steps, similar to the update inside a read statement of the denotational semantics, so including a condition of the values of logical clocks. Based on this step relation for one process, we have a step of n parallel processes, denoted (S1 , s1 ), ..., (Sn , sn ) −→ (S1 , s1 ), ..., (Sn , sn ), if there = i, Sj = Sj and exists an i with (Si , si ) −→ediset (Si , si ), and for all j sj = sj + ediset. This leads to the following semantics for n processes: OD(S1 ... Sn )(s0 ) = {(s1 , . . . sn ) | init(s0 )∧ (S1 ; E, s0 ), ..., (Sn ; E, s0 ) −→∗ (E, s1 ), ..., (E, sn ) } Lemma 3. O(S1 ... Sn )(os) = Obs(OD(S1 ... Sn )(Ext(os)) – OS which extends the operational semantics of a sequential process to the status of the denotational semantics, using the relation (S, s) −→ediset (S , s ) mentioned above. Lemma 4. OS(S) = M (S), for sequential programs S.
194
J. Hooman and J. van de Pol
Now, by the lemmas 1, 2, 3, and 4, theorem 1 reduces to the following lemma. Lemma 5. Obs(OD(S1 ... Sn )(Ext(os)) = Obs({(s1 , . . . , sn ) | init(Ext(os)), envw(Ext(os)) = ø and for all i, 1 ≤ i ≤ n, si ∈ OS(Si )(Ext(os)[envw := ∪j=i ownw(sj )]) }) Proof. We give the main ideas of the proof, showing that the sets are contained in each other. ⊆ Suppose (s1 , . . . sn ) ∈ OD(S1 ... Sn )(Ext(os)), that is, (S1 ; E, Ext(os)), ..., (Sn ; E, Ext(os)) −→∗ (E, s1 ), ..., (E, sn ). We have proved by induction on the number of steps in the execution sequence that this implies, for all i, 1 ≤ i ≤ n, (Si ; E, Ext(os)[envw := ∪j=i ownw(sj )]) −→ediset1 . . . −→edisetk (E, si ), that is, si ∈ OS(Si )(Ext(os)[envw := ∪j=i ownw(sj )]). ⊇ Assume, for all i, 1 ≤ i ≤ n that si ∈ OS(Si )(Ext(os)[envw := ∪j=i ownw(sj )]). Thus we have an operation execution (Si ; E, Ext(os)[envw := ∪j=i ownw(sj )]) −→ediset1 . . . −→edisetk (E, si ) for each of the sequential processes. We have to show, (S1 ; E, Ext(os)), ..., (Sn ; E, Ext(os)) −→∗ (E, s1 ), ..., (E, sn ), i.e., we have to show that these sequential executions can be merged into a global execution sequence for the parallel program. Basically, this is done by induction on the total number of steps in all sequential executions. The global execution sequence is constructed by selecting for each step the process with the lowest logical time after its next possible step. This construction is far from trivial, since the local, sequential executions start with all available environment writes, whereas in the global execution a process can only use what has been produced up to the current moment. However, the constraints on the logical clocks (that have been included in this extended operational semantics), ensure that only items produced before its current logical time are used. Formally, this is captured by the property that if (S, s+ediset) −→ediset1 (S , s ) (representing a step of a local process) and for all edi ∈ ediset, tm(edi) ≥ time(s ) then (S, s) −→ediset1 (S , s [envw := envw(s)]) (i.e. it can be used in the global sequence). Since we execute the process with the earliest logical time, we can also show that all items produced later cannot have a smaller logical time stamp.
7
Verification Framework
In this section we provide a framework that can be used to specify and verify processes, as shown in Sect. 8. First, in Sect. 7.1, the programming language is extended with a number of useful constructs. Section 7.2 contains the main specification and verification constructs.
Equivalent Semantic Models for a Distributed Dataspace Architecture
195
7.1 Language Extensions To deal with some more interesting examples, the simple programming language of Sect. 3 is extended with an assignment, if-then-else construct, and infinite loops. Accordingly, the denotational semantics of Sect. 5 is extended. Since infinite loops introduce non-terminating computations, we add one field to the status: – term ∈ {true, f alse}: indicates termination of the process; if it is false all subsequent statements are ignored. Henceforth, we assume that s0 is such that term(s0 ) = true, i.e. after s0 we can still execute subsequent statements. The definition of sequential composition has to be adapted, since it is possible that the first process does not terminate and thus prohibits execution of the second process. M(S1 ; S2 )(s0 ) = {s | s ∈ M(S1 )(s0 ) ∧ ¬term(s)}∪ {s | there exists an s1 with s1 ∈ M(S1 )(s0 )∧ term(s1 ) ∧ s ∈ M(S2 )(s1 )} The meaning of the skip statement can be defined easily. M(Skip)(s0 ) = {s0 } Similarly we can easily define x := e where x ∈ Svars and e an expression yielding a set of data items. We also add variables that range over data items and define assignments for such variables. Next we define an if-then-else statement, where b is a boolean expression. M(If b Then S1 Else S2 Fi)(s0 ) = {s | if b is true in st(s0 ) then s ∈ M(S1 )(s0 ) else s ∈ M(S2 )(s0 ) } Finally, we define an infinite loop by means of an infinite sequence of statuses s0 , s1 , s2 , . . ., where si is the result of executing the loop body i times, provided all these executions terminate. Otherwise the term-field of si is false. The written items are collected by taking the union of the produced items in each execution of the body. Note that only the own and environment writes are relevant. M(Do S Od)(s0 ) = {s | there exists a sequence s0 , s1 , s2 , . . . such that for all i, if term(si ) then si+1 ∈ M(S)(si ) else term(si+1 ) = f alse, and ownw(s) = ∪{i|term(si )} ownw(si+1 ) and envw(s) = envw(s0 ) } 7.2
Specification and Verification
To obtain a convenient specification and verification framework, we define a mixed formalism in which one can freely mix programs and specifications, based on earlier work [Hoo94]. Specifications are part of the program syntax; let p, p0 , p1 , . . . , q, q0 , q1 , . . . be assertions, that is, predicates over statuses. A specification is a “program” of the form Spec(p, q) with the following meaning.
196
J. Hooman and J. van de Pol
M(Spec(p, q))(s0 ) = {s | (p(s0 ) implies q(s)) and envw(s) = envw(s0 ) } Next we define a refinement relation ⇒ between programs (which now may include specifications). Definition 7 (Refinement). For any two programs P1 , P2 , we define P1 ⇒ P2 iff for all s0 , we have M(P1 )(s0 ) ⊆ M(P2 )(s0 ). Note that it is easy to prove that the refinement relation is reflexive and transitive. We have the usual consequence rule. Lemma 6 (Consequence). Spec(p, q).
If p → p0 and q0 → q then Spec(p0 , q0 ) ⇒
Based on the denotational semantics for Splice, we checked in PVS the soundness of a number of proof rules for programming constructs. For instance, for sequential composition we have a composition rule and a monotonicity rule which allows refinements in a sequential context. Lemma 7 (Sequential Composition). (Spec(p, r); Spec(r, q)) ⇒ Spec(p, q). Lemma 8 (Monotonicity of Sequential Composition). If P3 ⇒ P1 and P4 ⇒ P2 then (P3 ; P4 ) ⇒ (P1 ; P2 ). The reasoning about parallel composition in PVS mainly uses the semantics directly. We only have a monotonicity rule, which forms the basis of stepwise refinement of components. Lemma 9 (Monotonicity of Parallel Composition). If P3 ⇒ P1 and P4 ⇒ P2 then (P3 P4 ) ⇒ (P1 P2 ).
8
Verification Example
To illustrate our reasoning framework, we first show top-down development of a typical application consisting of a producer, a transformer, and a consumer in Sect. 8.1. Next, in Sect. 8.2, we consider transparent replication. The general question is whether we can replace a single process by two, or more, copies of the same process without having to change the environment. So, given the monotonicity rules mentioned above, we look for sufficient conditions for having P P ⇒ P . We investigate this for the concrete case study developed in Sect. 8.1. 8.1
Top-Down Development
Here we consider a concrete and simple case study, which is prototypical for the application area, with the following processes: – Producer: provides monotonically increasing data (here simply natural numbers) with name SensData.
Equivalent Semantic Models for a Distributed Dataspace Architecture
197
– Transformer: assuming it gets increasing SensData items, it provides monotonically increasing data with name Intern. – Consumer: assuming the environment provides increasing data with name Intern, it produces monotonically increasing Display items. To formalize this, we define the following types and functions: – DataN ame = {SensData, Intern, Display}, with typical variable dn. – DataV al = IN. – Data is a type of records with two fields: name of type DataN ame and val of type DataV al. Let dvar be a variable of type Data. – KeyData = DataN ame and key(dvar) = name(dvar). To formulate the specifications, first a few preliminary definitions are needed, where wset is a set of extended data items: – N ameOwnw(dn)(s) = ∀edi ∈ ownw(s) : name(edi) = dn – SensData(wset) = {edi | edi ∈ wset ∧ name(edi) = SensData} Similarly, we have Intern(wset) and Display(wset). – Increasing(wset) = ∀edi1 ∈ wset, edi2 ∈ wset : (val(edi1) < val(edi2) ↔ ts(edi1) < ts(edi2)) Let pre be an assertion expressing that db = ø, ownw = ø, and all variables ranging over sets of data items are initialized to the empty set. It is used as a precondition for the processes. The top-level specification of the overall system is defined as follows. postT opLevel(s) = envw(s) = ø → Increasing(Display(ownw(s))) T opLevel = Spec(pre, postT opLevel) We implement this top-level specification by the parallel composition of the three processes mentioned above: Producer Transformer Consumer We first specify the processes, without considering their implementation, and show that these specifications lead to the top-level specification. The producer writes an increasing sequence of sensor data. postP rod(s) = N ameOwnw(SensData)(s)∧ Increasing(ownw(s)) P rod = Spec(pre, postP rod) The consumer should produce an increasing sequence of Display data, assuming the environment provides increasing internal values. postCons = N ameOwnw(Display)(s)∧ Increasing(Intern(envw(s))) → Increasing(Display(ownw(s))) Cons = Spec(pre, postCons) To connect producer and consumer, we specify the transformer as follows.
198
J. Hooman and J. van de Pol
postT rans = N ameOwnw(Intern)(s)∧ Increasing(SensData(envw(s))) → Increasing(Intern(ownw(s))) T rans = Spec(pre, postT rans) We have proved in PVS that this leads to a correct refinement of the top-level specification. Theorem 2. (P rod (T rans Cons)) ⇒ T opLevel Next we consider the implementation of the three components. Let d be a variable ranging over Data, whereas dset and dold are variables ranging over sets of data items. P roducer = d := (#name := SensData, val := 0#) ; Do Write(d) ; d := (#name := SensData, val := val(d) + 1#) Od Note that the producer writes all natural numbers, which is not required by the specification. Also note that subscribers to data with name SensData will usually read only a (increasing) subsequence of these items. We have proved in PVS that this is indeed a correct refinement. Lemma 10. P roducer ⇒ P rod Similarly we provide a program for the transformer and show that it is a correct implementation. Let q(dn, old) be the query that specifies a set of data items with name dn and local time stamp different from those in variable old (which is initially empty). The set is allowed to be empty, to avoid blocking computations; otherwise it will be a singleton with a new, unread, item. The item that has been read is transformed using a function T r(dn, dset) which, for simplicity, just changes the name of the record of the item in dset into dn. Transformer = Do Read(dset, q(SensData, old)) ; If dset =ø Then Write(T r(Intern, dset)) ; old := dset Else Skip Fi Od Lemma 11. Transformer ⇒ T rans Similarly for the consumer. For simplicity, we used the same name transformation, which makes it possible to derive the correctness of transformer and consumer from a single proof that was parameterized by the name of the data sort. Consumer = Do Read(dset, q(Intern, old)) ; If dset =ø Then Write(T r(Display, dset)) ; old := dset Else Skip Fi Od Lemma 12. Consumer ⇒ Cons Finally observe that top-level theorem 2 and the lemmas 10, 11, and 12 for the components lead by the monotonicity property (lemma 9) to (P roducer (Transformer Consumer)) ⇒ T opLevel
Equivalent Semantic Models for a Distributed Dataspace Architecture
8.2
199
Transparent Replication
While investigating transparent replication, we observed that the current version of the transformer specification is not suitable. The next lemma expresses that we cannot replicate the transformer in a transparent way. Lemma 13. ¬((T rans T rans) ⇒ T rans) The lemma has been proved by a concrete counter example in PVS. The basic idea is that the two transformers each have increasing output, but - because they may write this output at different moment - the local time stamps in these sequences might be different and hence merging these output streams need not lead to an increasing sequence. The main problem is that the items produced get their local time stamp from the local clock when the item is written. This need not be related to the temporal validity of the data. Hence we propose an alternative specification for the transformer where the local time stamp is just copied from the incoming data item (as we will see later, this also requires a modified write statement). M aintainT s(s) = ∀edi ∈ ownw(s) : ∃edi1 ∈ envw(s) : ts(edi) = ts(edi1 )∧ name(edi1 ) = SensData∧ val(edi) = val(edi1 ) postT ransN ew = N ameOwnw(Intern) ∧ M aintainT s T ransN ew = Spec(pre, postT ransN ew) This indeed refines the transformer specification: Lemma 14. T ransN ew ⇒ T rans Moreover, this specification can indeed be replicated. Lemma 15 (Transformer Replication). (T ransN ew T ransN ew) ⇒ T ransN ew Hence we have (by theorem 2, lemma 14 and monotonicity): (P rod (T ransN ew Cons)) ⇒ T opLevel and by lemma 15 and monotonicity: (P rod ((T ransN ew T ransN ew) Cons)) ⇒ T opLevel It remains to implement T ransN ew. Important part of this specification is that it just copies the local time stamp (the ts-field). This, however, cannot be implemented with the current write statement, since it always use the current value of the local clock as its time stamp (the ts field is set to clock(s0 )). Therefore we introduce a new write statement Write(e, texp) which has an additional parameter, a time expression texp, which specifies the ts value, i.e. in the semantics of this extended write statement the ts-field in the data item gets the value of texp. Query Qtrans specifies a set of data items that is either empty or a singleton containing an item with name SensData. Expression MkIntern(