Modelling and analysis of the monotonic read consistent distributed system using coloured Petri net

摘要

Consistency is one of the key challenges in replicated distributed systems (DSs). Data centric and client centric are two main categories of consistency models. Monotonic read (MR) is one of the client centric consistency models that guarantees consistency from view point of a single client in terms of access to replicated data store. This consistency model guarantees that when a process reads a value of data item, it never sees a value older than the one it saw in previous read. Petri net is one of the formal methods to analyze behavioral properties of concurrent systems. In this paper a novel model of MR consistency DS and its analysis using coloured Petri nets is introduced. This model enables us to study that a given history is valid history for MR consistent DS or not. Proposed model using developed functions that are used for model checking can prove this and present a scenario that MR consistent DS can produce given history. By analysis of SSG of model we can prove that proposed model do not have true deadlocks and therefore proposed model is correct.