author: Jeroen Vonk
title: Bisimulation Reduction with MapReduce
keywords: LTSmin, Hadoop, branching bisimulation
topics: Algorithms and Data Structures
committee: Jaco van de Pol ,
Stefan Blom ,
Hiemstra ,
Djoerd
end: August 2016

Abstract

We will focus on reducing the size of the LTS models using bisimulation reduction. Bisimulation reduction allows to identify similar states that can be merged whilst preserving certain properties of the model. These similar, or redundant states will be identified by comparing them with other states in the model using a bisimulation relation. The bisimulation relation will identify states showing the same behavior, that therefore can be merged. This process is called bisimulation reduction. A common method to determine the smallest model is using partition refinement. 

In order to use the algorithm on large models it needs to be scalable. Therefore we will be using a framework for distributed processing that is part of Hadoop, called MapReduce. Using this framework provides us with a robust system that automatically recovers from e.g. hardware faults. The use of MapReduce also makes our algorithm scalable, and easily executed at third party clusters. However, this framework will put several limitations on the design of the algorithm, and the available data structures. It is reported that Hadoop can be slow when using multiple iterations. 

 

References

  1. LTSmin web site (Digital version available here)
  2. Hadoop web site (Digital version available here)
  3. Apache Giraph (Digital version available here)

Additional Resources

  1. The paper