Time, Clocks and the Reordering of Events - PWL San Francisco 14-Jul-2016

Time, Clocks and the Reordering of Events Papers We Love
Too - San Francisco 02016-7-14 18:30 Paul Borrill, EARTH Computing, Inc @plborrill [email protected] Lamport’s Unﬁnished Revolution

Lamport (Logical) Clocks Failure handling Computer Scientists & Physicists Notions
of TIME Reversible Computing Vive la Revolution The Matrix Quantum Computing Lamport’s Unﬁnished Revolution Image courtesy Shutterstock

Leslie Lamport, winner of the ACM Turing Prize, 2013 ‘78
Time, Clocks and the Ordering of Events in a Distributed System Operating R. Stockton Gaines Systems Editor Time, Clocks, and the Ordering of Events in a Distributed System Leslie Lamport Massachusetts Computer Associates, Inc. The concept of one event happening before another in a distributed system is examined, and is shown to define a partial ordering of the events. A distributed algorithm is given for synchronizing a system of logical clocks which can be used to totally order the events. The use of the total ordering is illustrated with a method for solving synchronization problems. The algorithm is then specialized for synchronizing physical clocks, and a bound is derived on how far out of synchrony the clocks can become. Key Words and Phrases: distributed systems, computer networks, clock synchronization, multiprocess systems CR Categories: 4.32, 5.29 Introduction A distributed system consists of a collection of distinct processes which are spatially separated, and which communicate with one another by exchanging messages. A network of interconnected computers, such as the ARPA net, is a distributed system. A single computer can also be viewed as a distributed system in which the central control unit, the memory units, and the input-output channels are separate processes. A system is distributed if the message transmission delay is not negligible compared to the time between events in a single process. We will concern ourselves primarily with systems of spatially separated computers. However, many of our remarks will apply more generally. In particular, a multiprocessing system on a single computer involves problems similar to those of a distributed system because of the unpredictable order in which certain events can occur. In a distributed system, it is sometimes impossible to say that one of two events occurred first. The relation "happened before" is therefore only a partial ordering of the events in the system. We have found that problems often arise because people are not fully aware of this fact and its implications. In this paper, we discuss the partial ordering defined by the "happened before" relation, and give a distributed algorithm for extending it to a consistent total ordering of all the events. This algorithm can provide a useful mechanism for implementing a distributed system. We illustrate its use with a simple method for solving synchronization problems. Unexpected, anomalous behavior can occur if the ordering obtained by this algorithm differs from that perceived by the user. This can be avoided by introducing real, physical clocks. We describe a simple method for synchronizing these clocks, and derive an upper bound on how far out of synchrony they

Leslie Lamport ‘78 Time, Clocks and the Ordering of Events
in a Distributed System Introduced: • Logical Clocks (a distributed algorithm for synchronizing a system of logical clocks which can be used to TOTALLY order events) • A time bound on the synchronization of physical clocks (This algorithm depends heavily on there being no faults in the system, and is not used by practitioners) Lamport Clocks are all about assigning labels to events, and that those assignments must be causally related

Leslie Lamport ‘78 Time, Clocks and the Ordering of Events
in a Distributed System Abstract The concept of one event happening before another in a distributed system is examined, and is shown to deﬁne a partial ordering of the events. A distributed algorithm is given for synchronizing a system of logical clocks which can be used to totally order the events. The use of the total ordering is illustrated with a method for solving synchronization problems. The algorithm is then specialized for synchronizing physical clocks, and a bound is derived on how far out of synchrony the clocks can become. Key Words and Phrases: distributed systems, computer networks, clock synchronization, multiprocess systems concept of one event happening before another in a distributed system is … is shown to define a partial ordering of the events.

Introduction The concept of time is fundamental to our way
of thinking. It is derived from the more basic concept of the order in which events occur. We say that something happened at 3:15 if it occurred after our clock read 3:15 and before it read 3:16. The concept of the temporal ordering of events pervades our thinking about systems. For example, in an airline reservation system we specify that a request for a reservation should be granted if it is made before the ﬂight is ﬁlled. However, we will see that this concept must be carefully reexamined when considering events in a distributed system. A distributed system consists of a collection of distinct processes which are spatially separated, and which communicate with one another by exchanging messages. A network of interconnected computers, such as the ARPA net, is a distributed system. A single computer can also be viewed as a distributed system in which the central control unit, the memory units, and the input- output channels are separate processes. A system is distributed if the message transmission delay is not negligible compared to the time between events in a single process. Leslie Lamport ‘78 Time, Clocks and the Ordering of Events in a Distributed System The concept of time is fundamental to our way of thinking. It is derived from the more basic concept of the order in which events occur. A distributed system consists of a collection of distinct processes which are spatially separated, and which communicate with one another by exchanging messages.

