AFRL Patent Wall Details

7877748

2011-01-25

View Full Patent

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.

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 .DELTA., 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 .DELTA.-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\'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 rea