Abstract:
A computer and software method and apparatus for distributed data processing which provides agreement between data sources (sensors) and data sinks (actuators) as to what data has been written into a shared buffer. The invention further provides methods and means for meeting data timeliness requirements. Invention employs a programming primitive which recognizes semantics so as to provide a consistent view of computation modules over prescribed time intervals, called “epochs”. Application-level control of the asynchrony and timing of information flow between various computation modules is realized. The invention has applications which include sensor fusion and network gaming.

Description:
PRIORITY CLAIM UNDER 35 U.S.C. §119(e) 
     This patent application claims the priority benefit of the filing date of provisional application Ser. No. 60/629,824, having been filed in the United States Patent and Trademark Office on Nov. 19, 2004 and now incorporated by reference herein. 
    
    
     STATEMENT OF GOVERNMENT INTEREST 
     The invention described herein may be manufactured and used by or for the Government for governmental purposes without the payment of any royalty thereon. 
    
    
     BACKGROUND OF THE INVENTION 
     This invention relates generally to distributed real-time information systems in which the data generated by source modules have timeliness constraints for dissemination by sink modules. 
     Generally, an embedded system consists of a distributed real-time computation that collects data from the external environment and processes this data to reason about the system behavior [1]. An example is the deployment of radar devices in battle terrains to detect the movement of enemy planes. An application thus involves the processing of time-sensitive data flowing from source modules (see  11 ,  FIG. 1 ) to sink modules (see  12 ,  FIG. 1 ), thereby requiring programming-level support to enable a timely processing of data. 
     The asynchronous execution of data sources and sinks is compounded by the lack of physical shared memory between them (i.e., these modules may be distributed over a network). Given this computation structure, the movement of data to a shared or common buffer (see  13 ,  FIG. 1 ) over the intervening network should satisfy certain correctness requirements, as follows:
         1. The source and sink modules should agree on what data items have been written into the remote buffer at a given point in time for processing;   2. The data generated by a source should be processed by the sinks in a timely manner (i.e., before the data deadline, as prescribed by Δ, expires).
 
