diff --git a/src/avalanche/processor.cpp b/src/avalanche/processor.cpp
--- a/src/avalanche/processor.cpp
+++ b/src/avalanche/processor.cpp
@@ -699,6 +699,10 @@
                 peerManager->updateNextRequestTime(pnode->GetId(), timeout);
             }
 
+            if (pnode->m_avalanche_statistics) {
+                pnode->m_avalanche_statistics->invsPolled(invs.size());
+            }
+
             // Send the query to the node.
             connman->PushMessage(
                 pnode, CNetMsgMaker(pnode->GetCommonVersion())
diff --git a/src/net.h b/src/net.h
--- a/src/net.h
+++ b/src/net.h
@@ -1045,6 +1045,47 @@
     // m_avalanche_state == nullptr if we're not using avalanche with this peer
     std::unique_ptr<AvalancheState> m_avalanche_state;
 
+    class AvalancheStatistics {
+        /** Time constant for the availability score computation */
+        uint64_t timeConstant;
+        /** How many invs have been polled */
+        uint64_t pollCounter;
+        /** How many invs have been voted on */
+        uint64_t responseCounter;
+        /** The node availability score, see getAvailabilityScore() */
+        double availabilityScore;
+
+        Mutex cs_statistics;
+
+    public:
+        AvalancheStatistics(uint64_t timeConstantIn)
+            : timeConstant(timeConstantIn), pollCounter(0), responseCounter(0),
+              availabilityScore(0.){};
+
+        /** The node was polled for count invs */
+        void invsPolled(size_t count);
+        /** The node voted for count invs */
+        void invsVoted(size_t count);
+        /**
+         * The availability score is calculated using an exponentially weighted
+         * average.
+         * This has several interesting properties:
+         *  - The most recent polls/responses have more weight than the previous
+         * ones. A node that recently stopped answering will see its ratio
+         * decrease quickly.
+         *  - This is a low-pass filter, so it causes delay. This means that a
+         * node needs to have a track record for the ratio to be high. A node
+         * that has been little requested will have a lower ratio than a node
+         * that failed to answer a few polls but answered a lot of them.
+         *  - It is cheap to compute.
+         */
+        double getAvailabilityScore();
+    };
+
+    // m_avalanche_statistics == nullptr if we're not using avalanche with this
+    // peer
+    std::unique_ptr<AvalancheStatistics> m_avalanche_statistics;
+
     // Used for headers announcements - unfiltered blocks to relay
     std::vector<BlockHash> vBlockHashesToAnnounce GUARDED_BY(cs_inventory);
 
diff --git a/src/net.cpp b/src/net.cpp
--- a/src/net.cpp
+++ b/src/net.cpp
@@ -44,6 +44,7 @@
               "miniUPnPc API version >= 10 assumed");
 #endif
 
+#include <algorithm>
 #include <cmath>
 #include <optional>
 #include <unordered_map>
@@ -3027,6 +3028,42 @@
     return nReceiveFloodSize;
 }
 
+void CNode::AvalancheStatistics::invsPolled(size_t count) {
+    assert(count > 0);
+
+    LOCK(cs_statistics);
+
+    pollCounter += count;
+
+    // Update the availability score
+    availabilityScore -=
+        availabilityScore / std::min(pollCounter, timeConstant);
+}
+
+void CNode::AvalancheStatistics::invsVoted(size_t count) {
+    assert(count > 0);
+
+    LOCK(cs_statistics);
+
+    // This should never happen as we don't accept votes for invs we didn't
+    // poll, but since it can cause a division by zero crash we use belt and
+    // suspenders
+    if (pollCounter == 0) {
+        return;
+    }
+
+    responseCounter += count;
+
+    // Update the availability score. Always account for 100% of the polled invs
+    // being voted on.
+    availabilityScore += 100. / std::min(pollCounter, timeConstant);
+}
+
+double CNode::AvalancheStatistics::getAvailabilityScore() {
+    LOCK(cs_statistics);
+    return availabilityScore;
+}
+
 CNode::CNode(NodeId idIn, ServiceFlags nLocalServicesIn,
              int nMyStartingHeightIn, SOCKET hSocketIn, const CAddress &addrIn,
              uint64_t nKeyedNetGroupIn, uint64_t nLocalHostNonceIn,
@@ -3051,9 +3088,12 @@
         m_addr_known = std::make_unique<CRollingBloomFilter>(5000, 0.001);
     }
 
