Abstract
Exogenous mining power presents an ongoing threat to the security of independent blockchains. Two or more independent blockchains implementing a single proof-of-work algorithm will result in only one strongly secure blockchain because no economic incentive prevents mining nodes on the strongest blockchain from attacking a weaker one. Parallel proof-of-work combines the cumulative work done in all participating networks, removing wasted competition, and bringing all networks to consensus by adding up their work.

Include deeper discussion on the current state of PoW security

We propose a proof-of-work system separating a block into two distinct logical categories. First, a header containing proof-of-work and a transaction tree, called the consensus proof. Second, a set of blocks called parallel blocks, each one containing the set of transactions from a corresponding participating blockchain. Nodes compete to find proof-of-work to secure all parallel blocks.

Merge mining/auxiliary proof of work namecoin
51% attack costs https://www.crypto51.app/
Sharding paradigms/IBC

b is a parallel blockchain, a blockchain participating in the parallel proof-of-work system.
B is the set of all parallel blockchains such that B = (b₀, b₁, …, b_n).
hash(P) is the hash digest of preimage data P.
nonce is the field of data used to satisfy the difficulty requirement for a consensus proof.
prev is the hash of the previous consensus proof.
T_b is a set of transactions waiting to be mined in a parallel blockchain b.
root(T) is the merkle root of all transactions within the set of transactions T.
R is a merkle root containing all T within B such that R = root(root(T₀), root(T₁), … root(T_n)).

Consider a system with two parallel blockchains, b₀ and b₁.

ConsensusProof = hash(nonce, prev, R)
ParallelBlock(b₀) = hash(ConsensusProof, T₀, root(T₀))
ParallelBlock(b₁) = hash(ConsensusProof, T₁, root(T₁))

The steps to construct the blockchain are mostly the same as classic proof-of-work:

1. New transactions from blockchain b₀ are broadcast to all other b₀-aware nodes.
2. Nodes attempting to find proof-of-work collect all transactions from all blockchains.
3. When a node finds proof-of-work for a consensus proof, it can issue parallel blocks for each blockchain it has collected transactions for, earning rewards from each.

The result is collaboration between multiple blockchains using the same mining algorithm. Mining nodes that find a valid consensus proof are able to construct parallel blocks for each participating blockchain in the network, generating coins in each blockchain.

Miners are now mining for a single nonce that validates the blocks of all parallel chains.

Miners get to reward themselves a coinbase for every parallel blockchain in the system if they find valid proof-of-work.

Exogeneous mining power is a threat means when DOGE hashrate falls, the LTC hashrate is a threat to the DOGE security model, because LTC miners have no incentive to not attack the DOGE chain. (DOGE and LTC both have ~200TH right now, but if DOGE falls lower, they are vulnerable to attack).

Network protocols definitely need to be compatible, practically speaking, this would be merging a few coins' networks together.

We're using the same method of checking transactions as bitcoin, litecoin, etc.

Yes. Fundamentally this isn't an issue because blocktime isn't significant, cumulative work over time is what is really significant.

No. Actually, this solution came about to solve that exact issue. When all miners are mining to find the same nonce, and all blockchains are using that nonce to consider their blocks valid, there is no weakest or strongest chain. They are all secured by the same hashrate.