As with Euclidean rings and rings admitting a restricted Nagata's pairwise algorithm, we will give an internal characterization of 2-stage Euclidean rings. Applying this characterization we are capable of providing infinitely many integral domains which are omega-stage Euclidean but not 2-stage Euclidean. Our examples solve finally a fundamental question related to the notion of k-stage Euclidean rings raised by G.E. Cooke [G.E. Cooke, A weakening of the Euclidean property for integral domains and applications to algebraic number theory I, J. Reine Angew, Math. 282 (1976) 133-156]. The question was stated as follows: "I do not know of an example of an omega-stage euclidean ring which is not 2-stage euclidean." Also, in this article we will give a method to construct the smallest restricted Nagata's pairwise algorithm theta on a unique factorization domain which admits a restricted Nagata's pairwise algorithm. It is of interest to point out that in a Euclidean domain the shortest length d(a, b) of all terminating division chains starting from a pair (a, b) and the value theta(a, b) with g.c.d.(a, b) not equal 1 can be determined by each other. (C) 2011 Elsevier Inc. All rights reserved.