Proof-of-work is the current consensus algorithm used by Bitcoin, Ethereum, and many other cryptocurrencies. A proof of work is a piece of data which is difficult (costly, time-consuming) to produce but easy for others to verify and which satisfies certain requirements. Producing a proof of work can be a random process with low probability so that a lot of trial and error is required on average before a valid proof of work is generated.
In order for a block to be accepted by network participants, miners must complete a proof of work which covers all of the data in the block. The difficulty of this work is adjusted so as to limit the rate at which new blocks can be generated by the network to one every 10 minutes. Due to the very low probability of successful generation, this makes it unpredictable which worker computer in the network will be able to generate the next block.
For a block to be valid it must hash to a value less than the current target called a nonce; this means that each block indicates that work has been done generating it. The most widely used proof-of-work scheme is based on SHA-256 and was introduced as a part of Bitcoin.
One criticism of PoW in Bitcoin is that it means mining will eventually become unattractive as the reward for mining drops to a point where it is economically unprofitable, or nearly so. If the mining pool becomes sufficiently small, Bitcoin will become increasingly subject to the possibility of a 51% attack due to the small mining pool.