Summary: This paper presents two parallel asynchronous algorithms for the solution of the optimal control problem of linear large-scale dynamic systems. These algorithms are based on the prediction concept. The first one adopts the interaction prediction approach and the second one is based upon the costate prediction approach. The convergence behaviour of the proposed algorithms is thoroughly investigated. The new algorithms are applied on three practical systems and simulation results are presented and compared with those obtained using the well-known synchronous algorithms. It is shown that substantial savings in computation time can be achieved by employing the proposed asynchronous algorithms.