We will concern ourselves primarily with systems of spatially separated
computers. However, many of our remarks will apply more generally. In particular, a multiprocessing system on a single computer involves problems similar to those of a distributed system because of the unpredictable order in which certain events can occur. In a distributed system, it is sometimes impossible to say that one of two events occurred first. The relation "happened before" is therefore only a partial ordering of the events in the system. We have found that problems often arise because people are not fully aware of this fact and its implications. In this paper, we discuss the partial ordering defined by the "happened before" relation, and give a distributed algorithm for extending it to a consistent total ordering of all the events. This algorithm can provide a useful mechanism for implementing a distributed system. We illustrate its use with a simple method for solving synchronization problems. Unexpected, anomalous behavior can occur if the ordering obtained by this algorithm differs from that perceived by the user. This can be avoided by introducing real, physical clocks. We describe a simple method for synchronizing these clocks, and derive an upper bound on how far out of synchrony they can drift. Leslie Lamport ‘78 Time, Clocks and the Ordering of Events in a Distributed System Introduces “happened before” relation “happened before” is meaningless unless intimately associated with “happened where” Well articulated by Lamport, but frequently misunderstood by readers

a, CY ,Y (9 (9 ~o ~ o P4' P3
P2' Pl ~ q7 q6 q5 ql r 4 r 3 r 2 r 1 event. We are assuming that the events of a process form a sequence, where a occurs before b in this sequence if a happens before b. In other words, a single process is cy (9 (9 O O -2 - - - q6 P3' ~ ~ ~ ~ ~ _ ~ ~ - ~ the diagram by moving forward in tim and message lines. For example, we h Figure 1. Space-time diagram The horizontal direction represents space, and the vertical direction represents time— later times being higher than earlier ones. The dots denote events, the vertical lines denote processes, and the wavy lines denote messages Basic Space-Time Diagram, Processes each along their own “timeline”

a, CY ,Y (9 (9 ~o ~ o P4' P3
P2' Pl ~ q7 q6 q5 ql r 4 r 3 r 2 r 1 event. We are assuming that the events of a process form a sequence, where a occurs before b in this sequence if a happens before b. In other words, a single process is cy (9 (9 O O -2 - - - q6 P3' ~ ~ ~ ~ ~ _ ~ ~ - ~ the diagram by moving forward in tim and message lines. For example, we h Figure 1. m f s l cy c~ (9 (9 ~) O O U -2 - - - q6 -- ;#.i Y _ P3' ~ ~ ~ ~ ~ _ ~ ~ - ~ r3 the diagram by moving forward in time along process and message lines. For example, we have p, --~ r4 in Figure 1. Space-time diagram The horizontal direction represents space, and the vertical direction represents time— later times being higher than earlier ones. The dots denote events, the vertical lines denote processes, and the wavy lines denote messages

Space-time diagram The horizontal direction represents space, and the vertical
direction represents time— later times being higher than earlier ones. The dots denote events, the vertical lines denote processes, and the wavy lines denote messages Key Assumptions: Events not Durations Continuous Physical Time Background ∴ Irreversible Time & Messages ∴ Timestamps are Monotonic Fig. 3. CY n¢ 8 8 8 c~! ~ ~iLql ~ .r 4 condition C2 means that every mess a tick line. From the pictorial meanin see why these two conditions impl dition. We can consider the tick lines to nate lines of some Cartesian coordina time. We can redraw Figure 2 to str dinate lines, thus obtaining Figure 3 alternate way of representing the sam as Figure 2. Without introducing the time into the system (which requires i clocks), there is no way to decide whi is a better representation. The reader may find it helpful dimensional spatial network of proce three-dimensional space-time diagr messages are still represented by l become two-dimensional surfaces. Let us now assume that the proce and the events represent certain a

Richard Feynman

Richard Feynman Leslie Lamport

Another way of viewing the definition is to say that
a → b means that it is possible for event a to causally affect event b. Two events are concurrent if neither can causally affect the other. For example, events p3 and q3 of Figure 1 are concurrent. Even though we have drawn the diagram to imply that q3 occurs at an earlier physical time than p3, process P cannot know what process Q did at q3 until it receives the message at p4, (Before event p4, P could at most know what Q was planning to do at q3.) This definition will appear quite natural to the reader familiar with the invariant space-time formulation of special relativity, as described for example in [1] or the first chapter of [2]. In relativity, the ordering of events is defined in terms of messages that could be sent. However, we have taken the more pragmatic approach of only considering messages that actually are sent. We should be able to determine if a system performed correctly by knowing only those events which did occur, without knowing which events could have occurred. Leslie Lamport ‘78 Time, Clocks and the Ordering of Events in a Distributed System This definition will appear quite natural to the reader familiar with the invariant spacetime formulation of special relativity … we have taken the more pragmatic approach of only considering messages that actually are sent. We should be able to determine if a system performed correctly by knowing only those events which did occur, without knowing which events could have occurred.

if either (i) Ci <a> < Cj<b> or (ii) Ci<a>
= Cj<b> and Pi < Pj. It is easy to see that this defines a total ordering, and that the Clock Condition implies that if a → b then a ⟹ b. In other words, the relation ⟹ is a way of completing the "happened before" partial ordering to a total ordering. [Footnote 3 : The ordering ≺ establishes a priority among the processes. If a “fairer” method is desired, then ≺ can be made a function of the clock value. For example, if Ci (a) = Cj(b) and j < i, then we can let a ⟹ b if j < Ci(a) mod N ≤ i, and b ⟹ a otherwise; where N is the total number of processes.] The ordering ⟹ depends upon the system of clocks Ci, and is not unique. Different choices of clocks which satisfy the Clock Condition yield different relations ⟹. Given any total ordering relation ⟹ which extends →, there is a system of clocks satisfying the Clock Condition which yields that relation. It is only the partial ordering which is uniquely determined by the system of events. Being able to totally order the events can be very useful in implementing a distributed system. In fact, the reason for implementing a correct system of logical clocks is to obtain such a total ordering. We will illustrate the use of this total ordering of events by solving the following version of the mutual exclusion problem. Consider a system composed of a fixed collection of processes which share a single resource. Only one process can use the resource at a time, so the processes must synchronize themselves to avoid conflict. We wish to find an algorithm for granting the resource to a process which satisfies the following three conditions: (I) A process which has been granted the resource must release it before it can be granted to another process. (II) Different requests for the resource must be granted in the order in which they are made. (III) If every process Leslie Lamport ‘78 Time, Clocks and the Ordering of Events in a Distributed System The ordering ⟹ depends upon the system of clocks Ci, and is not unique. Different choices of clocks which satisfy the Clock Condition yield different relations ⟹. Given any total ordering relation ⟹ which extends →, there is a system of clocks satisfying the Clock Condition which yields that relation. It is only the partial ordering which is uniquely determined by the system of events

latter message, P2 sends a request to P0. It is
possible for P2's request to reach P0 before Pl's request does. Condition II is then violated if P2's request is granted first. To solve the problem, we implement a system of clocks with rules IR1 and IR2, and use them to define a total ordering ⟹ of all events. This provides a total ordering of all request and release operations. With this ordering, finding a solution becomes a straightforward exercise. It just involves making sure that each process learns about all other processes' operations. To simplify the problem, we make some assumptions. They are not essential, but they are introduced to avoid distracting implementation details. We assume first of all that for any two processes Pi and Pj, the messages sent from Pi to Pj are received in the same order as they are sent. Moreover, we assume that every message is eventually received. (These assumptions can be avoided by introducing message numbers and message acknowledgment protocols.) We also assume that a process can send messages directly to every other process. Each process maintains its own request queue which is never seen by any other process. We assume that the request queues initially contain the single message T0:P0 requests resource, where P0 is the process initially granted the resource and T0 is less than the initial value of any clock. Leslie Lamport ‘78 Time, Clocks and the Ordering of Events in a Distributed System we assume that every message is eventually received. (These assumptions can be avoided by introducing message numbers and message acknowledgment protocols.) We also assume that a process can send messages directly to every other process

Each process independently simulates the execution of the State Machine,
using the commands issued by all the processes. Synchronization is achieved because all processes order the commands according to their timestamps (using the relation ⟹) , so each process uses the same sequence of commands. A process can execute a command timestamped T when it has learned of all commands issued by all other processes with timestamps less than or equal to T. The precise algorithm is straightforward, and we will not bother to describe it. This method allows one to implement any desired form of multiprocess synchronization in a distributed system. However, the resulting algorithm requires the active participation of all the processes. A process must know all the commands issued by other processes, so that the failure of a single process will make it impossible for any other process to execute State Machine commands, thereby halting the system. Leslie Lamport ‘78 Time, Clocks and the Ordering of Events in a Distributed System “The precisce algortithm is straightforward and we will not bother to describe it” Introduces the state machine: This is the genesis of the Paxos Consensus Algorithm

The problem of failure is a diﬃcult one, and it
is beyond the scope of this paper to discuss it in any detail. We will just observe that the entire concept of failure is only meaningful in the context of physical time. Without physical time, there is no way to distinguish a failed process from one which is just pausing between events. A user can tell that a system has "crashed" only because he has been waiting too long for a response. A method which works despite the failure of individual processes or communication lines is described in [3]. Leslie Lamport ‘78 Time, Clocks and the Ordering of Events in a Distributed System The problem of failure is a difficult one, and it is beyond the scope of this paper to discuss it in any detail. the entire concept of failure is only meaningful in the context of physical time Without physical time, there is no way to distinguish a failed process from one which is just pausing between events This significantly pre-dates the FLP result in 1985

Physical Clocks Let us introduce a physical time coordinate into
our space-time picture, and let Ci(t) denote the reading of the clock Ci at physical time t. [Footnote 8: We will assume a Newtonian space-time. If the relative motion of the clocks or gravitational effects are not negligible, then Ci(t) must be deduced from the actual clock reading by transforming from proper time to the arbitrarily chosen time coordinate.] For mathematical convenience, we assume that the clocks run continuously rather than in discrete "ticks." (A discrete clock can be thought of as a continuous one in which there is an error of up to 1⁄2 "tick" in reading it.) More precisely, we assume that Ci(t) is a continuous, differentiable function of t except for isolated jump discontinuities where the clock is reset. Then dCi(t)/dt represents the rate at which the clock is running at time t. In order for the clock Ci to be a true physical clock, it must run at approximately the correct rate. That is, we must have dCi(t)/dt ≈ 1 for all t. More precisely, we will assume that the following condition is satisfied: PC1. There exists a constant << 1  such that for all i: ⎪ dCi(t)/dt - 1 ⎪ < For typical crystal controlled clocks, ≤ 10-6. Leslie Lamport ‘78 Time, Clocks and the Ordering of Events in a Distributed System [Footnote 8: We will assume a Newtonian space-time. If the relative motion of the clocks or gravitational effects are not negligible, then Ci(t) must be deduced from the actual clock reading by transforming from proper time to the arbitrarily chosen time coordinate.] The infamous footnote 8 …. Principal assumption: a smooth “background” of Minkowski spacetime

Linearizability Sequential Regular Safe Eventual Causal+ Real-time causal Causal Read-your-writes
(RYW) Monotonic Reads (MR) Writes-follow-reads (WFR) Monotonic Writes (MW) PRAM (FIFO) Fork Fork* Fork-join causal Bounded fork-join causal Fork sequential Eventual linearizability Timed serial & ∆,Γ-atomicity Processor Fork-based models Slow memory Per-object models Per-record timeline & Coherence Timed causal Bounded staleness & Delta Weak fork-lin. Strong eventual Quiescent Weak k-regular k-safe PBS k-staleness k-atomicity Release Weak ordering Location Scope Lazy release Entry Synchronized models Causal models Staleness-based models Per-object causal Per-key sequential Prefix linearizable Prefix sequential PBS t-visibility Hybrid Tunable Rationing RedBlue Conit Vector-field PBS <k,t>-staleness Composite and tunable models Session models Eventual serializability All Roads Lead To Linearizability

AL: After Lamport BL: Before Lamport

Who will ﬁnish the revolution started by Leslie Lamport? A
General Theory of Concurrency?

Epicycles rotated with a period of a Earth year, they
were nothing but the shadow of Earth’s motion. Other adjustments required still more circles; it took fifty-five circles to get it all to work. By assigning the right periods to each of the big circles, Ptolemy calibrated the model to a remarkable degree of accuracy. A few centuries later, Islamic astronomers fine-tuned the Ptolemaic model, and in Tycho’s time it predicted the positions of the planets, the sun, and moon to an accuracy of 1 part in 1,000— good enough to agree with most of Tycho’s observations. Ptolemy’s model was beautiful mathematically, and its success convinced astronomers and theologians for more than a millennium that its premises were correct. And how could they be wrong? After all, the model had been confirmed by observation.* Then along came Copernicus … Epicycles? 15th Century Astrolabe, from the Museum of the History of Science, Oxford. *FROM Smolin, Lee. “Time Reborn” (2013).

Ptolemyi or Copernici?

Image courtesy Shutterstock

s @ @ @ @ @ @ @ @ @
@ @ @ @ e forward light cone from e - future of e ↵ x - y space plane t i m e ⌦ ⌦ ⌦ ⌦ ⌦ ⌦ ⌦ 6 Figure 1: Space-Time The Mutual Exclusion Problem Part I: A Theory of Interprocess Communication L. Lamport1 Digital Equipment Corporation 6 October 1980 Revised: 1 February 1983 1 May 1984 27 February 1985 June 26, 2000 To appear in Journal of the ACM 1Most of this work was performed while the author was at SRI International, where it was supported in part by the National Science Foundation under grant number MCS-7816783.

] Op b . and blue ur model, nd ./
= cquire no ) = ;). and blue our bank- e consis- re blue. nsistency nger than justed to a token intain an mally, we uates to a ery event plying its . with Fig- , a query m is the th T and r solving xplicitly. o reason roof rule ained by spective, m the op- t I holds a compu- te of a the reflexive and transitive closure of a relation R . For a relation R 2 P(A ⇥ B) and a predicate P 2 P(A) , the expression R(P) denotes the image of P under R . r r (a) (b) e X X X Fe↵ o ( ) Figure 6. Graphical illustrations of (a) the state-based rule; and (b) the event-based rule. o ’s effect changes the state of r , since this effect is applied to the state where it was generated: 8 . ( 2 I =) Fe↵ o ( )( ) 2 I). (10) The difficulty comes from the need to consider how o ’s effect changes the state of any other replica r 0 that receives it; see Fig- ure 6(a). At the time of the receipt, r 0 may be in a different state 0, due to operations executed at r 0 concurrently with o . We can show that it is sound to assume that this state 0 also satisfies the invariant. Thus, to check that the operation o preserves the invariant when applied at any replica, it is sufficient to ensure 8 , 0 . ( , 0 2 I =) Fe↵ o ( )( 0 ) 2 I). (11) However, establishing this without knowing anything about the relationship between and 0 is a tall order. In the bank account example, both = 100 and 0 = 0 satisfy the integrity invariant (5). Then Fe↵ withdraw (100)( )( 0 ) = 100 , which violates the invariant. Condition (11) fails in this case because it does not take into account the tokens acquired by withdraw. The proof rule in Figure 5 addresses the weakness of (11) by al- lowing us to assume a certain relationship between the state where an operation is generated ( ) and where its effect is applied ( 0), which takes into account the tokens acquired by the operation. To express this assumption, the rule uses a form of rely-guarantee reasoning [27]. Namely, it requires us to associate each token ⌧ with a guarantee relation G(⌧) , describing all possible state changes that an operation acquiring ⌧ can cause. Crucially, this includes not only the changes that the operation can cause on the state of its origin replica, but also any change that its effect causes at any other replica it is propagated to. We also have a guarantee relation G0 , describing Marc Shapiro Einstein Carlos Bacquero (from Carlos) acmqueue | march-april 2016 97 abort [1,1,0) tx aborted [2,4,1) replica 1 tx prepare [0,1,0) tx abort [1,4,1) r1 abort [1,3,1) r2 commit [0,2,1) tx manager commit [0,1,1) tx aborted [1,4,2) replica 2 FIGURE 1: Time-space diagram of an execution with three nodes 1 Newton Also, Herlihy & Shavit

