If the fee provided by the sender is too low there’s possibility that receipt never gets included by the the third party. This could be mitigated by making fees increase over time.
The following proposal tries to combine the “fees increasing over time” with the fixed fee model:
There is a global pool of third party operators which stake certain amount prior to validating.
Transaction’s fee on the destination shard is proportional to the block difference between inclusion on the destination minus the source shard.
When transaction finally gets included, the submitter gets the full fee (standard fee + temporal part).
This temporal part of the fee is taken from the pool and everyone’s stake is decreased proportionally to the amount staked.
Third party operator can leave by withdrawing his stake at any time.
This is zero-sum game from the pool’s perspective but increases the expected individual profit.