PaxosLease in Relativistic Inertial Frames

PaxosLease in Relativistic Inertial Frames Márton Trencséni (mtrencseni@gmail.com)

arXiv:2610.02879v1 [cs.DC] 2 Oct 2026

Abstract A lease grants one holder exclusive authority over a resource for a fixed term, and its safety property guarantees that at most one holder has the lease at any time. Under special relativity “at any time” has no frame-independent meaning for participants in relative motion. This note first restates the classical safety property with light cones, requiring a holder’s expiry to lie in the causal past of any later acquisition by a different holder, an order every observer agrees about. Second, the paper p modifies classical PaxosLease: the core change is that the containment and quarantine rules each gain a factor of k = (1 + β)/(1 − β), the relativistic Doppler factor, where β is relative speed as a fraction of the speed of light.

1. Introduction A lease grants exclusive time-limited authority over a resource to one holder [5]. While the holder owns the lease, it acts on the resource without checking with the grantor(s). Once the lease expires, the grantors may pass the lease to a new holder without hearing from the old one. A holder that has crashed and stopped sending messages therefore loses the lease on schedule. Lease algorithms have two important properties: (i) safety, that at most one holder has the lease at any time, and (ii) liveness, that a crashed holder does not block the distributed system. All participants, and the resource itself, are modeled as point-like particles moving through spacetime. The simplest approach to distributed algorithms is to assume an absolute frame of reference, with the single global time of Newtonian mechanics, where every event has a definite moment on the global timeline. Distributed algorithms already handle failure modes commonly found in data centers on Earth: system clocks may be offset from one another, and may drift in rate by a bounded amount; messages may be delayed or lost; processes may crash and restart. These faults limit what a participant can learn about events elsewhere, but none of them breaks the assumption of an absolute global time. In special relativity there is no frame-independent shared now for distant events. An observer can nevertheless assign a time to a distant event relative to a chosen inertial frame: from the reception time of its light, subtract the light-travel time calculated in that frame. Two observers at rest with respect to one another share an inertial frame and agree about when a distant event happened. Two observers in relative motion generally do not. The Lorentz transformation between their frames mixes space and time while preserving the same measured speed of light c for both [6]. That invariant speed determines the geometry of a spacetime diagram. With x and ct measured in the same units, light travels along the 45-degree diagonals for every inertial observer. A moving observer’s time axis and space

axis both tilt by the same angle toward the light diagonal in the direction of motion. The resulting change in what counts as a line of constant time is the geometric origin of the relativity of simultaneity. For two spacelike separated events (meaning neither event can send a signal, traveling no faster than light, that reaches the other), two observers in relative motion may place them in opposite orders, as Figure 1 shows. This is an aspect of our physical reality, described by special relativity; no better clock or measurement protocol removes this disagreement. Let P be one holder’s lease expiring and Q be the next, different holder acquiring it. Safety demands that P come first. The liveness property requires that the acquisition not wait on a signal from P, since the first lease holder may crash right at P. Classical lease algorithms’ timing rules do not prevent these two events from being spacelike separated, and observers in certain inertial frames then date P before Q (the next lease starts after the previous expired), while others date Q before P (the next lease starts before the previous expired, violating the safety property). Neither observer is mistaken; the ordering of spacelike separated events is relative to the observer. In both Newtonian mechanics and special relativity, every observer agrees on cause and effect. If a signal traveling no faster than light could have gone from one event to the other, the first could have caused the second, and every observer puts them in that order. Two events at one object are the plainest case, since the object carries the record of the first forward to the second. Relativity describes an object by its worldline, the path it traces through space and time, and events along one worldline have one order for all observers.1 Motivating this study, consider a relay in deep space, built long ago and still running. It executes any command 1 Lamport introduced happened-before [3] in 1978, with the analogy to relativity drawn explicitly. The two are not identical, since relativity orders events that a signal could have connected while happened-before orders those that a message actually did.

(b) Special relativity: x tilts with ct

(a) Newtonian: one global time

A

