What does the clock of blockchain look like?

What does the "clock" of blockchain look like?
Source: stakefish

"Time" is an eternal topic in the passage of time. The discussion around time has been carried out in block chain and other distributed systems. Time connects processes to nodes, and we also use the "granularity" of time to measure a decentralized network that links blocks.

The problem with time in a distributed system is that the "physical clocks" of the different actors can't quite agree. Distributed systems master Lamport provides a decentralized approach, transforming problems into time and order, and proposing the concept of a logical clock, as if introducing a "biological clock" for distributed systems including blockchain.

Stakefish has compiled an article by Vac analyst and ENS developer Dean Eigenmann, which introduces Lamport's discussion of time, clocks, and order to give you another perspective on understanding the time of blockchain and distributed systems.

Which topic would be appropriate to start this series of articles on distributed systems? Ethereum's privacy deal AZTEC? The notoriously difficult Paxos algorithm? Save these topics for later. Today, I started with a basic topic: the topic of time in distributed systems.

This article is about Time, clocks, and the ordering of events in a distributed system, a paper by Leslie Lamport, a Turing prize-winning computer scientist. It's interesting to reread the article a long time later and refine the key concepts.

For those unfamiliar with Leslie Lamport, who is best known for creating LaTeX, TLA+, and Paxos, he discusses the Byzantine generals. There is, of course, the Lamport clock (the first logical clock), the basic concepts of which are also covered in this article.

Let's take a look at the definition of distributed systems. The definition given by Lamport is as follows:

"If the delay in the transfer of information within a system is not negligible compared to the time between events in a single process, it is called a distributed system."

I like this definition because it focuses on the delay between sending and receiving messages.

With the definition clear, we begin the formal introduction.

The order

Sorting events locally is easy enough. You just give each event a timestamp as it happens. We can get the overall order of events, which means that all events can be arranged in a particular order.

But this problem is much more difficult in the context of distributed systems. Why?

Everything is due to a very simple nature of distributed systems: messages passed between nodes can arrive 0, 1, or more times at any future point in time after they are sent. In this way, the nodes of a distributed system cannot agree on time. For example:

One node can send a message to another to indicate that the current time is 12:00:00, but the receiver does not know how long the message took, so there is no way to determine if it still arrives at 12:00:00. If so, sending messages back and forth between nodes all day long will not determine whether the information is synchronized. If we can't agree on the timing, we can't agree on the sequence of events.

So how do you solve this problem?

In a distributed system, multiple nodes communicate by sending information to each other. When a node receives a message, it first confirms the message and then executes its next event. Such an order implies a "cause-and-effect relationship" : information must be sent before it can be received.

This causality is a temporal relationship, not a logical cause-effect relationship.

Then causation leads to order: the message must be sent before it is received. By looking at events A and B alone, we can describe the order in terms of what happens before.

Now, it is possible to identify this relationship without A concept of system physical time: if A has A causal effect on B, event A must have occurred before event B. Causality allows us to determine the order of related events in the system, which is a partial order.

Partial ordering also has a limitation: if the correlation is not determined, we may not know the exact order of each event in the system. Because there are many events that can occur concurrently (concorrent) throughout the system, not all nodes are aware that these events occur.

The clock

But now that we have partial ordering, we can add the clock to the system and get the total order of all events in the system.

Now that we know that using a physical clock is not feasible in a distributed system, we need to use a logical clock. A logical clock is essentially a function that assigns a number to an event. This number represents the time of the event (we will call this number time from now on) and has nothing to do with physical time.

We assume that each node in this distributed system has a clock. The clock ticks along with the events being executed, but the clock's march is not considered an event in the system. For each event that occurs on a node in the system, the logical clock assigns a number to that event. Based on this assumption, we can satisfy the following clock conditions:

•a,b a → bư C(a) < C(b)

What does this expression mean?

The arrow "→" means "happened before", while C stands for clock function, which can be simply understood as time. So the idea is that for every event a,b, if a happens before b, then the time for a is less than the time for b.

But extrapolation doesn't work, just because the time of one event is less than the time of the other doesn't mean that the event happened before and they can be concurrent.

In the above picture, we can see that on the node node, one event occurred at time 1 and one event occurred at time 2. Node node has 1 event on its own time 1. Events that occur at time 1 and time 2 on node nodes are concurrent with events that occur at time 1 on node nodes and have no causal relationship.

If a and b are two events on a single node and a occurs before b, the time of a should be less than the time of b.

If a is the node that sends the message and b is the node that receives the message, then a should still take less time than b.

Nodes need to time the clock between events. If not, the clock must be moved forward to a time later than that contained in any messages received from other nodes. B can happen after the clock is moved forward.

Now, we can use the clock that satisfies these conditions to create a general order for the whole distributed system, which is simply based on the time given by the clock of each event.

Use cases

Finally, let's set up a state machine to see how the logical clock works. For example, we have a distributed system in which multiple nodes want to access Shared resources, but only one node can be accessed at a time. The state machine needs to meet the following conditions:

Condition 1: a node that can access a resource must first release the resource before other nodes can access it.

Condition 2: requests to resources must be granted access in the order in which they were issued.

Condition 3: if each node granted access eventually frees the resource, then each request will eventually be granted.

Why not bring in an intermediate coordinator? Because in this case, if an earlier request occurs but arrives later, condition 2 cannot be satisfied; Another reason is that we want a decentralized solution.

So we still have to construct conditions that satisfy this logical clock. How do we satisfy that?

Lamport provides us with a decentralized solution. First, we want all nodes to store a request queue. Second, to satisfy some simple assumptions:

Assumption 1: all messages are received in the order they were sent.

Assumption 2: all messages are eventually received.

Assumption 3: each node can send messages directly to all other nodes in the system.

If you have more complex algorithms and protocols, you can ignore these assumptions.

Now we can define the algorithm that meets these three conditions and demonstrate the clock's function in practice:

1. If a node wants to request a resource, it will create a request at the current time, add it to its queue, and send it to every other node.

2. All other nodes queue the request and send back the response message.

3. The node that frees the resource sends a release message with the current time and deletes the original request from its queue.

4. When the node receives the release message, it will clear relevant requests from its queue.

5. When a node has its own request in its queue before any other request (in chronological order), it is free to access the resource, and it receives messages from all other nodes after that time.

The above algorithm is a decentralized algorithm executed by each node independently. It USES the clock to sort requests in general order, so as to realize access to resources and coordination between nodes.

Well, this article gives you a general idea of how to use these logical clocks to sort events in a distributed system, and analyzes the practical application of determining the order when accessing resources in a distributed system. I welcome your feedback and will continue to update more articles on distributed systems.

Clocks, clocks, and order
By Dean Eigenmann
Compiler: stakefish

Source:weixin.qq.com

Welcome to join the official BlockBeats community:

Telegram Subscription Group: https://t.me/theblockbeats

Telegram Discussion Group: https://t.me/BlockBeats_App

Official Twitter Account: https://twitter.com/BlockBeatsAsia