Index: pym/_emerge/depgraph.py
===================================================================
--- pym/_emerge/depgraph.py	(revision 13768)
+++ pym/_emerge/depgraph.py	(working copy)
@@ -54,7 +54,7 @@
 
 class _frozen_depgraph_config(object):
 
-	def __init__(self, settings, trees, myopts, spinner):
+	def __init__(self, settings, trees, myopts, spinner, allow_backtracking=False):
 		self.settings = settings
 		self.target_root = settings["ROOT"]
 		self.myopts = myopts
@@ -88,10 +88,11 @@
 				clone=self.trees[myroot]["vartree"].settings)
 
 		self._required_set_names = set(["system", "world"])
+		self._allow_backtracking = allow_backtracking
 
 class _dynamic_depgraph_config(object):
 
-	def __init__(self, depgraph, myparams):
+	def __init__(self, depgraph, myparams, runtime_pkg_mask):
 		self.myparams = myparams
 		# Maps slot atom to package for each Package added to the graph.
 		self._slot_pkg_map = {}
@@ -155,6 +156,8 @@
 		self._initially_unsatisfied_deps = []
 		self._ignored_deps = []
 		self._highest_pkg_cache = {}
+		self._runtime_pkg_mask = runtime_pkg_mask
+		self._need_restart = False
 
 		for myroot in depgraph._frozen_config.trees:
 			self._slot_pkg_map[myroot] = {}
@@ -245,12 +248,12 @@
 	_dep_keys = ["DEPEND", "RDEPEND", "PDEPEND"]
 	
 	def __init__(self, settings, trees, myopts, myparams, spinner,
-		frozen_config=None):	
+		frozen_config=None, runtime_pkg_mask=[], allow_backtracking=False):
 		if frozen_config is None:
 			frozen_config = _frozen_depgraph_config(settings, trees,
-			myopts, spinner)
+			myopts, spinner, allow_backtracking=allow_backtracking)
 		self._frozen_config = frozen_config
-		self._dynamic_config = _dynamic_depgraph_config(self, myparams)
+		self._dynamic_config = _dynamic_depgraph_config(self, myparams, runtime_pkg_mask)
 
 		self._select_atoms = self._select_atoms_highest_available
 		self._select_package = self._select_pkg_highest_available
@@ -696,13 +699,20 @@
 								(dep.parent, dep.atom))
 					return 1
 				else:
+					# A slot collision has occurred. 
+					if self._frozen_config._allow_backtracking:
+						#Mask existing_node and restart dependency calculation.
+						print "A slot collsion occured for ", existing_node.slot_atom, ". Masking ", existing_node.cpv, "."
+						self._dynamic_config._runtime_pkg_mask.append(existing_node)
+						self._dynamic_config._need_restart = True
+						return 0
+					else:
+						#Sometimes this coincides with unresolvable blockers, \
+						#so the slot collision will be shown later if there are \
+						#no unresolvable blockers.
+						self._add_slot_conflict(pkg)
+						slot_collision = True
 
-					# A slot collision has occurred.  Sometimes this coincides
-					# with unresolvable blockers, so the slot collision will be
-					# shown later if there are no unresolvable blockers.
-					self._add_slot_conflict(pkg)
-					slot_collision = True
-
 			if slot_collision:
 				# Now add this node to the graph so that self.display()
 				# can show use flags and --tree portage.output.  This node is
@@ -1945,6 +1955,9 @@
 
 				for pkg in self._iter_match_pkgs(root_config, pkg_type, atom, 
 					onlydeps=onlydeps):
+					if pkg in self._dynamic_config._runtime_pkg_mask:
+						#The package has been masked by the backtracking logic
+						continue
 					cpv = pkg.cpv
 					# Make --noreplace take precedence over --newuse.
 					if not pkg.installed and noreplace and \
@@ -4572,6 +4585,13 @@
 		graph in order to avoid making a potentially unsafe decision.
 		"""
 
+	def need_restart(self):
+		return self._dynamic_config._need_restart
+
+	def get_runtime_pkg_mask(self):
+		return self._dynamic_config._runtime_pkg_mask[:]
+
+
 class _dep_check_composite_db(portage.dbapi):
 	"""
 	A dbapi-like interface that is optimized for use in dep_check() calls.
Index: pym/_emerge/actions.py
===================================================================
--- pym/_emerge/actions.py	(revision 13768)
+++ pym/_emerge/actions.py	(working copy)
@@ -296,26 +296,36 @@
 		if ("--resume" in myopts):
 			print darkgreen("emerge: It seems we have nothing to resume...")
 			return os.EX_OK
+		
+		if "--quiet" not in myopts and "--nodeps" not in myopts:
+				print "Calculating dependencies  ",
+				sys.stdout.flush()
 
-		myparams = create_depgraph_params(myopts, myaction)
-		if "--quiet" not in myopts and "--nodeps" not in myopts:
-			print "Calculating dependencies  ",
-			sys.stdout.flush()
-		mydepgraph = depgraph(settings, trees, myopts, myparams, spinner)
-		try:
-			retval, favorites = mydepgraph.select_files(myfiles)
-		except portage.exception.PackageNotFound, e:
-			portage.writemsg("\n!!! %s\n" % str(e), noiselevel=-1)
-			return 1
-		except portage.exception.PackageSetNotFound, e:
-			root_config = trees[settings["ROOT"]]["root_config"]
-			display_missing_pkg_set(root_config, e.value)
-			return 1
+		runtime_pkg_mask = []
+		while True:
+			myparams = create_depgraph_params(myopts, myaction)
+			mydepgraph = depgraph(settings, trees, myopts, myparams, spinner, \
+				runtime_pkg_mask=runtime_pkg_mask, allow_backtracking=True)
+			try:
+				retval, favorites = mydepgraph.select_files(myfiles)
+			except portage.exception.PackageNotFound, e:
+				portage.writemsg("\n!!! %s\n" % str(e), noiselevel=-1)
+				return 1
+			except portage.exception.PackageSetNotFound, e:
+				root_config = trees[settings["ROOT"]]["root_config"]
+				display_missing_pkg_set(root_config, e.value)
+				return 1
+			if not retval:
+				if mydepgraph.need_restart():
+					runtime_pkg_mask = mydepgraph.get_runtime_pkg_mask()
+				else:
+					mydepgraph.display_problems()
+					return 1
+			else:
+				break
+
 		if show_spinner:
 			print "\b\b... done!"
-		if not retval:
-			mydepgraph.display_problems()
-			return 1
 
 	if "--pretend" not in myopts and \
 		("--ask" in myopts or "--tree" in myopts or \