Carlos Baquero

Logical Clocks are easy Sometimes all you need is the
right language Carlos Baquero

The trouble with timestamps Kyle Kingsbury

Its all about Heisenberg Master Slave is a Solution Oh
wait … Immutability changes everything Oh wait … Pat Helland

Darn it, that last write just got lost again! Sean
Cribbs Figures from Pat Helland

Disconnected Time May Be Slower or Faster Than Expected From
Pat Helland

Why would you want to coordinate that? Peter Bailis Coordination
Avoidance in Distributed Databases By Peter David Bailis A dissertation submitted in partial satisfaction of the requirements for the degree of Doctor of Philosophy in Computer Science in the Graduate Division of the University of California, Berkeley Committee in charge: Professor Joseph M. Hellerstein, Co-Chair Professor Ion Stoica, Co-Chair Professor Ali Ghodsi Professor Tapan Parikh Fall 2015

’Cause I’m Strong Enough: Reasoning about Consistency Choices in Distributed
Systems Alexey Gotsman IMDEA Software Institute, Spain Hongseok Yang University of Oxford, UK Carla Ferreira NOVA LINCS, DI, FCT, Universidade NOVA de Lisboa, Portugal Mahsa Najafzadeh Sorbonne Universit´ es, Inria, UPMC Univ Paris 06, France Marc Shapiro Sorbonne Universit´ es, Inria, UPMC Univ Paris 06, France Abstract Large-scale distributed systems often rely on replicated databases that allow a programmer to request different data consistency guarantees for different operations, and thereby control their performance. Using such databases is far from trivial: requesting stronger consistency in too many places may hurt performance, and requesting it in too few places may violate correctness. To help program- mers in this task, we propose the first proof rule for establishing that a particular choice of consistency guarantees for various operations on a replicated database is enough to ensure the preservation of a given data integrity invariant. Our rule is modular: it allows reasoning about the behaviour of every operation separately under some assumption on the behaviour of other operations. This leads to simple reasoning, which we have automated in an SMT-based tool. We present a nontrivial proof of soundness of our rule and illustrate its use on several examples. Categories and Subject Descriptors D.2.4 [Software Engineer- ing]: Software/Program Verification; F.3.1 [Logics and Meanings of Programs]: Specifying and Verifying and Reasoning about Pro- grams Keywords Replication; causal consistency; integrity invariants 1. Introduction To achieve availability and scalability, many modern distributed systems rely on replicated databases, which maintain multiple replicas of shared data. Clients can access the data at any of the replicas, and these replicas communicate changes to each other using message passing. For example, large-scale Internet services use data replicas in geographically distinct locations, and applications for mobile devices keep replicas locally to support offline use. Ideally, we would like replicated databases to provide strong consistency, i.e., to behave as if a single centralised node handles all operations. However, achieving this ideal usually requires synchronisation among replicas, which slows down the database and even makes it unavailable if network connections between replicas fail [2, 24]. For this reason, modern replicated databases often eschew synchronisation completely; such databases are commonly dubbed eventually consistent [47]. In these databases, a replica performs an operation requested by a client locally without any synchronisation with other replicas and immediately returns to the client; the effect of the operation is propagated to the other replicas only eventually. This may lead to anomalies—behaviours deviating from strong consistency. One of them is illustrated in Figure 1(a). Here Alice makes a post while connected to a replica r1 , and Bob, also connected to r1 , sees the post and comments on it. After each of the two operations, r1 sends a message to the other replicas in the system with the update performed by the user. If the messages with the updates by Alice and Bob arrive to a replica r2 out of order, then Carol, connected to r2 , may end up seeing Bob’s comment, but not Alice’s post it pertains to. The consistency model of a replicated database restricts the anomalies that it exhibits. For example, the model of causal consistency [33], which we consider in this paper, disallows the anomaly in Figure 1(a), yet can be implemented without any synchronisation. The model ensures that all replicas in the system see causally dependent events, such as the posts by Al- ice and Bob, in the order in which they happened. However, causal consistency allows different replicas to see causally independent events as occurring in different orders. This is illustrated in Fig- ure 1(b), where Alice and Bob concurrently make posts at r1 and r2 . Carol, connected to r3 initially sees Alice’s post, but not Bob’s, and Dave, connected to r4 , sees Bob’s post, but not Alice’s. This outcome cannot be obtained by executing the operations in any total order and, hence, deviates from strong consistency. Such anomalies related to the ordering of actions are often acceptable for applications. What is not acceptable is to violate cru- cial well-formedness properties of application data, called integrity invariants. Consistency models that do not require any synchronisation are often too weak to ensure these. For example, consider a toy banking application where the database stores the balance of a single account that clients can make deposits to and withdrawals from. In this case, an integrity invariant may require the account balance to be always non-negative. Consider the database compu- This is the author’s version of the work. It is posted here for your personal use. Not for redistribution. The definitive version was published in the following publication: POPL’16 , January 20–22, 2016, St. Petersburg, FL, USA ACM. 978-1-4503-3549-2/16/01... http://dx.doi.org/10.1145/2837614.2837625 371 Timestamps in Message-Passing Systems That Preserve the Partial Ordering Colin J. Fidge Department of Computer Science, Australian National University, Canberra, A CT. ABSTRACT Timestamping is a common method of totally ordering events in concurrent programs. However, for applications requiring access to the global state, a total ordering is inappro- priate. This paper presents algorithms for timestamping events in both synchronous and asynchronous n1essage-passing programs that allow for access to the partial ordering in- herent in a parallel system. The algorithms do not change the con1munications graph or require a central timestamp issuing authority. Keywords and phrases: concurrent programming, message-passing, timestamps, logical clocks CR categories: D.l.3 INTRODUCTION A fundamental problem in concurrent programming is determining the order in which events in different processes occurred. An obvious solution is to attach a number representing the current time to a permanent record of the execution of each event. This assumes that each process can access an accurate clock, but practical parallel systems, by their very nature, make it difficult to ensure consistency among the processes. There are two solutions to this problem. Firstly, have a central process to issue timestamps, i.e. provide the system with a global clock. In practice this has the major disadvantage of needing communication links from all processes to the central clock. More acceptable are separate clocks in each process that are kept synchronised as much as necessary to ensure that the timestamps represent, at the very least, a possible ordering of events (in light of the vagaries of distributed scheduling). Lamport (1978) describes just such a scheme of logical clocks that can be used to totally order events, without the need to introduce extra communication links. However this only yields one of the many possible, and equally valid, event orderings defined by a particular distributed computation. For problems concerned with the global program state it is far more useful to have access to the entire partial ordering, which defines the set of consistent "slices" of the global state at any arbitrary moment in time. This paper presents an implementation of the partially ordered relation "happened before" that is true for two given events iff the first could causally affect the second in all possible interleavings of events. This allows access to all possible global states for a particular distributed computation, rather than a single, arbitrarily selected ordering. Lamport's totally ordered relation is used as a starting point. The algorithm is first defined for the asynchronous case, and then extended to cater for concurrent programs using synchronous message-passing. ‘88 ‘88 Vector Clocks

