An active data structure is a data structure with an associated thread or process that performs internal operations.[1] More specifically, an active data structure is associated with a computing resource, which contains one or more concurrently executing processes, and data associated with those processes. Communication is modeled using remote procedure calls, as opposed to shared memory or message passing. The active data structure's internals are hidden behind its RPC interface, and may be accessed concurrently. Common examples include databases and file systems. Active data structures can perform maintenance when resources would otherwise be idle, and present multiple views of the data.[2]
A queue provided by the hardware or operating system is generally not unbounded, but rather has finite capacity. Suppose that the application has a strong requirement to never lose queue items. Then, the writing process must be modified to save items to a high-capacity storage medium if the queue is full, and the reading process must read the items back. Using the concept of active data structures, one can instead consider an "active queue" which manages saving and retrieving items from the high-capacity storage. Although there are now three running processes instead of two, potentially making synchronization more complex, the high level reader-writer abstraction for using an active queue is still simple and clear.
Self-adjusting computation is a technique for creating incremental computing programs that maintain internal state and can adjust to new inputs more efficiently than recomputing from scratch. This suggests that active data structures can be formalized by introducing the notion of time to the typical algebraic characterization of data structures. Specifically, Kanat Tangwongsan proposes that an active data structure is an algebra with these three meta-operations:[3]