Enforcing the requirements 1 and 2 above allows a consistent view of the processing of data across the various source and sink modules, thereby allowing them to be in step with one another about the flow of application-level computation. From a programming standpoint, the buffer interposed between the sources and sinks to hold data is abstracted as a (logically) shared buffer on which read and write operations occur (see  13 ,  FIG. 1 ). These operations satisfy some form of atomicity property as part of their semantics. For use in real-time settings, the semantics of read and write should be extended to capture the ‘passage of time’ in the application. The atomicity augmented with the timing property enforces the required consistency of state in the application-level computation.
       

     The programming-level enforcement of timing and consistency has become a necessity in the evolving application domains of distributed multimedia systems and real-time embedded systems. The prior art provides atomicity of data access operations on a shared buffer only in a ‘logical time’ framework where the ordering of operations define the forward progress of the underlying computation without any relationship to the time elapsed for these operations. This notion of logical time is, however, difficult to adapt to real-time embedded systems which have their data access operations originate from and culminate on physical systems that form the external environment of the computation subsystems. Therefore, there is a pressing need for programming primitives that accommodate the ‘passage of time’ as part of the semantics of data access operations. 
     REFERENCES 
     
         
         [1] H. Kopetz and P. Verissmo.  Real - time Dependability Concepts , Chapter 16, in Distributed Systems, Ed. S. Mullender, Addison-Wesley Publ., 1993. 
         [2] A. Singh. Atomic Registers:  Theory and Implementation, in ACM Transactions on Programming Languages and System,  1993. 
         [3] M. Singhal and N. Sivaratri.  Distributed Transactions , Chapter in  Distributed Operating Systems , McGraw-Hill Publ., 1993. 
         [4] K. Birman and et al. ISIS/Horus Distributed System, Cornell University Technical Report, 1997. 
         [5] L. Peterson and et al. x-Kernel system University of Arizona Technical Report, 1995. 
         [6] J. P. Courtiat, L. Fernando, Rust da Costa Carmo, Roberto Cruz de Oliveira. General-purpose Multimedia Synchronization Mechanism based on Causal Relations. IEEE Journal of Selected Areas in Communications, vol. 14, pp. 185-195, January 1996. 
         [7] R. Baldoni, R. Prakash, M. Raynal, M. Singhal. Efficient Δ-Causal Broadcasting. International Journal of Computer Systems Science and Engineering, 1998. 
         [8] S. L. Presti, D. Bert, A. Duda. Tao: Temporal Algebraic Operators for Modeling Multimedia Presentations, Journal of Network and Computer Applications (Elsevier Science Ltd.), vol. 25, pp. 319-342, 2002. 
         [9] K. Ravindran. Transport-oriented Service Models for Multimedia Data Presentation, proc. SPECTS&#39;00, Vancouver (Canada), July 2000. 
       
    
     OBJECTS AND SUMMARY OF THE INVENTION 
     The present invention provides a programming primitive that embodies both the atomicity and timing properties of data access operations on a shared buffer and is referred to as ‘timed atomic write’ (TAW). 
     The time interval over which a set of time-dependent data items can be processed by the sources and sinks in an application constitutes an epoch. During an epoch, one or more sources write their data items in the buffer as an unordered set, and thereupon, the sinks process various data items from the buffer as determined by the application needs. The reaching of agreement between the various modules as to which data items are processed in a given time interval is subsumed into the notion of epoch. The present invention&#39;s TAW primitive allows a programmer to prescribe epochs by stipulating an application-specific timing condition on the data items processed through a shared buffer. It is the responsibility of an application to enforce state consistency across the various modules by exercising a temporal ordering on the epochs. Thus, the TAW primitive enables integrating the ‘passage of real-time’ and ‘state consistency’ in an application program through a prescription of epochs. 
     The TAW primitive is different from ‘atomic registers’ [2] in that the latter enforces an agreement not only on the set of data items but also on the order in which they will be written into the buffer. With TAW, the application needs to enforce an ordering of data items only to the extent required. Comparing with ‘distributed transactions’ [3], the latter often determines a serializable schedule on the set of writes on the buffer, which may not be consistent with the application&#39;s expected ordering (and hence requires a re-ordering of data items at the application level). With TAW provided by the present invention, however, an application implements its own ordering of data items in the buffer to the extent desired. This entails a higher potential for execution performance of applications. Thus, the TAW may be viewed as providing a thin layer of functionality (i.e., a weaker semantics) as part of the distributed programming abstraction, in comparison with existing works that (implicitly) advocate a thick layer of functionality (i.e., a stronger semantics) with the attendant performance penalty. 
     Furthermore, unlike the TAW primitive, the prior art works [2,3] do not consider the ‘passage of time’ as part of an application state. So, a potential use of the existing primitives for embedded systems programming requires a separate sub-layer of functionality to integrate ‘time’ as part of the read-write semantics, thereby entailing inflexibility and complexity in application-level programming. 
     Thus, the TAW primitive of the present invention, with its explicit application-level control of the asynchrony and timing of information flow between various application modules is highly desirable. The architectural differences in the programming structures that employ the TAW primitive, relative to the existing primitives, are a part of the invention. This present invention provides the structure and semantics of the TAW primitive, and the application-level programming structures using the TAW primitive. 
     It is therefore an object of the present invention to provide a method and apparatus for agreement on common data and its availability in distributed systems. 
     It is a further object of the present invention to provide programming primitives which utilize systems semantics in distributive data processing so as to provide a consistent view of common data. 
     It is still a further object of the present invention to extract parallelism among tasks in distributed system so as to provide for agreement between sensors and acuators about shared data availability and process timelines. 
     Briefly stated, the present invention achieves these and other objects through a computer and software method and apparatus for distributed data processing which provides agreement between data sources (sensors) and data sinks (actuators) as to what data has been written into a shared buffer. The invention further provides methods and means for meeting data timeliness requirements. Invention employs a programming primitive which recognizes semantics so as to provide a consistent view of computation modules over prescribed time intervals, called “epochs”. Application-level control of the asynchrony and timing of information flow between various computation modules is realized. The invention has applications which include sensor fusion and network gaming. 
     The above, and other objects, features and advantages of the present invention will become apparent from the following description read in conjunction with the accompanying drawings, in which like reference numerals designate the same elements. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  is a graphical representation of typical operations in real-time embedded systems. 
         FIG. 2  is a projection of a sample functional embedded system onto its computational realization in a typical distributed programming implementation. 
         FIG. 3  is a graphical representation of data and timing parameters of a TAW primitive in the present invention. 
         FIG. 4  is a graphical representation of a sample timing scenario of task scheduling employing a TAW of the present invention. 
         FIG. 5  is a graphical representation of prior art sample timing scenario of task scheduling without any data synchronization such as would be provided by the present invention. 
         FIG. 6  is a representation of timing scenario to show TAW benefits of the present invention over a prior art ordered write. 
         FIG. 7  is a graphical representation of monolithically structured prior art ordered write program for a sample application. 
         FIG. 8  is a graphical representation of a timing scenario to show the present invention&#39;s TAW benefits versus a prior art ordered write with monolithic program structures. 
         FIG. 9  is a table summarizing the benefits of present invention&#39;s TAW over a prior art ordered write. 
         FIG. 10  depicts a flowchart of the process steps performed by the write_buf and read_buf programming primitives employed by the present invention&#39;s TAW. 
     
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT 
     In the present invention, the spontaneity in the arrival of input data for a distributed task, the timeliness of generation of results by the task, and therefore the overall system performance, is inextricable from the parallelism in computing these results. Since each sensor (see  11 ,  FIG. 1 ) constitutes a distinct unit of data collection for input to the task, the extraction of parallelism in the flow of data through various subsystems implementing the task should be at the data semantics level. The relevant semantics pertaining to a sensor data item x (see  FIG. 2 ) basically involves identifying the task execution points when x is needed relative to the processing of other data items or the partial results generated therefrom. Such an ordered execution of sub-tasks to process various sensor data items constitutes the processing pipeline associated with the main task. 
     System Model 
     Referring to  FIG. 2 , u 1 , u 2 , uN are the source processes  27  collecting data from the external environment for input to the application task through the shared data buffer  29 . The sink processes  28  represented by v 1 , v 2 , . . . , vM disseminate the results output by the application task onto the external environment (note that N, M≧1). The application task is itself built into computation processes  8 ,  9 ,  10  represented by fx, fy, . . . , fz that are interposed between the sources  27  and sinks  28 . In a given time interval [Ti, Ti+1], a set of sources W generate requests to write into the shared buffer. The processes attempting a write are drawn from a set W′ declared as eligible to write during [Ti, Ti+1], i.e., W ⊂ W′ ⊂  {u 1 , u 2 , . . . , uN}. The set of sources W″ whose data are actually written into the buffer is then selected from W′, i.e., W″ ⊂ W′. The accesses to the shared buffer containing the data items W″ are realized through ‘read’ and ‘write’ operations exercised in an asynchronous manner. 
     The computation modules may be either part of the source  27  and/or sink  28  modules or realized on separate nodes of a multi-processor/distributed system. The present invention relies upon the various modules having access to a synchronized real-time clock, at a sufficient level of time granularity (for use by the protocols underlying a TAW realization). 
     The application task comprises sensors u 1 , u 2 , u 3  generating data d 1 , d 2 , d 3 , respectively  21 ,  22 ,  23 , and further comprising a computation subsystem of processes implementing sub-tasks fx, fy, fz,  8 ,  9 ,  10  and actuators v 1 , v 2  taking actions on the environment. The use of such an application scenario to simplify the discussions does not however compromise the generality of our model to a case of arbitrary number of sensors and actuators and an arbitrary set of computation modules. 
     ‘Dataflow’-Style Programming for Real-Time Tasks 
     Still referring to  FIG. 2 , an exemplary programming structure for the present invention is depicted. The interconnections of the various modules depict the ‘functional dependency’ relationships between them, specifically, the arrow  25  from fx  8  to fz  10  indicates the dependency that fz needs its input data from fx before its computation can start. The module fz starts executing as soon as the inputs  25 ,  26 ,  22  from fx and fy and the sensor module u 2 , respectively, are available. In turn, the output of fz,  7  in conjunction with the output of fy  26 , triggers the execution of actuator module vb. Such a ‘dataflow’-style program structuring enhances the parallelism in task execution. The input-output relationships of various modules are as shown in the Figure. 
     In a distributed programming-level implementation, fx and fy are part of the sensor modules u 1  and u 3  respectively  27  and fz is a part of the actuator module vb  28 . The computations fx  8  and fy  9  execute in parallel if the data d 1   21  and d 3   23  are available, providing their results in a shared buffer  29  for use by fz  25 ,  26 . Since fz also needs the input data d 2   22  from u 2 , the ordering on {d 1 , d 2 , d 3 } may be prescribed as: ∥{d 1 , d 3 }→d 2 . This ordering is enforced by the computation structure with the use of TAW primitive, as opposed to enforcing the ordering by the communication layer in alternative programming models. 
     Extraction of Fine-Grained Parallelism 
     Any application run on the present invention occurs within the context of the input-output relationships between the results produced at various intermediate stages of computation on the input data. The computation may be partitioned into sub-tasks that synchronize their results at appropriate points in the computation. A task dependency graph (TSG) functions as a task scheduler  20  tracks the fine-grained parallelism between various computation modules. The task scheduler  20  ensures the prescribed real-time task deadlines are met. This is functionally possible because of the predictability of execution times of various sub-tasks and the well-defined interconnect structure between them to move the intermediate computation results (note that the task dependency relations form a part of the global knowledge at various computation modules). This parallelism among various sub-tasks itself falls under the realm of application-level programming. 
     To enable the software construction of such a task “pipeline”, the present invention requires a communication primitive with a proper level of abstraction. Such a primitive enables complete utilization of the available parallelism among sub-tasks, but should not in any way limit the programmer&#39;s ability to structure these sub-tasks. TAW primitive in the present invention is an enabler for such application-level program constructions. 
     Structure and Semantics of TAW Primitive 
     The TAW primitive basically allows writing an unordered set of data items W″ into the shared buffer  29 . The various sub-tasks embodied in an application program take the required data items from this buffer for processing. The TAW primitive embodies functional requirements to deal with two inter-woven issues that are relevant to the application-level processing of sensor data in a distributed embedded system, these requirements being:
         1. Agreement among the sensor and actuator modules as to what data items have been written into the shared buffer (i.e., the modules are provided with a consistent view of what the constituents of W″ are);   2. Prescription of the time budget available to process the sensor data items (it allows determining the duration of time interval [Ti, Ti+1]).
 
