This is a repository for my research, paper reading summaries/reviews, and relevant blog-like posts in markdown.
The paper describes the CAP theorem in formal words. CAP (and BASE?) was initially described by Eric Brewer during a Keynote at PODC (principles of distributed computing). The CAP theorem states that a distributed system cannot have 100% of 3 properties:
Gilbert and Lynch decided to formalize and prove the conjecture using an asynchronous network model, and then explore the implications of the theory and related proofs using a partially synchonous model.
This is the first paper I read which uses the formal asynchronous network model to prove properties of distributed algorithms. It also gives me a sense of how powerful clocks make understanding a distributed system, since it allows a partially synchronous network model to be used. Having read part of the paper, ``Time, Clocks, and the Ordering of Events in a Distributed System,’’ by Leslie Lamport, I understand the difference between logical and real clocks. What I think is interesting is that although time is a universal property, using time provides partial synchronicity. Yet, how time is captured can be as simple as a logical counter sent with the data, and not necessarily captured from the environment.
I feel like network partitions are always defined in such a way that a graph of connected components: G, is split into two subgraphs: G’ and G’’, and a client: C. Where C is capable of sending messages to G’ and G’’, but for some reason G’ and G’’ are unable to find each other. It seems more general and correct to assume that C is on a side of the partition, and thus able to communicate only with components in G’ or G’’, but not both.
I am interested in further properties of partially synchronous network models, and why partially synchronous is a property that allows the benefits of a fully asynchronous network but with slightly stronger guarantees that come with a fully synchronous network. It makes me wonder if there is much work on implementing such clocks at the network level and pushing analysis of consistency and availability down the technical stack, but making that information available for higher level applications to use.
Consistency tends to be something typically analyzed at a particular level of the stack, typically by an application that is implementing the consistency protocol. It would be useful to find research that divides the mechanism and policy of a consistency protocol into multiple levels of abstraction. Further research that may be relevant to find would be something that allows mechanisms or policies of various protocols to be dynamically included.