P P:0 Q:-- R:-- Q P:-- Q:0 R:-- R P:--
Q:-- R:0 P P:1 Q:2 R:1 P P:2 Q:2 R:1 P P:3 Q:3 R:3 Q P:-- Q:1 R:1 Q P:-- Q:2 R:1 Q P:-- Q:3 R:1 Q P:2 Q:4 R:1 Q P:2 Q:5 R:1 R P:-- Q:-- R:1 R P:-- Q:3 R:2 R P:-- Q:3 R:3 R P:2 Q:5 R:4 R P:2 Q:5 R:5 P P:4 Q:5 R:5 t Process Causal History Future Effect slope ≤ c slope ≤ c slope ≤ c slope ≤ c 11 12 13 14 21 22 23 24 25 32 31 33 34 35

Why Can’t Links Be Reversible?

‘91 ‘94

So your packets can be dropped, delayed, duplicated, reoordered or
just plain f**ked Kyle Kingsbury

Summary • Defined “happened before” relation: a partial order •
Defined “logical timestamps” which forms an arbitrary total order, restricting the available concurrency of a system (i.e. algorithm proceeds no faster than a single thread execution) • This “concurrency efficiency loss” gets worse as: • We add more nodes to a distributed system • These nodes become more spatially separated • Our processors and networks get faster • Our processors are comprised of more cores

