conan: AssertionError (non-deterministic?) in graph evaluation

I have just seen the following error in our CI:

$ conan install -u -r artifactory --build=outdated ./packaging -s python=cpython -s python.version=3.6
Version range '^2.1' required by 'fbthrift/2018.05.21.00@igs/testing' resolved to 'gflags/2.2.0@igs/testing'
Version range '^2.1' required by 'folly/2018.05.21.00@igs/testing' resolved to 'gflags/2.2.0@igs/testing'
Version range '^0.3.5' required by 'folly/2018.05.21.00@igs/testing' resolved to 'glog/0.3.5@igs/testing'
Version range '^1.1' required by 'folly/2018.05.21.00@igs/testing' resolved to 'double-conversion/1.1.5@igs/testing'
glog/0.3.5@igs/testing requirement gflags/[^2.2]@igs/testing overriden by folly/2018.05.21.00@igs/testing to gflags/2.2.0@igs/testing 
Version range '^2.2' required by 'glog/0.3.5@igs/testing' valid for downstream requirement 'gflags/2.2.0@igs/testing'
Version range '^2.1' required by 'wangle/2018.05.21.00@igs/testing' resolved to 'gflags/2.2.0@igs/testing'
wangle/2018.05.21.00@igs/testing: WARN: Can't update, no package in remote
wangle/2018.05.21.00@igs/testing: Package is up to date
Traceback (most recent call last):
  File "/usr/local/lib/python3.6/dist-packages/conans/model/ref.py", line 70, in loads
    name, version, user, channel = tokens
ValueError: not enough values to unpack (expected 4, got 2)

During handling of the above exception, another exception occurred:

Traceback (most recent call last):
  File "/usr/local/lib/python3.6/dist-packages/conans/client/command.py", line 314, in install
    reference = ConanFileReference.loads(args.path_or_reference)
  File "/usr/local/lib/python3.6/dist-packages/conans/model/ref.py", line 73, in loads
    "OpenCV/1.0.6@user/stable" % text)
conans.errors.ConanException: Wrong package recipe reference ./packaging
Write something like OpenCV/1.0.6@user/stable

During handling of the above exception, another exception occurred:

Traceback (most recent call last):
  File "/usr/local/lib/python3.6/dist-packages/conans/client/command.py", line 1219, in run
    method(args[0][1:])
  File "/usr/local/lib/python3.6/dist-packages/conans/client/command.py", line 325, in install
    install_folder=args.install_folder)
  File "/usr/local/lib/python3.6/dist-packages/conans/client/conan_api.py", line 79, in wrapper
    return f(*args, **kwargs)
  File "/usr/local/lib/python3.6/dist-packages/conans/client/conan_api.py", line 482, in install
    no_imports=no_imports)
  File "/usr/local/lib/python3.6/dist-packages/conans/client/manager.py", line 258, in install
    profile.build_requires)
  File "/usr/local/lib/python3.6/dist-packages/conans/client/graph/graph_manager.py", line 108, in load_graph
    binaries_analyzer.evaluate_graph(graph, build_mode, update, remote_name)
  File "/usr/local/lib/python3.6/dist-packages/conans/client/graph/graph_binaries.py", line 138, in evaluate_graph
    self._evaluate_node(node, build_mode, update, evaluated_references, remote_name)
  File "/usr/local/lib/python3.6/dist-packages/conans/client/graph/graph_binaries.py", line 47, in _evaluate_node
    assert node.binary is None
AssertionError

Unfortunately, this error did not reproduce after retrying exactly the same build (with the same cache state), everything was OK. Likely relevant info about our CI setup: the entire .conan directory is cached between jobs, but it is only stored at the end of a successful job. So, while the .conan contents were quite possibly written by an older conan version, they were exactly the same for the unsuccessful and successful tries.

Environment info: Conan 1.5.1, Ubuntu 18.04 x86_64