Proof of work schmes used in Bitcoin protocol is an expensive affair and tends to move toward the thermodynamic limit. Many of the alt-coins has tweaked existing Bitcoin style POW and in most cases it does not achieve anything new.
What is POW?
Computational proof that some scarce resource was consumed.
POW does a great job in restricting malicious actor altering the state or history of given chain ie blockchain. In order to reach consensus and to extend history of the chain "enough time" is required to verify the data with speed of verification of data.
In this model individual actors are not trusted, Bitcoin model implements a partial hash inversion where repeated hashing is done and each attempt has tiny chance. In result it gives us Poisson process.
POW must be progress free it should not depend on any part of calculation at time T` < T, it should be rare enough to limit block speed such probabliity of a POW is [t0,t1] is ≈ (t0-t1) but independent of t0 and t1.
Bitcoin blocks are generated every +-10 M independent of how long ago the last block was found.
There are other algorithmic considerations such as Optimization free i.e if there are any algorithmic speedups found or Approximation free i.e there should not be defective variant.
Proof of physical work ie energy dissipation any irreversible proof of computational work.
Reversible computing , where there is no increase in entropy, such computation are reversible in time. Hash based POW are not reversible thus requiring computational energy to go zero.
The current state of POW is the thermodynamic limit which is a physical incentive for decentralisation of miners where they can push towards limit.
Dedicated hardware such as ASIC are good for mining decentralisation where one machine can generate more hashes at same energy because ASIC are closer to thermodynamic limit but the centralisation of Manufacturer still persists.
Whereas Memory hard algorithm requires upfront cost relative to energy cost provided in the case of mining setup. In case of scyprt and sha2 , the first one is more complex to ASIC-resistant and is much slower to validate and more memory hard. Examples like primecoin also fails as compared to tradeoffs between sha2.
There are many incentives for miners to achieve the above thermodynamic limit on his expense where a miner is looking for a reward it can be a social reward or a currency reward which secures the network as he put more resources to solve and compete in the puzzle finding race.
Proof of Stake
Instead of provisioning upfront capital for generating hashes to secure network POS is an idea where perhaps miner can consume the currency itself rather then doing the stated.
It works by associating votes to individual coins and to prevent "tyranny of the rich" each block is voted on a small set of coin holder. Although most of the cryptocurrency right now is stuck at problem known as "nothing at stake" .
The problem with POS is that a miner can perform POW to create future votes and behave honestly.