There is no now Justin Sheehy

I agree

Simultaneity is a Myth “A circular argument: To determine the
simultaneity of distant events we need to know a velocity, and to measure a velocity we require knowledge of the simultaneity of distant events” * *Quoting Reichenbach, in: “Concepts of Simultaneity. From Antiquity to Einstein and Beyond.” Max Jammer( 2006)

Euler’s Identity

Pi Patel Richard Parker

Pi Patel

A smooth background of spacetime?

Richard Parker

What is Time? • Time is change that we can
count • All change is part of a tree; pick your root • Entanglements are roots of irreversible change • Anything that can happen can unhappen • Messages that can be sent can be unsent

ER=EPR Leonard Susskind

The man himself … Can you prove that?

To get from the unspeakable to the better speakable John
S. Bell John S. Bell

“We have to bear in mind that all our propositions
involving time are always propositions about simultaneous events” Einstein

either quantum mechanics must break down, or our understanding of
spacetime must be wrong Joseph Polchinski

2. LVARS: LATTICE-BASED DATA STRUCTURES FOR DETERMINISTIC PARALLELISM (Bot,Bot) (Bot,T)
(T,Bot) (T,T) Top (F,F) (F,Bot) (Bot,F) (T,F) (F,T) Figure 2.7. The lattice of states that an AndLV can take on. The ﬁve red sta lattice correspond to a false result, and the one green state corresponds to a t We can represent the states an AndLV can take on as pairs (x, y), where each of x "Qi. The ("Qi, "Qi) state is the state in which no input has yet been received, and element in the lattice of states that our AndLV can take on, shown in Figure 2.7. An Lindsey Kuper What about lattice variables to capture causality?