B, t

tQ

P

tQ

Q

tP

B, ct tP

tQ

Q

tP

ct

t

tP

A

P

x

tQ

A: P then Q B: P then Q x axis = x axis

A: P then Q B: Q then P

x

x

Figure 1: A is at rest and B moves at β = 0.6. Dashed lines are lines of simultaneity, and the diamonds are the time coordinates of events P and Q. (a) Newtonian mechanics: observers A and B agree that P occurs before Q, or tP < tQ and t′P < t′Q . (b) Special relativity: A still finds tP < tQ , but B’s time coordinates are reversed, t′Q < t′P .

that expires DP later on its own clock, and sends Prepare to every acceptor. An acceptor that answers promises to reject every smaller ballot and reports any live lease it has granted. If a majority answer and none reports a live lease, or the only lease reported is the exact one this proposer still holds and is renewing, the proposer sends Accept. An acceptor that accepts records the lease and reports it to any proposer that asks, until a deadline DA later on its own clock. It will still accept a higher ballot from the same owner, which is a renewal, or from anyone once that deadline has passed, but it refuses an Accept that would replace a live lease of a different owner, for the reason given in Section 4.2. An owner is a proposer incarnation, as in [2], so a restarted proposer is a new owner. Once a majority of acceptances reach the proposer while its timer is still running, it has acquired the lease and is its owner until the timer, started at Prepare, expires. Two proposers cannot both hold the lease because any two majorities share an acceptor, and that shared acceptor either reports the live lease or has already promised a ballot high enough to stop the lower-ballot attempt. Acceptors keep promises and leases in memory only, so an acceptor that restarts has lost them, and it stays silent for a quarantine DQ before voting again. Figure 2 shows one acquisition. Throughout, DP is the proposer’s lease duration, DA the acceptor’s exclusion duration, DQ the restart quarantine, each measured on the clock of the participant that uses it, taken as ideal until the end of Section 4.3.2 A relative speed is written β, as a fraction of the speed of light c.

sent to it. It cannot tell who sent a command, cannot reject a command that a later one has superseded, and cannot arbitrate between two senders. Several probes pass it on different trajectories at relativistic speeds, and each wants to use the relay to send messages into deep space. This requires multiple commands, first to point the relay to the destination, and then to send the messages. Two probes commanding it at once would leave it in a state neither intended. The relay cannot stop two probes from commanding it at once, so the probes exclude one another instead: they run PaxosLease, and the lease holder alone commands the relay until its lease expires. This note answers two questions. How should the safety property be stated so that participants in relative motion can agree on whether it holds? And what must PaxosLease [1, 2], the lease protocol this note takes as its example, change so that it satisfies the restated property? Section 2 recaps PaxosLease. Section 3 defines relativistic versions of safety, Section 4 relativistic PaxosLease. Section 5 discusses the results and their limitations. Relativistic ideas are explained where they are first used. 2. PaxosLease This section gives a brief description of PaxosLease, the lease protocol which we will adapt to special relativity in the later sections. The protocol reuses the machinery of Paxos, ballots and prepare/accept rounds decided by majorities. In Paxos, participants agree on an arbitrary value, while in PaxosLease agreement is reached on who holds the lease for some limited time, with automatic expiry; unlike Paxos, PaxosLease acceptors store nothing on disk. The full algorithm is in [1, 2]. The version modified here omits the optional early release of [2], which the argument of Section 4.2 does not cover. A proposer picks a fresh ballot, never used by any proposer, including its own earlier incarnations, starts a timer

3. The safety property in relativistic inertial frames PaxosLease’s safety property is that at most one proposer holds the lease at any time. In special relativity “at 2 Proper time is what an ideal clock carried along a worldline reads. It is the only time a participant can measure directly.

2

acquired majority

Aold = J + (P0 ) \ J + (P),

the proposer's lease timer has expired, but the acceptors' timers have not, so no other proposer can acquire the lease here.

DA starts

DP starts

acceptances Accept

E(W) :

