diff --git a/src/avalanche.h b/src/avalanche.h
--- a/src/avalanche.h
+++ b/src/avalanche.h
@@ -13,6 +13,7 @@
 #include "uint256.h"
 
 #include <atomic>
+#include <chrono>
 #include <condition_variable>
 #include <cstdint>
 #include <vector>
@@ -127,6 +128,7 @@
     AvalancheResponse(uint32_t cooldownIn, std::vector<AvalancheVote> votesIn)
         : cooldown(cooldownIn), votes(votesIn) {}
 
+    uint32_t getCooldown() const { return cooldown; }
     const std::vector<AvalancheVote> &GetVotes() const { return votes; }
 
     // serialization support
@@ -191,6 +193,8 @@
 
 typedef std::map<const CBlockIndex *, VoteRecord, CBlockIndexWorkComparator>
     BlockVoteMap;
+typedef std::map<std::chrono::time_point<std::chrono::steady_clock>, NodeId>
+    NodeCooldownMap;
 
 class AvalancheProcessor {
 private:
@@ -221,6 +225,7 @@
     std::atomic<uint32_t> round;
     RWCollection<std::set<NodeId>> nodeids;
     RWCollection<std::map<NodeId, RequestRecord>> queries;
+    RWCollection<NodeCooldownMap> nodecooldown;
 
     /**
      * Start stop machinery.
diff --git a/src/avalanche.cpp b/src/avalanche.cpp
--- a/src/avalanche.cpp
+++ b/src/avalanche.cpp
@@ -68,6 +68,10 @@
 bool AvalancheProcessor::registerVotes(
     NodeId nodeid, const AvalancheResponse &response,
     std::vector<AvalancheBlockUpdate> &updates) {
+    // Save the time at which we can query again.
+    auto cooldown_end = std::chrono::steady_clock::now() +
+                        std::chrono::milliseconds(response.getCooldown());
+
     RequestRecord r;
 
     {
@@ -162,8 +166,8 @@
     }
 
     // Put the node back in the list of queriable nodes.
-    auto w = nodeids.getWriteView();
-    w->insert(nodeid);
+    auto w = nodecooldown.getWriteView();
+    w->insert(std::make_pair(cooldown_end, nodeid));
     return true;
 }
 
@@ -250,7 +254,26 @@
 
 NodeId AvalancheProcessor::getSuitableNodeToQuery() {
     auto w = nodeids.getWriteView();
-    if (w->empty()) {
+    bool isCooldownMapEmpty;
+
+    {
+        // Recover nodes for which cooldown is over.
+        auto now = std::chrono::steady_clock::now();
+        auto wcooldown = nodecooldown.getWriteView();
+        for (auto it = wcooldown.begin();
+             it != wcooldown.end() && it->first < now;) {
+            w->insert(it->second);
+            wcooldown->erase(it++);
+        }
+
+        isCooldownMapEmpty = wcooldown->empty();
+    }
+
+    // If the cooldown map is empty and we don't have any nodes, it's time to
+    // fish for new ones.
+    // FIXME: Clearly, we need a better way to fish for new nodes, but this is
+    // out of scope for now.
+    if (isCooldownMapEmpty && w->empty()) {
         auto r = queries.getReadView();
 
         // We don't have any candidate node, so let's try to find some.
diff --git a/src/test/avalanche_tests.cpp b/src/test/avalanche_tests.cpp
--- a/src/test/avalanche_tests.cpp
+++ b/src/test/avalanche_tests.cpp
@@ -20,6 +20,8 @@
     static NodeId getSuitableNodeToQuery(AvalancheProcessor &p) {
         return p.getSuitableNodeToQuery();
     }
+
+    static uint32_t getRound(const AvalancheProcessor &p) { return p.round; }
 };
 
 BOOST_FIXTURE_TEST_SUITE(avalanche_tests, TestChain100Setup)
@@ -495,18 +497,37 @@
     // Add a new block. Check it is added to the polls.
     BOOST_CHECK(p.addBlockToReconcile(pindex));
 
-    bool hasQueried = false;
+    uint32_t round = AvalancheTest::getRound(p);
     for (int i = 0; i < 1000; i++) {
         // Technically, this is a race condition, but this should do just fine
         // as we wait up to 1s for an event that should take 10ms.
         boost::this_thread::sleep_for(boost::chrono::milliseconds(1));
-        if (AvalancheTest::getSuitableNodeToQuery(p) == -1) {
-            hasQueried = true;
+        if (AvalancheTest::getRound(p) != round) {
+            break;
+        }
+    }
+
+    // Check that we effectively got a request and not timed out.
+    BOOST_CHECK(AvalancheTest::getRound(p) > round);
+
+    // Respond and check the cooldown time is respected.
+    round = AvalancheTest::getRound(p);
+    auto queryTime =
+        std::chrono::steady_clock::now() + std::chrono::milliseconds(100);
+
+    std::vector<AvalancheBlockUpdate> updates;
+    p.registerVotes(nodeid, {100, {AvalancheVote(0, blockHash)}}, updates);
+    for (int i = 0; i < 1000; i++) {
+        // We make sure that we do not get a request before queryTime.
+        boost::this_thread::sleep_for(boost::chrono::milliseconds(1));
+        if (AvalancheTest::getRound(p) != round) {
+            BOOST_CHECK(std::chrono::steady_clock::now() > queryTime);
             break;
         }
     }
 
-    BOOST_CHECK(hasQueried);
+    // But we eventually get one.
+    BOOST_CHECK(AvalancheTest::getRound(p) > round);
 
     // Stop event loop.
     BOOST_CHECK(p.stopEventLoop());