Ta da! Mark van Raamsdonk Spacetime is built from entanglement

Christopher Meiklejohn Order and causality expressed as lattices

Alan Turing Brian Swingle Entanglement is transferable and it’s universal

What I’ve learned about time is that we still don’t
fully understand it Max Tegmark

Simultaneity is a Myth Maurice Herlihy and Nir Shavit: The
Art of Multiprocessor Programming [2008]: "In 1689, Isaac Newton stated ‘absolute, true and mathematical time, of itself and from its own nature, ﬂows equably without relation to anything external.’” “We endorse his notion of time" A notion of time proven incorrect over a hundred years ago ...

if nothing were to change we could not say that
time passes Julian Barbour

a subsystem of an entangled state works as a "clock"
of another subsystem Ta da! Lorenzo Maccone

The Arrow of Time Dilemma* The laws of physics are
invariant for time inversion. The phenomena we see everyday are not (entropy increases) Within a quantum mechanical framework, all phenomena which leave a trail of information behind (and hence can be studied by physics) are those where entropy necessarily increases or remains constant All phenomena where the entropy decreases must not leave any information of their having happened. This situation is completely indistinguishable from their not having happened at all The second law of thermodynamics is reduced to a tautology: physics cannot study those processes where entropy has decreased, even if they were commonplace– because the evidence has been erased *Lorenzo Maccone. “Quantum Solution to the Arrow-of-Time Dilemma.” Physical Review Letters 103, no. 8 (2009)