W ∩ Aold ∩ Anew = ∅.

This condition is frame independent as well, since it too is written with cones. Observer exclusion. Write tS (E) for the time coordinate of an event E in a chosen inertial frame S . Observer exclusion F(S ) is classical PaxosLease’s safety property as an observer at rest in S reads it, and requires the two owners’ authority intervals on that frame’s time axis to be disjoint,

promises Prepare

Figure 2: One acquisition in classical PaxosLease, as a message-sequence diagram rather than a spacetime diagram.

any time” depends on the frame of reference, so the property is meaningless without choosing one, and different chosen frames may give different answers. In Figure 3(b), event P is one owner’s lease expiry and event Q the next owner’s acquisition; the two are spacelike separated, so observers in suitable frames disagree about their order.

F(S ) :

[ tS (P0 ), tS (P) ) ∩ [ tS (Q), tS (Q1 ) ) = ∅.

3.2. Exclusion theorems Take any one resource worldline W0 and any one frame S . Since C names whichever owner is causally the earlier, in these labels it reads Q ∈ J + (P) or P0 ∈ J + (Q1 ).

3.1. Exclusion definitions

3.2.1. C ⇔ E(W) for every W Causal exclusion holds exactly when resource exclusion holds on every resource worldline. Under C the later owner’s region lies inside the earlier owner’s future cone, since Anew ⊆ J + (Q) ⊆ J + (P), while Aold excludes J + (P) by construction. The two are disjoint everywhere, so no worldline meets both at one event, as Figure 3(a) draws. Conversely, let C fail, so neither Q ∈ J + (P) nor P0 ∈ J + (Q1 ), and compare the two acquisitions. If Q ∈ J + (P0 ), then Q lies in both regions, being outside J + (P) by the first failure and outside J + (Q1 ) because Q1 is later along a timelike worldline; if P0 ∈ J + (Q), then P0 does the same by the mirror argument; and if the two are spacelike separated, their future cone surfaces meet at events null separated from each, which J + (P) and J + (Q1 ), lying strictly inside those cones, cannot contain. Every event lies on some timelike worldline, so a resource carried through the one found obeys both owners at once.

Leases. Each successful attempt gives one lease, which runs along its owner’s worldline from the acquisition to the expiry. Participants are massive, so their worldlines are timelike, and an attempt is acquired strictly before its timer expires, so every lease has positive duration and its acquisition lies strictly inside the past cone of its expiry. A renewal is a new lease by the same proposer, which usually overlaps the one it extends on the same worldline, so the three conditions below compare leases held by different proposers, and with more than two such leases each condition applies to every pair. Causal exclusion. Let J + (E) be the causal future of an event E, the events a signal from E traveling no faster than light can reach, and J − (E) its causal past, the events from which such a signal can reach E. These are the future and past light cones of E, their interiors, and E itself. Both sets are defined on spacetime itself rather than in any frame, so every observer agrees about them. Causal exclusion C requires that of any two such leases, one has its expiry in the past cone of the other’s acquisition; write P for that expiry and Q for that acquisition, so that C:

Anew = J + (Q) \ J + (Q1 ).

Resource exclusion E(W) on a resource worldline W requires the two regions to be disjoint along W,

DA

expires

news of its acquisition could have arrived and news of its expiry could not, so the two regions are

acceptor 1 acceptor 2 acceptor 3

DP

time

proposer

3.2.2. C ⇔ F(S ) for every S Causal exclusion holds exactly when observer exclusion holds in every frame. Causal order survives every boost, so C gives tS (P) ≤ tS (Q), or else tS (Q1 ) ≤ tS (P0 ), in every frame, and the interval that ends first ends before the other begins. Conversely, each owner’s acquisition precedes its expiry in every frame, and two such non-empty half-open intervals are disjoint exactly when one ends at or before the other begins, so F(S ) says that tS (P) ≤ tS (Q) or tS (Q1 ) ≤ tS (P0 ). No frame satisfies both, which would close the cycle tS (P0 ) < tS (P) ≤ tS (Q) < tS (Q1 ) ≤ tS (P0 ), so the frames satisfying each form disjoint closed sets, and

