A framework for provenance-preserving history distribution and incremental reduction

Alberto Lluch Lafuente*

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingBook chapterResearchpeer-review

193 Downloads (Pure)


Provenance properties help asses the level of trust on the integrity of resources and events. One of the problems of interest is to find the right balance between the expressive power of the provenance specification language and the amount of historical information that needs to be remembered for each resource or event. This gives rise to possibly conflicting objectives relevant to integrity, privacy, and performance. Related problems are how to reduce historical information in a way that the provenance properties of interest are preserved, that is suitable for a distributed setting, and that relies on an incremental construction. We investigate these problems in a simple model of computation where resources/events and their dependencies form an acyclic directed graph, and computation steps consist of addition of new resources and of provenance-based queries. The model is agnostic with respect to the actual provenance specification language. We present then a framework, parametric on such language, for distributing, and incrementally constructing reduced histories in a sound and complete way. In the resulting model of computation, reduced histories are computed incrementally and queries are tested locally on reduced histories. We study different choices for instantiating the framework with concrete provenance specification languages, and their corresponding provenance-preserving history reduction techniques.

Original languageEnglish
Title of host publicationModels, Languages, and Tools for Concurrent and Distributed Programming
Publication date1 Jan 2019
ISBN (Print)978-3-030-21484-5
Publication statusPublished - 1 Jan 2019
SeriesLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11665 LNCS


  • Concurrency theory
  • Integrity
  • Minimisation
  • Provenance
  • Temporal logics


Dive into the research topics of 'A framework for provenance-preserving history distribution and incremental reduction'. Together they form a unique fingerprint.

Cite this