Parallel iterative algorithms for Markovian systems on distributed architectures

This paper explores parallel iterative methods for solving Markovian systems, aiming to tackle computational challenges in scientific and industrial contexts. Two strategies for parallelising the Gauss-Seidel iterative scheme in the circuit-switching networks model are deployed and evaluated on both shared memory multiprocessor systems and networks of shared memory multiprocessor machines. The first strategy involves modifying the Gauss-Seidel iterative scheme, while the second employs a colouring technique for components in red and black. An activation message-based termination method is introduced for asynchronous iterations on networks of shared memory multiprocessor machines. Additionally, a novel parallel iterative method for general Markovian systems is proposed and evaluated for both synchronous and asynchronous implementations. This method distributes computational workload differently from the conventional approach used in circuit switching networks.