P ∈ J − (Q),

equivalently J + (Q) ⊆ J + (P): everything the acquisition can reach, the expiry can reach too. Every observer therefore agrees whether C holds. Resource exclusion. Each owner’s lease runs between two events on its own worldline: the old owner acquires at P0 and expires at P, and the new owner acquires at Q and expires at Q1 . An owner is authorized at the events where 3

(a)

holds: P J (Q)

(b) W

new

Wa

Q ct

ct

Wb

both owners

RQ

Q1

old

fails: P, Q spacelike

Q1

old

RP

P

P

P0

P0 x

new

Q line of now in S

x

Figure 3: Authority regions Aold and Anew , shaded, in the drawn frame S . (a) Disjoint. (b) Overlapping: F(S ) holds, but C and E(Wb ) fail.

acceptor

3.2.5. F(S ) ⇏ C 3.2.6. F(S ) ⇏ E(W0 ) Observer exclusion does not imply causal exclusion or resource exclusion on a given worldline. Figure 3(b) is the counterexample for 3.2.3–3.2.6. Causal exclusion fails there, yet the relay on Wa satisfies resource exclusion, since light from P reaches it at RP before light from Q reaches it at RQ , and the two leases are disjoint on the drawn frame’s time axis, so F(S ) holds. A resource on Wb obeys both owners at once, so E(Wb ) fails, and since C fails, some frame violates observer exclusion by the equivalence above: for the drawn events, every observer moving from P’s side toward Q’s at between 0.15c and 0.95c sees the leases overlap.

an acquisition here is spacelike to P

k DP

ct

DP

proposer

P

DA

DP proper

x

Figure 4: The proposer’s timer runs DP of its own proper time, from Prepare to expiry. The proposer recedes in between, so light from the two endpoints reaches the acceptor kDP apart. The arrow marked DA must reach at least the second arrival. An exclusion of γDP , the proposer’s timer dilated into the acceptor’s frame, would end βγDP too early, and a proposer beside the acceptor that acquires in that gap does so at an event spacelike separated from the expiry P.

3.3. Commands and messages Assuming messages from the lease holder to the resource travel at the speed of light and are processed in arrival order, relativistic PaxosLease honoring causal exclusion yields correct execution at the resource. The old owner sent its commands before P, so they arrive before light from P, and the new owner sends its commands at or after Q, so they arrive no earlier than light from Q. Since J + (Q) ⊆ J + (P), every command of the old owner arrives before any command of the new one.

if F holds everywhere these sets cover the family of all frames, which is connected: one is empty and the other is everything. A separation with non-negative time coordinate in every frame is future directed and causal, since a spacelike one reverses under some boost and a past directed one is negative everywhere. The surviving case is therefore Q ∈ J + (P) or P0 ∈ J + (Q1 ), which is C.

4. PaxosLease timeouts in relativistic inertial frames In this section we will modify classical PaxosLease to achieve causal exclusion in relativistic inertial frames by modifying timeouts, since requiring a release message before regranting would break the algorithm’s liveness property.

3.2.3. E(W0 ) ⇏ C 3.2.4. E(W0 ) ⇏ F(S ) Resource exclusion on one worldline does not imply causal exclusion or observer exclusion. 4

4.1. Relativistic Doppler factor Pick a frame and watch a clock move through it at a speed β. The moving clock accumulates 1/γ seconds forp every second of the frame’s own time, where γ = 1/ 1 − β2 is the Lorentz factor. Since 0 ≤ β < 1, γ ≥ 1 and 1/γ ≤ 1, so the moving clock runs slow. That is time dilation. An acceptor sees more than dilation, because it learns of each tick of the proposer’s clock from the light that tick sends out, and if the proposer is receding, each successive tick is emitted from farther away.3 In the acceptor’s frame the ticks are γ seconds apart, and in those γ seconds the proposer moves βγ light-seconds farther off, so the light of each tick has that much farther to travel than the light of the tick before. The interval between arriving ticks is therefore stretched by s 1+β , k = γ (1 + β) = 1−β

