Incorporating the Concept of Priority into Lamport Timestamps to Prevent Starvation in Systems That Use Timestamps for Concurrency Control

EasyChair Preprint 3097

Abstract

Lamport timestamps are an elementary tool that can be used to maintain system-wide temporal consistency in a distributed system. By making all processes involved able to agree on the order of any two or more events (although not necessarily on their causal relation) they can be used as building block for many more complex algorithms intended for distributed systems. Without excluding other applications of such timestamps, we are interested in how these can be used for concurrency control in transactional databases through timestamp ordering algorithms, especially with less conservative algorithms that while being usually more efficient, are also prone to starvation. In this paper we propose an extension to Lamport timestamps that can work with any existing algorithm, by taking into account priority in order to prevent starvation: with priority we intend a dynamic property of a process that depends by its transaction failure rate, so that higher priority is symptom of more transaction rejections.

Keyphrases: Lamport timestamps, Priority, Starvation, Timestamp ordering, concurrency control

@booklet{EasyChair:3097,
  author    = {Gianluca Rombolà and Loredana Vigliano},
  title     = {Incorporating the Concept of Priority into Lamport Timestamps to Prevent Starvation in Systems That Use Timestamps for Concurrency Control},
  howpublished = {EasyChair Preprint 3097},
  year      = {EasyChair, 2020}}