DNS resolution fails

A service suddenly can't reach one of its dependencies. The logs show 'no such host' / name-resolution errors when it tries to call that dependency's hostname, while calls to other dependencies work fine. The dependency itself is up and reachable from a teammate's laptop by hostname. Your service didn't deploy. How do you triage this resolution failure?