its attempt timer when it broadcasts Prepare, before it owns the lease. If the acquisition succeeds, that same timer becomes the lease timer, and the lease expires when it runs out. The broadcast and the expiry are DP apart on the proposer’s clock, and light from each of them travels to the acceptor. By the previous subsection the two arrivals are kDP apart, as Figure 4 shows. An acceptor grants the lease only in response to messages of this attempt, sent by the proposer at or after its timer started, so the acceptor cannot start excluding before light from the broadcast could have reached it. The acceptor’s exclusion therefore starts no earlier than the first arrival, and if it lasts at least kDP , it ends no earlier than the second arrival, which is when light from the expiry reaches the acceptor. That is the containment rule with moving participants: DP ≤ DA /k. Nothing in the resulting rule depends on how far apart the participants are. Causal exclusion follows from the containment rule, provided an acceptor also keeps the leases it has granted. Lemma (lease retention). Once an acceptor has accepted a lease, and while it stays up, it reports a live lease of that lease’s owner at least until its exclusion for that lease ends, which by the containment rule is no earlier than when light from the lease’s expiry reaches it. Three rules guarantee this. First, an acceptor never replaces a live lease of a different owner, even under a higher ballot, the acceptor-side rule of [2]. Second, an Accept from the same owner, a renewal, may replace the record, but its new deadline is the later one, being the same duration from a later moment. Third, there is no early release: the optional release of [2] clears the record and would break the property. Theorem (causal exclusion). For any two leases held by different proposers, one lease’s expiry lies in the past cone of the other’s acquisition. Proof. Write P for the expiry of the lower-ballot lease and Q for the acquisition of the higher-ballot one. The majority whose answers to the higher Prepare were counted shares an acceptor with the lower-ballot lease’s accept majority. Consider that acceptor’s acceptance of the lower ballot and its answer to the higher Prepare. Case 1: no restart between the two events. The acceptor accepted first: a prior promise of the higher ballot would have made it refuse the lower Accept. Both events lie on its worldline, so every observer agrees on their order. By the lemma, until its exclusion for the lower-ballot lease ended it would have reported a live lease of that owner, which the higher-ballot proposer cannot count as open, whether acquiring afresh or renewing, since the renewal qualifier admits only its own lease. So the answer came after the exclusion ended, and hence after light from P reached the acceptor. The acquisition Q follows the answer, so P ∈ J − (Q). Case 2: restart after the acceptance, before the answer. The acceptor forgot its acceptance of the lower-

the relativistic Doppler factor [4], and this is the factor k the acceptor needs. With β ≥ 0 it satisfies k = γ(1 + β) ≥ γ ≥ 1. If the proposer’s clock ticks once per second, the acceptor receives one tick every k of its own seconds, so it observes the clock running at rate 1/k. The factor is computed from a relative speed, so it belongs to a pair of participants rather than to one. An acceptor may use a pair’s own k if it knows a bound on their relative speed, for instance from trajectories both have committed to. The Doppler shift it observes on the proposer’s messages is no substitute: that shift depends on direction as well as speed, falls below one while the proposer approaches, and mixes the proposer’s clock rate error into its apparent motion. An acceptor without such a bound has to use kmax , the stretch at an assumed bound βmax on relative speed, an assumption of the same kind as the clock drift bound that classical PaxosLease already makes. So does any acceptor emerging from a restart, since it has forgotten which proposers it answered. Section 4.2 relies on the acceptor-side rule of [2], refusing to replace another owner’s live lease. With this approach the acceptors stay diskless. 4.2. Containment The containment rule requires the end of a granting acceptor’s exclusion to lie in J + (P), the future cone of the expiry P of the lease it granted. Otherwise the acceptor could report the absence of a live lease before light from the expiry reached it, and the next proposer could acquire the lease outside J + (P). Put the acceptor at rest and let the proposer recede, which is the worst case (Section 4.1). The proposer starts 3 The stretch depends on direction: 1/k for a proposer heading straight at the receiver, γ for a tick emitted at closest approach, and k for direct recession, the largest, so a single bound has to use k.