The functional requirement 1 is required to deal with the spontaneity in data writes by various sources. Here, spontaneity means that the attempt to write by a source process uj ε W does not have a bearing on that of the other (eligible) sources W-uj. The ensuing concurrency in data collection and/or processing by the sensor and actuator modules, compounded by their potentially distributed realization, needs to be dealt with by a multi-process protocol that is executed by the various modules to reach agreement.
       

     The functional requirement 2 allows determining whether the time required to process various input data items for generating the composite output results meets prescribed deadlines. Often, a data d written into the buffer has real-time constraints Δ(d) for dissemination, i.e., a time limit Δ(d) before which d should be acted upon. The task scheduler  20 , which may itself be distributed in the various computation modules, makes this determination based on the sub-task execution times and interconnect structure. 
     The present invention&#39;s TAW primitive combined with functional requirements 1 and 2 provide the ability to extract the parallelism among various sub-tasks involved in processing input data and output results. 
     Programming Model of TAW: Timing Spec 
     Referring now to  FIG. 3 , the temporal axis consists of a sequence of epochs e(0), e(1), . . . , e(j), . . . , where an epoch e(j) encompasses the write requests generated by one or more sources and their processing over a distinct time interval [Ti, Ti+1]. The duration of e(j) is given by:
 
 Ti+ 1 −Ti &gt;ε+β+max({ζ k }),  k= 1, . . . ,  M  
 
