Computational Models for Information Reuse

Techniques that optimize computations by reusing partial results have a long tradition in computer science. Seen from the point of view of sequential computations, all these techniques share the common execution strategy of storing partial results in a centralized data structure, while they differ as to how the results are computed, e.g. in a data-driven or constraint-driven fashion. Concurrent systems, namely the wide variety of systems that range from fine-grained parallelism to coarse-grained distribution, add another variable into the game. In fact, information reuse is here tangled with issues of local memory of agents and inter-agent communication. Thus, optimal strategies for information reuse directly affect agent configurations as well as agent communication protocols and strictly depend on those morphological aspects of the computational domain related to the sharing of structures among different data values. In this paper, we define a formal framework suitable for the study of information reuse from the point of view of concurrent systems. The main result of our work is in the identification of two distinct morphological features of computational domains, namely recursively replicated structures and structure copying. These features induce two different forms of information reuse that can be optimized, respectively, by solipsistic agents with large local memory and by large bandwidth networks of collaborative agents.