Title: Parallel iterative algorithms for Markovian systems on distributed architectures

Authors: Mohamed Jarraya

Addresses: Information Technology Department, College of Computation and Informatics, Saudi Electronic University (SEU), Riyadh 11673, Saudi Arabia

Abstract: 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.

Keywords: Markovian systems; asynchronous iterations; synchronous iterations; termination algorithms; shared memory multiprocessor; network of shared memory multiprocessor; relaxation method; over-relaxation method; parallel alternate components relaxation method.

DOI: 10.1504/IJCNDS.2025.147301

International Journal of Communication Networks and Distributed Systems, 2025 Vol.31 No.4, pp.457 - 479

Received: 04 Jun 2024
Accepted: 25 Aug 2024
Published online: 14 Jul 2025 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article