On Sun, Sep 27, 2015 at 2:39 AM, Gregory Maxwell via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org> wrote:

Unless the weak block transaction list can be a superset of the block
transaction list size proportional propagation costs are not totally
eliminated.

The POW threshold could be dynamic. The first weak-block that builds on a new block could be forwarded with a smaller target.

This reduces the window size until at least one weak block is propagated.

The change in threshold could be time based (for the first 30 seconds or so). This would cause a surge of traffic when a new block once a new block has propagated, so perhaps not so good an idea.

As even if the weak block criteria is MUCH lower than the block
criteria (which would become problematic in its own right at some
point) the network will sometimes find blocks when there hasn't been
any weak block priming at all (e.g. all prior priming has made it into
blocks already).

If there is a transaction backlog, then miners could forward merkle branches with transactions in the memory pool with a commitment in the coinbase.