Repository: libp2p/go-libp2p-kad-dht

Issue:
provider: resume reprovide operations
## Current situtation

A fresh reprovide cycle starts as soon as the `SweepingProvider` is created.

This means that if the node has been providing (and reproviding) content, then is turned off (not just offline) for a few hours/days, and then is restarted, it will take up to `reprovideInterval` for all keys to be reprovided.

## Ideal situation

We want a similar behaviour to when the `provide` goes `offline`, which is to keep track of regions that should have been reprovided but weren't because the node was offline, and reprovide them as fast as possible when the `provider` comes back online.

We need to write reprovide timestamps to a datastore, so that when the `SweepingProvider` is started it can look in the datastore for regions that haven't been provided since at least `reprovideInterval` and schedule them to be reprovided ASAP.

Discussion:

Solution patch:
diff --git a/provider/dual/options.go b/provider/dual/options.go
index 90f5e84..eacba4e 100644
--- a/provider/dual/options.go
+++ b/provider/dual/options.go
@@ -24,7 +24,8 @@ const (
 )
 
 type config struct {
-	keystore keystore.Keystore
+	resumeCycle [2]bool
+	keystore    keystore.Keystore
 
 	reprovideInterval [2]time.Duration // [0] = LAN, [1] = WAN
 	maxReprovideDelay [2]time.Duration
@@ -47,6 +48,7 @@ type Option func(opt *config) error
 // getOpts creates a config and applies Options to it.
 func getOpts(opts []Option, d *dual.DHT) (config, error) {
 	cfg := config{
+		resumeCycle:       [2]bool{true, true},
 		reprovideInterval: [2]time.Duration{amino.DefaultReprovideInterval, amino.DefaultReprovideInterval},
 		maxReprovideDelay: [2]time.Duration{provider.DefaultMaxReprovideDelay, provider.DefaultMaxReprovideDelay},
 
@@ -85,6 +87,27 @@ func getOpts(opts []Option, d *dual.DHT) (config, error) {
 	return cfg, nil
 }
 
+func withResumeCycle(resume bool, dhts ...uint8) Option {
+	return func(cfg *config) error {
+		for _, dht := range dhts {
+			cfg.resumeCycle[dht] = resume
+		}
+		return nil
+	}
+}
+
+func WithResumeCycle(resume bool) Option {
+	return withResumeCycle(resume, lanID, wanID)
+}
+
+func WithResumeCycleLAN(resume bool) Option {
+	return withResumeCycle(resume, lanID)
+}
+
+func WithResumeCycleWAN(resume bool) Option {
+	return withResumeCycle(resume, wanID)
+}
+
 func WithKeystore(ks keystore.Keystore) Option {
 	return func(cfg *config) error {
 		if ks == nil {
diff --git a/provider/dual/provider.go b/provider/dual/provider.go
index 9d6f747..28d626c 100644
--- a/provider/dual/provider.go
+++ b/provider/dual/provider.go
@@ -64,6 +64,7 @@ func New(d *dual.DHT, opts ...Option) (*SweepingProvider, error) {
 			provider.WithAddLocalRecord(func(h mh.Multihash) error {
 				return dht.Provide(dht.Context(), cid.NewCidV1(cid.Raw, h), false)
 			}),
+			provider.WithResumeCycle(cfg.resumeCycle[i]),
 			provider.WithKeystore(cfg.keystore),
 			provider.WithMessageSender(cfg.msgSenders[i]),
 			provider.WithReprovideInterval(cfg.reprovideInterval[i]),
diff --git a/provider/internal/keyspace/key.go b/provider/internal/keyspace/key.go
index 4b5c426..07e72a6 100644
--- a/provider/internal/keyspace/key.go
+++ b/provider/internal/keyspace/key.go
@@ -1,3 +1,5 @@
+// Package keyspace provides utilities for Kademlia keyspace operations,
+// including keys, prefixes, and trie operations.
 package keyspace
 
 import (
diff --git a/provider/internal/keyspace/trie.go b/provider/internal/keyspace/trie.go
index 5a8ed90..485cc70 100644
--- a/provider/internal/keyspace/trie.go
+++ b/provider/internal/keyspace/trie.go
@@ -17,16 +17,16 @@ var zeroKey = bit256.ZeroKey()
 
 // AllEntries returns all entries (key + value) stored in the trie `t` sorted
 // by their keys in the supplied `order`.
-func AllEntries[K0 kad.Key[K0], K1 kad.Key[K1], D any](t *trie.Trie[K0, D], order K1) []*trie.Entry[K0, D] {
+func AllEntries[K0 kad.Key[K0], K1 kad.Key[K1], D any](t *trie.Trie[K0, D], order K1) []trie.Entry[K0, D] {
 	return allEntriesAtDepth(t, order, 0)
 }
 
-func allEntriesAtDepth[K0 kad.Key[K0], K1 kad.Key[K1], D any](t *trie.Trie[K0, D], order K1, depth int) []*trie.Entry[K0, D] {
+func allEntriesAtDepth[K0 kad.Key[K0], K1 kad.Key[K1], D any](t *trie.Trie[K0, D], order K1, depth int) []trie.Entry[K0, D] {
 	if t == nil || t.IsEmptyLeaf() {
 		return nil
 	}
 	if t.IsNonEmptyLeaf() {
-		return []*trie.Entry[K0, D]{{Key: *t.Key(), Data: t.Data()}}
+		return []trie.Entry[K0, D]{{Key: *t.Key(), Data: t.Data()}}
 	}
 	b := int(order.Bit(depth))
 	return append(allEntriesAtDepth(t.Branch(b), order, depth+1),
@@ -188,6 +188,109 @@ func pruneSubtrieAtDepth[K0 kad.Key[K0], K1 kad.Key[K1], D any](t *trie.Trie[K0,
 	return false
 }
 
+// CoalesceTrie merges sibling keys into their parent prefix recursively. When
+// two keys in the trie differ only in their last bit (e.g., "1100" and "1101"),
+// they are replaced by their common parent prefix (e.g., "110"). This process
+// continues recursively until no more sibling pairs exist, reducing the trie to
+// its minimal prefix coverage.
+// Data associated with coalesced keys is discarded.
+func CoalesceTrie[D any](t *trie.Trie[bitstr.Key, D]) {
+	if t == nil || t.IsLeaf() {
+		return
+	}
+	branches := [2]*trie.Trie[bitstr.Key, D]{t.Branch(0), t.Branch(1)}
+	for _, b := range branches {
+		if b != nil && !b.IsLeaf() {
+			CoalesceTrie(b)
+		}
+	}
+	if branches[0].IsNonEmptyLeaf() && branches[1].IsNonEmptyLeaf() {
+		keys := [2]bitstr.Key{*branches[0].Key(), *branches[1].Key()}
+		l := keys[0].BitLen() - 1
+		if keys[0].BitLen() == keys[1].BitLen() && keys[0].CommonPrefixLength(keys[1]) == l {
+			// Remove siblings from self (parent), and set common prefix as key.
+			*t = trie.Trie[bitstr.Key, D]{}
+			parentKey := keys[0][:l]
+			var d D
+			t.Add(parentKey, d)
+		}
+	}
+}
+
+// SubtractTrie returns a new trie containing all entries from trie `t0` that
+// are not covered by any prefix in trie `t1`. This performs a set subtraction
+// operation (t0 - t1) where keys in `t0` are excluded if they match or are
+// prefixed by any key in `t1`.
+//
+// For example:
+//   - t0: ["0000", "0010", "0100"]
+//   - t1: ["00"]
+//   - Result: ["0100"]
+//
+// The subtraction is prefix-aware: if `t1` contains "00", all keys in `t0`
+// starting with "00" (like "0000" and "0010") are excluded from the result.
+func SubtractTrie[D0, D1 any](t0 *trie.Trie[bitstr.Key, D0], t1 *trie.Trie[bitstr.Key, D1]) *trie.Trie[bitstr.Key, D0] {
+	res := trie.New[bitstr.Key, D0]()
+	subtractTrieAtDepth(t0, t1, res, 0)
+	return res
+}
+
+// subtractTrieAtDepth recursively performs trie subtraction (t0 - t1) at the
+// specified depth, adding entries from `t0` to `res` that are not covered by
+// prefixes in `t1`. The `depth` parameter tracks the current bit position being
+// examined during the traversal.
+func subtractTrieAtDepth[D0, D1 any](t0 *trie.Trie[bitstr.Key, D0],
+	t1 *trie.Trie[bitstr.Key, D1], res *trie.Trie[bitstr.Key, D0], depth int,
+) {
+	if t0 == nil || t0.IsEmptyLeaf() {
+		return
+	}
+	if t1 == nil || t1.IsEmptyLeaf() {
+		// t1 is empty, nothing to subtract, add all t0 to result.
+		res.AddMany(AllEntries(t0, bit256.ZeroKey())...)
+		return
+	}
+
+	if t0.HasKey() && t1.HasKey() {
+		// Both t0 and t1 are leaves.
+		k0, k1 := *t0.Key(), *t1.Key()
+		if !IsBitstrPrefix(k1, k0) {
+			res.Add(k0, t0.Data())
+		}
+		return
+	}
+	if t0.HasKey() && !t1.HasKey() {
+		// t0 is a leaf, but t1 is not.
+		k0 := t0.Key()
+		if k0.BitLen() <= depth {
+			res.Add(*k0, t0.Data())
+			return
+		}
+		b := int(k0.Bit(depth))
+		// Go deeper in t1's branch that could cover t0's key.
+		subtractTrieAtDepth(t0, t1.Branch(b), res, depth+1)
+		return
+	}
+	if t1.HasKey() && !t0.HasKey() {
+		// t1 is a leaf, but t0 is not.
+		k1 := t1.Key()
+		if k1.BitLen() <= depth {
+			// t1 covers all entries in t0, nothing to add.
+			return
+		}
+		b := int(k1.Bit(depth))
+		// Add all entries in t0's branch that is not covered by t1.
+		res.AddMany(AllEntries(t0.Branch(1-b), bit256.ZeroKey())...)
+		// Go deeper in the branch covered by t1.
+		subtractTrieAtDepth(t0.Branch(b), t1, res, depth+1)
+		return
+	}
+	// Both t0 and t1 are not leaves.
+	for i := range 2 {
+		subtractTrieAtDepth(t0.Branch(i), t1.Branch(i), res, depth+1)
+	}
+}
+
 // TrieGaps returns all prefixes that aren't covered by a key (prefix) in the
 // trie, at the `target` location. Combining the prefixes included in the trie
 // with the gap prefixes results in a full keyspace coverage of the `target`
diff --git a/provider/internal/queue/prefix.go b/provider/internal/queue/prefix.go
index d561a0e..7bf12df 100644
--- a/provider/internal/queue/prefix.go
+++ b/provider/internal/queue/prefix.go
@@ -27,17 +27,19 @@ type prefixQueue struct {
 // supplied prefix at the position of the first superstring in the queue, and
 // remove all superstrings from the queue. The prefixes are consolidated around
 // the shortest prefix.
-func (q *prefixQueue) Push(prefix bitstr.Key) {
-	if firstRemovedIndex := q.removeSuperstrings(prefix); firstRemovedIndex >= 0 {
-		// `prefix` has superstrings in the queue. Remove them all and insert
-		// `prefix` in the queue at the location of the first removed superstring.
-		q.queue.Insert(firstRemovedIndex, prefix)
-		// Add `prefix` to prefixes trie.
-		q.prefixes.Add(prefix, struct{}{})
-	} else if _, ok := keyspace.FindPrefixOfKey(q.prefixes, prefix); !ok {
-		// No prefixes nor superstrings of `prefix` found in the queue.
-		q.queue.PushBack(prefix)
-		q.prefixes.Add(prefix, struct{}{})
+func (q *prefixQueue) Push(prefixes ...bitstr.Key) {
+	for _, prefix := range prefixes {
+		if firstRemovedIndex := q.removeSuperstrings(prefix); firstRemovedIndex >= 0 {
+			// `prefix` has superstrings in the queue. Remove them all and insert
+			// `prefix` in the queue at the location of the first removed superstring.
+			q.queue.Insert(firstRemovedIndex, prefix)
+			// Add `prefix` to prefixes trie.
+			q.prefixes.Add(prefix, struct{}{})
+		} else if _, ok := keyspace.FindPrefixOfKey(q.prefixes, prefix); !ok {
+			// No prefixes nor superstrings of `prefix` found in the queue.
+			q.queue.PushBack(prefix)
+			q.prefixes.Add(prefix, struct{}{})
+		}
 	}
 }
 
diff --git a/provider/internal/queue/provide.go b/provider/internal/queue/provide.go
index 4b1f8fa..52ea5c2 100644
--- a/provider/internal/queue/provide.go
+++ b/provider/internal/queue/provide.go
@@ -215,13 +215,61 @@ func (q *ProvideQueue) Persist(ctx context.Context, d ds.Batching, batchSize int
 	q.mu.Lock()
 	defer q.mu.Unlock()
 
-	// Create a batch for efficient writes
+	commitBatchIfFull := func(b *ds.Batch, size int) error {
+		if size%batchSize == 0 {
+			// Max batch size reached, commit and start a new batch.
+			if err := (*b).Commit(ctx); err != nil {
+				return fmt.Errorf("failed to commit batch: %w", err)
+			}
+			newBatch, err := d.Batch(ctx)
+			if err != nil {
+				return fmt.Errorf("failed to create batch: %w", err)
+			}
+			*b = newBatch
+		}
+		return nil
+	}
+	finalCommit := func(b ds.Batch, size int) error {
+		if size%batchSize != 0 {
+			if err := b.Commit(ctx); err != nil {
+				return fmt.Errorf("failed to commit batch: %w", err)
+			}
+		}
+		return nil
+	}
+
+	// Remove all existing persisted entries first.
 	batch, err := d.Batch(ctx)
 	if err != nil {
 		return fmt.Errorf("failed to create batch: %w", err)
 	}
-
+	res, err := d.Query(ctx, query.Query{KeysOnly: true})
+	if err != nil {
+		return fmt.Errorf("failed to query datastore: %w", err)
+	}
+	defer res.Close()
 	i := 0
+	for r := range res.Next() {
+		if r.Error != nil {
+			return fmt.Errorf("error reading query result: %w", r.Error)
+		}
+		batch.Delete(ctx, ds.NewKey(r.Key))
+		i++
+		if err := commitBatchIfFull(&batch, i); err != nil {
+			return err
+		}
+	}
+	if err := finalCommit(batch, i); err != nil {
+		return err
+	}
+
+	// Batch writes
+	batch, err = d.Batch(ctx)
+	if err != nil {
+		return fmt.Errorf("failed to create batch: %w", err)
+	}
+
+	i = 0
 	for prefix := range q.queue.queue.Iter() {
 		// Find all keys matching this prefix
 		if subtrie, ok := keyspace.FindSubtrie(q.keys, prefix); ok {
@@ -239,25 +287,15 @@ func (q *ProvideQueue) Persist(ctx context.Context, d ds.Batching, batchSize int
 				return fmt.Errorf("failed to store prefix data: %w", err)
 			}
 		}
-
 		i++
-
-		if i%batchSize == 0 {
-			// Max batch size reached, commit and start a new batch.
-			if err := batch.Commit(ctx); err != nil {
-				return fmt.Errorf("failed to commit batch: %w", err)
-			}
-			batch, err = d.Batch(ctx)
-			if err != nil {
-				return fmt.Errorf("failed to create batch: %w", err)
-			}
+		if err := commitBatchIfFull(&batch, i); err != nil {
+			return err
 		}
 	}
 
-	if err := batch.Commit(ctx); err != nil {
-		return fmt.Errorf("failed to commit batch: %w", err)
+	if err := finalCommit(batch, i); err != nil {
+		return err
 	}
-
 	return nil
 }
 
diff --git a/provider/internal/queue/reprovide.go b/provider/internal/queue/reprovide.go
index 666b03a..1516039 100644
--- a/provider/internal/queue/reprovide.go
+++ b/provider/internal/queue/reprovide.go
@@ -27,10 +27,10 @@ func NewReprovideQueue() *ReprovideQueue {
 // supplied prefix at the position of the first superstring in the queue, and
 // remove all superstrings from the queue. The prefixes are consolidated around
 // the shortest prefix.
-func (q *ReprovideQueue) Enqueue(prefix bitstr.Key) {
+func (q *ReprovideQueue) Enqueue(prefixes ...bitstr.Key) {
 	q.mu.Lock()
 	defer q.mu.Unlock()
-	q.queue.Push(prefix)
+	q.queue.Push(prefixes...)
 }
 
 // Dequeue removes and returns the first prefix from the queue.
diff --git a/provider/options.go b/provider/options.go
index 84ece16..e684f38 100644
--- a/provider/options.go
+++ b/provider/options.go
@@ -57,7 +57,8 @@ type config struct {
 	dedicatedBurstWorkers    int
 	maxProvideConnsPerWorker int
 
-	loggerName string
+	resumeCycle bool
+	loggerName  string
 }
 
 type Option func(opt *config) error
@@ -78,6 +79,8 @@ func getOpts(opts []Option) (config, error) {
 		maxProvideConnsPerWorker: 20,
 
 		addLocalRecord: func(mh mh.Multihash) error { return nil },
+
+		resumeCycle: true,
 	}
 
 	// Apply options
@@ -300,6 +303,25 @@ func WithDatastore(ds datastore.Batching) Option {
 	}
 }
 
+// WithResumeCycle sets whether the reprovider should resume the previous
+// reprovide cycle from where it left off when the node was last shut down.
+//
+// When set to true (default), the provider will restore its state from the
+// datastore and continue reproviding regions according to their previous
+// schedule. This ensures continuity across node restarts and prevents gaps
+// in provider record availability.
+//
+// When set to false, the provider starts a fresh reprovide cycle, ignoring
+// any previously persisted state. All regions will be scheduled for
+// reprovision from scratch. This is useful for testing or when you want to
+// reset the reprovide schedule.
+func WithResumeCycle(resume bool) Option {
+	return func(cfg *config) error {
+		cfg.resumeCycle = resume
+		return nil
+	}
+}
+
 // WithLoggerName sets the go-log logger name for the DHT provider.
 func WithLoggerName(name string) Option {
 	return func(cfg *config) error {
diff --git a/provider/provider.go b/provider/provider.go
index ad2f582..99daf9d 100644
--- a/provider/provider.go
+++ b/provider/provider.go
@@ -21,7 +21,9 @@ import (
 	"context"
 	"errors"
 	"fmt"
+	"path"
 	"strconv"
+	"strings"
 	"sync"
 	"sync/atomic"
 	"time"
@@ -32,6 +34,8 @@ import (
 
 	ds "github.com/ipfs/go-datastore"
 	"github.com/ipfs/go-datastore/namespace"
+	"github.com/ipfs/go-datastore/query"
+	dssync "github.com/ipfs/go-datastore/sync"
 	"github.com/ipfs/go-log/v2"
 	"github.com/ipfs/go-test/random"
 	"github.com/libp2p/go-libp2p/core/peer"
@@ -95,6 +99,10 @@ const (
 	// minimalRegionReachablePeersRatio is the minimum ratio of reachable peers
 	// in a region for the provide to be considered a success.
 	minimalRegionReachablePeersRatio float32 = 0.2
+
+	// providerDatastoreNamespace is the namespace in the datastore where
+	// provider data is stored.
+	providerDatastoreNamespace string = "provider"
 )
 
 var (
@@ -105,6 +113,13 @@ var (
 	// performed as usual, but keys aren't added to provide queue nor advertised
 	// to the network.
 	ErrOffline = errors.New("provider: offline")
+
+	// reprovideHistoryKeyPrefix is the prefix for keys storing the timestamp of
+	// the last reprovide for a given region in the datastore.
+	reprovideHistoryKeyPrefix = path.Join(providerDatastoreNamespace, "history")
+	// reprovideCycleStartKey is the key storing the start time of the initial
+	// reprovide cycle.
+	reprovideCycleStartKey = ds.NewKey(path.Join(providerDatastoreNamespace, "cycle_start"))
 )
 
 type KadClosestPeersRouter interface {
@@ -136,6 +151,10 @@ type SweepingProvider struct {
 
 	keystore keystore.Keystore
 
+	datastore              ds.Batching
+	lastReprovideHistoryGC atomic.Int64
+	resumeReprovidesOnce   sync.Once
+
 	replicationFactor int
 
 	provideQueue         *queue.ProvideQueue
@@ -146,6 +165,7 @@ type SweepingProvider struct {
 	workerPool               *pool.Pool[workerType]
 	maxProvideConnsPerWorker int
 
+	startedAt         time.Time
 	cycleStart        time.Time
 	reprovideInterval time.Duration
 	maxReprovideDelay time.Duration
@@ -185,10 +205,10 @@ func New(opts ...Option) (*SweepingProvider, error) {
 	}
 	cleanupFuncs := []func() error{}
 
-	var mapDs *ds.MapDatastore
+	var mapDs ds.Batching
 	if cfg.keystore == nil {
 		// Setup KeyStore if missing
-		mapDs = ds.NewMapDatastore()
+		mapDs = dssync.MutexWrap(ds.NewMapDatastore())
 		cleanupFuncs = append(cleanupFuncs, mapDs.Close)
 		cfg.keystore, err = keystore.NewKeystore(mapDs)
 		if err != nil {
@@ -200,7 +220,7 @@ func New(opts ...Option) (*SweepingProvider, error) {
 	if cfg.datastore == nil {
 		// Setup datastore if missing
 		if mapDs == nil {
-			mapDs = ds.NewMapDatastore()
+			mapDs = dssync.MutexWrap(ds.NewMapDatastore())
 			cleanupFuncs = append(cleanupFuncs, mapDs.Close)
 		}
 		cfg.datastore = mapDs
@@ -256,13 +276,12 @@ func New(opts ...Option) (*SweepingProvider, error) {
 		avgPrefixLenValidity: defaultPrefixLenValidity,
 		cachedAvgPrefixLen:   -1,
 
-		cycleStart: time.Now(),
-
 		msgSender:      cfg.msgSender,
 		getSelfAddrs:   cfg.selfAddrs,
 		addLocalRecord: cfg.addLocalRecord,
 
-		keystore: cfg.keystore,
+		keystore:  cfg.keystore,
+		datastore: cfg.datastore,
 
 		schedule:      trie.New[bitstr.Key, time.Duration](),
 		scheduleTimer: time.NewTimer(time.Hour),
@@ -276,31 +295,97 @@ func New(opts ...Option) (*SweepingProvider, error) {
 		logger:         log.Logger(cfg.loggerName),
 		stats:          newOperationStats(cfg.reprovideInterval, cfg.maxReprovideDelay),
 	}
-	// Set up callbacks after both provider and connectivity checker are initialized
-	// This breaks the circular dependency between connectivity, onOnline, and approxPrefixLen
-	prov.connectivity.SetCallbacks(prov.onOnline, prov.onOffline)
-	prov.connectivity.Start()
-
-	pqueueDs := namespace.Wrap(cfg.datastore, ds.NewKey("pqueue"))
-	// Load keys that were logged to the datastore back to the provide queue.
-	if err := prov.provideQueue.DrainDatastore(ctx, pqueueDs); err != nil {
-		prov.logger.Errorw("failed to drain provide queue from datastore", "error", err)
-	}
 
 	// Provide queue is persisted on close, reuse keystore batch size.
+	pqueueDs := namespace.Wrap(cfg.datastore, ds.NewKey("pqueue"))
 	batchSize := prov.keystore.BatchSize()
 	persistProvideQueue := func() error { return prov.provideQueue.Persist(ctx, pqueueDs, batchSize) }
 	prov.cleanupFuncs = append(prov.cleanupFuncs, prov.workerPool.Close, persistProvideQueue)
 
+	if cfg.resumeCycle {
+		// Restore reprovide cycle start time from datastore or initialize it.
+		prov.setCycleStart()
+
+		// Load keys that were saved to the datastore back to the provide queue.
+		if err := prov.provideQueue.DrainDatastore(ctx, pqueueDs); err != nil {
+			prov.logger.Errorw("failed to drain provide queue from datastore", "error", err)
+		}
+	}
+
 	// Don't need to start schedule timer yet
 	prov.scheduleTimer.Stop()
 
+	// Set up callbacks after both provider and connectivity checker are initialized
+	// This breaks the circular dependency between connectivity, onOnline, and approxPrefixLen
+	prov.connectivity.SetCallbacks(prov.onOnline, prov.onOffline)
+	prov.connectivity.Start()
+
 	prov.wg.Add(1)
 	go prov.run()
 
 	return prov, nil
 }
 
+// initFromPersistedState initializes the provider from persisted state on
+// startup. It restores the reprovide cycle start time and enqueues any regions
+// that expired during downtime for immediate reproviding.
+func (s *SweepingProvider) setCycleStart() {
+	now := time.Now()
+	cycleStart, err := s.readCycleStart()
+	if err != nil || cycleStart.IsZero() {
+		// cycle start time is zero on initial run.
+		if err != nil {
+			s.logger.Warnf("couldn't read cycle start time: %s", err)
+		}
+		s.writeCycleStart(now)
+		cycleStart = now
+	}
+	s.startedAt = now
+	s.cycleStart = cycleStart
+}
+
+// writeCycleStart persists the reprovide cycle start time to the datastore.
+func (s *SweepingProvider) writeCycleStart(t time.Time) error {
+	return s.datastore.Put(s.ctx, reprovideCycleStartKey, []byte(formatTimestampHex(t)))
+}
+
+// readCycleStart reads the reprovide cycle start time from the datastore.
+// Returns a zero time if the key is not found (first run).
+func (s *SweepingProvider) readCycleStart() (time.Time, error) {
+	v, err := s.datastore.Get(s.ctx, reprovideCycleStartKey)
+	if err != nil {
+		if errors.Is(err, ds.ErrNotFound) {
+			// Initial run, no cycle start time stored yet.
+			return time.Time{}, nil
+		}
+		return time.Time{}, err
+	}
+	t, err := parseTimestampHex(string(v))
+	if err != nil {
+		return time.Time{}, err
+	}
+	return t, nil
+}
+
+// formatTimestampHex returns a hex representation of the given timestamp,
+// suitable for lexicographical ordering.
+//
+// 8 hex digits = 32 bits, valid until year 2106.
+func formatTimestampHex(t time.Time) string {
+	return fmt.Sprintf("%08x", t.Unix())
+}
+
+// parseTimestampHex parses a hex representation of a timestamp as returned by
+// formatTimestampHex.
+func parseTimestampHex(s string) (time.Time, error) {
+	var ts int64
+	_, err := fmt.Sscanf(s, "%x", &ts)
+	if err != nil {
+		return time.Time{}, err
+	}
+	return time.Unix(ts, 0), nil
+}
+
 func (s *SweepingProvider) run() {
 	defer s.wg.Done()
 
@@ -415,7 +500,7 @@ func (s *SweepingProvider) schedulePrefixNoLock(prefix bitstr.Key, justReprovide
 		// The key following prefix is the schedule cursor.
 		timeUntilPrefixReprovide := s.timeUntil(nextReprovideTime)
 		_, scheduledAlarm := trie.Find(s.schedule, s.scheduleCursor)
-		if timeUntilPrefixReprovide < s.timeUntil(scheduledAlarm) {
+		if timeUntilPrefixReprovide < s.timeUntil(scheduledAlarm)%s.reprovideInterval {
 			s.scheduleNextReprovideNoLock(prefix, timeUntilPrefixReprovide)
 		}
 	}
@@ -501,6 +586,21 @@ func (s *SweepingProvider) reprovideTimeForPrefix(prefix bitstr.Key) time.Durati
 	return time.Duration(int64(s.reprovideInterval) * val / maxInt)
 }
 
+// nextPrefixToReprovideNoLock returns the next prefix to reprovide, based on
+// the current time offset.
+func (s *SweepingProvider) nextPrefixToReprovideNoLock(offset time.Duration) (bitstr.Key, error) {
+	maxVal := 1 << maxPrefixSize
+	// Division before multiplication to avoid integer overflow. This is why we
+	// need to use float.
+	intPrefix := uint64(float64(offset) / float64(s.reprovideInterval) * float64(maxVal))
+	prefix := bitstr.Key(fmt.Sprintf("%0*b", maxPrefixSize, int64(intPrefix)))
+	nextRegion := keyspace.NextNonEmptyLeaf(s.schedule, prefix, s.order)
+	if nextRegion == nil {
+		return "", errors.New("schedule is empty")
+	}
+	return nextRegion.Key, nil
+}
+
 // approxPrefixLen makes a few GetClosestPeers calls to get an estimate
 // of the prefix length to be used in the network.
 //
@@ -885,13 +985,13 @@ func (s *SweepingProvider) handleReprovide() {
 			// reprovideInterval.
 			nextKeyFound := false
 			scheduleEntries := keyspace.AllEntries(s.schedule, s.order)
-			next = scheduleEntries[0]
+			next = &scheduleEntries[0]
 			for _, entry := range scheduleEntries {
 				// Add all regions from the schedule to the reprovide queue. The next
 				// region to be scheduled for reprovide is the one immediately
 				// following the current time offset in the schedule.
 				if !nextKeyFound && entry.Data > currentTimeOffset {
-					next = entry
+					next = &entry
 					nextKeyFound = true
 				}
 				s.reprovideQueue.Enqueue(entry.Key)
@@ -938,7 +1038,7 @@ func (s *SweepingProvider) handleReprovide() {
 	s.wg.Add(1)
 	go func() {
 		if err := s.workerPool.Acquire(periodicWorker); err == nil {
-			s.batchReprovide(currentPrefix, true)
+			s.batchReprovide(currentPrefix)
 			s.workerPool.Release(periodicWorker)
 		}
 		s.wg.Done()
@@ -1073,11 +1173,143 @@ func (s *SweepingProvider) onOnline() {
 		s.approxPrefixLenRunning.Unlock()
 
 		s.RefreshSchedule()
+
+		// When the node initially comes online, add all regions that weren't
+		// reprovided in the last reprovideInterval to the reprovide queue.
+		s.resumeReprovidesOnce.Do(func() {
+			now := time.Now()
+			currentOffset := s.timeOffset(now)
+			recentlyReprovided, err := s.loadRecentlyReprovidedRegions(now)
+			s.scheduleLk.Lock()
+			if err == nil {
+				s.enqueueExpiredRegionsNoLock(recentlyReprovided)
+			} else {
+				s.logger.Warnf("couldn't load not expired regions: %s", err)
+			}
+			if nextPrefix, err := s.nextPrefixToReprovideNoLock(currentOffset); err == nil {
+				timeUntilReprovide := s.timeUntil(s.reprovideTimeForPrefix(nextPrefix)) % s.reprovideInterval
+				s.scheduleNextReprovideNoLock(nextPrefix, timeUntilReprovide)
+			}
+			s.scheduleLk.Unlock()
+		})
 	}
 
 	s.catchupPendingWork()
 }
 
+// enqueueExpiredRegionsNoLock identifies regions in the schedule that haven't
+// been reprovided within the reprovide interval and adds them to the reprovide
+// queue. Assumes the schedule lock is held.
+func (s *SweepingProvider) enqueueExpiredRegionsNoLock(recentlyReprovided *trie.Trie[bitstr.Key, struct{}]) {
+	keyspace.CoalesceTrie(recentlyReprovided)
+	// Take a copy of schedule from which we remove recently reprovided regions.
+	toReprovideTrie := keyspace.SubtractTrie(s.schedule, recentlyReprovided)
+	toReprovideEntries := keyspace.AllEntries(toReprovideTrie, s.order)
+	toReprovideKeys := make([]bitstr.Key, len(toReprovideEntries))
+	for i, entry := range toReprovideEntries {
+		toReprovideKeys[i] = entry.Key
+	}
+	s.reprovideQueue.Enqueue(toReprovideKeys...)
+}
+
+// persistSuccessfulReprovide logs a successful reprovide to the datastore for
+// resumption after restarts.
+func (s *SweepingProvider) persistSuccessfulReprovide(prefix bitstr.Key) {
+	now := time.Now()
+	k := ds.NewKey(path.Join(reprovideHistoryKeyPrefix, formatTimestampHex(now), string(prefix)))
+	if err := s.datastore.Put(s.ctx, k, []byte{}); err != nil {
+		s.logger.Warnf("couldn't persist successful reprovide for prefix %s: %s", prefix, err)
+	}
+	s.gcReprovideHistoryIfNeeded(now)
+}
+
+// loadRecentlyReprovidedRegions loads all regions that have been successfully
+// reprovided within the last reprovide interval from the datastore.
+func (s *SweepingProvider) loadRecentlyReprovidedRegions(now time.Time) (*trie.Trie[bitstr.Key, struct{}], error) {
+	s.gcReprovideHistoryIfNeeded(now)
+
+	q := query.Query{
+		Prefix:   reprovideHistoryKeyPrefix,
+		Orders:   []query.Order{query.OrderByKey{}},
+		KeysOnly: true,
+	}
+	res, err := s.datastore.Query(s.ctx, q)
+	if err != nil {
+		return nil, err
+	}
+	regions := trie.New[bitstr.Key, struct{}]()
+	for r := range res.Next() {
+		if r.Error != nil {
+			return nil, r.Error
+		}
+		_, key, err := parseReprovideHistoryKey(r.Key)
+		if err != nil {
+			s.datastore.Delete(s.ctx, ds.NewKey(r.Key))
+			continue
+		}
+		regions.Add(key, struct{}{})
+	}
+	return regions, nil
+}
+
+// gcReprovideHistoryIfNeeded removes reprovide log entries older than the
+// reprovide interval. GC runs at most once per reprovide interval.
+func (s *SweepingProvider) gcReprovideHistoryIfNeeded(now time.Time) {
+	lastGC := time.Unix(s.lastReprovideHistoryGC.Load(), 0)
+	if now.Sub(lastGC) < s.reprovideInterval {
+		// Only run GC once per reprovide interval.
+		return
+	}
+
+	q := query.Query{
+		Prefix:   reprovideHistoryKeyPrefix,
+		Orders:   []query.Order{query.OrderByKey{}},
+		KeysOnly: true,
+	}
+	deadline := now.Add(-s.reprovideInterval)
+	res, err := s.datastore.Query(s.ctx, q)
+	if err != nil {
+		s.logger.Warnf("couldn't query reprovide history for gc: %s", err)
+		return
+	}
+	for r := range res.Next() {
+		if r.Error != nil {
+			s.logger.Warnf("couldn't query reprovide history for gc: %s", r.Error)
+			return
+		}
+		k := r.Key
+		t, _, err := parseReprovideHistoryKey(k)
+		if err == nil && t.After(deadline) {
+			// Reached non-expired entries; cleanup complete as keys are sorted by
+			// time.
+			break
+		}
+		// Either key is invalid or log is expired, delete key.
+		s.datastore.Delete(s.ctx, ds.NewKey(k))
+	}
+	s.lastReprovideHistoryGC.Store(now.Unix())
+}
+
+// parseReprovideLogKey parses a datastore key from the reprovide history log.
+// Expected format: /provider/history/<hex-timestamp>/<prefix>
+func parseReprovideHistoryKey(k string) (time.Time, bitstr.Key, error) {
+	parts := strings.Split(k, "/")
+	lenParts := len(parts)
+	if lenParts < 4 || lenParts > 5 {
+		return time.Time{}, "", fmt.Errorf("invalid reprovide log key: %s", k)
+	}
+	t, err := parseTimestampHex(parts[3])
+	if err != nil {
+		return time.Time{}, "", fmt.Errorf("invalid reprovide log key: %s", k)
+	}
+	var prefix bitstr.Key
+	if lenParts == 5 {
+		prefix = bitstr.Key(parts[4])
+	}
+	// lenParts == 4 means empty prefix ("").
+	return t, prefix, nil
+}
+
 // catchupPendingWork is called when the provider comes back online after being offline.
 //
 // 1. Try again to reprovide regions that failed to be reprovided on time.
@@ -1169,7 +1401,7 @@ func (s *SweepingProvider) reprovideLateRegions() {
 		if ok {
 			s.wg.Add(1)
 			go func(prefix bitstr.Key) {
-				s.batchReprovide(prefix, false)
+				s.batchReprovide(prefix)
 				s.workerPool.Release(burstWorker)
 				s.wg.Done()
 			}(prefix)
@@ -1202,7 +1434,7 @@ func (s *SweepingProvider) batchProvide(prefix bitstr.Key, keys []mh.Multihash)
 	if keyCount <= individualProvideThreshold {
 		// Don't fully explore the region, execute simple DHT provides for these
 		// keys. It isn't worth it to fully explore a region for just a few keys.
-		s.individualProvide(prefix, keys, false, false)
+		s.individualProvide(prefix, keys, false)
 		return
 	}
 
@@ -1222,12 +1454,12 @@ func (s *SweepingProvider) batchProvide(prefix bitstr.Key, keys []mh.Multihash)
 	}
 	regions = keyspace.AssignKeysToRegions(regions, keys)
 
-	if !s.provideRegions(regions, addrInfo, false, false) {
+	if !s.provideRegions(regions, addrInfo, false) {
 		s.logger.Warnf("failed to provide any region for prefix %s", prefix)
 	}
 }
 
-func (s *SweepingProvider) batchReprovide(prefix bitstr.Key, periodicReprovide bool) {
+func (s *SweepingProvider) batchReprovide(prefix bitstr.Key) {
 	addrInfo, ok := s.selfAddrInfo()
 	if !ok {
 		// Don't provide if the node doesn't have a valid address to include in the
@@ -1239,9 +1471,7 @@ func (s *SweepingProvider) batchReprovide(prefix bitstr.Key, periodicReprovide b
 	keys, err := s.keystore.Get(s.ctx, prefix)
 	if err != nil {
 		s.failedReprovide(prefix, fmt.Errorf("couldn't reprovide, error when loading keys: %s", err))
-		if periodicReprovide {
-			s.reschedulePrefix(prefix)
-		}
+		s.reschedulePrefix(prefix)
 		return
 	}
 	keyCount := len(keys)
@@ -1260,16 +1490,14 @@ func (s *SweepingProvider) batchReprovide(prefix bitstr.Key, periodicReprovide b
 	if keyCount <= individualProvideThreshold {
 		// Don't fully explore the region, execute simple DHT provides for these
 		// keys. It isn't worth it to fully explore a region for just a few keys.
-		s.individualProvide(prefix, keys, true, periodicReprovide)
+		s.individualProvide(prefix, keys, true)
 		return
 	}
 
 	regions, coveredPrefix, err := s.exploreSwarm(prefix)
 	if err != nil {
 		s.failedReprovide(prefix, fmt.Errorf("reprovide '%s': %w", prefix, err))
-		if periodicReprovide {
-			s.reschedulePrefix(prefix)
-		}
+		s.reschedulePrefix(prefix)
 		return
 	}
 	s.logger.Debugf("reprovide: requested prefix '%s' (len %d), prefix covered '%s' (len %d)", prefix, len(prefix), coveredPrefix, len(coveredPrefix))
@@ -1296,15 +1524,16 @@ func (s *SweepingProvider) batchReprovide(prefix bitstr.Key, periodicReprovide b
 		if err != nil {
 			err = fmt.Errorf("couldn't reprovide, error when loading keys: %s", err)
 			s.failedReprovide(prefix, err)
-			if periodicReprovide {
-				s.reschedulePrefix(prefix)
-			}
+			s.reschedulePrefix(prefix)
 		}
 		s.stats.ongoingReprovides.addKeys(len(keys) - keyCount)
+		prefix = coveredPrefix
 	}
 	regions = keyspace.AssignKeysToRegions(regions, keys)
 
-	if !s.provideRegions(regions, addrInfo, true, periodicReprovide) {
+	if s.provideRegions(regions, addrInfo, true) {
+		s.persistSuccessfulReprovide(prefix)
+	} else {
 		s.logger.Warnf("failed to reprovide any region for prefix %s", prefix)
 	}
 }
@@ -1343,7 +1572,7 @@ func (s *SweepingProvider) selfAddrInfo() (peer.AddrInfo, bool) {
 // without exploring the associated keyspace regions. It performs "normal" DHT
 // provides for the supplied keys, handles failures and schedules next
 // reprovide is necessary.
-func (s *SweepingProvider) individualProvide(prefix bitstr.Key, keys []mh.Multihash, reprovide bool, periodicReprovide bool) {
+func (s *SweepingProvider) individualProvide(prefix bitstr.Key, keys []mh.Multihash, reprovide bool) {
 	if len(keys) == 0 {
 		return
 	}
@@ -1351,17 +1580,17 @@ func (s *SweepingProvider) individualProvide(prefix bitstr.Key, keys []mh.Multih
 	var provideErr error
 	if len(keys) == 1 {
 		coveredPrefix, err := s.vanillaProvide(keys[0], reprovide)
+		// Schedule next reprovide for the prefix that was actually covered by
+		// the GCP, otherwise we may schedule a reprovide for a prefix too short
+		// or too long.
 		if err != nil && !reprovide {
 			// Put the key back in the provide queue.
 			s.failedProvide(prefix, keys, fmt.Errorf("individual provide failed for prefix '%s', %w", prefix, err))
 		}
-		provideErr = err
-		if periodicReprovide {
-			// Schedule next reprovide for the prefix that was actually covered by
-			// the GCP, otherwise we may schedule a reprovide for a prefix too short
-			// or too long.
-			s.reschedulePrefix(coveredPrefix)
+		if reprovide && err == nil {
+			prefix = coveredPrefix
 		}
+		provideErr = err
 	} else {
 		wg := sync.WaitGroup{}
 		success := atomic.Bool{}
@@ -1384,19 +1613,21 @@ func (s *SweepingProvider) individualProvide(prefix bitstr.Key, keys []mh.Multih
 			// Only errors if all provides failed.
 			provideErr = fmt.Errorf("all individual provides failed for prefix %s", prefix)
 		}
-		if periodicReprovide {
-			s.reschedulePrefix(prefix)
-		}
 	}
-	if reprovide && provideErr != nil {
-		s.failedReprovide(prefix, provideErr)
+	if reprovide {
+		s.reschedulePrefix(prefix)
+		if provideErr == nil {
+			s.persistSuccessfulReprovide(prefix)
+		} else {
+			s.failedReprovide(prefix, provideErr)
+		}
 	}
 }
 
 // provideRegions contains common logic to batchProvide() and batchReprovide().
 // It iterate over supplied regions, and allocates the regions provider records
 // to the appropriate DHT servers.
-func (s *SweepingProvider) provideRegions(regions []keyspace.Region, addrInfo peer.AddrInfo, reprovide, periodicReprovide bool) bool {
+func (s *SweepingProvider) provideRegions(regions []keyspace.Region, addrInfo peer.AddrInfo, reprovide bool) bool {
 	errCount := 0
 	for _, r := range regions {
 		allKeys := keyspace.AllValues(r.Keys, s.order)
@@ -1423,9 +1654,7 @@ func (s *SweepingProvider) provideRegions(regions []keyspace.Region, addrInfo pe
 			s.stats.cycleStatsLk.Unlock()
 
 			s.releaseRegionReprovide(r.Prefix)
-			if periodicReprovide {
-				s.reschedulePrefix(r.Prefix)
-			}
+			s.reschedulePrefix(r.Prefix)
 		} else {
 			s.stats.keysPerProvide.Add(int64(nKeys))
 			s.stats.cycleStatsLk.Unlock()
diff --git a/provider/stats.go b/provider/stats.go
index 383b84f..d8b34a5 100644
--- a/provider/stats.go
+++ b/provider/stats.go
@@ -107,7 +107,7 @@ func (s *SweepingProvider) Stats() stats.Stats {
 
 	// Timing information
 	snapshot.Timing = stats.Timing{
-		Uptime:             time.Since(s.cycleStart),
+		Uptime:             time.Since(s.startedAt),
 		ReprovidesInterval: s.reprovideInterval,
 		CycleStart:         now.Add(-currentOffset),
 		CurrentTimeOffset:  currentOffset,



Test patch:
diff --git a/provider/internal/keyspace/trie_test.go b/provider/internal/keyspace/trie_test.go
index ec116eb..6d7d589 100644
--- a/provider/internal/keyspace/trie_test.go
+++ b/provider/internal/keyspace/trie_test.go
@@ -427,6 +427,216 @@ func TestPruneSubtrie(t *testing.T) {
 	require.True(t, tr.Branch(0).IsEmptyLeaf())
 }
 
+func TestCoalesceTrie(t *testing.T) {
+	keys := []bitstr.Key{
+		"0000",
+		"0001",
+		"0010",
+		"0011",
+		"01",
+		"1000",
+		"1011",
+		"110",
+		"111",
+	}
+	tr := trie.New[bitstr.Key, struct{}]()
+	// Try coalescing an empty trie
+	CoalesceTrie(tr)
+	entries := make([]trie.Entry[bitstr.Key, struct{}], len(keys))
+	for i, k := range keys {
+		entries[i] = trie.Entry[bitstr.Key, struct{}]{Key: k, Data: struct{}{}}
+	}
+	tr.AddMany(entries...)
+
+	CoalesceTrie(tr)
+
+	coalescedKeys := []bitstr.Key{
+		"0",
+		"1000",
+		"1011",
+		"11",
+	}
+	require.Equal(t, len(coalescedKeys), tr.Size())
+	for _, k := range coalescedKeys {
+		ok, _ := trie.Find(tr, k)
+		require.True(t, ok)
+	}
+}
+
+func TestSubtractTrie(t *testing.T) {
+	initTries := func(keys [2][]bitstr.Key) [2]*trie.Trie[bitstr.Key, struct{}] {
+		tries := [2]*trie.Trie[bitstr.Key, struct{}]{}
+		for i, ks := range keys {
+			tr := trie.New[bitstr.Key, struct{}]()
+			entries := make([]trie.Entry[bitstr.Key, struct{}], len(ks))
+			for i, k := range ks {
+				entries[i] = trie.Entry[bitstr.Key, struct{}]{Key: k, Data: struct{}{}}
+			}
+			tr.AddMany(entries...)
+			tries[i] = tr
+		}
+		return tries
+	}
+	t.Run("Subtract from empty trie", func(t *testing.T) {
+		keys := [2][]bitstr.Key{
+			{},
+			{
+				"0",
+				"10",
+			},
+		}
+		tries := initTries(keys)
+		for i, tr := range tries {
+			require.Equal(t, len(keys[i]), tr.Size())
+		}
+		res := SubtractTrie(tries[0], tries[1])
+		require.True(t, trie.Equal(tries[0], res))
+	})
+	t.Run("Subtract empty trie", func(t *testing.T) {
+		keys := [2][]bitstr.Key{
+			{
+				"00",
+				"01",
+				"10",
+				"11",
+			},
+			{},
+		}
+		tries := initTries(keys)
+		for i, tr := range tries {
+			require.Equal(t, len(keys[i]), tr.Size())
+		}
+		res := SubtractTrie(tries[0], tries[1])
+		require.True(t, trie.Equal(tries[0], res))
+	})
+	t.Run("Subtract trie with empty key", func(t *testing.T) {
+		keys := [2][]bitstr.Key{
+			{
+				"00",
+				"01",
+				"10",
+				"11",
+			},
+			{""},
+		}
+		tries := initTries(keys)
+		for i, tr := range tries {
+			require.Equal(t, len(keys[i]), tr.Size())
+		}
+		res := SubtractTrie(tries[0], tries[1])
+		require.True(t, res.IsEmptyLeaf())
+	})
+	t.Run("Subtract trie with full coverage", func(t *testing.T) {
+		keys := [2][]bitstr.Key{
+			{
+				"00",
+				"01",
+				"10",
+				"11",
+			},
+			{
+				"0",
+				"10",
+				"11",
+			},
+		}
+		tries := initTries(keys)
+		for i, tr := range tries {
+			require.Equal(t, len(keys[i]), tr.Size())
+		}
+		res := SubtractTrie(tries[0], tries[1])
+		require.True(t, res.IsEmptyLeaf())
+	})
+	t.Run("Subtract trie with half coverage ('0')", func(t *testing.T) {
+		keys := [2][]bitstr.Key{
+			{
+				"00",
+				"01",
+				"10",
+				"11",
+			},
+			{
+				"0",
+			},
+		}
+		tries := initTries(keys)
+		for i, tr := range tries {
+			require.Equal(t, len(keys[i]), tr.Size())
+		}
+		res := SubtractTrie(tries[0], tries[1])
+		require.False(t, res.IsEmptyLeaf())
+		require.Equal(t, 2, res.Size())
+		found, _ := trie.Find(res, "10")
+		require.True(t, found)
+		found, _ = trie.Find(res, "11")
+		require.True(t, found)
+	})
+	t.Run("Subtract trie with half coverage ('10', '11')", func(t *testing.T) {
+		keys := [2][]bitstr.Key{
+			{
+				"00",
+				"01",
+				"10",
+				"11",
+			},
+			{
+				"10",
+				"11",
+			},
+		}
+		tries := initTries(keys)
+		for i, tr := range tries {
+			require.Equal(t, len(keys[i]), tr.Size())
+		}
+		res := SubtractTrie(tries[0], tries[1])
+		require.False(t, res.IsEmptyLeaf())
+		require.Equal(t, 2, res.Size())
+		found, _ := trie.Find(res, "00")
+		require.True(t, found)
+		found, _ = trie.Find(res, "01")
+		require.True(t, found)
+	})
+	t.Run("Subtract complex trie", func(t *testing.T) {
+		keys := [2][]bitstr.Key{
+			{
+				"000",
+				"001",
+				"010",
+				"100000",
+				"1100",
+				"1110",
+				"1111",
+			},
+			{
+				"00000",
+				"00001",
+				"001",
+				"011",
+				"10010",
+				"10011",
+				"101",
+				"11",
+			},
+		}
+		tries := initTries(keys)
+		for i, tr := range tries {
+			require.Equal(t, len(keys[i]), tr.Size())
+		}
+		res := SubtractTrie(tries[0], tries[1])
+		require.False(t, res.IsEmptyLeaf())
+		expectedKeys := []bitstr.Key{
+			"000",
+			"010",
+			"100000",
+		}
+		require.Equal(t, len(expectedKeys), res.Size())
+		for _, k := range expectedKeys {
+			found, _ := trie.Find(res, k)
+			require.True(t, found)
+		}
+	})
+}
+
 func TestTrieGaps(t *testing.T) {
 	initTrie := func(keys []bitstr.Key) *trie.Trie[bitstr.Key, struct{}] {
 		tr := trie.New[bitstr.Key, struct{}]()
diff --git a/provider/provider_test.go b/provider/provider_test.go
index b9bf379..4e64a97 100644
--- a/provider/provider_test.go
+++ b/provider/provider_test.go
@@ -18,7 +18,8 @@ import (
 	"time"
 
 	"github.com/guillaumemichel/reservedpool"
-	ds "github.com/ipfs/go-datastore"
+	"github.com/ipfs/go-datastore"
+	dssync "github.com/ipfs/go-datastore/sync"
 	logging "github.com/ipfs/go-log/v2"
 	"github.com/ipfs/go-test/random"
 	"github.com/libp2p/go-libp2p/core/peer"
@@ -94,6 +95,14 @@ func genMultihashesMatchingPrefix(prefix bitstr.Key, n int) []mh.Multihash {
 	return mhs
 }
 
+func getMockAddrs(t *testing.T) func() []ma.Multiaddr {
+	return func() []ma.Multiaddr {
+		addr, err := ma.NewMultiaddr("/ip4/127.0.0.1/tcp/4001")
+		require.NoError(t, err)
+		return []ma.Multiaddr{addr}
+	}
+}
+
 var _ pb.MessageSender = (*mockMsgSender)(nil)
 
 type mockMsgSender struct {
@@ -432,12 +441,12 @@ func TestIndividualProvideSingle(t *testing.T) {
 	}
 
 	// Providing no keys returns no error
-	r.individualProvide(prefix, nil, false, false)
+	r.individualProvide(prefix, nil, false)
 	require.True(t, noWarningsNorAbove(obsLogs))
 	assertAdvertisementCount(0)
 
 	// Providing a single key - success
-	r.individualProvide(prefix, mhs, false, false)
+	r.individualProvide(prefix, mhs, false)
 	require.True(t, noWarningsNorAbove(obsLogs))
 	assertAdvertisementCount(1)
 
@@ -446,7 +455,7 @@ func TestIndividualProvideSingle(t *testing.T) {
 	router.getClosestPeersFunc = func(ctx context.Context, k string) ([]peer.ID, error) {
 		return nil, gcpErr
 	}
-	r.individualProvide(prefix, mhs, false, false)
+	r.individualProvide(prefix, mhs, false)
 	require.True(t, takeAllContainsErr(obsLogs, gcpErr.Error()))
 	assertAdvertisementCount(1)
 	// Verify failed key ends up in the provide queue.
@@ -455,7 +464,7 @@ func TestIndividualProvideSingle(t *testing.T) {
 	require.Equal(t, mhs, keys)
 
 	// Reproviding a single key - failure
-	r.individualProvide(prefix, mhs, true, true)
+	r.individualProvide(prefix, mhs, true)
 	require.True(t, takeAllContainsErr(obsLogs, gcpErr.Error()))
 	assertAdvertisementCount(1)
 	// Verify failed prefix ends up in the reprovide queue.
@@ -495,6 +504,7 @@ func TestIndividualProvideMultiple(t *testing.T) {
 	}
 	reprovideInterval := time.Hour
 	maxDelay := time.Minute
+	ds := datastore.NewMapDatastore()
 	r := SweepingProvider{
 		router:                   router,
 		msgSender:                msgSender,
@@ -510,6 +520,7 @@ func TestIndividualProvideMultiple(t *testing.T) {
 		addLocalRecord:           func(mh mh.Multihash) error { return nil },
 		provideCounter:           provideCounter(),
 		stats:                    newOperationStats(reprovideInterval, maxDelay),
+		datastore:                ds,
 		logger:                   defaultLogger,
 	}
 
@@ -524,7 +535,7 @@ func TestIndividualProvideMultiple(t *testing.T) {
 	}
 
 	// Providing two keys - success
-	r.individualProvide(prefix, ks, false, false)
+	r.individualProvide(prefix, ks, false)
 	require.True(t, noWarningsNorAbove(obsLogs))
 	assertAdvertisementCount(1)
 
@@ -533,7 +544,7 @@ func TestIndividualProvideMultiple(t *testing.T) {
 	router.getClosestPeersFunc = func(ctx context.Context, k string) ([]peer.ID, error) {
 		return nil, gcpErr
 	}
-	r.individualProvide(prefix, ks, false, false)
+	r.individualProvide(prefix, ks, false)
 	require.True(t, takeAllContainsErr(obsLogs, gcpErr.Error()))
 	assertAdvertisementCount(1)
 	// Assert keys are added to provide queue
@@ -547,7 +558,7 @@ func TestIndividualProvideMultiple(t *testing.T) {
 	require.ElementsMatch(t, pendingKeys, ks)
 
 	// Reproviding two keys - failure
-	r.individualProvide(prefix, ks, true, true)
+	r.individualProvide(prefix, ks, true)
 	require.True(t, takeAllContainsErr(obsLogs, "all individual provides failed for prefix"))
 	assertAdvertisementCount(1)
 	// Assert prefix is added to reprovide queue.
@@ -568,7 +579,7 @@ func TestIndividualProvideMultiple(t *testing.T) {
 		return closestPeers, nil
 	}
 
-	r.individualProvide(prefix, ks, false, false)
+	r.individualProvide(prefix, ks, false)
 	require.True(t, takeAllContainsErr(obsLogs, gcpErr.Error()))
 	// Verify one key was now provided 2x, and other key only 1x since it just failed.
 	msgSenderLk.Lock()
@@ -585,7 +596,7 @@ func TestIndividualProvideMultiple(t *testing.T) {
 	require.True(t, r.reprovideQueue.IsEmpty())
 	require.True(t, r.provideQueue.IsEmpty())
 
-	r.individualProvide(prefix, ks, true, true)
+	r.individualProvide(prefix, ks, true)
 	require.True(t, noWarningsNorAbove(obsLogs))
 	// Verify only one of the 2 keys was provided. Providing failed for the other.
 	msgSenderLk.Lock()
@@ -731,16 +742,10 @@ func TestClose(t *testing.T) {
 			WithRouter(router),
 			WithMessageSender(msgSender),
 			WithReplicationFactor(1),
-
 			WithMaxWorkers(4),
 			WithDedicatedBurstWorkers(0),
 			WithDedicatedPeriodicWorkers(0),
-
-			WithSelfAddrs(func() []ma.Multiaddr {
-				addr, err := ma.NewMultiaddr("/ip4/127.0.0.1/tcp/4001")
-				require.NoError(t, err)
-				return []ma.Multiaddr{addr}
-			}),
+			WithSelfAddrs(getMockAddrs(t)),
 		)
 		require.NoError(t, err)
 		synctest.Wait()
@@ -800,11 +805,7 @@ func TestProvideOnce(t *testing.T) {
 			WithPeerID(pid),
 			WithRouter(router),
 			WithMessageSender(msgSender),
-			WithSelfAddrs(func() []ma.Multiaddr {
-				addr, err := ma.NewMultiaddr("/ip4/127.0.0.1/tcp/4001")
-				require.NoError(t, err)
-				return []ma.Multiaddr{addr}
-			}),
+			WithSelfAddrs(getMockAddrs(t)),
 			WithOfflineDelay(offlineDelay),
 			WithConnectivityCheckOnlineInterval(checkInterval),
 		}
@@ -903,11 +904,7 @@ func TestStartProvidingSingle(t *testing.T) {
 			WithPeerID(pid),
 			WithRouter(router),
 			WithMessageSender(msgSender),
-			WithSelfAddrs(func() []ma.Multiaddr {
-				addr, err := ma.NewMultiaddr("/ip4/127.0.0.1/tcp/4001")
-				require.NoError(t, err)
-				return []ma.Multiaddr{addr}
-			}),
+			WithSelfAddrs(getMockAddrs(t)),
 			WithOfflineDelay(offlineDelay),
 			WithConnectivityCheckOnlineInterval(checkInterval),
 		}
@@ -1026,11 +1023,7 @@ func TestStartProvidingMany(t *testing.T) {
 			WithPeerID(pid),
 			WithRouter(router),
 			WithMessageSender(msgSender),
-			WithSelfAddrs(func() []ma.Multiaddr {
-				addr, err := ma.NewMultiaddr("/ip4/127.0.0.1/tcp/4001")
-				require.NoError(t, err)
-				return []ma.Multiaddr{addr}
-			}),
+			WithSelfAddrs(getMockAddrs(t)),
 		}
 		prov, err := New(opts...)
 		require.NoError(t, err)
@@ -1178,11 +1171,7 @@ func TestStartProvidingUnstableNetwork(t *testing.T) {
 			WithPeerID(pid),
 			WithRouter(router),
 			WithMessageSender(msgSender),
-			WithSelfAddrs(func() []ma.Multiaddr {
-				addr, err := ma.NewMultiaddr("/ip4/127.0.0.1/tcp/4001")
-				require.NoError(t, err)
-				return []ma.Multiaddr{addr}
-			}),
+			WithSelfAddrs(getMockAddrs(t)),
 			WithOfflineDelay(offlineDelay),
 			WithConnectivityCheckOnlineInterval(connectivityCheckInterval),
 		}
@@ -1260,7 +1249,7 @@ func TestAddToSchedule(t *testing.T) {
 
 func TestRefreshSchedule(t *testing.T) {
 	ctx := context.Background()
-	mapDs := ds.NewMapDatastore()
+	mapDs := datastore.NewMapDatastore()
 	defer mapDs.Close()
 	ks, err := keystore.NewKeystore(mapDs)
 	require.NoError(t, err)
@@ -1346,11 +1335,7 @@ func TestOperationsOffline(t *testing.T) {
 			WithPeerID(pid),
 			WithRouter(router),
 			WithMessageSender(&mockMsgSender{}),
-			WithSelfAddrs(func() []ma.Multiaddr {
-				addr, err := ma.NewMultiaddr("/ip4/127.0.0.1/tcp/4001")
-				require.NoError(t, err)
-				return []ma.Multiaddr{addr}
-			}),
+			WithSelfAddrs(getMockAddrs(t)),
 			WithOfflineDelay(offlineDelay),
 			WithConnectivityCheckOnlineInterval(checkInterval),
 		}
@@ -1512,7 +1497,7 @@ func TestQueuePersistence(t *testing.T) {
 		require.NoError(t, err)
 
 		// Create a datastore that will be shared across provider instances
-		mapDs := ds.NewMapDatastore()
+		mapDs := dssync.MutexWrap(datastore.NewMapDatastore())
 		defer mapDs.Close()
 
 		router := &mockRouter{
@@ -1520,12 +1505,7 @@ func TestQueuePersistence(t *testing.T) {
 				return []peer.ID{pid}, nil
 			},
 		}
-		msgSender := &mockMsgSender{
-			sendMessageFunc: func(ctx context.Context, p peer.ID, m *pb.Message) error {
-				// Don't actually send messages in this test
-				return nil
-			},
-		}
+		msgSender := &mockMsgSender{}
 
 		checkInterval := time.Second
 
@@ -1534,13 +1514,9 @@ func TestQueuePersistence(t *testing.T) {
 		opts0 := []Option{
 			WithPeerID(pid),
 			WithRouter(router),
-			WithMessageSender(msgSender),
+			WithMessageSender(&mockMsgSender{}),
 			WithDatastore(mapDs),
-			WithSelfAddrs(func() []ma.Multiaddr {
-				addr, err := ma.NewMultiaddr("/ip4/127.0.0.1/tcp/4001")
-				require.NoError(t, err)
-				return []ma.Multiaddr{addr}
-			}),
+			WithSelfAddrs(getMockAddrs(t)),
 			WithConnectivityCheckOnlineInterval(checkInterval),
 			WithMaxWorkers(0),               // No workers = keys stay in queue
 			WithDedicatedBurstWorkers(0),    // No dedicated burst workers
@@ -1552,7 +1528,7 @@ func TestQueuePersistence(t *testing.T) {
 		synctest.Wait()
 		require.True(t, prov0.connectivity.IsOnline())
 
-		// SKip the avg prefix length estimation
+		// Skip the avg prefix length estimation
 		prov0.avgPrefixLenLk.Lock()
 		prov0.cachedAvgPrefixLen = 4
 		prov0.avgPrefixLenLk.Unlock()
@@ -1579,11 +1555,7 @@ func TestQueuePersistence(t *testing.T) {
 			WithRouter(router),
 			WithMessageSender(msgSender),
 			WithDatastore(mapDs),
-			WithSelfAddrs(func() []ma.Multiaddr {
-				addr, err := ma.NewMultiaddr("/ip4/127.0.0.1/tcp/4001")
-				require.NoError(t, err)
-				return []ma.Multiaddr{addr}
-			}),
+			WithSelfAddrs(getMockAddrs(t)),
 			WithConnectivityCheckOnlineInterval(checkInterval),
 			WithMaxWorkers(0),               // Still no workers to keep queue stable
 			WithDedicatedBurstWorkers(0),    // No dedicated burst workers
@@ -1611,3 +1583,191 @@ func TestQueuePersistence(t *testing.T) {
 		require.ElementsMatch(t, mhs, dequeuedKeys, "dequeued keys should match original keys")
 	})
 }
+
+func TestResumeReprovides(t *testing.T) {
+	synctest.Test(t, func(t *testing.T) {
+		ctx := context.Background()
+		pid, err := peer.Decode("12D3KooWCPQTeFYCDkru8nza3Af6u77aoVLA71Vb74eHxeR91Gka") // kadid starts with 16*"0"
+		require.NoError(t, err)
+
+		replicationFactor := 4
+		peerPrefixBitlen := 6
+		require.LessOrEqual(t, peerPrefixBitlen, bitsPerByte)
+		var nPeers byte = 1 << peerPrefixBitlen // 2**peerPrefixBitlen
+		peers := make([]peer.ID, nPeers)
+		for i := range nPeers {
+			b := i << (bitsPerByte - peerPrefixBitlen)
+			k := [32]byte{b}
+			peers[i], err = kb.GenRandPeerIDWithCPL(k[:], uint(peerPrefixBitlen))
+			require.NoError(t, err)
+		}
+
+		reprovideInterval := time.Hour
+
+		router := &mockRouter{
+			getClosestPeersFunc: func(ctx context.Context, k string) ([]peer.ID, error) {
+				sortedPeers := kb.SortClosestPeers(peers, kb.ConvertKey(k))
+				return sortedPeers[:min(replicationFactor, len(peers))], nil
+			},
+		}
+
+		var prov *SweepingProvider
+		getPrefixFromSchedule := func(k bit256.Key) bitstr.Key {
+			prov.activeReprovidesLk.Lock()
+			defer prov.activeReprovidesLk.Unlock()
+			prefix, ok := keyspace.FindPrefixOfKey(prov.activeReprovides, k)
+			require.True(t, ok)
+			return prefix
+		}
+
+		reprovidedLk := sync.Mutex{}
+		reprovided := make(map[bitstr.Key]struct{})
+		msgSender := &mockMsgSender{
+			sendMessageFunc: func(ctx context.Context, p peer.ID, m *pb.Message) error {
+				h, err := mh.Cast(m.GetKey())
+				require.NoError(t, err)
+				k := keyspace.MhToBit256(h)
+				regionalPrefix := getPrefixFromSchedule(k)
+
+				reprovidedLk.Lock()
+				reprovided[regionalPrefix] = struct{}{}
+				reprovidedLk.Unlock()
+				return nil
+			},
+		}
+
+		requireNoPendingReprovides := func() {
+			prov.activeReprovidesLk.Lock()
+			require.Zero(t, prov.activeReprovides.Size())
+			prov.activeReprovidesLk.Unlock()
+			require.Zero(t, prov.reprovideQueue.Size())
+		}
+
+		ds := dssync.MutexWrap(datastore.NewMapDatastore())
+		ks, err := keystore.NewKeystore(ds)
+		require.NoError(t, err)
+		defer ks.Close()
+
+		mhs := genBalancedMultihashes(10)
+		ks.Put(ctx, mhs...)
+
+		opts := []Option{
+			WithReprovideInterval(reprovideInterval),
+			WithReplicationFactor(replicationFactor),
+			WithMaxWorkers(1),
+			WithDedicatedBurstWorkers(0),
+			WithDedicatedPeriodicWorkers(0),
+			WithPeerID(pid),
+			WithRouter(router),
+			WithMessageSender(msgSender),
+			WithSelfAddrs(getMockAddrs(t)),
+			WithDatastore(ds),
+			WithKeystore(ks),
+		}
+		prov, err = New(opts...)
+		require.NoError(t, err)
+
+		synctest.Wait()
+		require.True(t, prov.connectivity.IsOnline())
+
+		prov.scheduleLk.Lock()
+		nRegions := prov.schedule.Size()
+		prov.scheduleLk.Unlock()
+		require.Len(t, reprovided, nRegions, "should have reprovided all regions")
+		requireNoPendingReprovides()
+
+		// All keys have been provided once, clear for cycle of reprovides.
+		reprovidedLk.Lock()
+		clear(reprovided)
+		reprovidedLk.Unlock()
+
+		cycleStart := prov.cycleStart
+		require.Equal(t, time.Now(), cycleStart)
+
+		time.Sleep(reprovideInterval / 2) // wait half a reprovide cycle
+		synctest.Wait()
+
+		reprovidedLk.Lock()
+		require.Len(t, reprovided, nRegions/2, "should have reprovided %d regions", nRegions/2)
+		reprovidedLk.Unlock()
+		requireNoPendingReprovides()
+
+		time.Sleep(2 * reprovideInterval)
+		// Provider has run for 2.5*reprovideInterval
+		synctest.Wait()
+		requireNoPendingReprovides()
+
+		// Close provider
+		err = prov.Close()
+		require.NoError(t, err)
+
+		time.Sleep(reprovideInterval / 4) // wait some time before restarting
+		// 2.75*reprovideInterval since initial start
+		synctest.Wait()
+
+		// Clear reprovided regions
+		reprovidedLk.Lock()
+		clear(reprovided)
+		reprovidedLk.Unlock()
+
+		// Restart provider
+		prov, err = New(opts...)
+		require.NoError(t, err)
+		defer prov.Close()
+		synctest.Wait()
+		require.True(t, prov.connectivity.IsOnline())
+
+		require.Equal(t, prov.cycleStart, cycleStart, "cycle start should be unchanged after restart")
+
+		// Since the node was offline for reprovideInterval/4, the provider needs
+		// to reprovide nRegions/4 ASAP. They should be provided by now.
+		require.Len(t, reprovided, nRegions/4, "should have reprovided %d regions in second round", nRegions/4)
+		requireNoPendingReprovides()
+
+		time.Sleep(reprovideInterval / 4)
+		synctest.Wait()
+
+		// 0.25*reprovideInterval after restart.
+		// 0.5*reprovideInterval after shutdown.
+		// 3*reprovidesInterval since initial start.
+		reprovidedLk.Lock()
+		require.Len(t, reprovided, nRegions/2)
+		reprovidedLk.Unlock()
+		requireNoPendingReprovides()
+
+		// reprovideInterval/2 after restart.
+		// 0.75*reprovideInterval after shutdown.
+		// 3.25*reprovidesInterval since initial start.
+		time.Sleep(reprovideInterval / 4)
+		synctest.Wait()
+		reprovidedLk.Lock()
+		require.Len(t, reprovided, 3*nRegions/4)
+		reprovidedLk.Unlock()
+		requireNoPendingReprovides()
+
+		// 0.75*reprovideInterval after restart.
+		// 1*reprovideInterval after shutdown.
+		// 3.5*reprovidesInterval since initial start.
+		time.Sleep(reprovideInterval / 4)
+		synctest.Wait()
+		reprovidedLk.Lock()
+		require.Len(t, reprovided, nRegions, "should have reprovided all regions")
+		reprovidedLk.Unlock()
+		requireNoPendingReprovides()
+
+		// All keys have been provided once, clear for cycle of reprovides.
+		reprovidedLk.Lock()
+		clear(reprovided)
+		reprovidedLk.Unlock()
+
+		// 1.75*reprovideInterval after restart.
+		// 2*reprovideInterval after shutdown.
+		// 4.5*reprovidesInterval since initial start.
+		time.Sleep(reprovideInterval)
+		synctest.Wait()
+		reprovidedLk.Lock()
+		require.Len(t, reprovided, nRegions, "should have reprovided all regions")
+		reprovidedLk.Unlock()
+		requireNoPendingReprovides()
+	})
+}