This paper deals with the efficient computation of solutions of robust nonlinear model predictive control problems that are formulated using multi-stage stochastic programming via the generation of a scenario tree. Such a formulation makes it possible to consider explicitly the concept of recourse, which is inherent to any receding horizon approach, but it results in large-scale optimization problems. One possibility to solve these problems in an efficient manner is to decompose the large-scale optimization problem into several subproblems that are iteratively modified and repeatedly solved until a solution to the original problem is achieved. In this paper we review the most common methods used for such decomposition and apply them to solve robust nonlinear model predictive control problems in a distributed fashion. We also propose a novel method to reduce the number of iterations of the coordination algorithm needed for the decomposition methods to converge. The performance of the different approaches is evaluated in extensive simulation studies of two nonlinear case studies. (C) 2015 Elsevier Ltd. All rights reserved.