FInite State Automata library

Initial release of a library that allows the modeling and the simulation of State Machines or Petri Nets:

• No limitation in the number of states and transitions that can be used to build a machine. 
• Machines created match closely the specifications of "State Machines" as described in SysML or in UML.
• Provides consistency information such as multiple transitions firing from the same state.
• Timed events.
• Fully supported on Open-source platforms such as Linux, FreeBSD ..., and on Windows.

To get the library or to contribute at its development: https://github.com/jean-ahmad/Fisa

Distributed computing optimization with Markov chains applied to queue systems

Computing a mathematical model, like the one of the earth's magnetic field, and 3D data requires a lot of processing resources. To view a simulation in real-time, it is then necessary to use many machines. A simple architecture to do this could be as in the following schema:

To exchange the data, 3D rendering for example, between servers for computation and the client in charge of displaying, one can use a Message Passing Interface implementation, as Mpich which work perfectly. The MPI_Bsend and MPI_Recv routines can be used for the communication. The first routine allows an asynchronism because it returns immediately after being called and the data sent are buffered before being dispatched. The second one works synchronously. In this way, the client doesn’t have to wait computation completion on the servers and can manage their activity. But, if there is an overflow of the buffer attached to the MPI_Bsend routine, the application will crash and returns a message like this one:

To overcome this problem, it is necessary to manage the sending buffers as queues. For data coming from servers and that go to the client, a possible architecture of the queues system can be represented like this:

The simplest way to describe queue behavior is with Markov chains. In this mathematical model, the number of packets in the queue is a state of the Markov chain and the state changing is described by a probability. The exponential probability density function \(\lambda e^{-\lambda x}\) is frequently used to describe fixed rate random processes. By choosing the time between two incoming data packets in the queue, and the time needed to retrieve and display a packet (service time) as random variables with exponential probability density functions, the Markov chain describing the queue behavior is then a Birth-Death process. Let’s call \(\lambda_{1}, \lambda_{2}, ..., \lambda_{n}\) the rates of data computation in server 1, server 2, …, server n respectively. The data packets are ordered with simulation time, so queues discipline is First Come First Served. Let’s call the rate to retrieve a packet through the network and to display it \(\mu\). Then, it is established in Birth-Death process theory, that the mean number of packets in server i will be:

$$\bar{\pi_i}=\frac{\lambda_{i}}{\mu \eta - \lambda_{i}}$$ with $$\eta=\frac{\lambda_i}{\sum_{k=1}^n \lambda_k}$$

The system is stable if \(\sum_{k=1}^n \lambda_k < \mu\) and this formula also gives a limit on the computation servers number to use depending on the client speed. If one call the mean size of a packet \(\rho\), then, on average, there will be \(\rho \bar{\pi_i}\) data on server i. Those values give an ideal asymptotic behavior and because of the variance of estimates, it will be necessary to avoid overflows of buffers.

In practice, the implementation of the management of the servers work and the retrieving of data, on the client side, looks difficult. This is a typical problem of real-time systems. The stochastic modeling of the communication between machines is very interesting and is a never ending problem. For now, watch my previous post, I can use many machines to compute a mathematical model and 3d data, the method is not optimal but the results are beautiful:

I will post updates on the investigation of the problem and you can contribute by leaving your ideas.

You can learn about the queueing systems with the book ISBN 978-1-4614-5317-8.

Computing the Magnetosphere

I show in a video that I can use many machines to compute a earth's magnetic field model and 3D data.