where ε  30  depicts the time window during which write requests are generated, β  33  is the time needed to process the data generated by the computation sub-system, and ζk denotes the persistence time of action triggered by vk  38 .
 
     By way of example, consider a temperature control system for a boiler plant that consists of multiple sensors and valves located at different points in the boiler to collect temperature data and to inject coolant liquids respectively. Here, an epoch depicts the time interval for sampling and processing of temperature data where ε is the maximum time skew allowed between the samples of various sensors in a given interval, β depicts the time to process temperature data, and ζ is the time to open (or close) the coolant valves. 
     The ‘passage of time’ in an application may be captured by the ε and ζ parameters, with ζ viewed as a non-deterministic time duration to model the transition from a current epoch e(j) to the next epoch e(j+1), where ε, ζ&gt;&gt;β. 
     Programming Model of TAW: Distributed Agreement 
     Still referring to  FIG. 3 , the ‘write’ semantics requires that various processes agree on the set of data items W″ actually written into the buffer (a source can write no more than one data item in a given time interval). The sink processes then generate actions based on processing the agreed datum. W″={d 1 , d 3 }  31 . 
     A situation may arise where a programming primitive that guarantees agreement (on W″) among various modules as part of the read/write semantics is not provided. In the absence of a consistent global knowledge as to what W″ is, it is difficult (if not impossible) for the scheduler to precisely determine the actual dependency relations that are satisfied. Consequently, a specific instantiation of the task dependency relations for the writes that are deemed to have occurred, cannot be inferred. This in turn makes it difficult for the task scheduler  20  to determine if the real-time constraints of the task on hand can be met. 
     The semantics of presenting an unordered set of data items that is consistent across the various computational processes {p 1 , p 2 , . . . , pN} enables a ‘data-driven’ computation in which each process picks up the data items that it needs to accomplish its part of the application-level computation  35 ,  36  and then produce results to synchronize with that produced by the other processes  37 . With data arrivals occurring asynchronously, the non-imposition of any ordering among the data by the communication layer allows the computation modules to start executing as soon as their required input data are committed in the buffer  31 . This in turn allows the present invention to benefit from the fine-grained parallelism in the computation, and accordingly enhance the ability to meet real-time deadlines of data. 
     Program Notations for TAW 
     A process p housing a sensor ui may invoke a write_buf primitive after its data di becomes available for processing, in the form:
 
 wrtset :=write —   buf ( di,E,grp,e ),
 
