Fractal-based decomposition is a flexible framework representing a family of optimization algorithms based on a hierarchical decomposition of the search space. We have built a software called Zellij, in which we were able to instantiate popular decomposition-based algorithms. Our goal is to tackle optimization problems characterized by computationally expensive objective functions and high dimensional search space. In this paper, we propose a generic asynchronous parallel methodology of fractal-based optimization algorithms on multi-nodes and multi-CPUs distributed environments. Experimental results show a significantly reduced computation time between the mono-threaded version and the asynchronous one. The obtained results are also analyzed according to the various search components such as tree search, exploration, and exploitation strategies.