This paper presents approaches to parallelization of algorithms for maintaining external and internal consistency in algebraic Bayesian networks as one of the representatives of probabilistic graphical models. The algorithms modified based on these approaches are described and presented in the form of schemes.