where wrtset is the set of successful writes on the buffer in the current epoch e and grp is the broadcast group address to which the process p is subscribed to. Here, 1≦|wrtset|≦nwrt≦|W′|, where nwrt is the application-specified maximum number of processes that are allowed to write in the current epoch. The parameter nwrt is made available to the communication layer as part of a control entity in the application program that manages the flow of epochs in the computation. Each element xε wrtset has 2 fields: x.dt and x.id, denoting the data written in the buffer and the id of process who wrote this data respectively. The case of ui ε wrtset. {id}indicates that the write of ui successfully completed at the buffer, i.e., committed; ui ∉wrtset. {id} indicates otherwise. A process p′ housing an actuator vk and subscribed to the group address grp may examine the buffer contents by invoking a primitive of the form:
 
 wrtset :=read —   buf ( grp,e ).
 
The invocation blocks vk until all the writes selected by the communication layer for the epoch e complete.
 
     The ε-parameter provides a time-window over which the competing write requests are collected by the communication layer. The collection takes place until the time-window expires or nwrt requests are collected, whichever occurs earlier. The wrtset contains the set of data items in the shared buffer, as agreed upon by all the processes subscribed to the group address grp. 
     Benefits of TAW Over Non-Synchronized Data Writes 
     Referring to  FIG. 4 , the TSG is implemented in a decentralized manner in various processes. The TSG information, combined with an agreement among processes about the data being committed in the current epoch, allows each process in the computation subsystem to have a consistent view of which of the task input requirements have been met. Given that a process P implementing a sub-task is often equipped with recovery procedures to deal with the absence of a data d at its input, P can determine its output that is consistent with the outputs of other processes that also depend on d. The consistency can be achieved without a need for P to coordinate with the other processes about whether they saw d or otherwise. Such a consistent view of processes about the TSG relative to the actual data inputs in the current epoch  45  enhances the ability of processes to determine their local computation schedules relative to the overall task deadline. 
     Still referring to  FIG. 4 , a timing scenario depicts the asynchronous arrival of d 1 , d 2 , d 3 , with the arrival of d 2  delayed past the initial ε-window at fz, due, for example, to source-level timing errors  41 . With a non-commit of d 2 , the present invention consistently decides that actuator vb triggers its action but actuator va does not  42 , 43 . This consistent enforcement of timing and recovery procedures by sinks va and vb. 
     Referring to  FIG. 5 , a prior art scenario is depicted where no agreement is reached on the non-commit of d 2 ,  51  because unlike the present invention, no TAW-like primitive is available to the programmer. Here, d 2  is seen by va but not by vb  53 ,  54  Accordingly, the scheduler at va determines that both va and vb trigger their actions but the scheduler at vb determines that only vb triggers its action but va does not. Since the schedulers at va and vb need to coordinate with each other to determine what exactly they saw at the buffer, it is difficult to decide on the consistency and timing of their actions. 
     Benefits of TAW Over ‘Ordered Data Writes’ 
     The present invention can achieve agreement on the set of data written into the shared buffer by using programming primitives that order the data writes on the buffer over time. The temporal ordering is based on application-level prescription of the causal dependency relation among the data messages, combined with timing constraints. Referring back to  FIG. 2 , the causal dependency relation is: ∥{d 1 , d 3 }→d 2 . The temporal ordering may be transcribed onto the communication layer using ‘vector clocks’ [4] or ‘message dependency graphs’ [5] and incorporating timing constraints therein using the specification techniques described in [6,7,8,9]. But, having the communication layer order the data writes is an overkill in terms of timeliness and performance of data delivery, in comparison to the application layer synchronizing the data to the extent required. This is because an ordering imposed by the communication layer is indifferent to the asynchrony in data arrivals and/or the process computation times on dependent data. Therefore, an ordered write needs to stipulate a temporal constraint based on a worst-case data arrival pattern and a conservative estimate of the process computation times. Consequently, the use of ordered write primitive may incur an additional synchronization delay in many cases, with an ordered write of data equaling the performance of TAW only in the limiting case. 
     Case of ‘Dataflow’-Structured Programs 
     Referring to  FIG. 6 , a timing scenario of the data arrivals and processing in the sample computation structure depicts the benefits of the present inventions TAW over prior art ordered write. The temporal constraint passed on from the application to the communication layer for an ordered write of d 2  relative to d 1  and d 3  is:
 
