Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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).
You should take a look to CRDTs (Conflict-free replicated data type)
Those are data structures designed for distributed networks that can be updated concurrently without coordination between the replicas, as the resolution of conflicts is handled mathematically.
I was researching and working on Operational Transformation algorithms (SOCT4) some years ago, to implement a distributed collaboration software, and had some contacts with a Inria team, experts on this area, who provided this information, check their website for papers about latest research on this topic, they are doing an incredible work.
When I looked at them they were somehow limited, but increasing and decreasing sequences was already supported at the time (2013)