Shh … don’t tell that Schwinger fellow, but it’s really
all particles … Richard Feynman

Oh shit … That means time goes backwards for positrons
…

A Myth: Common Error In reality, a distributed program runs
on multiple nodes; with multiple CPUs and multiple streams of operations coming in. You can still assign a total order, but it requires either accurate clocks or some form of communication. You could timestamp each operation using a completely accurate clock then use that to ﬁgure out the total order. Or you might have some kind of communication system that makes it possible to assign sequential numbers as in a total order. – Not even wrong – So what if you did it?

General Theory of Concurrency Physicists and computer scientists are talking
past each other when they talk about time If we could resolve that we might make progress on a general theory of concurrency

A computer's task is often taken to be that of
starting with some input, grinding for a while, and eventually returning an output. Remarkably, all such tasks can be accomplished "reversibly", with an arbitrarily low intrinsic entropy cost, and in reasonable space and time relative to irreversible approaches. Robin Hanson, 1992

Reversible Computing

Reversible Time: Secret to Concurrency •Google created the ﬁrst WAN
scale SQL in Spanner, by redeﬁning the time API: •Uses GPS Clocks •Time is no longer a single scalar, it is now an “interval bounded by events”, testable through an API •Distributed systems today use timestamps as a crutch •What happens when they go backwards? Image courtesy Shutterstock

Seth Lloyd entanglement might explain the arrow of time

You know, you really ought to use formal methods for
that! Caitie McCaﬀrey

Ta da! Spacetime is doomed, and something has to replace
it Nima Arkani-Hamed

You want proof I’ll give you proof!

Is Quantum Computing speedup real or an illusion? Scott Aaronson

Imperial College London Department of Physics Negative Probabilities in Physics:
a Review Adam C. Levy September 2015 Submitted in part fulﬁlment of the requirements for the degree of Master of Science in Physics of Imperial College London Interpretations of Negative Probabilities M. Burgin Department of Mathematics University of California, Los Angeles 405 Hilgard Ave. Los Angeles, CA 90095 Abstract In this paper, we give a frequency interpretation of negative probability, as well as for extended probability, demonstrating that to a great extent these new types of probabilities, behave as conventional probabilities. Extended probability comprises both conventional probability and negative probability. The frequency interpretation of negative probabilities gives supportive evidence to the axiomatic system built in (Burgin, 2009) for extended probability as it is demonstrated in this paper that frequency probabilities satisfy all axioms of extended probability. Keywords: probability; negative probability; extended probability; axiom; relative frequency; random experiment; random event