α&gt;max({ Tcmp ( fx ), Tcmp ( fy )}),
 
where Tcmp( . . . ) denotes the computation time of a sub-task  62 . The communication layer delivers d 2  after a time of a has elapsed since the delivery of d 1  and d 3   63 ,  68 . In comparison, the TAW primitive in the present invention allows the delivery of d 2  to occur without any ordering constraint  69 . Accordingly, the additional synchronization delay incurred by a prior art ordered write relative to the present invention TAW is:
 
max({0,max({ Tarr ( d 1), Tarr ( d 3)})+α−max({[ Tarr ( d 1)+ Tcmp ( fx )], [ Tarr ( d 3)+ Tcmp ( fy )]})}),
 
where Tarr( . . . ) denotes the arrival time of a data 61.
 
Case of Monolithically Structured Programs
 
     Referring to  FIG. 7  and  FIG. 8 , a monolithically structured program for the sample computation (see  FIG. 2 ) is depicted. Here, a rigid programming structure has the functions fx, fy and fz executed sequentially by a processing subsystem that is separate from the sensor and actuator modules  73 . Here, the temporal constraint on the delivery of d 2  is depicted in the prior art ordered write primitive  83  and in the present invention&#39;s TAW primitive  87 :
 
α&gt; Tcmp ( fx )+ Tcmp ( fy ).
 
     With a monolithic structure, the additional synchronization delay incurred by a prior art ordered write relative to the present invention&#39;s TAW is  82 :
 
max({0,max({ Tarr ( d 1), Tarr ( d 3)})+α−max({[ Tarr ( d 1)+ Tcmp ( fx )], Tarr ( d 3)})+ Tcmp ( fy )}).
 
     As can be seen, even with a ‘dataflow’-style program structure that offers the potential to reap the maximum performance, a prior art ordered write incurs additional synchronization delay over the present invention TAW primitive under normal cases. 
       FIG. 9  provides a table summarizing the performance benefits of the present invention&#39;s TAW primitive over a prior art ordered write primitive. 
     A Reference Code Skeleton in ‘Dataflow’-Style Program Structure 
     Referring to  FIG. 10 , a real-time embedded application modeled as per the “produce-consume” style of computation may employ the write_buf and read_buf primitives as building blocks. The processing of a data d by an actuator vk be denoted by a function f(k,j)(d) where j indicates the epoch number. The global state Sj+1, as indicated,  116  is guaranteed to be consistent across all the processes, since the TAW primitive enforces an agreement on wrtset and Tj+1 among all the processes. 
     Having described preferred embodiments of the invention with reference to the accompanying drawings, it is to be understood that the invention is not limited to those precise embodiments, and that various changes and modifications may be effected therein by one skilled in the art without departing from the scope or spirit of the invention as defined in the appended claims.