diff --git a/src/avalanche.h b/src/avalanche.h
--- a/src/avalanche.h
+++ b/src/avalanche.h
@@ -5,7 +5,8 @@
 #ifndef BITCOIN_AVALANCHE_H
 #define BITCOIN_AVALANCHE_H
 
-#include "net.h"      // for NodeId
+#include "blockindexworkcomparator.h"
+#include "net.h"
 #include "protocol.h" // for CInv
 #include "rwcollection.h"
 #include "serialize.h"
@@ -134,12 +135,15 @@
     }
 };
 
+typedef std::map<const CBlockIndex *, VoteRecord, CBlockIndexWorkComparator>
+    BlockVoteMap;
+
 class AvalancheProcessor {
 private:
     /**
      * Blocks to run avalanche on.
      */
-    RWCollection<std::map<const CBlockIndex *, VoteRecord>> vote_records;
+    RWCollection<BlockVoteMap> vote_records;
 
     /**
      * Start stop machinery.
@@ -162,6 +166,11 @@
 
     bool startEventLoop(CScheduler &scheduler);
     bool stopEventLoop();
+
+private:
+    std::vector<CInv> getInvsForNextPoll() const;
+
+    friend struct AvalancheTest;
 };
 
 #endif // BITCOIN_AVALANCHE_H
diff --git a/src/avalanche.cpp b/src/avalanche.cpp
--- a/src/avalanche.cpp
+++ b/src/avalanche.cpp
@@ -15,9 +15,9 @@
         .second;
 }
 
-static const VoteRecord *GetRecord(
-    const RWCollection<std::map<const CBlockIndex *, VoteRecord>> &vote_records,
-    const CBlockIndex *pindex) {
+static const VoteRecord *
+GetRecord(const RWCollection<BlockVoteMap> &vote_records,
+          const CBlockIndex *pindex) {
     auto r = vote_records.getReadView();
     auto it = r->find(pindex);
     if (it == r.end()) {
@@ -80,6 +80,10 @@
  * Run the avalanche event loop every 10ms.
  */
 static int64_t AVALANCHE_TIME_STEP_MILLISECONDS = 10;
+/**
+ * Maximum item that can be polled at once.
+ */
+static size_t AVALANCHE_MAX_ELEMENT_POLL = 4096;
 }
 
 bool AvalancheProcessor::startEventLoop(CScheduler &scheduler) {
@@ -126,3 +130,26 @@
     stopRequest = false;
     return true;
 }
+
+std::vector<CInv> AvalancheProcessor::getInvsForNextPoll() const {
+    std::vector<CInv> invs;
+
+    auto r = vote_records.getReadView();
+    for (const std::pair<const CBlockIndex *, VoteRecord> &p :r) {
+        const VoteRecord &v = p.second;
+        if (v.hasFinalized()) {
+            // If this has finalized, we can just skip.
+            continue;
+        }
+
+        // We don't have a decision, we need more votes.
+        invs.push_back(CInv(MSG_BLOCK, p.first->GetBlockHash()));
+        if (invs.size() >= AVALANCHE_MAX_ELEMENT_POLL) {
+            // Make sure we do not produce more invs than specified by the
+            // protocol.
+            return invs;
+        }
+    }
+
+    return invs;
+}
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
@@ -8,6 +8,12 @@
 
 #include <boost/test/unit_test.hpp>
 
+struct AvalancheTest {
+    static std::vector<CInv> getInvsForNextPoll(const AvalancheProcessor &p) {
+        return p.getInvsForNextPoll();
+    }
+};
+
 BOOST_FIXTURE_TEST_SUITE(avalanche_tests, TestChain100Setup)
 
 #define REGISTER_VOTE_AND_CHECK(vr, vote, state, finalized, confidence)        \
@@ -70,20 +76,26 @@
     AvalancheProcessor p;
 
     CBlock block = CreateAndProcessBlock({}, CScript());
-    const uint256 hash = block.GetHash();
-    const CBlockIndex *pindex = mapBlockIndex[hash];
+    const uint256 blockHash = block.GetHash();
+    const CBlockIndex *pindex = mapBlockIndex[blockHash];
 
     // Querying for random block returns false.
     BOOST_CHECK(!p.isAccepted(pindex));
     BOOST_CHECK(!p.hasFinalized(pindex));
 
-    // Newly added blocks are also considered rejected.
+    // Add a new block. Check it is added to the polls.
     BOOST_CHECK(p.addBlockToReconcile(pindex));
+    auto invs = AvalancheTest::getInvsForNextPoll(p);
+    BOOST_CHECK_EQUAL(invs.size(), 1);
+    BOOST_CHECK_EQUAL(invs[0].type, MSG_BLOCK);
+    BOOST_CHECK(invs[0].hash == blockHash);
+
+    // Newly added blocks are also considered rejected.
     BOOST_CHECK(!p.isAccepted(pindex));
     BOOST_CHECK(!p.hasFinalized(pindex));
 
     // Let's vote for this block a few times.
-    AvalancheResponse resp{0, {AvalancheVote(0, hash)}};
+    AvalancheResponse resp{0, {AvalancheVote(0, blockHash)}};
     for (int i = 0; i < 5; i++) {
         p.registerVotes(resp);
         BOOST_CHECK(!p.isAccepted(pindex));
@@ -97,12 +109,22 @@
         BOOST_CHECK(!p.hasFinalized(pindex));
     }
 
+    // As long as it is not finalized, we poll.
+    invs = AvalancheTest::getInvsForNextPoll(p);
+    BOOST_CHECK_EQUAL(invs.size(), 1);
+    BOOST_CHECK_EQUAL(invs[0].type, MSG_BLOCK);
+    BOOST_CHECK(invs[0].hash == blockHash);
+
     // Now finalize the decision.
-    resp = {0, {AvalancheVote(1, hash)}};
+    resp = {0, {AvalancheVote(1, blockHash)}};
     p.registerVotes(resp);
     BOOST_CHECK(p.isAccepted(pindex));
     BOOST_CHECK(p.hasFinalized(pindex));
 
+    // Once the decision is finalized, there is no poll for it.
+    invs = AvalancheTest::getInvsForNextPoll(p);
+    BOOST_CHECK_EQUAL(invs.size(), 0);
+
     // Now let's undo this and finalize rejection.
     for (int i = 0; i < 5; i++) {
         p.registerVotes(resp);
@@ -117,11 +139,21 @@
         BOOST_CHECK(!p.hasFinalized(pindex));
     }
 
+    // As long as it is not finalized, we poll.
+    invs = AvalancheTest::getInvsForNextPoll(p);
+    BOOST_CHECK_EQUAL(invs.size(), 1);
+    BOOST_CHECK_EQUAL(invs[0].type, MSG_BLOCK);
+    BOOST_CHECK(invs[0].hash == blockHash);
+
     // Now finalize the decision.
     p.registerVotes(resp);
     BOOST_CHECK(!p.isAccepted(pindex));
     BOOST_CHECK(p.hasFinalized(pindex));
 
+    // Once the decision is finalized, there is no poll for it.
+    invs = AvalancheTest::getInvsForNextPoll(p);
+    BOOST_CHECK_EQUAL(invs.size(), 0);
+
     // Adding the block twice does nothing.
     BOOST_CHECK(!p.addBlockToReconcile(pindex));
     BOOST_CHECK(!p.isAccepted(pindex));