Nobody Knows What Time It Is

@vaidehijoshi Nobody Knows What Time It Is Vaidehi Joshi

@vaidehijoshi hola!

@vaidehijoshi hola! i’m vaidehi

@vaidehijoshi i work on

@vaidehijoshi how things work

@vaidehijoshi time

@vaidehijoshi hard problem

@vaidehijoshi hardest problems

@vaidehijoshi 4/27/18 9:51 AM

@vaidehijoshi how did we all agree on this?

@vaidehijoshi vaidehi’s very (very!) brief history of telling time

@vaidehijoshi sundials

@vaidehijoshi

@vaidehijoshi egyptians greeks

@vaidehijoshi egyptians greeks romans

@vaidehijoshi

@vaidehijoshi water clocks

@vaidehijoshi

@vaidehijoshi incense clocks

@vaidehijoshi

@vaidehijoshi hourglass

@vaidehijoshi

@vaidehijoshi mechanical clock

@vaidehijoshi

@vaidehijoshi 19,192,631,770 cycles of cesium a single second =

@vaidehijoshi

@vaidehijoshi only half the question

@vaidehijoshi how did we agree on the time?

@vaidehijoshi great american railroad

@vaidehijoshi 10:15 10:30 10:04 10:25 10:02

@vaidehijoshi

@vaidehijoshi 10:15 10:02 ❓ ❓

@vaidehijoshi

@vaidehijoshi standard time zones

@vaidehijoshi

@vaidehijoshi ⏱ ⏰ local time train time

@vaidehijoshi Standard Time Act (1918)

@vaidehijoshi 1840

@vaidehijoshi greenwich mean time

@vaidehijoshi 1900

@vaidehijoshi 24 hour day, GMT offset

@vaidehijoshi international time zones

@vaidehijoshi

@vaidehijoshi distributed systems

@vaidehijoshi network of processes

@vaidehijoshi processes communication channel

@vaidehijoshi ticket booking system my server hipmunk united

@vaidehijoshi my server hipmunk united

@vaidehijoshi my server hipmunk united 8:00 pm 8:03 pm

@vaidehijoshi my server hipmunk united

@vaidehijoshi 8:03pm < 8:00pm ⁉

@vaidehijoshi ☹

@vaidehijoshi multiple processes asynchronous ^

@vaidehijoshi ordering of events time time

@vaidehijoshi just one process in a system

@vaidehijoshi a

@vaidehijoshi snapshot

@vaidehijoshi wait, but what is an “event”?

@vaidehijoshi 3. instruction within process itself 1. receiving a message
2. sending a message

@vaidehijoshi a 1 2 3 4 linearly

@vaidehijoshi a b c 1? 1? 1? 2? 2?

@vaidehijoshi drift

@vaidehijoshi ntp (network time protocol)

@vaidehijoshi doesn’t eliminate clock drift

@vaidehijoshi ⏳

@vaidehijoshi if one thing happened before another?

@vaidehijoshi timestamps

@vaidehijoshi

@vaidehijoshi “When I looked at the algorithm, I realized that
it wasn’t quite right. It permitted a system to do things that, in ways, seemed to violate causality. — Leslie Lamport

@vaidehijoshi

@vaidehijoshi it’s actually simpler than it sounds

@vaidehijoshi a

@vaidehijoshi 1. instruction

@vaidehijoshi a b c

@vaidehijoshi 3. receive 1. instruction 2. send

@vaidehijoshi events affecting one another

@vaidehijoshi events happening concurrently

@vaidehijoshi time isn’t linear anymore

@vaidehijoshi time

@vaidehijoshi time what happened before

@vaidehijoshi “happened before”, or →

@vaidehijoshi a → b p a b

@vaidehijoshi a → b p a q b

@vaidehijoshi p a q b r a → b →c
c

@vaidehijoshi

@vaidehijoshi causal paths

@vaidehijoshi p a q b r d c e g
h f a → d → e a → b→ g → h

@vaidehijoshi back to timestamps

@vaidehijoshi timestamps must follow causality

@vaidehijoshi counter (logical “clock”)

@vaidehijoshi p q r 0 0 0

@vaidehijoshi 1 p q r 0 0 0

@vaidehijoshi 1 1 p q r 0 0 0 1

@vaidehijoshi 1 p q r 0 0 0 1 1

@vaidehijoshi 1 0 1 p q r 0 0 0
1 1

@vaidehijoshi 1 1 p q r 0 0 0 1
1 + 1 2 2

@vaidehijoshi p q r 0 0 0 1 1 2

@vaidehijoshi anytime an event occurs, the logical clock counter must
be incremented

@vaidehijoshi when sending events, a process sends its own counter’s
value with it

@vaidehijoshi when receiving events, a process chooses the greater of
the two counters, and increments it by 1 to acknowledge the receive event

@vaidehijoshi and that’s it! that’s the entire algorithm.

@vaidehijoshi there is one problem. it’s still not clear if
something is causal or concurrent :(

@vaidehijoshi vector clocks (look them, up! they’re cool.)

@vaidehijoshi nobody knows what time it is …but maybe that’s
actually okay

@vaidehijoshi

@vaidehijoshi basecs.org ✨

@vaidehijoshi basecs.org muchas gracias! ✨

Nobody Knows What Time It Is

Nobody Knows What Time It Is

More Decks by Vaidehi Joshi

Featured

Transcript