connect in a background until success
Your use of executor.awaitTermination() seems odd to me. I would instead have used a CountdownLatch to trigger success in a blocked thread. But I also agree with @Craig P. Motlin that a Future makes sense.

Besides that specific comment, you might consider some asynchronous notification technique for the dependency to declare that it's alive. That might be overkill for your scenario, but it's worked for me. Jini service registry, JMS messages, Hazelcast, plain UDP multicast, etc.