Can we have a strictly monotonically increasing/decreasing sequence generated by a distributed system? Just what the title says.
Can we have a strictly monotonically increasing/decreasing sequence generated by a distributed system (without a single point of failure)?

My current thoughts are that this is a consensus problem, and is thus impossible to achieve in an asynchronous messaging system (like the Internet). Another way I look at it is that if we could generate such a sequence in a distributed system, then the problem of total ordering is solved. 

Please correct me if I'm wrong.
You're right that this is an impossible problem to solve in an asynchronous distributed system, and you're also right that it would solve a lot of problems if we could get a totally ordered clock. But it only solves "all" our problems if the clock has the additional constraint of a meaningful relationship with real time.

The two best solutions we have are partial ordering (Lamport clocks) and consensus (which can be fault tolerant but is typically driven by an elected leader). The latter provides total order and works well in practice (with randomized timers), but is impossible to guarantee in theory (FLP).