Thanks for the fixes @fjetter . Do we not test bad_dep in unit tests ?

At least not explicitly. I was also trying to figure out which tests even trigger this section but couldn't find any, yet (without executing all tests on my machine)
Will have another look :)

Py3.6 tests fail due to a timeout error in test_gather_then_submit_after_failed_workers but I can't see how this would be connected.

I do see some more logged errors, though

  File "D:\a\distributed\distributed\distributed\worker.py", line 1801, in ensure_communicating
454

455
    assert all(dep.key in self.tasks for dep in deps)
456

457
AssertionError

and

Traceback (most recent call last):
572

573
  File "D:\a\distributed\distributed\distributed\worker.py", line 2868, in validate_task
574

575
    self.validate_task_ready(ts)
576

577
  File "D:\a\distributed\distributed\distributed\worker.py", line 2843, in validate_task_ready
578

579
    assert ts.key not in self.data
580

581
AssertionError

maybe there is still something else left over :/

FWIW I can sporadically reproduce the logs locally when running test_worker_who_has_clears_after_failed_connection but I'm still looking for the bug. My suspicion is that we call release_key too often, but I'm still searching

cc @gforsyth

I'm closing out this PR as 7fa4a32 was merged into master as a part of #4206 -- thanks for the fix, @fjetter !