All IP Routing Protocols are eventually consistent. In addition, the internal architecture of all modern IP routers is also eventually consistent. The latter refers to IP routers' control plane, implemented as software on a general-purpose CPU, communicating routing, signaling, or other configuration information to its corresponding forwarding plane, implemented by ASICs or NPUs.

The critical question that I have is: must we accept that the internal architecture of IP routers is eventually consistent with few robustness guarantees, other than it should ultimately achieve convergence? Or, are there alternatives, in academia or the storage/database industry, that can be applied to modern router systems to provide more powerful forms of eventual consistency and have negligible, or no, impact on availability and throughput within the system?

A definition of eventual consistency[1] is as follows, (italics, for emphasis, is mine):

the storage system guarantees that if no new updates are made to the object, eventually all accesses will return the last updated value. If no failures occur, the maximum size of the inconsistency window can be determined based on factors such as communication delays, the load on the system, and the number of replicas involved in the replication scheme.

Read the last sentence very carefully. Notice that eventually consistent systems do not guarantee a bounds on the length of time required for a system to have converged or become ‘consistent.’ I believe the above sentence states that one may informally measure, but not formally guarantee, the upper bounds of the inconsistency window.

All distributed systems possess one of two properties: safety and liveness. Eventual consistency is a liveness property[2]: “Informally, a liveness property stipulates that a ‘good thing’ happens during execution.” For example, “in guaranteed service, which states that every request for service is satisfied eventually, the ‘good thing’ is receiving service.” On the other hand, the safety property[2] “stipulates that some ‘bad thing’ does not happen during execution.” As one example, in “partial correctness, it is terminating in a state not satisfying the postcondition after having been started in a state that satisfies the precondition.”

The safety property is stringent – it is a formal guarantee that a single- or multi-process program will be executed correctly and completely. As a result, it is incredibly challenging to design, build and offer formal proof that a given distributed system perfectly satisfies a set of safety properties.

The liveness property is much more relaxed. In the context of eventually consistent systems, the liveness property offers that a good thing will happen in time. The liveness property does not define what delays are acceptable for ‘eventually’ to be realized. In my opinion, the latter also leaves unresolved, or at least rarely discussed, what must happen if an eventually consistent system cannot attain convergence. In the context of IP router system architects and operators of these systems, is there an established framework that both can reference, which clearly defines both the choices and their corresponding consequences?

General-purpose, distributed database and storage systems designed for eventual consistency leave it up to higher-level applications or services built atop these systems to decide what should happen if convergence does not occur. Inarguably, that has provided a significant degree of design latitude to distributed system architects when determining whether and, if necessary, how to solve this problem and is good.

On the other hand, the academic research into eventual consistency is, in my opinion, extremely mature. Notably, several landmark research papers on safety, liveness, and eventual consistency have existed since the 1970s and 1980s. Furthermore, several dozen eventually consistent distributed systems implementations have been built and analyzed in the last couple of decades (notably database and storage systems). Ultimately, this leaves me perplexed whether it may be possible to apply those precedents to the architecture of modern IP routers so they can implement more potent forms of eventual consistency.

References:

  1. Vogels, Werner. “Eventually Consistent” Communications of the ACM, January 2009, Vol. 52, No. 1, pp 40-44. https://cacm.acm.org/magazines/2009/1/15666-eventually-consistent/fulltext. Accessed: January 3, 2022.
  2. Alpern, Bowen and Schneider, Fred B. “Defining Liveness”. Information Processing Letters 21, 7 October 1985, pp. 181-185. https://www.cs.cornell.edu/fbs/publications/DefLiveness.pdf. Accessed: January 3, 2022.