Time and Computer Science Simultaneity is a Myth “at the
same time” is like asking what’s north of the north pole Negative probability is just as real as positive probability Just with before and after subsituted In quantum mechanics, all proabilities are complex Time is change, and change can be represented as a tree, be careful what to pick for a root

The universe is like a box of chocolates Lee Smolin

A Potential Insight: The Subtime Conjecture “We must, therefore, be
prepared to find that further advance into this region will require a still more extensive renunciation of features which we are accustomed to demand of the space time mode of description” ~ Niels Bohr

Rasputin Genius or lunatic?

Morpheus

Would you like to take the red pill or the
blue pill?

I mean, like, you really want to take the red
pill? Morpheus

Nature News

Computer Science Driving? DEMONIC programming: a computational language for single-particle
equilibrium thermodynamics, and its formal semantics Samson Abramsky Dominic Horsman Department of Computer Science, University of Oxford, Parks Road, Oxford, OX1 3QD, UK { samson.abramsky,clare.horsman } @cs.ox.ac.uk Maxwell’s Demon, ‘a being whose faculties are so sharpened that he can follow every molecule in its course’, has been the centre of much debate about its abilities to violate the second law of thermodynamics. Landauer’s hypothesis, that the Demon must erase its memory and incur a thermodynamic cost, has become the standard response to Maxwell’s dilemma, and its implications for the thermodynamics of computation reach into many areas of quantum and classical computing. It remains, however, still a hypothesis. Debate has often centred around simple toy models of a single particle in a box. Despite their simplicity, the ability of these systems to accurately represent thermodynamics (specifically to satisfy the second law) and whether or not they display Landauer Erasure, has been a matter of ongoing argument. The recent Norton-Ladyman controversy is one such example. In this paper we introduce a programming language to describe these simple thermodynamic processes, and give a formal operational semantics and program logic as a basis for formal reasoning about thermodynamic systems. We formalise the basic single-particle operations as statements in the language, and then show that the second law must be satisfied by any composition of these basic operations. This is done by finding a computational invariant of the system. We show, furthermore, that this invariant requires an erasure cost to exist within the system, equal to kT ln2 for a bit of information: Landauer Erasure becomes a theorem of the formal system. The Norton-Ladyman controversy can therefore be resolved in a rigorous fashion, and moreover the formalism we introduce gives a set of reasoning tools for further analysis of Landauer erasure, which are provably consistent with the second law of thermodynamics. 1 Introduction The issue with Maxwell’s Demon is now resolved, thanks to formal methods from computer science Samson Abramsky

I told you you should use formal methods for that!
Caitie McCaﬀrey

Who will ﬁnish the revolution Lamport started? A General Theory
of Concurrency **All of You**

Leslie was right in the ﬁrst place, it’s not about
time, it’s about events, and in introducing “happened before” I would like to introduce: “unhappened” “before” “happened before”

Take-aways • “Instantaneus” has no meaning: simultaneity is a myth
• Entanglement: Once I measure my one of the entangled particles, I know what you would measure or will measure; our actions are uncoordinated • Entanglement is monogomous • Spacetime is doomed • Time is change that we can count

Questions?

Lamport (Logical) Clocks Failure handling Computer Scientists & Physicists Notions
of TIME Reversible Computing Vive la Revolution The Matrix Quantum Computing Lamport’s Unﬁnished Revolution Image courtesy Shutterstock

Special thanks to: Leslie Lamport for his inspiration, Ines Sombra
for fabulous organization, and João Taveira for the Keynote Template References Nima Arkani Hamed: Science Museum Interview, London: https://www.youtube.com/watch?v=pup3s86oJXU Cornell Lecture: Space-time is doomed. What replaces it? Perimeter Lecture: A 21st-century discourse on quantum mechanics and space-time. Lorenzo Maccone Physics ArXiv Blog: How Time Emerges from Entanglement. Original ArXiv Paper:A quantum solution to the arrow of time dilemma. Experiment: Time from quantum entanglement: an experimental illustration Leonard Susskind Stanford: Entanglement builds spacetime The ER=EPR argument from Juan Maldacena. ER=EPR but Entanglement is Not Enough (With a connection to complexity theory). Cornell: Entanglement and the Hooks that Hold Space Together. There are many others, e.g: How Spacetime is built by Quantum Entanglement: New Insight into Uniﬁcation of General Relativity and Quantum Mechanics. New Scientist. Entanglement is the thread that binds spacetime together. Seth Lloyd, Brian Swingle, Van Raamsdonk, Sean Carroll. By this Author: Paul Borrill. Stanford EE380 Seminar on Time in Computer Science Youtube Video: Stanford Seminar. @plborrill [email protected]

Time, Clocks and the Reordering of Events - PWL...

Time, Clocks and the Reordering of Events - PWL San Francisco 14-Jul-2016

More Decks by Boz

Other Decks in Technology

Featured

Transcript