5

Classical

Relativistic

Safety property

one holder per instant of a global time

P ∈ J − (Q) for leases of different proposers

Ballots, quorums, messages

as in classical PaxosLease

same, without early release

Proposer’s lease timer

DP on its own clock

same

Acceptor’s exclusion timer

1+ρmax DA ≥ DP 1−ρ max max DQ ≥ DP 1+ρ 1−ρmax

1+ρmax DA ≥ k DP 1−ρ max

Assumed bounds

maximum clock rate error ρmax

ρmax , and maximum relative speed βmax

Acceptor uses

its own clock

same, and optionally a known bound on relative speed

Acceptor disk writes

none

none

Acceptor’s quarantine timer

max DQ ≥ kmax DP 1+ρ 1−ρmax

Table 1: Comparison of classical and relativistic PaxosLease.

5. Discussion

ballot lease. The quarantine of Section 4.3 places its answer, and hence Q, in the future cone of P. Case 3: restart after the answer, before the acceptance. The acceptor forgot its promise of the higher ballot and then accepted the lower one. The same quarantine places that acceptance, and hence the lower-ballot acquisition, in the future cone of the higher-ballot expiry. Here the lower-ballot lease is the causally later one, and causal exclusion still holds.

The paper’s results have two limitations. First, every command must travel at the speed of light, and the resource must act on commands in the order they arrive; those arrivals lie on the resource’s own worldline, so their order is one every observer agrees about. Second, the note uses special relativity only, which assumes flat spacetime, a good approximation far from large masses and a poor one near them, and it assumes that all participants move inertially. Table 1 summarizes how the rules change from classical to relativistic PaxosLease.

4.3. Quarantine An acceptor that restarts has forgotten every promise it made and every lease it granted, so it quarantines itself for DQ time, until light from the expiry of any previous proposer leases has reached it. Each one belongs to an attempt one of whose messages, sent at or after its Prepare, reached the acceptor before the crash, so light from that Prepare had too, and light from the attempt’s expiry arrives at most kmax DP later. The acceptor no longer knows which proposers those attempts belonged to, so no known pair value is available to it. Waiting kmax DP after restarting therefore places the acceptor in J + (P) for the expiry P of every attempt it has forgotten:

References [1] M. Trencséni, A. Gazsó, and H. Reinhardt. “PaxosLease: Diskless Paxos for Leases.” arXiv:1209.4187, 2012. [2] M. Trencséni. “PaxosLease Revisited: A Checked Model of Diskless Distributed Leases.” arXiv:2609.14640, 2026. [3] L. Lamport. “Time, Clocks, and the Ordering of Events in a Distributed System.” CACM, 21(7), 1978. [4] H. Bondi. Relativity and Common Sense. Doubleday, 1964. [5] C. Gray and D. Cheriton. “Leases: An Efficient FaultTolerant Mechanism for Distributed File Cache Consistency.” SOSP, 1989. [6] A. Einstein. “Zur Elektrodynamik bewegter Körper.” Annalen der Physik, 17:891–921, 1905.

DQ ≥ kmax DP . A Prepare that arrives during the quarantine needs no such argument, since the acceptor does not answer it. With imperfect clocks, each clock’s rate against its own proper time lies between rmin = 1−ρmax and rmax = 1+ρmax , for 0 ≤ ρmax < 1; containment and quarantine then require, respectively, k DP rmax ≤ DA rmin ,

kmax DP rmax ≤ DQ rmin .

6

Related documents

• PaxosLease in Relativistic Inertial Frames#1187557
• Deference and Infinite Frames#100058
• Relativity for Everyone#1316303
• Quantum Reference Frames in terms of Tetrads#1342102
• The non-invariant time and Lorentz-like transformations#100717