Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Time, Clocks, Ordering #10

Closed
7 tasks done
decanus opened this issue Jan 2, 2020 · 7 comments
Closed
7 tasks done

Time, Clocks, Ordering #10

decanus opened this issue Jan 2, 2020 · 7 comments
Labels
Projects

Comments

@decanus
Copy link
Owner

decanus commented Jan 2, 2020

This is mainly to freshen up knowledge on time, clocks, and ordering in distributed systems as well as provide me with enough research to write a complete summary on the subject.

Questions

  • How does ordering work in distributed systems?
  • What problems do we face when ordering events?

Literature

  • Time, clocks, and the ordering of events in a distributed system - paper
  • Causal Ordering - post
  • Time and clocks and ordering of events in a distributed system (Medium Coinmonks) - post
  • Ordering Distributed Events - post
  • Logical Time and Lamport Clocks - post
  • Lamport's Logical Clocks - post
  • Time, Clocks and Ordering of Events in a Dist. System by Dan Rubenstein - video

Results

@decanus decanus added this to To do in research via automation Jan 2, 2020
@decanus decanus moved this from To do to In progress in research Jan 2, 2020
@decanus
Copy link
Owner Author

decanus commented Jan 2, 2020

Time, Clocks and Ordering of Events in a Dist. System by Dan Rubenstein

How do we know the order of two events?

Partial ordering:

  • If events A and B are partially ordered, we say A happened before B.
  • If they are not partially ordered, we say A and B are concurrent

Rules:

  • Single Process: In a single process we have a total ordering, old events happened before new events that we see.
  • Message Transmission: All communication is asynchronous. Sending a message happens before a receiving a message.
  • Transitivity: If event A happened before B and B happened before C then A happened before C

Logical Clock

func(Event): Timestamp

Logical clocks are a function that take in an event and return a timestamp for that event. The rate of increase is arbitrary but must be positive. All distributed processes keep their own clock.

When receiving events, update clock timestamp with following function: max(last_sent_clock, last_received_clock) + 1

  • If 2 events are partially ordered, then their logical clocks are also ordered.
    If A happened before B then clock time of A is less than B.
  • If clock time A is less than B, the events are not necessarily partially ordered.
    This would imply that all concurrent events have to happen at the same clock time.

To break ties we use any arbitrary total ordering of the processes.

@decanus
Copy link
Owner Author

decanus commented Jan 2, 2020

Ordering Distributed Events

We do not really care about time in a distributed system, what we care about is which events happened at what time, their ordering. Timestamps are used to indicate when something was created or deleted, or sent and received. In these scenarios it is often not the timestamp we actually care about, but the ordering it provides us with of those specific events. We never really care about the timestamp on its own.

We tend to think time is linear, and make a few assumptions:

  • Time is agreed upon
  • We believe that events happen one after the other
  • We believe events have an exact order based on which event happened before another.

However in distributed systems

  • There is no global clock
  • Events can occur concurrently
  • Events occur independent of each other making them hard to order.

Total Ordering - When every event can be placed into a specific order. A single process can have total ordering.
Partial Ordering - When we can be sure that dependant events are ordered. But we do not know the exact order for every event. (casually consistent ?)

A -> B -> C

If we are sure B happened before C but are uncertain of when A occurred, we have a partially ordered system. A could've happened at any time.

In distributed systems we deal with partial ordering, nodes can only be certain about the ordering of their own events but not about the ordering of those that occur on other nodes.

@decanus
Copy link
Owner Author

decanus commented Jan 2, 2020

Causal ordering

Property of Distributed Systems: Messages sent between nodes may arrive zero or more times at any point after they are sent.

This property makes it impossible to agree on a time between multiple nodes. If we can't agree on time, we also can't fully agree on the order of events. We can however agree on some ordering if events are dependent. I send you a message, you receive it and acknowledge it before sending me a message.

Time is a total order. Causal order is a partial ordering, sometimes events happen with no causal relationship.

