diff --git a/src/avalanche/peermanager.h b/src/avalanche/peermanager.h
--- a/src/avalanche/peermanager.h
+++ b/src/avalanche/peermanager.h
@@ -22,6 +22,9 @@
     Slot(uint64_t startIn, uint32_t scoreIn, PeerId peeridIn)
         : start(startIn), score(scoreIn), peerid(peeridIn) {}
 
+    Slot withStart(uint64_t startIn) const {
+        return Slot(startIn, score, peerid);
+    }
     Slot withScore(uint64_t scoreIn) const {
         return Slot(start, scoreIn, peerid);
     }
@@ -56,6 +59,18 @@
 
     PeerId selectPeer() const;
 
+    /**
+     * Trigger maintenance of internal datastructures.
+     * Returns how much slot space was saved after compaction.
+     */
+    uint64_t compact();
+
+    /**
+     * Perform consistency check on internal data structures.
+     * Mostly useful for tests.
+     */
+    bool verify() const;
+
     // Accssors.
     uint64_t getSlotCount() const { return slotCount; }
     uint64_t getFragmentation() const { return fragmentation; }
diff --git a/src/avalanche/peermanager.cpp b/src/avalanche/peermanager.cpp
--- a/src/avalanche/peermanager.cpp
+++ b/src/avalanche/peermanager.cpp
@@ -29,7 +29,7 @@
 
     if (i + 1 == slots.size()) {
         slots.pop_back();
-        slotCount = slots.empty() ? 0 : slots.rbegin()->getStop();
+        slotCount = slots.empty() ? 0 : slots.back().getStop();
     } else {
         fragmentation += slots[i].getScore();
         slots[i] = slots[i].withPeerId(NO_PEER);
@@ -92,6 +92,80 @@
     }
 }
 
+uint64_t PeerManager::compact() {
+    auto clearLastElements = [this] {
+        while (!slots.empty() && slots.back().getPeerId() == NO_PEER) {
+            slots.pop_back();
+        }
+    };
+
+    // Always make sure that the last element is not dead.
+    clearLastElements();
+
+    uint64_t prevStop = 0;
+    for (size_t i = 0; i < slots.size(); i++) {
+        if (slots[i].getPeerId() != NO_PEER) {
+            // This element is good, just slide it to the right position.
+            slots[i] = slots[i].withStart(prevStop);
+            prevStop = slots[i].getStop();
+            continue;
+        }
+
+        // This element is dead, put the last one it its place.
+        slots[i] = slots.back().withStart(prevStop);
+        prevStop = slots[i].getStop();
+
+        assert(slots[i].getPeerId() != NO_PEER);
+        peerIndices[slots[i].getPeerId()] = i;
+
+        slots.pop_back();
+        clearLastElements();
+    }
+
+    const uint64_t saved = slotCount - prevStop;
+    slotCount = prevStop;
+    fragmentation = 0;
+
+    return saved;
+}
+
+bool PeerManager::verify() const {
+    uint64_t prevStop = 0;
+    for (size_t i = 0; i < slots.size(); i++) {
+        const Slot &s = slots[i];
+
+        // Slots must be in correct order.
+        if (s.getStart() < prevStop) {
+            return false;
+        }
+
+        prevStop = s.getStop();
+
+        // If this is a dead slot, then nothing more needs to be checked.
+        if (s.getPeerId() == NO_PEER) {
+            continue;
+        }
+
+        // We have a live slot, verify index.
+        auto it = peerIndices.find(s.getPeerId());
+        if (it == peerIndices.end() || it->second != i) {
+            return false;
+        }
+    }
+
+    for (const auto &pair : peerIndices) {
+        auto p = pair.first;
+        auto i = pair.second;
+
+        // The index must point to a slot refering to this peer.
+        if (i >= slots.size() || slots[i].getPeerId() != p) {
+            return false;
+        }
+    }
+
+    return true;
+}
+
 PeerId selectPeerImpl(const std::vector<Slot> &slots, const uint64_t slot,
                       const uint64_t max) {
     assert(slot <= max);
diff --git a/src/avalanche/test/peermanager_tests.cpp b/src/avalanche/test/peermanager_tests.cpp
--- a/src/avalanche/test/peermanager_tests.cpp
+++ b/src/avalanche/test/peermanager_tests.cpp
@@ -99,8 +99,7 @@
 
     // Update the slots to be heavily skewed toward the first element.
     for (int i = 0; i < 100; i++) {
-        slots[i] = Slot(slots[i].getStart() + 100, slots[i].getScore(),
-                        slots[i].getPeerId());
+        slots[i] = slots[i].withStart(slots[i].getStart() + 100);
     }
 
     slots[0] = Slot(1, slots[0].getStop() - 1, slots[0].getPeerId());
@@ -240,6 +239,12 @@
     BOOST_CHECK(!pm.removePeer(peerids[2]));
     BOOST_CHECK(!pm.removePeer(peerids[7]));
     BOOST_CHECK(!pm.removePeer(NO_PEER));
+
+    // Compact the peer manager.
+    BOOST_CHECK_EQUAL(pm.compact(), 200);
+    BOOST_CHECK(pm.verify());
+    BOOST_CHECK_EQUAL(pm.getSlotCount(), 500);
+    BOOST_CHECK_EQUAL(pm.getFragmentation(), 0);
 }
 
 BOOST_AUTO_TEST_CASE(rescore_peer, *boost::unit_test::timeout(5)) {
@@ -303,6 +308,34 @@
             }
         }
     }
+
+    // Compact the peer manager.
+    BOOST_CHECK_EQUAL(pm.compact(), 100);
+    BOOST_CHECK(pm.verify());
+    BOOST_CHECK_EQUAL(pm.getSlotCount(), 500);
+    BOOST_CHECK_EQUAL(pm.getFragmentation(), 0);
+}
+
+BOOST_AUTO_TEST_CASE(compact_slots) {
+    PeerManager pm;
+
+    // Add 4 peers.
+    std::array<PeerId, 4> peerids;
+    for (int i = 0; i < 4; i++) {
+        peerids[i] = pm.addPeer(100);
+    }
+
+    // Remove all peers.
+    for (auto p : peerids) {
+        pm.removePeer(p);
+    }
+
+    BOOST_CHECK_EQUAL(pm.getSlotCount(), 300);
+    BOOST_CHECK_EQUAL(pm.getFragmentation(), 300);
+    BOOST_CHECK_EQUAL(pm.compact(), 300);
+    BOOST_CHECK(pm.verify());
+    BOOST_CHECK_EQUAL(pm.getSlotCount(), 0);
+    BOOST_CHECK_EQUAL(pm.getFragmentation(), 0);
 }
 
 BOOST_AUTO_TEST_SUITE_END()