Abstract: Recent research has experimentally shown that parallelization of Greedy Best-First Search (GBFS), a satisficing best-first search method, can behave very differently from sequential GBFS. In this paper, we propose a theoretical framework to compare parallel best-first search with sequential best-first search, including not only GBFS but also A* and Weighted A*, optimal and suboptimal best-first search methods. We show to which extent exiting parallel best-first search methods are different from sequential best-first search. We show that this framework can be used to design a parallel best-first search method which is guaranteed to behave somewhat similarly to sequential best-first search.