Causal ordering is conveyed between messages, since sending messages is the only way one node can affect another. If A -> B is not true, then A cannot have caused B. Since we have no notion of global time, this is the only thing that allows us to reason about causality in a distributed system.

Communication bounds causality

@decanus
Copy link
Owner Author

decanus commented Jan 2, 2020

Lamport's Logical Clocks

Physical time forms a natural partial ordering. Using time we know if a happened before b or b happened before a or if they are unrelated (concurrent).

denotes a happened before ordering.

Clocks are imprecise, we can't use them in a distributed system.

Clock Condition:

We define C as the system clock, a function from event to a timestamp.

∀a,b. a → b ⟹ C(a) < C(b)

The above means that for all events a, b if a happened before b then the clock time of a is smaller than that of b.

When a process P1 receives clock C0 from process P0 it sets its clock C1 to be greater than the received C0.

@decanus
Copy link
Owner Author

decanus commented Jan 2, 2020

Time and clocks and ordering of events in a distributed system (Medium Coinmonks)

Establishing a local order of events is simple, but how can we establish an order across multiple nodes?

We could have a physical clock, but these are not accurate and can drift.

We can define a distributed system as a collection of processes consisting of a queue of events (these events can be anything). When processes communicate, they send messages which are events.

  • If a comes before b in the same process, then a → b
  • If process i sends message a to process j, and j acknowledges that message in event b, then a → b (Ci(a) < Cj(b))
  • If a → b and b → c then a → c
  • If a does not happen before b and b does not happen before a then the events are concurrent. This makes it clear that we have a partial order as we can not have a total order over the complete system as process i does not know about all events occurring on process j.

Lamports clock is essentially a counter C, C ticks regularly in a process. Between any two events there needs to be at least one tick.

To get a total order we simply arbitrarily break ties.

@decanus
Copy link
Owner Author

decanus commented Jan 2, 2020

Logical Time and Lamport Clocks

We need to change our thinking from "when" something happened, to "before" what it happened. This is one of the main changes in thinking, it allows ordering without time.

@decanus
Copy link
Owner Author

decanus commented Jan 3, 2020

Time, Clocks, and the Ordering of Events in a Distributed System

Time is generally how we order events. Sometimes it is hard in a distributed system to state which event happened before another, the "happened before" relation is only a partial ordering of the system.

A system is distributed if the message transmission delay is not negligible compared to the time between events in a single process.

We can say that a happened before b if a causally affected b, we can say this without needing a notion of time within a system. Events are concurrent if neither causally affected the other.

With this ordering of events, we can add a clock to the system. The clock is a way of assigning a number to an event representing at which point in time an event has occurred.

clock Ci exists for every process Pi and assigns a number Ci(a) for every event a in that process.

C represents the entire system of clocks where C(b) assigns a number to event b where C(b) == Cj(b) if b is an event of process j.

The clocks we have implemented are logical clocks meaning they may be implemented with counters and not actual physical time.

If an event a happened before b then the clock value of a should be smaller than that of b. The converse does not hold as this would mean that all concurrent events must happen at the same clock value. If 2 events occur on one node, they can both be concurrent to the same event on another node without occurring at the same clock value.

Changing the value of Ci takes place between events, meaning that the changing of the value does not itself constitute an event.

When a node receives a message from another node, that message contains a clock value indicating its clock value on the sender node, the receiving node must then set its own clock value to be greater than the one received.

We can use these clocks to totally order the set of all events that occurred in our system by sorting them using their clock values. To break ties we use an arbitrary ordering of events.

@decanus decanus moved this from In progress to Done in research Jan 3, 2020
This was referenced Jan 3, 2020
@decanus decanus closed this as completed Jan 6, 2020
Repository owner locked as resolved and limited conversation to collaborators Jan 6, 2020
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Labels
Projects
research
  
Done
Development

No branches or pull requests

1 participant