Workload-Aware Partitioning for Maintaining Temporal Consistency upon Multiprocessor Platforms

Deriving deadlines and periods of update transactions for maintaining timeliness and data freshness has long been recognized as an important problem in real-time database research. Despite years of active research, the state of the art only focuses on uniprocessor systems. In this paper, we take a first step of studying the workload-aware temporal consistency maintenance problem upon multiprocessor platforms. We consider the problem of how to partition a set of update transactions to m ≥ 2 processors to maintain the temporal consistency of real-time data objects under earliest deadline first (EDF) scheduling, while minimizing the total workload on m processors. Firstly, we only consider the feasibility aspect of the problem by proposing a polynomial time partitioning scheme, Temporal Consistency Partitioning (TCP), and formally showing that the resource augmentation bound of TCP is (3 - 1/m). Secondly, we address the partition problem globally by proposing a polynomial time heuristic, Density factor Balancing Fit (DBF), where density factor balancing plays a major role in producing workload-efficient partitionings. Finally, we evaluate the feasibility and workload performances of DBF versus other heuristics with comparable quality experimentally.