-    // Don't relay proofs if avalanche is disabled
     if (isAvalancheEnabled(gArgs)) {
+        // Don't relay proofs if avalanche is disabled
         m_proof_relay = std::make_unique<ProofRelay>();
+        // Don't collect vote statistics if avalanche is disabled
+        // Statistics are computed using a 24h time constant
+        m_avalanche_statistics = std::make_unique<AvalancheStatistics>(144);
     }
 
     for (const std::string &msg : getAllNetMessageTypes()) {
diff --git a/src/net_processing.cpp b/src/net_processing.cpp
--- a/src/net_processing.cpp
+++ b/src/net_processing.cpp
@@ -4347,6 +4347,10 @@
             return;
         }
 
+        if (pfrom.m_avalanche_statistics) {
+            pfrom.m_avalanche_statistics->invsVoted(response.GetVotes().size());
+        }
+
         if (updates.size()) {
             for (avalanche::BlockUpdate &u : updates) {
                 CBlockIndex *pindex = u.getBlockIndex();
diff --git a/src/test/net_tests.cpp b/src/test/net_tests.cpp
--- a/src/test/net_tests.cpp
+++ b/src/test/net_tests.cpp
@@ -22,6 +22,7 @@
 #include <boost/test/unit_test.hpp>
 
 #include <algorithm>
+#include <cmath>
 #include <ios>
 #include <memory>
 #include <string>
@@ -944,4 +945,54 @@
     }
 }
 
+BOOST_AUTO_TEST_CASE(avalanche_statistics) {
+    const uint64_t tau = 144;
+
+    CNode::AvalancheStatistics avastats(tau);
+
+    double previousScore = avastats.getAvailabilityScore();
+    BOOST_CHECK_SMALL(previousScore, 1e-6);
+
+    // Check the statistics follow an exponential response for 1 to 10 tau
+    for (size_t i = 1; i <= 10; i++) {
+        for (size_t j = 0; j < tau; j++) {
+            // Use exactly the window size for the following tests to be
+            // correct. This is an IIR filter so the value won't matter after an
+            // infinite time elapsed which is not really what we want for unit
+            // tests.
+            avastats.invsPolled(tau);
+            // Always respond to everything correctly
+            avastats.invsVoted(tau);
+
+            // Expect a monotonic rise
+            BOOST_CHECK_GE(avastats.getAvailabilityScore(), previousScore);
+            previousScore = avastats.getAvailabilityScore();
+        }
+
+        // We expect 100% * (1 - e^-i) after i * tau. The tolerance is expressed
+        // as a percentage, and we add a (large) 0.1% margin to account for
+        // floating point error accumulation.
+        BOOST_CHECK_CLOSE(previousScore, 100. * (1. - std::exp(-1. * i)),
+                          100.1 / tau);
+    }
+
+    // After 10 tau we should be very close to 100% (about 99.995%)
+    BOOST_CHECK_CLOSE(previousScore, 100., 0.01);
+
+    for (size_t i = 1; i <= 3; i++) {
+        for (size_t j = 0; j < tau; j++) {
+            avastats.invsPolled(tau);
+
+            // Stop responding to the polls.
+
+            // Expect a monotonic fall
+            BOOST_CHECK_LE(avastats.getAvailabilityScore(), previousScore);
+            previousScore = avastats.getAvailabilityScore();
+        }
+    }
+
+    // After 3 more tau we should be under 5%
+    BOOST_CHECK_LT(previousScore, 5.);
+}
+
 BOOST_AUTO_TEST_SUITE_END()