# Observers in superposition and the no-signaling principle

Veronika Baumann<EMAIL_ADDRESS>Institute for Quantum Optics and
Quantum Information (IQOQI), Austrian Academy of Sciences, Boltzmanngasse 3,
1090 Vienna, Austria  Atominstitut, Technische Universität Wien, 1020 Vienna,
Austria  Caslav Brukner<EMAIL_ADDRESS>Institute for Quantum
Optics and Quantum Information (IQOQI), Austrian Academy of Sciences,
Boltzmanngasse 3, 1090 Vienna, Austria  University of Vienna, Faculty of
Physics, Boltzmanngasse 5, 1090 Vienna, Austria

###### Abstract

The Wigner’s friend experiment is a thought experiment in which a so-called
superobserver (Wigner) observes another observer (the friend) who has
performed a quantum measurement on a physical system. In this setup Wigner
treats the friend the system and potentially other degrees of freedom involved
in the friend’s measurement as one joint quantum system. In general, Wigner’s
measurement changes the internal record of the friend’s measurement result
such that after the measurement by the superobserver the result stored in the
observer’s memory register is no longer the same as the result the friend
obtained at her measurement, i.e. before she was measured by Wigner. Here, we
show that any awareness by the friend of such a change, which can be modeled
by an additional memory register storing the information about the change,
conflicts with the no-signaling condition in extended Wigner-friend scenarios.

##  I Introduction

$S$$\ket{\phi}_{S}$$\ket{0}_{S}\ket{\bm{0}}_{F}\,$$\ket{1}_{S}\ket{\bm{1}}_{F}\,$F$\ket{\Phi}_{SF}$W
Figure 1: In the original Wigner’s friend setup the source emits a quantum
system in state $\ket{\phi}_{S}$, which is measured by the friend in the
computational basis at time $t_{F}$. The result observed by the friend in
stored in some memory register $\ket{\cdot}_{F}$. Then Wigner performs his
measurement on both the system and the friend’s memory register at time
$t_{W}$. His measurement will in general alter the friend’s memory register
meaning that what is stored in her memory at time $t_{2}>t_{W}$ is different
from what was encoded in her memory at time $t_{1}<t_{W}$.

In the famous Wigner’s friend thought experiment wigner1963problem  one
considers the observation of an observer in order to illustrate the quantum
measurement problem maudlin1995three ; bub2010two ; brukner2017quantum . It
comprises an observer – called Wigner’s friend (F) –, who measures a quantum
system (S), as well as a so-called superobserver – Wigner (W) – who performs a
measurement on the joint quantum system S and F. It is assumed that Wigner’s
friend uses the state-update rule after obtaining a definite outcome for her
measurement. However, provided that the joint system S+F is sufficiently
isolated, Wigner assigns an entangled state to the composite system and
describes the friend’s measurement via unitary dynamics. This difference in
description of the same process is called the Wigner’s friend paradox.

In recent years new setups combining Wigner’s-friend-type scenarios with
various non-locality proofs Zukowski2020 ; Leegwater:2018aa ; brukner2018no ;
frauchiger2018quantum ; brukner2017quantum  have been proposed. These extended
Wigner’s friend experiments have been used to devise new powerful no-go
theorems for quantum theory. The common conclusion that can be drawn from the
theoretical results and experimental proof-of-principle tests is that
maintaining an observer-independent notion of measurement results is limited.
More concretely, a set of assumptions called local friendliness Bong2020  –
namely, that the superobservers’ and observers’ results are both “objective
facts”, “locality”, “freedom of choice”, and “universality of quantum theory”
– cannot all hold in extended Wigner’s friend setups. The last assumption
asserts that Wigner’s unitary description of the friend’s measurement
correctly predicts his observed statistics. The performed proof-of-principle
tests of the no-go theorems conform the quantum mechanical correlations for
the results of the superobservers. The “friend” was in that case a single
photon proietti2019experimental ; Bong2020 , for which the assignment of the
notion “observer” or “observation” has little physical meaning. Recently,
however, an extended Wigner’s friend experiment involving a human level AI on
a quantum computer, taking the role of the friend, has been proposed
wiseman2022thoughtful . This friend is assumed to have “internal thoughts”,
which in wiseman2022thoughtful  constitutes a sufficient condition to be an
observer. In this work we address the question: What properties the internal
thoughts of observers in superposition must have in order to be compatible
with known physical principles?

Wigner’s measurement will, in general, alter the friend’s perception of her
measurement result, i.e. state of the friend’s memory which encodes the result
deutsch1985quantum ; baumann2018formalisms ; cavalcanti2021view ;
baumann2020wigner . The paper allard2020no  considers the perception state of
the friend in the original Wigner’s friend experiment before and after
Wigner’s measurement, see Fig. 1. It proves that no joint probability
distribution of the friend’s perceptions before and after Wigner’s measurement
can agree with the unitary description endorsed by Wigner and be a convex
linear function of the initial state. Hence, the knowledge of a single
observer across time cannot be considered “objective” in Wigner’s friend
scenarios. In this paper, we derive a further constraint on the perception of
observers in superpositions from the no-signaling condition. We consider the
extended Wigner-friend scenario and show that if the friend can be aware of
the change in her memory (i.e. if she has an additional memory register that
can record whether or not a change has occurred in memory registers storing
the measurement result), this can lead to signaling. A distant observer –Bob
(B)– could signal to the friend by choosing different measurement settings in
his lab. We then conclude that compatibility with the non-signaling condition
requires that observers cannot be aware of the change in their internal memory
induced by a superobserver.

The paper is structured as follows. In section II we reexamine the simple
Wigner’s friend experiment and consider what the changes of the friend’s
perception could look like. In section III we then apply this to extended
Wigner’s friend setups and give an example of a protocol that would be
signaling, if the friend was aware of the change of her memory. We present our
conclusions in section IV.

##  II Changes of the friend’s memory

In the following, we consider probabilities for the results $f$ stored in the
friend’s memory at a certain time $t$. We describe the situation where Wigner
makes a joint measurement on the system and the friend, and compare the
probabilities for these results before and after Wigner’s measurement. We
further assume that unitary quantum theory prescribes the assignments of a
probability for observations at each individual point in time and that an
observer, who applies this prescription, will predict probabilities that are
consistent with the relative frequencies in an actual experiment. If the
friend measures a qubit in the computational basis at time $t_{F}$ and is then
measured by Wigner at time $t_{W}$, the probabilities for the results $\bm{0}$
and $\bm{1}$ are, in general, different at a time $t_{1}<t_{W}$ and
$t_{2}>t_{W}$. Suppose that at time $t_{W}$ Wigner performs a measurement
given by states $\ket{W=1}=a\ket{0}_{S}\ket{0}_{F}+b\ket{1}_{S}\ket{1}_{F}$,
$\ket{W=2}=b^{*}\ket{0}_{S}\ket{0}_{F}-a^{*}\ket{1}_{S}\ket{1}_{F}$ and their
orthogonal complement $\Pi_{\perp}=\mathds{1}-|W=1\rangle\langle
W=1|-|W=2\rangle\langle W=2|$. For an initial system state
$\ket{\phi}_{S}=\alpha\ket{0}+\beta\ket{1}$ we obtain

$\displaystyle p(f_{1}=0)=$ $\displaystyle|\alpha|^{2}$ (II.1) $\displaystyle
p(f_{1}=1)=$ $\displaystyle|\beta|^{2}$ (II.2) $\displaystyle p(f_{2}=0)=$
$\displaystyle|\alpha|^{2}(|a|^{4}+|b|^{4})+2|\beta|^{2}|a|^{2}|b|^{2}$ (II.3)
$\displaystyle+2|\alpha||\beta|(|a|^{3}|b|-|a||b|^{3})\cos{\theta}$
$\displaystyle p(f_{2}=1)=$
$\displaystyle|\beta|^{2}(|a|^{4}+|b|^{4})+2|\alpha|^{2}|a|^{2}|b|^{2}$ (II.4)
$\displaystyle-2|\alpha||\beta|(|a|^{3}|b|-|a||b|^{3})\cos{\theta},$

where $\theta$ is a relative phase factor, see Appendix A for details. Here,
we denote by $p(f_{1}=i)$ the probability of result $i$ being stored in the
friend’s memory at time $t_{1}$ and by $p(f_{2}=i)$ the probability that at
time $t_{2}$ the result $i$ is stored in the friend’s memory. Both these
probabilities can be empirically accessible to Wigner if he asks the friend
which result is stored in her memory at the corresponding instant of time. If
Wigner inquires the friend’s observed result before he performs the
measurement, the relative frequencies of the results $i$ correspond to
$p(f_{1})$. If Wigner performs his measurement first and inquires the result
stored in his friend’s memory afterwards, the relative frequencies correspond
to $p(f_{2})$.

###  II.1 Memory changes in the simplest Wigner’s friend setup

(a)$\bm{0}$$\bm{1}$$\bm{0}$$\bm{1}$$q$$1-q$$1-q$(b)$\bm{0}$$\bm{1}$$\bm{0}$$\bm{1}$$q^{0}$$q^{1}$$1-q^{0}$$1-q^{1}$
Figure 2: The results stored in the friend’s memory at time $t_{1}$ are shown
in green, while the memory entries at time $t_{2}$ are depicted in purple.
(a): Both results $\bm{0}$ and $\bm{1}$ are flipped with probability $q$ and
stay the same with probability $1-q$. (b): With probability $q^{0}$ an
initially observed result $\bm{0}$ gets flipped to result $\bm{1}$. With
probability $1-q^{0}$ the stored result $\bm{0}$ is not changed by Wigner’s
measurement. Similarly an initially stored $\bm{1}$ gets altered with
probability $q^{1}$ and remains unchanged with probability $1-q^{1}$.

As implied by Ref. allard2020no  we cannot model the change of the friend’s
memory by parameters that are independent of the initial state. The memory
change can be mathematically described by

$\displaystyle p(f_{2})=\sum_{f_{1}}p(f_{1})p(f_{2}|f_{1}).$ (II.5)

Let’s assume $p(f_{2}|f_{1})=q$ if $f_{2}\neq f_{1}$ corresponds to the
probability of the result stored in the friend’s memory being flipped during
Wigner’s measurement, see Fig. 2(a). More concretely, using a single parameter
$q$ we can write $p(f_{2})$ for the setup in Fig. 1 as follows.

$\displaystyle p(f_{2}=0)=|\alpha|^{2}(1-q)+|\beta|^{2}q$ (II.6)
$\displaystyle p(f_{2}=1)=|\alpha|^{2}q+|\beta|^{2}(1-q).$ (II.7)

Since these probabilities also have to satisfy Eqs. (II.3) and (II.4) we
obtain the following system of equations

$\displaystyle|\alpha|^{2}$ $\displaystyle-q(|\alpha|^{2}-|\beta|^{2})=$
(II.8)
$\displaystyle\qquad|\alpha|^{2}(|a|^{4}+|b|^{4})+2|\beta|^{2}|a|^{2}|b|^{2}+2\chi$
$\displaystyle|\beta|^{2}$ $\displaystyle+q(|\alpha|^{2}-|\beta|^{2})=$ (II.9)
$\displaystyle\qquad|\beta|^{2}(|a|^{4}+|b|^{4})+2|\alpha|^{2}|a|^{2}|b|^{2}-2\chi,$

where $\chi=|\alpha||\beta|(|a|^{3}|b|-|a||b|^{3})\cos{\theta}$. Potential
solutions of these equations are non-linear functions of the initial state, as
implied by the no-go theorem in allard2020no . Moreover, for various $\alpha$,
$\beta$, $a$ and $b$ there exist no solution $q\in[0,1]$ for Eqs. (II.8)-
(II.9) at all, see Appendix A.

However, we can model the memory flip, for arbitrary settings, if we assume
different flipping probabilities for the different outcomes encoded in the
memory register at $t_{1}$, see Fig. 2(b). In that case we get the following
two equations for $p(f_{2})$

$\displaystyle|\alpha|^{2}(1-q^{0})$ $\displaystyle+|\beta|^{2}q^{1}=$ (II.10)
$\displaystyle\qquad|\alpha|^{2}(|a|^{4}+|b|^{4})+2|\beta|^{2}|a|^{2}|b|^{2}+2\chi$
$\displaystyle|\beta|^{2}(1-q^{1})$ $\displaystyle+|\alpha|^{2}q^{0}=$ (II.11)
$\displaystyle\qquad|\beta|^{2}(|a|^{4}+|b|^{4})+2|\alpha|^{2}|a|^{2}|b|^{2}-2\chi,$

which now always have solutions $q^{0}$ and $q^{1}$ $\in[0,1]$. Note that,
now, these solutions are not necessarily unique and one can impose further
conditions on them. For example, we could require that the memory flip is as
symmetric as possible, i.e. $q^{1}=q^{0}+\epsilon$ with $|\epsilon|$ being
minimal. This additional requirement, ensures that, whenever Eqs. (II.8) -
(II.9) have a solutions we recovery it by solving Eqs. (II.10) - (II.11).

In what follows we will consider whether the friend can be aware of these
flipping probabilities. Note that, if she was aware of whether individual
memory registers have been flipped or not, she could reconstruct the content
of her memory before Wigner’s measurement from the content after Wigner’s
measurement and her knowledge about the flip. In this way, she would have
complete information about the observable that is complementary to the one
measured by Wigner. She could further communicate this to Wigner who, in turn,
could inform the friend about the result of his measurement. This would
violate the complementarity principle, since observer and superobserver would
have complete information about two mutually complementary observables. One
can, however, imagine scenarios where the friend, after having stored the
measurement results of multiple runs in different memory registers, is subject
to Wigner performing his measurement on all this registers in parallel. The
friend could have a perception of how much her memory registers have been
altered, without knowing whether individual registers have been flipped or
not. This would correspond to a more direct perception of flipping
probabilities $q^{0}$ and $q^{1}$, and not create a conflict with the
complementarity principle. As we will show below, such a perception of the
changes of the friend’s memory conflicts with the no signaling principle.

###  II.2 Memory changes in extended Wigner’s-friend setups

We now consider extended Wigner’s friend experiments, where the friend
measures only part of a bipartite quantum state and, again, try to model the
changes of her memory register. The simplest version of an extended Wigner’s
friend experiment consists of one Wigner’s friend setup and an additional
observer Bob, who measures the second part of the bipartite initial state, see
Fig. 3. Consider the initial two qubit state
$\ket{\Phi}=\alpha\ket{0,1}+\beta\ket{1,0}$. The first qubit is measured by
the friend in the computational basis at time $t_{F}$. Bob performs a
measurement corresponding to states $\ket{B=0}=\mu\ket{0}+\nu\ket{1}$ and
$\ket{B=1}=\nu^{*}\ket{0}-\mu^{*}\ket{1}$ on the second qubit at some time
$t_{B}>t_{F}$. Finally, at $t_{W}$, Wigner performs the same measurement as in
the simple Wigner’s friend scenario in section II, given by states $\ket{W=1}$
and $\ket{W=2}$ and their orthogonal complement.

$\ket{\Phi}$FWB Figure 3: The simplest version of an extended Wigner’s friend
experiment comprises a Wigner’s friend setup and an additional observer Bob.
The source emits a bipartite state, one part of which is measured by the
friend in a fixed basis, while the other part is measured by Bob. Like in the
original setup in Fig. 1, Wigner measures the friend together with the
respective subsystem, thereby potentially altering the result encoded in the
friend’s memory.

Similar to the simple Wigner’s friend scenario, let us now consider the
results stored in the friend’s and Bob’s memory across the time sequence
$t_{F}<t_{1}<t_{B}<t_{2}<t_{W}<t_{3}$. The detailed calculations are given in
Appendix B. After the friend performed her measurement the probabilities for
the results $\bm{0}$ and $\bm{1}$ being stored in her memory are again simply

$\displaystyle p(f_{1}=0)=$ $\displaystyle|\alpha|^{2}$ (II.12) $\displaystyle
p(f_{1}=1)=$ $\displaystyle|\beta|^{2}.$ (II.13)

When performing his measurement, Bob will see results $B$ with the following
probabilities.

$\displaystyle p(B_{2}=0)=$
$\displaystyle|\alpha|^{2}|\nu|^{2}+|\beta|^{2}|\mu|^{2}$ (II.14)
$\displaystyle p(B_{2}=1)=$
$\displaystyle|\alpha|^{2}|\mu|^{2}+|\beta|^{2}|\nu|^{2},$ (II.15)

where $B_{2}$ can be thought of as a result stored in Bob’s memory at time
$t_{2}$. The probabilities for the friend’s memory stay the same before and
after Bob’s measurement, i.e. $p(f_{2})=p(f_{1})$, as otherwise Bob could
signal superluminaly to the other side. Until Wigner performs his measurement
the friend and Bob are simply measuring two parts of a bipartite quantum
state, nothing one of them does should change the perception of the other.
Finally, after Wigner’s measurement, the probabilities for the result stored
in the friend’s memory are given by

$\displaystyle p(f_{3}=0)=$
$\displaystyle|\alpha|^{2}(|a|^{4}+|b|^{4})+2|\beta|^{2}|a|^{2}|b|^{2}$
(II.16) $\displaystyle p(f_{3}=1)=$
$\displaystyle|\beta|^{2}(|a|^{4}+|b|^{4})+2|\alpha|^{2}|a|^{2}|b|^{2},$
(II.17)

while those for Bob’s result stay the same $p(B_{3})=p(B_{2})$. Moreover, the
probabilities for the friend’s memory entries are independent of Bob’s
measurement. These two facts, again, show that the no-signaling condition is
respected in the set-up in terms of the observed measurement results.

$p(f,B)\text{ for }\bm{t_{2}}<t_{W}$
---
$f_{2}$ $B_{2}$ | 0 | 1
0 | $|\alpha|^{2}|\nu|^{2}$ | $|\alpha|^{2}|\mu|^{2}$
1 | $|\beta|^{2}|\mu|^{2}$ | $|\beta|^{2}|\nu|^{2}$

$p(f,B)\text{ for }\bm{t_{3}}>t_{W}$
---
$f_{3}$ $B_{3}$ | 0 | 1
0 | $|\alpha|^{2}|\nu|^{2}(|a|^{4}+|b|^{4})+$ | $|\alpha|^{2}|\mu|^{2}(|a|^{4}+|b|^{4})+$
$2|\beta|^{2}|\mu|^{2}|a|^{2}|b|^{2}+2\xi$ | $2|\beta|^{2}|\nu|^{2}|a|^{2}|b|^{2}-2\xi$
1 | $|\beta|^{2}|\mu|^{2}(|a|^{4}+|b|^{4})+$ | $|\beta|^{2}|\nu|^{2}(|a|^{4}+|b|^{4})+$
$2|\alpha|^{2}|\nu|^{2}|a|^{2}|b|^{2}-2\xi$ | $2|\alpha|^{2}|\mu|^{2}|a|^{2}|b|^{2}+2\xi$
with $\xi=(|a|^{3}|b|-|a||b|^{3})|\alpha||\beta||\mu||\nu|\cos\vartheta$

Table 1: The joint probabilities for the results $f$ and $B$ recorded in the
friend’s and Bob’s memory respectively. The top table shows the joint
probability before Wigner’s measurement. The bottom table presents the joint
probability after Wigner has performed his measurement. The detailed
calculation and the explicit form of relative phase factor $\vartheta$ can be
found in Appendix B.

When trying to consistently model the change of the friend’s memory, we
further have to consider the joint probabilities for the results of the friend
and Bob, see Tab. 1. The joint probabilities at $t_{3}$ and $t_{2}$ are
related as follows

$\displaystyle
p(f_{3},B_{3})=\sum_{f_{2},B_{2}}p(f_{2},B_{2})p(f_{3},B_{3}|f_{2},B_{2})$
(II.18)

where the conditional probability $p(f_{3},B_{3}|f_{2},B_{2})$, which still
needs to be specified, encodes how the records of the results of the friend
and Bob change from before to after Wigner’s measurement. This conditional
probability can further be written as
$p(f_{3},B_{3}|f_{2},B_{2})=p(B_{3}|f_{2},B_{2},f_{3})p(f_{3}|f_{2},B_{2})$.
Since the result stored in Bob’s memory should not be affected by any action
of Wigner between $t_{2}$ and $t_{3}$, i.e.
$p(B_{3}|B_{2})=\delta_{B_{3}B_{2}}$, one has that

$\displaystyle
p(f_{3},B_{3})=\sum_{f_{2},B_{2}}p(f_{2},B_{2})p(f_{3}|f_{2},B_{2})\delta_{B_{3}B_{2}}.$
(II.19)

In order to make the joint probabilities at different times empirically
accessible, imagine that both the friend and Bob have multiple memory
registers available, such that they can record results for multiple rounds of
measurements. Wigner can then measure all the friend’s registers and
respective subsystems in his computations basis (i.e.
$\ket{0}_{S}\ket{0}_{F}$, $\ket{1}_{S}\ket{1}_{F}$), which returns the
probabilities with which the friend observed one or the other result during
her measurement. In this case, Bob, the friend and Wigner will establish the
joint probability before Wigner’s measurement $p(f_{2},B_{2})=p(f_{3},B_{3})$.
In another set of rounds, however, Wigner will first measure all the registers
of his friend and the respective subsystems in some other basis (i.e.
$\ket{W=1}_{SF}$, $\ket{W=2}_{SF}$ and their orthogonal complement) and
perform the computational basis measurement afterwards. In this case
$p(f_{3},B_{3})\neq p(f_{2},B_{2})$ will be established.

Similar to section II we try to model the change of the the friend’s memory by
flipping probabilities $q^{0}$ and $q^{1}$ and obtain the following set of
equations:

$\displaystyle(1-q^{0})|\alpha|^{2}|\nu|^{2}+q^{1}|\beta|^{2}|\mu|^{2}=p(0_{3},0_{3})$
(II.20)
$\displaystyle(1-q^{0})|\alpha|^{2}|\mu|^{2}+q^{1}|\beta|^{2}|\nu|^{2}=p(0_{3},1_{3})$
(II.21)
$\displaystyle(1-q^{1})|\beta|^{2}|\mu|^{2}+q^{0}|\alpha|^{2}|\nu|^{2}=p(1_{3},0_{3})$
(II.22)
$\displaystyle(1-q^{1})|\beta|^{2}|\nu|^{2}+q^{0}|\alpha|^{2}|\mu|^{2}=p(1_{3},1_{3}),$
(II.23)

where the $p(f_{3},B_{3})$ are given by the bottom table of Tab.1. This set of
equations does not always have solutions $q^{0},q^{1}\in[0,1]$. But we can
introduce a dependence on Bob’s result to increase the number of parameters,
$q^{00},q^{01},q^{10}$ and $q^{11}$ to model the memory change for all
possible settings. As in the simple Wigner’s friend scenario, this introduces
non-uniqueness for the potential solutions. Most importantly, however,
solutions of Eqs. (II.20) - (II.23) and their modifications will depend non-
trivially on $\mu$ and $\nu$ and, therefore, on Bob’s measurement setting, see
Appendix B for details. This means the flipping probabilities for the results
stored in the friend’s memory must, in general, be signaling. As we show in
the next section, this could be used to transmit information from Bob to the
friend and Wigner at superluminal speed, even if the friend has only a partial
awareness of the change of her memory.

The possibility of superluminal signaling can be understood in the following
way. The result stored in the friend’s memory before Wigner’s measurement
plays the role of a hidden variable, that encodes the result Wigner would have
obtained if he had measured in the computational basis. In order to be
compatible with the violations of Bell-like inequalities from the no-go
theorems in Bong2020 ; brukner2018no , these variables must change non-
locally. In other words, during Wigner’s measurement the records in the
friend’s memory will change in non-local dependence of the choice of Bob’s
measurement setting. If the friend was now aware of the change of her memory,
even just partially, this would constitute superluminal signaling from Bob to
her. Moreover, she could inform Wigner about the change after all measurements
have been performed, enabling superluminal signaling between Bob and Wigner.

##  III A signaling protocol

We now describe a specific hypothetical protocol for the extended Wigner’s
friend scenario depicted in Fig. 3 and show that it could be used to signal at
superluminal speed if the friend was aware of the change of her memory. We
assume that the flipping probabilities are such that the dependence on Bob’s
outcome is minimal, meaning that we obtain the solutions to the simpler Eqs.
(II.20)- (II.23), if they exist 111Note, that this assumption simplifies the
calculation for the example we present here, but is not necessary for
establishing a signaling protocol in general-.

Consider, a version of the setup in Fig. 3 where Bob resides in spacelike
separation from Wigner and his friend. Let Bob and the friend have multiple
memory registers available and perform a sequence of $N\gg 1$ measurements.
Then Wigner performs his measurement, given by states $\ket{W=1}$, $\ket{W=2}$
which are superpositions of $\ket{0}_{S}\ket{0}_{F}$ and
$\ket{1}_{S}\ket{1}_{F}$, and their orthogonal complement, on the friend’s $N$
memory registers and the respective qubits. Now suppose they repeat the
sequence of $N$ measurements multiple times, while Bob chooses between two
different measurement settings for these repetitions. Within each repetition,
however, he performs the same chosen measurement all $N$ times he receives his
subsystem from the source. We further assume that the friend has some notion
on how much her collection of $N$ memory registers has been changed by
Wigner’s measurement. For example, the friend could be aware of whether the
results stored in her $N$ memory registers have been flipped rather than
stayed the same during Wigner’s measurement, i.e. whether $q$ is larger or
smaller than $1/2$.

Now, let the source emit $N$ maximally entangled two-qubit state

$\displaystyle\ket{\Phi}=\frac{1}{\sqrt{2}}\left(\ket{0}\ket{1}+\ket{1}\ket{0}\right),$
(III.1)

and Bob choose between measuring his $N$ qubits either in the computational
basis $\ket{0}$, $\ket{1}$ or in the basis
$\ket{B=0}=1/\sqrt{3}\ket{0}+\sqrt{2/3}\ket{1}$,
$\ket{B=1}=\sqrt{2/3}\ket{0}-1/\sqrt{3}\ket{1}$. Wigner always performs the
measurement give by the states

$\displaystyle\ket{W=1}$
$\displaystyle=\sin\left(\frac{\pi}{8}\right)\ket{0,0}_{SF}+\cos\left(\frac{\pi}{8}\right)\ket{1,1}_{SF}$
(III.2) $\displaystyle\ket{W=2}$
$\displaystyle=\cos\left(\frac{\pi}{8}\right)\ket{0,0}_{SF}-\sin\left(\frac{\pi}{8}\right)\ket{1,1}_{SF},$
(III.3)

and the orthogonal complement. If Bob measures his qubit in the computational
basis, the joint probabilities before Wigner’s measurement are

$\begin{array}[]{c|c|c}p(f_{2},B_{2})&B=0&B=1\\\\[2.5pt] \hline\cr
f=0&0&\frac{1}{2}\\\\[2.5pt] f=1&\frac{1}{2}&0\;,\end{array}$

while after Wigner’s measurement, we obtain

$\begin{array}[]{c|c|c}p(f_{3},B_{3})&B=0&B=1\\\\[2.5pt] \hline\cr
f=0&\frac{1}{8}&\frac{3}{8}\\\\[2.5pt]
f=1&\frac{3}{8}&\frac{1}{8}\;.\end{array}$

In this case, the solution to Eqs. (II.20)- (II.23) is $q^{0}=q^{1}=q=1/4$,
which means that the result stored in the friend’s memory rather stays the
same (with probability $1-q=3/4$) than gets flipped during Wigner’s
measurement. On the other hand, if Bob measures his $N$ qubits in the basis
$\ket{B=0}=1/\sqrt{3}\ket{0}+\sqrt{2/3}\ket{1}$,
$\ket{B=1}=\sqrt{2/3}\ket{0}-1/\sqrt{3}\ket{1}$, the joint probabilities
before Wigner measures are

$\begin{array}[]{c|c|c}p(f_{2},B_{2})&B=0&B=1\\\\[2.5pt] \hline\cr
f=0&\frac{1}{6}&\frac{1}{3}\\\\[2.5pt]
f=1&\frac{1}{3}&\frac{1}{6}\;,\end{array}$

while after Wigner’s measurement we have

$\begin{array}[]{c|c|c}p(f_{3},B_{3})&B=0&B=1\\\\[2.5pt] \hline\cr
f=0&\frac{1}{6}\left(\frac{5}{4}+\frac{1}{4}\omega\right)&\frac{1}{3}\left(\frac{7}{8}-\frac{1}{8}\omega\right)\\\\[2.5pt]
f=1&\frac{1}{3}\left(\frac{7}{8}-\frac{1}{8}\omega\right)&\frac{1}{6}\left(\frac{5}{4}+\frac{1}{4}\omega\right)\;,\end{array}$

where $\omega=1+\sqrt{2}-\sin\left(\frac{\pi}{8}\right)$. Now, the solution to
Eqs. (II.20)- (II.23) is
$q^{0}=q^{1}=q=1/2+1/4(\sqrt{2}-\sqrt{1/2(1-1/\sqrt{2}})>3/4$, which means
that the friend’s memory registers get flipped more often than they stay the
same when Wigner performs his measurement. Even with the limited awareness of
whether her collection of $N$ memory registers got flipped rather than not in
a repetition of the sequence, the friend could distinguish between these two
measurement settings of Bob and communicate this to Wigner. Hence, Bob could,
via his choice of measurement setting for each repetition, transmit
information to Wigner and his friend at superluminal speed provided that
Wigner’s collective measurement happens outside of the future light cone of
Bob’s measurements. In turn, under the assumption of the no-signaling
condition, no perception of the change in the friend’s memory in Wigner’s
friend experiments is possible. In other words, the friend’s inner thoughts
must be changed by Wigner’s measurement such that no knowledge about the
memory before Wigner’s measurement remains. This is in agreement with the
assumptions in wiseman2022thoughtful .

##  IV Conclusions

We considered the compatibility of certain models of the observer’s (the
friend’s) internal thoughts in Wigner’s friend scenarios with the no-signaling
condition. In general, Wigner’s measurement affects the record of the
measurement result stored in the freind’s memory register. This change in
perception, just like the result the friend initially observed, is not
directly accessible to Wigner and does not correspond to any observable on the
joint system of S+F. However, identifying the friend with states of perception
and inner thoughts begs the question in how far she can be aware of what
happens to her memory. We considered the idea that the friend might have
_some_ perception of the change Wigner’s measurement induces to her memory.
More concretely, we described the case where the friend can have multiple
registers available for storing results which are then each measured by Wigner
in some fixed basis. The friend could have a notion of the overall change to
these memory registers (for example, the probability of entries being flipped
during Wigner’s measurement) without having a persistent perception of
individual results across Wigner’s measurement. We modeled the change of the
friend’s memory and found that, even if the friend has only a very limited
awareness of the change of her memory, this awareness could be used by a
distant observer (Bob) to signal superluminalny to the friend and Wigner. We
take this as a strong argument against the friend being able to have such an
awareness, meaning that not only can the friend not know about the specific
result she observed before Wigner’s measurement once her memory changed, she
cannot have awareness of the change either.

## References

  * (1) E. P. Wigner, “The problem of measurement,” American Journal of Physics, vol. 31, no. 1, pp. 6–15, 1963.
  * (2) T. Maudlin, “Three measurement problems,” Topoi, vol. 14, no. 1, pp. 7–15, 1995.
  * (3) J. Bub and I. Pitowsky, “Two dogmas about quantum mechanics,” Many worlds, pp. 433–459, 2010.
  * (4) Č. Brukner, “On the quantum measurement problem,” in Quantum [Un] Speakables II, pp. 95–117, Springer, 2017.
  * (5) M. Żukowski and M. Markiewicz, “Even performed pre-measurements have no results,” pp. 1–10, 2020.
  * (6) G. Leegwater, “When Greenberger, Horne and Zeilinger meet Wigner’s friend,” arXiv:1811.02442, 11 2018.
  * (7) Č. Brukner, “A no-go theorem for observer-independent facts,” Entropy, vol. 20, no. 5, p. 350, 2018.
  * (8) D. Frauchiger and R. Renner, “Quantum theory cannot consistently describe the use of itself,” Nature communications, vol. 9, no. 1, p. 3711, 2018.
  * (9) K.-W. Bong, A. Utreras-Alarcón, F. Ghafari, Y.-C. Liang, N. Tischler, E. G. Cavalcanti, G. J. Pryde, and H. M. Wiseman, “A strong no-go theorem on the Wigner’s friend paradox,” Nature Physics, vol. 16, no. 12, pp. 1199–1205, 2020.
  * (10) M. Proietti, A. Pickston, F. Graffitti, P. Barrow, D. Kundys, C. Branciard, M. Ringbauer, and A. Fedrizzi, “Experimental test of local observer independence,” Science advances, vol. 5, no. 9, p. eaaw9832, 2019.
  * (11) H. M. Wiseman, E. G. Cavalcanti, and E. G. Rieffel, “A “thoughtful” local friendliness no-go theorem: a prospective experiment with new assumptions to suit,” arXiv preprint arXiv:2209.08491, 2022.
  * (12) D. Deutsch, “Quantum theory as a universal physical theory,” International Journal of Theoretical Physics, vol. 24, no. 1, pp. 1–41, 1985\.
  * (13) V. Baumann and S. Wolf, “On formalisms and interpretations,” Quantum, vol. 2, p. 99, 2018.
  * (14) E. G. Cavalcanti, “The view from a Wigner bubble,” Foundations of Physics, vol. 51, no. 2, p. 39, 2021.
  * (15) V. Baumann and Č. Brukner, “Wigner’s friend as a rational agent,” in Quantum, Probability, Logic, pp. 91–99, Springer, 2020.
  * (16) P. Allard Guérin, V. Baumann, F. Del Santo, and Č. Brukner, “A no-go theorem for the persistent reality of Wigner’s friend’s perception,” Communications Physics, vol. 4, no. 1, p. 93, 2021.

##  Appendix A Memory changes in the simplest Wigner’s friend setup

Assuming that a unitary description of a setup is valid even if the total
system involves observers, we have the following state evolution for the
simplest Wigner’s friend experiment, depicted in Fig. 1. Initially the state
is given by

$\displaystyle\ket{\Psi(t_{0})}=\left(\alpha\ket{0}_{S}+\beta\ket{1}_{S}\right)\ket{r}_{F}\ket{r}_{W},$
(A.1)

where $\ket{r}$ denotes the ready state of an observer, when he or she has not
performed a measurement yet. Measurements are described by entangling
unitaries which correlate the respective observer (F and W) with the measured
quantum system

$\displaystyle
U_{O}:\ket{i}_{S}\ket{r}_{O}\mapsto\ket{i}_{S}\ket{I_{i}}_{O}\qquad\forall i,$
(A.2)

where $\ket{i}$ are the eigenstates of the observable being measured and
$\ket{I_{i}}$ is the state of the observer having registered outcome $i$.
After the friend measured the system S in the computational basis, we
therefore obtain the state

$\displaystyle\ket{\Psi(t_{1})}=\left(\alpha\ket{0,\bm{0}}_{SF}+\beta\ket{1,\bm{1}}_{SF}\right)\ket{r}_{W}.$
(A.3)

After Wigner performed his measurement with eigenvectors

$\displaystyle\ket{W=1}$
$\displaystyle=a\ket{0}_{S}\ket{0}_{F}+b\ket{1}_{S}\ket{1}_{F}$ (A.4)
$\displaystyle\ket{W=2}$
$\displaystyle=b^{*}\ket{0}_{S}\ket{0}_{F}-a^{*}\ket{1}_{S}\ket{1}_{F},$ (A.5)

we obtain the overall state

$\displaystyle\ket{\Psi(t_{2})}$ $\displaystyle=a(\alpha a^{*}+\beta
b^{*})\ket{0,\bm{0}}_{SF}\ket{\bm{1}}_{W}$ $\displaystyle+b(\alpha a^{*}+\beta
b^{*})\ket{1,\bm{1}}_{SF}\ket{\bm{1}}_{W}$ $\displaystyle+b^{*}(\alpha b-\beta
a)\ket{0,\bm{0}}_{SF}\ket{\bm{2}}_{W}$ $\displaystyle-a^{*}(\alpha b-\beta
a)\ket{1,\bm{1}}_{SF}\ket{\bm{2}}_{W}.$ (A.6)

The probability of an observer having registered outcome $x$ at time $t_{j}$
is then given by

$\displaystyle p(x_{j})=\tr\left(\mathds{1}\otimes|X_{x}\rangle\langle
X_{x}|_{O}\cdot|\Psi(t_{j})\rangle\langle\Psi(t_{j})|\right)$ (A.7)

Writing the complex coefficients as $z=|z|e^{i\phi_{z}}$ we obtain the
following probabilities for the result encoded in the friend’s state
$\ket{\cdot}_{F}$, i.e. the entry in her memory register. Before Wigner’s
measurement we have

$\displaystyle p(0_{1})$
$\displaystyle=\tr\left(\mathds{1}\otimes|\bm{0}\rangle\langle\bm{0}|_{F}\cdot|\Psi(t_{1})\rangle\langle\Psi(t_{1})|\right)=|\alpha|^{2}$
(A.8) $\displaystyle p(1_{1})$
$\displaystyle=\tr\left(\mathds{1}\otimes|\bm{1}\rangle\langle\bm{1}|_{F}\cdot|\Psi(t_{1})\rangle\langle\Psi(t_{1})|\right)=|\beta|^{2},$
(A.9)

and after Wigner’s measurement we obtain

$\displaystyle p(0_{2})=$
$\displaystyle\tr\left(\mathds{1}\otimes|\bm{0}\rangle\langle\bm{0}|_{F}\cdot|\Psi(t_{2})\rangle\langle\Psi(t_{2})|\right)=$
$\displaystyle|\alpha|^{2}(|a|^{4}+|b|^{4})+2|\beta|^{2}|a|^{2}|b|^{2}$
$\displaystyle+2|\alpha||\beta|(|a|^{3}|b|-|a||b|^{3})\cos{\theta}$ (A.10)
$\displaystyle p(1_{2})=$
$\displaystyle\tr\left(\mathds{1}\otimes|\bm{1}\rangle\langle\bm{1}|_{F}\cdot|\Psi(t_{2})\rangle\langle\Psi(t_{2})|\right)=$
$\displaystyle|\beta|^{2}(|a|^{4}+|b|^{4})+2|\alpha|^{2}|a|^{2}|b|^{2}$
$\displaystyle-2|\alpha||\beta|(|a|^{3}|b|-|a||b|^{3})\cos{\theta},$ (A.12)

where $\theta=\phi_{\alpha}-\phi_{\beta}+\phi_{b}-\phi_{a}$ and we define
$|\alpha||\beta|(|a|^{3}|b|-|a||b|^{3})\cos{\theta}=:\chi$. Modeling the
change of the memory by flipping probability $q$ we can further write

$\displaystyle p(0_{2})$ $\displaystyle=(1-q)p(0_{1})+qp(1_{1})$
$\displaystyle=(1-q)|\alpha|^{2}+q|\beta|^{2}$ (A.13) $\displaystyle p(1_{2})$
$\displaystyle=qp(0_{1})+(1-q)p(1_{1})$
$\displaystyle=q|\alpha|^{2}+(1-q)|\beta|^{2},$ (A.14)

which, when equated with (A.10) and (A.12), gives Eqs. (II.8) - (II.9) in the
main text. Adding and subtracting the latter leads to

$\displaystyle|\alpha|^{2}+|\beta|^{2}=|a|^{4}+|b|^{4}+2|a|^{2}|b|^{2}$
$\displaystyle(|\alpha|^{2}-|\beta|^{2})(1-2q)=(|\alpha|^{2}-|\beta|^{2})[|a|^{2}-|b|^{2}]^{2}+4\chi,$

from which it is easy to see that there is not always a solution $q$. For
example, if $|\alpha|=|\beta|=1/\sqrt{2}$ solutions $q$ only exist for
$|a|=|b|=1/\sqrt{2}$ (where $q=1/2$) and $a=0,b=1$ or $a=1,b=0$ (where $q=0$).

One way to obtain solutions for all settings is to increase the number of
variables in Eqs. (II.8) - (II.9) by assuming different flipping probabilities
depending on which outcome the friend initially observed, see Fig. 2(b). In
that case we obtain

$\displaystyle p(0_{2})=$
$\displaystyle(1-q^{0})|\alpha|^{2}+q^{1}|\beta|^{2}$ (A.15) $\displaystyle
p(1_{2})=$ $\displaystyle q^{0}|\alpha|^{2}+(1-q^{1})|\beta|^{2},$ (A.16)

which then leads to Eqs. (II.10) - (II.11) in the main text. These, in turn,
give equations

$\displaystyle|\alpha|^{2}+|\beta|^{2}=1$
$\displaystyle|\alpha|^{2}(1-2q^{0})-|\beta|^{2}(1-2q^{1})$
$\displaystyle\qquad\qquad\qquad=(|\alpha|^{2}-|\beta|^{2})[|a|^{2}-|b|^{2}]^{2}+4\chi,$

which now can be solved for $q^{0},q^{1}$. Note that, the solutions are not
unique. For example, if $|\alpha|=|\beta|=1/\sqrt{2}$ and further
$|a|=|b|=1/\sqrt{2}$, we obtain only $q^{0}-q^{1}=0$ from Eqs. (II.10) -
(II.11), which is solved by any number $q^{0}=q^{1}\in[0,1]$. One can further
require that the solutions are as symmetric as possible $q^{1}=q^{0}+\epsilon$
with minimal $|\epsilon|$, which means that if there is a solution to Eqs.
(II.8) - (II.9) we recover it when solving Eqs. (II.10) - (II.11).

##  Appendix B Memory changes in an extended Wigner’s friend experiment

Similar to Section A, we now consider the extended Wigner’s friend experiment
in Fig. 3. Before any measurement happened we have the overall state.

$\displaystyle\ket{\Psi(t_{0})}=$
$\displaystyle\left(\alpha\ket{0,1}_{12}+\beta\ket{1,0}_{12}\right)\ket{r}_{F}\ket{r}_{B}\ket{r}_{W},$
(B.1)

where, again $\ket{r}$ denotes the ready state of an observer. After the
friend performed her measurement in the computational basis, the state becomes

$\displaystyle\ket{\Psi(t_{1})}=$
$\displaystyle\Big{(}\alpha\ket{0,0}_{1F}\ket{1}_{2}$ (B.2)
$\displaystyle+\beta\ket{1,1}_{1F}\ket{0}_{2}\Big{)}\ket{r}_{B}\ket{r}_{W}.$

Then Bob measures the other subsystem in some basis,
$\ket{B=0}=\mu\ket{0}+\nu\ket{1}$, $\ket{B=1}=\nu^{*}\ket{0}-\mu^{*}\ket{1}$
leading to overall state

$\displaystyle\ket{\Psi(t_{2})}=$
$\displaystyle\Big{(}\alpha\nu^{*}\ket{0,0}_{1F}\ket{B=0,0}_{2B}$ (B.3)
$\displaystyle-\alpha\mu\ket{0,0}_{1F}\ket{B=1,1}_{2B}$
$\displaystyle+\beta\mu^{*}\ket{1,1}_{1F}\ket{B=0,0}_{2B}$
$\displaystyle+\beta\nu\ket{1,1}_{1F}\ket{B=1,1}_{2B}\Big{)}\ket{r}_{W}.$

Finally, after Wigner’s measurement of
$\ket{W=1}=a\ket{0,0}_{1F}+b\ket{1,1}_{1F}$ and
$\ket{W=2}=b^{*}\ket{0,0}_{1F}-a^{*}\ket{1,1}_{1F}$ the unitarily evolved
state is

$\displaystyle\ket{\Psi(t_{3})}=$
$\displaystyle\qquad(\alpha\nu^{*}a^{*}+\beta\mu^{*}b^{*})\ket{W=1,\bm{1}}_{1F,W}\ket{B=0,\bm{0}}_{2,B}$
$\displaystyle\qquad+(\beta\nu b^{*}-\alpha\mu
a^{*})\ket{W=2,\bm{2}}_{1F,W}\ket{B=1,\bm{1}}_{2,B}$
$\displaystyle\qquad+(\alpha\nu^{*}b+\beta\mu^{*}a)\ket{W=1,\bm{1}}_{1F,W}\ket{B=0,\bm{0}}_{2,B}$
$\displaystyle\qquad+(\alpha\mu b+\beta\nu
a)\ket{W=2,\bm{2}}_{1F,W}\ket{B=1,\bm{1}}_{2,B}.$ (B.4)

From Eqs. (B.2)-(B) we can calculate the individual probabilities for the
friend and Bob using Eq. (A.7) both before and after Wigner’s measurement.
Before Wigner measures, the probabilities for the results stored in the
friend’s memory are

$\displaystyle p(f_{1}=0)=$ $\displaystyle|\alpha|^{2}=p(f_{2}=0)$ (B.5)
$\displaystyle p(f_{1}=1)=$ $\displaystyle|\beta|^{2}=p(f_{2}=0),$ (B.6)

which do not change upon Bob’s measurement, as was to be expected since,
before Wigner’s measurement, the friend and Bob constitute two regular
observers measuring different parts of a bipartite quantum state. Nothing one
of them does should affect the result the other one observes. For Bob’s
results we obtain

$\displaystyle p(B_{2}=0)=$
$\displaystyle|\alpha|^{2}|\nu|^{2}+|\beta|^{2}|\mu|^{2}$ (B.7) $\displaystyle
p(B_{2}=1)=$ $\displaystyle|\alpha|^{2}|\mu|^{2}+|\beta|^{2}|\nu|^{2}.$ (B.8)

The joint probabilities for two outcomes $x,y$ being stored at time $t_{j}$ in
the memories of two observers $O_{1}$ and $O_{2}$ respectively is

$\displaystyle p(x_{j},y_{j})=\tr\left(|X\rangle\langle
X|_{O_{1}}\otimes|Y\rangle\langle
Y|_{O_{2}}\cdot|\Psi(t_{j})\rangle\langle\Psi(t_{j})|\right),$ (B.9)

which gives the following joint probabilities for the results recoded by the
friend and Bob before Wigner’s measurement

$\begin{array}[]{c|c|c}p(f_{2},B_{2})&B=0&B=1\\\\[2.5pt] \hline\cr
f=0&|\alpha|^{2}|\nu|^{2}&|\alpha|^{2}|\mu|^{2}\\\\[2.5pt]
f=1&|\beta|^{2}|\mu|^{2}&|\beta|^{2}|\nu|^{2}\;.\end{array}$ (B.10)

After Wigner’s measurement we obtain the following individual probabilities

$\displaystyle p(f_{3}=0)=$
$\displaystyle|\alpha|^{2}(|a|^{4}+|b|^{4})+2|\beta|^{2}|a|^{2}|b|^{2}$ (B.11)
$\displaystyle p(f_{3}=1)=$
$\displaystyle|\beta|^{2}(|a|^{4}+|b|^{4})+2|\alpha|^{2}|a|^{2}|b|^{2},$
(B.12)

for the result stored in the friend’s memory register and

$\displaystyle p(B_{3}=0)=$
$\displaystyle|\alpha|^{2}|\nu|^{2}+|\beta|^{2}|\mu|^{2}=p(B_{2}=0)$ (B.13)
$\displaystyle p(B_{3}=1)=$
$\displaystyle|\alpha|^{2}|\mu|^{2}+|\beta|^{2}|\nu|^{2}=p(B_{2}=1)$ (B.14)

for Bob’s memory. The latter is the same as before Wigner’s measurement. Since
Bob is a regular observer, whose memory is not subject to any further
measurement and who can in principle freely communicate to Wigner, his record
of an observed result should not be affected by anything Wigner does to his
friend.

The joint probabilities for the results stored in the friend’s and Bob’s
memory after Wigner’s measurement, according to Eq. (B.9), are given by

$\begin{array}[]{c|c| c}p(f_{3},B_{3})&B=0&B=1\\\\[2.5pt] \hline\cr
f=0&|\alpha|^{2}|\nu|^{2}(|a|^{4}+|b|^{4})+2|\beta|^{2}|\mu|^{2}|a|^{2}|b|^{2}+2\xi&|\alpha|^{2}|\mu|^{2}(|a|^{4}+|b|^{4})+2|\beta|^{2}|\nu|^{2}|a|^{2}|b|^{2}-2\xi\\\\[2.5pt]
f=1&|\beta|^{2}|\mu|^{2}(|a|^{4}+|b|^{4})+2|\alpha|^{2}|\nu|^{2}|a|^{2}|b|^{2}-2\xi&|\beta|^{2}|\nu|^{2}(|a|^{4}+|b|^{4})+2|\alpha|^{2}|\mu|^{2}|a|^{2}|b|^{2}+2\xi\;.\end{array}$

with
$\xi=(|a|^{3}|b|-|a||b|^{3})|\alpha||\beta||\mu||\nu|\cos(\phi_{\alpha}-\phi_{\beta}+\phi_{\mu}-\phi_{\nu}+\phi_{b}-\phi_{a}).$
We can now try to model the change in the friend’s memory like we did in
Appendix A, using different flipping probabilities depending on the friends
initial result, and obtain the following system of equations

$\displaystyle(1-q^{0})|\alpha|^{2}|\nu|^{2}+q^{1}|\beta|^{2}|\mu|^{2}=$
(B.15)
$\displaystyle\qquad\qquad|\alpha|^{2}|\nu|^{2}(|a|^{4}+|b|^{4})+2|\beta|^{2}|\mu|^{2}|a|^{2}|b|^{2}+2\xi$
$\displaystyle(1-q^{0})|\alpha|^{2}|\mu|^{2}+q^{1}|\beta|^{2}|\nu|^{2}=$
(B.16)
$\displaystyle\qquad\qquad|\alpha|^{2}|\mu|^{2}(|a|^{4}+|b|^{4})+2|\beta|^{2}|\nu|^{2}|a|^{2}|b|^{2}-2\xi$
$\displaystyle(1-q^{1})|\beta|^{2}|\mu|^{2}+q^{0}|\alpha|^{2}|\nu|^{2}=$
(B.17)
$\displaystyle\qquad\qquad|\beta|^{2}|\mu|^{2}(|a|^{4}+|b|^{4})+2|\alpha|^{2}|\nu|^{2}|a|^{2}|b|^{2}-2\xi$
$\displaystyle(1-q^{1})|\beta|^{2}|\nu|^{2}+q^{0}|\alpha|^{2}|\mu|^{2}=$
(B.18)
$\displaystyle\qquad\qquad|\beta|^{2}|\nu|^{2}(|a|^{4}+|b|^{4})+2|\alpha|^{2}|\mu|^{2}|a|^{2}|b|^{2}+2\xi,$

which, similar to before, do not always have a solution. Consider, for
example, the case where the source emits the state maximally entangled state
in Eq. (III.1) in the main text and Bob measures in the X-basis, i.e.
$\mu=\nu=1/\sqrt{2}$. In this case Eqs. (B.15)- (B.18) become

$\displaystyle\frac{1}{4}\left(1-q^{0}+q^{1}\right)=\frac{1}{4}+\frac{1}{8}(|a|^{3}|b|-|a||b|^{3})\cos(\Delta\phi)$
$\displaystyle\frac{1}{4}\left(1-q^{0}+q^{1}\right)=\frac{1}{4}-\frac{1}{8}(|a|^{3}|b|-|a||b|^{3})\cos(\Delta\phi)$
$\displaystyle\frac{1}{4}\left(1-q^{1}+q^{0}\right)=\frac{1}{4}-\frac{1}{8}(|a|^{3}|b|-|a||b|^{3})\cos(\Delta\phi)$
$\displaystyle\frac{1}{4}\left(1-q^{1}+q^{0}\right)=\frac{1}{4}+\frac{1}{8}(|a|^{3}|b|-|a||b|^{3})\cos(\Delta\phi),$

which clearly do not have a solution unless
$(|a|^{3}|b|-|a||b|^{3})\cos(\Delta\phi)=0$. Analogous to the case of the
simple Wigner’s friend experiment we can obtain solutions by increasing the
number of variables. These will now introduce a dependence on Bob’s result and
lead to the modified set of equations

$\displaystyle(1-q^{00})|\alpha|^{2}|\nu|^{2}+q^{10}|\beta|^{2}|\mu|^{2}=$
(B.19)
$\displaystyle\qquad\qquad|\alpha|^{2}|\nu|^{2}(|a|^{4}+|b|^{4})+2|\beta|^{2}|\mu|^{2}|a|^{2}|b|^{2}+2\xi$
$\displaystyle(1-q^{01})|\alpha|^{2}|\mu|^{2}+q^{11}|\beta|^{2}|\nu|^{2}=$
(B.20)
$\displaystyle\qquad\qquad|\alpha|^{2}|\mu|^{2}(|a|^{4}+|b|^{4})+2|\beta|^{2}|\nu|^{2}|a|^{2}|b|^{2}-2\xi$
$\displaystyle(1-q^{10})|\beta|^{2}|\mu|^{2}+q^{00}|\alpha|^{2}|\nu|^{2}=$
(B.21)
$\displaystyle\qquad\qquad|\beta|^{2}|\mu|^{2}(|a|^{4}+|b|^{4})+2|\alpha|^{2}|\nu|^{2}|a|^{2}|b|^{2}-2\xi$
$\displaystyle(1-q^{11})|\beta|^{2}|\nu|^{2}+q^{01}|\alpha|^{2}|\mu|^{2}=$
(B.22)
$\displaystyle\qquad\qquad|\beta|^{2}|\nu|^{2}(|a|^{4}+|b|^{4})+2|\alpha|^{2}|\mu|^{2}|a|^{2}|b|^{2}+2\xi,$

which can be solved for flipping probabilities $q^{nm}$. Like in the simple
case, the solutions are not unique and allow for introducing additional
requirements, for example that the dependence on Bob’s result is as small as
possible, i.e. $q^{n0}=q^{n1}+\varepsilon$ with minimal $|\varepsilon|$. Like
in the simple case this requirement ensures that if there are solutions to
Eqs. (B.15)- (B.18), we recover them when solving Eqs. (B.19)- (B.22).

Figure 4: Flipping probabilities $q^{00}=q^{11}$ (according to Eq.(B.29)) for
an extended Wigner’s friend setup with initial state
$\ket{\Phi}=1/\sqrt{2}\left(\ket{0}\ket{1}+\ket{1}\ket{0}\right)$. Bob
measures in the basis $\ket{B=0}=1/\sqrt{3}\ket{0}+\sqrt{2/3}\ket{1}$,
$\ket{B=1}=\sqrt{2/3}\ket{0}-1/\sqrt{3}\ket{1}$ and Wigner’s measurement is
given by $a=\sin(x)$, $b=\cos(x)$ and $\cos(\Delta\phi)=1$. Since these
$q^{00}=q^{11}$ become negative for some values of $x$, they are not always
well defined probabilities.

In general, all these solutions depend on Bob’s measurement setting and might,
therefore, lead to signaling. Note, however, that Wigner and his friend do not
necessarily have access to Bob’s result and may then at most access effective
flipping probabilities

$\displaystyle\bar{q}^{0}=p(B_{2}=0)q^{00}+p(B_{2}=1)q^{01}$ (B.23)
$\displaystyle\bar{q}^{1}=p(B_{2}=0)q^{10}+p(B_{2}=1)q^{11}.$ (B.24)

As long as the these effective probabilities are the same for all measurement
settings of Bob, while solving Eqs. (B.19)- (B.22), the changes in the
friend’s memory register can not be used to signal from Bob to Wigner and his
friend. As we will show below, this cannot always be the case.

First consider the scenario where the source emits the maximally entangled
state (i.e. $\alpha=\beta=1/\sqrt{2}$ in Eq. (III.1)) and Bob measures in the
computational basis, i.e. $\mu=1$, $\nu=0$. Eqs. (B.19)- (B.22) now simply
read

$\displaystyle\frac{1}{2}q^{10}=|a|^{2}|b|^{2}$
$\displaystyle\frac{1}{2}(1-q^{10})=\frac{1}{2}(|a|^{4}+|b|^{4})$
$\displaystyle\frac{1}{2}(1-q^{01})=\frac{1}{2}(|a|^{4}+|b|^{4})$
$\displaystyle\frac{1}{2}q^{01}=|a|^{2}|b|^{2}$

and are solved by $q^{01}=\bar{q}^{0}=2|a|^{2}|b|^{2}=q^{10}=\bar{q}^{1}$.
Hence, all other measurement setting by Bob must give the same effective
flipping probabilities to avoid signalling. Now, consider the same scenario
but Bob measuring in the basis given by $\mu=1/\sqrt{3},\nu=\sqrt{2/3}$. In
this case Eqs. (B.19)- (B.22) become

$\displaystyle\frac{1}{6}q^{10}-\frac{1}{3}q^{00}=\frac{1}{3}\left((|a|^{3}|b|-|a||b|^{3})\cos(\Delta\phi)-|a|^{2}|b^{2}\right)$
$\displaystyle\frac{1}{3}q^{11}-\frac{1}{6}q^{01}=\frac{1}{3}\left(|a|^{2}|b|^{2}-(|a|^{3}|b|-|a||b|^{3})\cos(\Delta\phi)\right)$
$\displaystyle\frac{1}{3}q^{00}-\frac{1}{6}q^{10}=\frac{1}{3}\left(|a|^{2}|b|^{2}-(|a|^{3}|b|-|a||b|^{3})\cos(\Delta\phi)\right)$
$\displaystyle\frac{1}{6}q^{01}-\frac{1}{3}q^{11}=\frac{1}{3}\left((|a|^{3}|b|-|a||b|^{3})\cos(\Delta\phi)-|a|^{2}|b|^{2}\right),$

with $\Delta\phi=\phi_{b}-\phi_{a}$. These equations only determine the
flipping probabilities of the friend’s memory up to

$\displaystyle
2q^{00}-q^{10}=2\left(|a|^{2}|b|^{2}-|a|^{3}|b|+|a||b|^{3}\right)$ (B.25)
$\displaystyle
2q^{00}-q^{10}=2\left(|a|^{2}|b|^{2}-|a|^{3}|b|+|a||b|^{3}\right).$ (B.26)

Now assume that there exist solutions $q^{nm}$, such that the flipping of the
friend’s memory would be non signaling for any $a,b$. This means that in
addition to Eqs. (B.25) - (B.26) we further have

$\displaystyle q^{00}+q^{01}=4|a|^{2}|b|^{2}$ (B.27) $\displaystyle
q^{11}+q^{01}=4|a|^{2}|b|^{2}.$ (B.28)

Plugging Eqs. (B.27) - (B.28) into Eqs. (B.25) - (B.26) gives

$\displaystyle
q^{00}=2|a|^{2}|b|^{2}-\frac{2}{3}(|a|^{3}|b|-|a||b|^{3})\cos(\Delta\phi)=q^{11}.$
(B.29)

As shown in Fig. 4 there exist measurements by Wigner (i.e. values of $a,b$)
such that these solutions are negative and, therefore, not proababiliteis.
This, in turn, means that for some settings solutions to Eqs. (B.25) and
(B.26) that are probabilities cannot simultaneously fulfill Eqs. (B.27) and
(B.28). Hence, for these settings the effective flipping probabilities have to
be signaling.


# GTX: A Transactional Graph Data System For HTAP Workloads

Libin Zhou  Purdue UniversityP.O. Box 1212West LafayetteIndiana47906
<EMAIL_ADDRESS>and  Walid G. Aref  0000-0002-1825-0097 Purdue University1
Thørväld CircleWest LafayetteIndiana<EMAIL_ADDRESS>
###### Abstract.

Processing, managing, and analyzing dynamic graphs are the cornerstone in
multiple application domains including fraud detection, recommendation system,
graph neural network training, etc. This demo presents GTX, a latch-free
write-optimized transactional graph data system that supports high throughput
read-write transactions while maintaining competitive graph analytics. GTX has
a unique latch-free graph storage and a transaction and concurrency control
protocol for dynamic power-law graphs. GTX leverages atomic operations to
eliminate latches, proposes a delta-based multi-version storage, and designs a
hybrid transaction commit protocol to reduce interference between concurrent
operations. To further improve its throughput, we design a delta-chains index
to support efficient edge lookups. GTX manages concurrency control at delta-
chain level, and provides adaptive concurrency according to the workload.
Real-world graph access and updates exhibit temporal localities and hotspots.
Unlike other transactional graph systems that experience significant
performance degradation, GTX is the only system that can adapt to temporal
localities and hotspots in graph updates and maintain million-transactions-
per-second throughput. GTX is prototyped as a graph library and is evaluated
using a graph library evaluation tool using real and synthetic datasets.

††This work is licensed under the Creative Commons BY-NC-ND 4.0 International
License. Visit https://creativecommons.org/licenses/by-nc-nd/4.0/ to view a
copy of this license. For any use beyond those covered by this license, obtain
permission by emailing<EMAIL_ADDRESS>Copyright is held by the
owner/author(s). Publication rights licensed to the VLDB Endowment.
Proceedings of the VLDB Endowment, Vol. 14, No. 1 ISSN 2150-8097.
doi:XX.XX/XXX.XX

##  1\. Introduction

Dynamic graph management is an important part of many application domains
including risk management, knowledge graph applications, recommendation
services, etc (Li and et al., 2022; Fuchs et al., 2022). Real-world graphs can
reach hundreds of millions of vertices and billions of edges (Fuchs et al.,
2022; Kunegis, [n.d.]) while hundreds of thousands to millions of updates take
place per second (Li and et al., 2022). These applications need to run
concurrent graph analytics while ingesting graph updates. Moreover, to
concurrently run graph analytics and updates while preserving graph’s
consistency and avoiding anomalies, graph systems need to support read-write
transactions (De Leo and Boncz, 2021; Cheng et al., [n.d.]; Fuchs et al.,
2022). Besides having high arrival rate, graph updates also exhibit temporal
localities and hotspots (Fuchs et al., 2022; Kunegis, [n.d.]). Namely, updates
arriving at the same time frame likely belong to the same vertex
(neighborhood) and a large number of such updates may arrive simultaneously.
For example, at a certain time, lots of users are liking the same post on
social media, creating a large amount of edges to the post simultaneously. In
the rest of the paper, we use ”temporal localities” to collectively refer to
graph updates with both temporal localities and hotspots. State-of-the-art
transactional graph systems use coarse-grained concurrency control (e.g.,
vertex-centric locking (Zhu and et al., 2020; Fuchs et al., 2022)) and suffer
from these update patterns (Fuchs et al., 2022). To address these challenges
and requirements, a graph system needs to support transactions, adapt to the
temporal localities, and reduce the interference between concurrent
transactions and analytics.

This demo presents GTX, a main memory latch-free transactional graph data
system that is optimized for read-write transactions while maintaining
competitive graph analytics. It targets the open problem of maintaining high
throughput in workloads involving temporal localities (Fuchs et al., 2022).
Many real world graphs are power-law graphs with hub vertices (vertices with
large degree) (Fuchs et al., 2022; Zhu and et al., 2020). For example, one of
the real world graph edit-wiki has vertices with millions of adjacent edges
and the edges’ creation follows temporal localities and contains hotspots
(Fuchs et al., 2022; Kunegis, [n.d.]). Most of the existing transactional
graph systems only support transactions, but are unware of temporal
localities. Moreover, they suffer from concurrently running updates and graph
analytics. Two of the three state-of-the-art systems that we have evaluated
have some bugs under such concurrent workloads. Therefore, we design GTX with
the following features to resolve these challenges:

1. GTX has a latch-free graph storage that uses atomic operations to update vertices and edges. It eliminates latching overheads and reduces thread idling.

2. GTX combines chain-based delta storage and linear delta storage to benefit from delta-chains’ efficient lookup and linear storage’s cache performance.

3. GTX has an efficient transaction management and concurrency control protocol by managing concurrency control at delta-chain level that adopts to the workload history.

4. GTX has a hybrid group commit protocol that improves transaction commit throughput.

In this demo, we will present how GTX handles vertex and edge creation
transactions of real world power-law graphs with and without temporal
localities and how GTX executes read-write transactions while concurrently
executing graphs analytics using synthetic graph logs in Graph Framework
Evaluation(GFE) (De Leo and Boncz, 2021; Fuchs et al., 2022).

##  2\. Overview of GTX

GTX addresses the problem of managing and analyzing dynamic labeled property
graphs. It consists of a latch-free adjacency list-based graph store and a
transaction manager and a concurrency control protocol. GTX can manage both
uniform and power-law graphs but is optimized for power-law graphs as many
real-world graphs are power-law graphs (Zhu and et al., 2020). In this
demonstration, we focus on managing power-law graphs.

Figure 1. GTX Storage: 1.Vector-based vertex index (entry). 2.Vertex delta
chain. 3.Edge-deltas block

GTX’s graph store is a multi-version delta store, where each delta captures an
operation (insert, update) of a vertex or (insert, delete, update) of an edge.
An overview of GTX’s storage is given in Figure 1. Each edge-delta takes 1
cache line to avoid false sharing and is optionally associated with a
variable-sized property that either resides inside the delta or at the other
end of the block depending on the property size. GTX stores vertex versions as
vertex delta-chains, and each vertex’s adjacency list consecutively in a
single edge-deltas block. Within each block, GTX organizes edge-deltas as
delta-chains. Delta-chains support efficient single edge lookup and
concurrency control and the linear edge-delta storage reduces random memory
access, and improves cache performance during adjacency list scan. To support
efficiently locating a vertex’s delta-chain and edge-deltas block, GTX has a
vertex index providing $O(1)$ lookup given vertex ID. Note that GTX supports
edge labels, and stores edge-deltas (edges) of the same label in an edge-
deltas block, but for simplicity of this demonstration, we assume all edges
have the same label. GTX manages a delta-chains index of each edge-deltas
block. Each edge-deltas block determines its delta-chains number at its
allocation time, and allocates a vector where each vector entry $i$ stores the
offset of the $i^{th}$ delta-chain within the block.

GTX adopts multi-version concurrency control (Wu et al., 2017), and uses
atomic operations to access and update vertex and edge versions, e.g.
$fetch\\_add$, $load$, and $compare\\_and\\_swap$($CAS$). Vertex versions are
updated by a $CAS$ on the vertex delta-chains pointer. Each edge-deltas block
maintains a combined_offset that combines the offsets of the edge data region
and edge-delta region (each 32 bits) into a 64 bits integer. Edge-delta
allocation is done by executing a fetch_add to the combined_offset and write
the edge-delta and its associated property data at the offsets returned by the
operation.

GTX allocates a fixed number of worker threads that execute read-write
transactions while additionally supports collectively running graph analytics
using OpenMP (ope, [n.d.]). Besides a commit manager, GTX has no other server
thread. Transactions’ isolation and consistency ensures the correctness of
concurrent operations. GTX read-write transactions support vertex inserts and
updates, edge inserts, deletes, updates and lookups, and adjacency list scans.
GTX guarantees atomicity of each transaction’s updates. GTX implements all
graph analytics under read-only transactions. While each read-write
transaction is executed by its creator worker thread, a read-only transaction
can be executed by several OpenMP threads concurrently. GTX further implements
a state protection protocol to support edge-deltas block consolidation when it
becomes overflow.

GTX adopts the block manager from (Zhu and et al., 2020) and manages garbage
collection lazily. Memory blocks are recycled when no concurrent and future
transactions can see them.

##  3\. GTX Transaction Operations

Each GTX transaction is assigned a read timestamp ($rts$) at its creation time
from a global read epoch, and it does not know its write timestamp ($wts$)
until it gets committed. GTX guarantees Snapshot Isolation (Berenson and et
al., 1995) of its transactions. Let $t$ refer to both the transaction and its
transaction ID interchangeably.

###  3.1. Vertex Operations

GTX transactions can insert new vertices and update them to new versions.
Transaction $t$ reads a vertex $v$ by using an atomic $load$ on $v$’s delta-
chains pointer after locating the $v$’s entry in the index. $t$ checks $v$’s
delta-chain head, and compares its $rts$ against the vertex-delta’s creation
time. A transaction can see all deltas created before its $rts$. If the
current vertex-delta represents the future version, $t$ uses the
$previous\\_ptr$ to read the previous vertex-delta (previous version) on the
delta-chain. Vertex writes (insertion and updates) are handled by creating a
new vertex-delta (new version), and invoking a $CAS$ on $v$’s delta-chain
pointer. If the $CAS$ fails, $t$ observes write-write conflict and immediately
abort.

###  3.2. Edge Write Operations

GTX supports edge inserts, update and deletes, and they are handled similarly
except having different delta types. GTX executes checked operations. An edge
delete only takes place after determining the edge’s existence. An edge insert
only takes place after checking that the edge does not exist. Otherwise, the
write operation is executed as an update. $t$ inserts/updates/deletes an edge,
say $e(u,v)$, by creating an insert/update/delete edge-delta of $e(u,v)$.
Edge-deltas blocks manage concurrency at the delta-chain level. $t$ calculates
the delta-chain $e(u,v)$ belongs to, say the $i^{th}$ delta-chain, and locks
it in the delta-chains index. After locking the delta-chain, $t$ searches the
latest edge-delta(version) of $e(u,v)$ using each edge-delta’s
$previous\\_offset$, and writes $t$ as its invalidation timestamp if the edge-
delta exists. Then, $t$ allocates memory by updating the combined_offset, and
write the edge-delta in the corresponding locations. The edge-delta stores the
offset of the current $i^{th}$ delta-chain head, and stores the offset of the
previous edge-delta of $e(u,v)$. Moreover, it stores $t$ as the new edge-
delta’s creation timestamp. If $t$ fails to lock the $i^{th}$ delta-chain, $t$
will abort.

###  3.3. Edge Read Operation

GTX supports two types of edge read operations: Single-edge lookup and
adjacency list scan. Single-edge lookup uses the delta-chains index and is
identical as checking whether an edge exists in an edge write operation.
Adjacency list scan is implemented as scanning the whole edge-deltas block.
After locating the edge-deltas block, $t$ loads the combined_offset. The
combined_offset determines where in the edge-deltas block the scan starts. $t$
scans all edge-deltas starting from there, and can see all edge-deltas created
before and invalidated after (or not invalidated at all) $t$’s $rts$.

###  3.4. Hybrid Commit

GTX supports a hybrid group commit protocol. GTX manages a transaction table
that provides $O(1)$ access time of looking up a transaction’s status. A
transaction registers a commit request by informing the commit manager. The
commit manager keeps a global write epoch number, and assigns its value as the
$wts$ to the commit group of transactions by updating their status in the
transaction table. After committing each group, the commit manager increments
the global read epoch and global write epoch by 1. The committing transactions
eagerly find and update their deltas’ timestamps with their commit timestamp.
Concurrent transactions may observe a delta’s timestamp is a committed
transaction (ID) by querying the transaction table, and update the delta’s
timestamp for the committing transaction. We call this cooperative commit
protocol hybrid commit. It reduces group commit latency, and saves cost in
synchronizing committing transactions and commit manager.

###  3.5. Block Consolidation and Garbage Collection

Edge-deltas blocks may become overflowed and require allocating a new block
for the most recent edge-deltas while recycling the old block with the
outdated edge-deltas. GTX uses a latch-free state protection protocol inspired
by (Li et al., 2022) for each edge-deltas block that eliminates latches in
shared memory and preserves cache coherence. Its core is analyzing the edge-
deltas block, allocating a new block according to workload history, and
migrating the latest version edge-deltas to the new block while concurrent
transactions can still read the original edge-deltas block. After
consolidating an edge-deltas block, the old deltas block is considered
outdated and is placed in a queue. GTX tracks timestamps of current running
transactions, and periodically has its worker threads free the memory blocks
no transactions can access.

###  3.6. Transaction Example

Figure 2. Examples

We present how GTX transactions lookup and update edges. We use $ts$,
$ts_{c}$, $ts_{r}$, $ts_{cr}$, and $ts_{i}$ to indicate timestamp,
commit_timestamp, read_timestamp, creation_timestamp, and
invalidation_timestamp, respectively.Figure 2 illustrates how transactions
execute edge insert, delete, and update. Transactions and their modification
to the edge-deltas block and delta-chains index are in the same color. The
edge-deltas block for Vertex 1 originally stores the 3 edges $(1,12)$,
$(1,3)$, and $(1,5)$ using 3 edge-deltas and 2 delta-chains. Delta-chains
Index Entry 0 stores $offset=64$ that points to $(1,12)$, and Entry 1 stores
$offset=192$ pointing to $(1,5)$. Transaction $T_{1}$ inserts a new edge
$(1,8)$ with 32 bytes of property data. $T_{1}$ calculates that Edge $(1,8)$
belongs to Delta-Chain $0=8\bmod 2$ where 2 is the number of delta-chains, and
uses the $0^{th}$ delta-chains index entry $64$ to locate the edge-deltas
chain, and searches for a previous version of $(1,8)$. Then, it allocates
space in both the delta region and the data region by updating combined_offset
atomically. Next, it writes the new insert edge-delta and its property into
the allocated region. Note that the new edge-delta has previous_offset=64 and
previous_version=0 because it needs to point to the previous edge-delta on the
delta-chain, and Edge $(1,8)$ has no previous version. At commit phase,
$T_{1}$ updates delta-chains index entry to point to the new edge-delta, and
the commit manager commits $T_{1}$ at $ts_{c}=14$. The edge-delta’s $ts_{cr}$
gets updated to 14. Next, Transaction $T_{2}$ deletes Edge $(1,5)$. $T_{2}$
uses the delta-chains index entry 1 to find the previous version of $(1,5)$ at
offset $196$. Then, it allocates the space for its edge-delta by updating the
combined_offset. Since $T_{2}$ is deleting $(1,5)$, it does not allocate space
in the data region. $T_{2}$ creates its delete edge-delta, and stores offset
$192$ as the new delta’s previous version. $T_{2}$ commits in a similar way by
updating the delta-chains index Entry 1 and registers with the commit manager.
After the commit manager commits $T_{2}$ at $ts_{c}=20$, the delete edge-
delta’s $ts_{cr}$ and the previous version edge-delta’s $ts_{i}$ are both
updated to $20$. Transaction $T_{3}$ updates Edge $(1,12)$ with a new 32 bytes
property. $T_{3}$ finds the previous version of $(1,12)$ at offset 64 using
the delta-chain similarly. $T_{3}$ allocates space and creates an update edge-
delta for $(1,12)$ and commits, and the delta-chains index, the new edge-
delta’s $ts_{cr}$, and the previous version’s $ts_{i}$ get updated.

Dataset | Category | Vertex Count | Edge Count
---|---|---|---
yahoo-songs | real-world | 1,625,951 | 256,804,235
edit-wiki | real-world | 50,757,442 | 572,591,272
graph500-24 | synthetic | 8,870,942 | 260,379,520
Table 1. Dataset Statistics

##  4\. Demonstration and Evaluation

We demonstrate GTX’s abilities to ingest real-world graphs with hotspots and
to efficiently execute concurrent read-write transactions and graph analytics.
We evaluate GTX’s performance against other state-of-the-art transactional
graph systems, illustrating GTX’s high throughput in transactions, and
robustness across workloads while maintaining competitive graph analytics
performance.

###  4.1. Demonstration Scenario

We showcase GTX’s high transaction throughput for workloads with temporal
localities, while maintaining competitive graph analytics performance. We
compare GTX’s transaction throughput and graph analytics latency against
state-of-the-art transactional graph systems.We adopt the Graph Framework4
Evaluation (GFE) from Teseo (De Leo and Boncz, 2021) and Sortledton (Fuchs et
al., 2022) for evaluation and demonstration. We use two real-world power-law
graph datasets yahoo-songs(y-s) and edit-wiki(e-w) (Kunegis, [n.d.]) and two
sets of synthetic graph update logs (2.6 billion entries each) generated by
(De Leo, [n.d.]) on graph500-24 (Iosup and et al., 2016). One graph log
shuffles edge updates and the other contains temporal localities. The
statistics of the datasets can be found in Table 1.

We execute the demonstration on a dual-socket machine with Intel(R) Xeon(R)
Platinum 8368 CPU @ 2.40GHz processors with 156 CPU and 192GB of DRAM. We run
all evaluations in a single NUMA node if the memory size fits. All systems
execute checked operations as transactions, checking an edge’s existence
before performing the write. This demonstration only considers undirected
graphs and each system treats an undirected edge as two directed edges.
Therefore, for each edge $e(u,v)$, each system creates a transaction that
checks whether $e(u,v)$ and $e(v,u)$ exist, and inserts both edges.

| y-s shuffled | y-s ordered | e-w shuffled | e-w ordered
---|---|---|---|---
GTX | 6727920 | 4864010 | 3909976 | 3946243
Sortledton | 4118089 | 443473 | 3686403 | 432638
Teseo | 3534455 | 105234 | 2609071 | 24640
LiveGraph | 723299 | 151309 | 603040 | 102398
Table 2. Graph Construction Throughput(txns/s) | PR | SSSP | PR hotspot | SSSP hotspot
---|---|---|---|---
GTX | 4365903 | 4265851 | 4959926 | 4265851
Sortledton | 3568179 | 3490729 | 1364880 | N/A
LiveGraph | 640138 | 630250 | 418388 | 405232
Table 3. Mixed-Workload Throughput(txns/s) | PR | SSSP | PR hotspot | SSSP hotspot
---|---|---|---|---
GTX | 15993070 | 22575448 | 14020837 | 18414454
Sortledton | 10525814 | 15560585 | 10391524 | N/A
LiveGraph | 13720317 | 21072157 | 10633277 | 18571507
Table 4. Mixed-Workload Latency(microsecond)

###  4.2. Evaluation

We run two sets of experiments to show GTX’s high performance. The first
experiment constructs real-world power-law graphs with (ordered) and without
(shuffled) temporal localities to evaluate each system’s transaction
throughput (shown in Table 2). Then, we make each system process update logs
with and without temporal localities and concurrently run graph analytics
(pagerank(PR) and single source shortest path(SSSP)). We report the
transaction throughput and graph analytics latency in Table 3, 4. The results
demonstrate significant advancement in performance of GTX over other systems
w.r.t. transcation throughput and analytics workloads.

###### Acknowledgements.

Walid G. Aref acknowledges the support of the National Science Foundation
under Grant Number IIS-1910216.

## References

  * (1)
  * ope ([n.d.]) [n.d.].  _OpenMP_.  https://www.openmp.org/
  * Berenson and et al. (1995) Hal Berenson and et al. 1995.  A critique of ANSI SQL isolation levels.  _SIGMOD Rec._ 24, 2 (may 1995), 1–10.  https://doi.org/10.1145/568271.223785
  * Cheng et al. ([n.d.]) Audrey Cheng, Jack Waudby, Hugo Firth, Natacha Crooks, and Ion Stoica. [n.d.].  Mammoths Are Slow: The Overlooked Transactions of Graph Data.  ([n. d.]).
  * De Leo ([n.d.]) Dean De Leo. [n.d.].  _graphlog_.  https://github.com/whatsthecraic/graphlog
  * De Leo and Boncz (2021) Dean De Leo and Peter Boncz. 2021.  Teseo and the Analysis of Structural Dynamic Graphs.  14, 6 (feb 2021), 1053–1066.  https://doi.org/10.14778/3447689.3447708
  * Fuchs et al. (2022) Per Fuchs, Domagoj Margan, and Jana Giceva. 2022.  Sortledton: A Universal, Transactional Graph Data Structure.  _Proc. VLDB Endow._ 15, 6 (feb 2022), 1173–1186.  https://doi.org/10.14778/3514061.3514065
  * Iosup and et al. (2016) Alexandru Iosup and et al. 2016.  LDBC Graphalytics: A Benchmark for Large-Scale Graph Analysis on Parallel and Distributed Platforms.  9, 13 (2016), 12.
  * Kunegis ([n.d.]) Jérôme Kunegis. [n.d.].  _The KONECT Project_.  http://konect.cc/
  * Li and et al. (2022) Changji Li and et al. 2022.  ByteGraph: A High-Performance Distributed Graph Database in ByteDance.  _Proc. VLDB Endow._ 15, 12 (2022).
  * Li et al. (2022) Tianyu Li, Badrish Chandramouli, and Samuel Madden. 2022.  Performant Almost-Latch-Free Data Structures Using Epoch Protection. In _Data Management on New Hardware_ _(DaMoN’22)_. Article 1, 10 pages.
  * Wu et al. (2017) Yingjun Wu, Joy Arulraj, Jiexi Lin, Ran Xian, and Andrew Pavlo. 2017.  An Empirical Evaluation of In-Memory Multi-Version Concurrency Control.  _Proc. VLDB Endow._ 10, 7 (2017).  https://doi.org/10.14778/3067421.3067427
  * Zhu and et al. (2020) Xiaowei Zhu and et al. 2020.  LiveGraph: A Transactional Graph Storage System with Purely Sequential Adjacency List Scans.  13, 7 (mar 2020), 1020–1034.


# The camel-banana problem

Michiel de Bondt

(June 12, 1996111The proof of Lemma B has been replaced by a shorter proof on
February 10, 2024.)

> A camel can carry one banana at a time on its back. It is on a diet and
> therefore can only have one banana at a time in its stomach. As soon as it
> has eaten a banana it walks a mile and then it needs a new banana (in order
> to be able to continue its itinerary).
>
> Let there be a stock of $N$ bananas at the border of the desert. How far can
> the camel penetrate into the desert, starting at this point? (Of course it
> can form new stocks with transported bananas.)222This was problem number 10
> of the “Universitaire Wiskunde Competitie” of 1992-93, a Dutch mathematical
> competition for students. A partial solution then was given by the author.
> Here he presents a full solution.

It is easy to see that the camel can penetrate $1$ mile into the desert with
$1$ banana, $2$ miles with $2$ bananas and $2\frac{1}{3}$ miles with $3$
bananas. But how far can the camel get with $73083734$ bananas? We shall give
the answer in the following pages.

We can assume that the camel will use only one line of the desert. It is
natural to take a real co-ordinate along this line, with the starting point at
the origin and a mile as the unit length. Positions along the line will be
given by their co-ordinate. An ‘Ultra Wise Camel’ might apply the following
strategy, since it is optimal, as we shall prove.

UWC-STRATEGY: Repeat the following until there are $3$ bananas left:

  1. (1)

If the number of bananas left is even: eat a banana, carry another banana as
far as possible and return to the banana(s) closest to the origin.

  2. (2)

If the number of bananas left is odd: eat a banana, carry another banana to
the furthest banana, then carry both bananas (each in turn) as far as
possible, and finally return to the banana(s) closest to the origin.

When there are $2$ or $3$ bananas left, do the above without returning to the
banana(s) closest to the origin.

Figure 1: a UWC-strategy step for an even number of bananas. Figure 2: a UWC-
strategy step for an odd number of bananas. Figure 3: the last 3 steps of the
UWC-strategy.

Figure 3 shows the last $3$ steps of this strategy. Steps (1) and (2) are
illustrated in Figures 1 and 2. The figures show that the following properties
holding at the beginning are not affected by applying the UWC-strategy:

  1. (a)

During meal-time, the camel is with the banana(s) closest to the origin and
there is an interval of length $\frac{1}{2}$ containing all bananas.

  2. (b)

Just before step (1), the bananas can be divided into pairs, such that the
bananas of each pair are at the same position (but different pairs may also be
at the same position). Figure 1 makes clear that the camel can transform the
hindmost pair into one furthest banana (with one of the two bananas being
eaten and the other being transported) and leave all other pairs where they
are in step (1).

  3. (c)

Just before step (2), the bananas can be divided into pairs in the same way as
in (b), except one furthest banana. Figure 2 makes clear that the camel can
transform the hindmost pair and the sole furthest banana into a new furthest
pair and leave all other pairs where they are in step (2).

Let $c(N)$ denote the distance the camel can penetrate into the desert, when
applying the UWC-strategy.

EXAMPLES: We illustrate the UWC-strategy for the cases of $N=3$, $4$, $5$,
$6$, $7$ bananas by giving the positions of the bananas at each step just
before the camel starts eating.

$N=3$: |  $(0,0,0)$, $(\frac{1}{3},\frac{1}{3})$, $(1\frac{1}{3})$ $\Longrightarrow c(3)=2\frac{1}{3}$
---|---
$N=4$: |  $(0,0,0,0)$, $(0,0,\frac{1}{2})$, $(\frac{2}{3},\frac{2}{3})$, $(1\frac{2}{3})$ $\Longrightarrow c(4)=2\frac{2}{3}$
$N=5$: |  $(0,0,0,0,0)$, $(0,0,\frac{1}{4},\frac{1}{4})$, $(\frac{1}{4},\frac{1}{4},\frac{5}{8})$, $(\frac{5}{6},\frac{5}{6})$, $(1\frac{5}{6})$ $\Longrightarrow c(5)=2\frac{5}{6}$
$N=6$: |  $(0,0,0,0,0,0)$, $(0,0,0,0,\frac{1}{2})$, $(0,0,\frac{1}{2},\frac{1}{2})$, $(\frac{1}{2},\frac{1}{2},\frac{3}{4})$, $(1,1)$, $(2)$ $\Longrightarrow c(6)=3$
$N=7$: |  $(0,0,0,0,0,0,0)$, $(0,0,0,0,\frac{1}{4},\frac{1}{4})$, $(0,0,\frac{1}{4},\frac{1}{4},\frac{1}{2})$, $(\frac{1}{4},\frac{1}{4},\frac{9}{16},\frac{9}{16})$, $(\frac{9}{16},\frac{9}{16},\frac{29}{32})$, $(1\frac{1}{8},1\frac{1}{8})$, $(2\frac{1}{8})$ $\Longrightarrow c(7)=3\frac{1}{8}$

Suppose that the camel applies the UWC-strategy. Since pairs of bananas as
described in properties (b) and (c) are destructed only during meal-time, each
position of a pair is an eating position: a position where a banana is eaten
during the strategy.

Let $e_{i}$ denote the eating position where the camel eats its $(N+1-i)$-th
banana in the UWC-strategy. Then

$0=e_{N}\leq e_{N-1}\leq\ldots\leq e_{2}\leq e_{1}=c(N)-1$

When there are $2n$ bananas left just before a strategy step, the $n$ pairs of
bananas are lying at $e_{2n}$, $e_{2n-1}$, $e_{2n-2}$, $\ldots$, $e_{n+1}$.
Inspection of what happens at the next two steps of the UWC-strategy reveals
that

$e_{n}=\frac{1}{4}e_{2n-2}+\frac{1}{2}e_{2n-1}+\frac{1}{4}e_{2n}+\frac{1}{2}\quad(n\geq
2)$ (1)

Note that for $n=2$, this equality simplifies to

$e_{2}=\frac{2}{3}e_{3}+\frac{1}{3}e_{4}+\frac{2}{3}$

This implies that for each $n\geq 2$, the number $e_{2}$ can be expressed as
an affinely linear function of $e_{2n}$, $e_{2n-1}$, $e_{2n-2}$, $\ldots$,
$e_{n+1}$ with coefficients depending only on $n$ and not on the original
number $N$ of bananas at the starting position. The same holds for
$c(N)=e_{2}+2$, in other words, for each $n\geq 2$ with $2n\leq N$ there are
constants $\lambda_{n,i}$ ($i=0$, $1$, $\ldots$, $n$) such that

$c(N)=\lambda_{n,n}e_{2n}+\lambda_{n,n-1}e_{2n-1}+\ldots+\lambda_{n,1}e_{n+1}+\lambda_{n,0}$

Note also that $\sum_{i=1}^{n}\lambda_{n,i}=1$ for all $n$. Indeed, this
relation holds for $n=2$, and it is preserved during all subsequent
substitutions. We shall use these observations to prove:

## Theorem I.

If $n\geq 1$, then $c$ satisfies the following equalities

$\displaystyle c(2n+1)$ $\displaystyle=$
$\displaystyle\frac{1}{2}c(2n)+\frac{1}{2}c(2n+2)$ $\displaystyle c(2n)$
$\displaystyle=$ $\displaystyle\frac{1}{2}c(n)+\frac{1}{2}c(n+1)+\frac{1}{2}$

## Proof:

The examples above show that the first equality holds for $n=1$, so let $n>1$.
Suppose that there are $2n$ bananas left and the camel is about to eat its
next banana, while applying the UWC-strategy for $N$ bananas ($N\geq 2n$).
Then:

  * •

if $N=2n$ then there are $2n$ bananas at $0$, so $e_{2n}=\ldots=e_{n+1}=0$,
and $c(2n)=\lambda_{n,0}$,

  * •

if $N=2n+1$ then there are $2n-2$ bananas at $0$ and $2$ bananas at
$\frac{1}{4}$, so $e_{2n}=\ldots=e_{n+2}=0$, $e_{n+1}=\frac{1}{4}$, and
$c(2n+1)=\frac{1}{4}\lambda_{n,1}+\lambda_{n,0}$,

  * •

if $N=2n+2$ then there are $2n-2$ bananas at $0$ and $2$ bananas at
$\frac{1}{2}$, so $e_{2n}=\ldots=e_{n+2}=0$, $e_{n+1}=\frac{1}{2}$, and
$c(2n+2)=\frac{1}{2}\lambda_{n,1}+\lambda_{n,0}$.

The first equality of the theorem thus is proved. The proof of the second
equality is slightly more complicated. We split it into two cases, $n=2m$ and
$n=2m+1$:

$\displaystyle c(4m)$ $\displaystyle=$
$\displaystyle\frac{1}{2}c(2m)+\frac{1}{2}c(2m+1)+\frac{1}{2}$ $\displaystyle
c(4m+2)$ $\displaystyle=$
$\displaystyle\frac{1}{2}c(2m+1)+\frac{1}{2}c(2m+2)+\frac{1}{2}$

The above examples show that these equalities hold for $m=1$, so let $m>1$. We
apply the UWC-strategy for $N=4m$ and $N=4m+2$ separately, and consider in
each case the situation when there are $2m$ bananas left.

  * •

If $N=4m$ then there are $2m-2$ bananas at $\frac{1}{2}$ and $2$ bananas at
$\frac{5}{8}$, so $e_{2m}=\ldots=e_{m+2}=\frac{1}{2}$ and
$e_{m+1}=\frac{5}{8}$. It follows that

$\displaystyle c(4m)$ $\displaystyle=$
$\displaystyle\frac{1}{2}\sum_{i=2}^{m}\lambda_{m,i}+\frac{5}{8}\lambda_{m,1}+\lambda_{m,0}=\frac{1}{2}+\frac{1}{8}\lambda_{m,1}+\lambda_{m,0}$
$\displaystyle=$
$\displaystyle\frac{1}{2}c(2m)+\frac{1}{2}c(2m+1)+\frac{1}{2}$

  * •

If $N=4m+2$ then there are $2m-2$ bananas at $\frac{1}{2}$ and $2$ bananas at
$\frac{7}{8}$, so $e_{2m}=\ldots=e_{m+2}=\frac{1}{2}$ and
$e_{m+1}=\frac{7}{8}$. It follows that

$\displaystyle c(4m+2)$ $\displaystyle=$
$\displaystyle\frac{1}{2}\sum_{i=2}^{m}\lambda_{m,i}+\frac{7}{8}\lambda_{m,1}+\lambda_{m,0}=\frac{1}{2}+\frac{3}{8}\lambda_{m,1}+\lambda_{m,0}$
$\displaystyle=$
$\displaystyle\frac{1}{2}c(2m+1)+\frac{1}{2}c(2m+2)+\frac{1}{2}$

This completes the proof of Theorem I. $\Box$

Although the equalities of theorem I and the initial value $c(1)=1$ completely
determine the numbers $c(n)$ for all $n$, to compute, say, $c(73083734)$, it
is more convenient to have an explicit formula. We now shall derive one.

Define

$F(n,m)=\frac{{}^{2}\\!\log
m}{2}+g(\frac{n-1}{m})+\frac{(n-1)\pmod{2}}{6m^{2}}\quad(n,m>0)$ (2)

where

$g(x)=-\frac{1}{6}x^{2}+x+1$

Then it is a trivial exercise to verify the following equalities:

$\displaystyle F(2m,2m)$ $\displaystyle=$ $\displaystyle F(2m,m)$ (3)
$\displaystyle F(2n+1,m)$ $\displaystyle=$
$\displaystyle\frac{1}{2}F(2n,m)+\frac{1}{2}F(2n+2,m)$ (4) $\displaystyle
F(2n,2m)$ $\displaystyle=$
$\displaystyle\frac{1}{2}F(n,m)+\frac{1}{2}F(n+1,m)+\frac{1}{2}$ (5)

Define

$h(n)=2^{\lfloor{{}^{2}\\!\log n}\rfloor}\quad(n\geq 1)$

so $h(n)$ is the largest power of $2$ such that $h(n)\leq n$.

## Theorem II.

$c(n)=F(n,h(n))\quad(n\geq 1)$

## Proof:

The case $n=1$ is trivial, so let $n>1$. It is sufficient to check the
equalities corresponding to those of theorem I:

$\displaystyle F(2n+1,h(2n+1))$ $\displaystyle=$
$\displaystyle\frac{1}{2}F(2n,h(2n))+\frac{1}{2}F(2n+2,h(2n+2))\quad(n\geq 1)$
$\displaystyle F(2n,h(2n))$ $\displaystyle=$
$\displaystyle\frac{1}{2}F(n,h(n))+\frac{1}{2}F(n+1,h(n+1))+\frac{1}{2}\quad(n\geq
1)$

To do so, we consider two cases:

  * •

$n+1=2^{k}$ for some integer $k\geq 1$.
Then $h(n)=2^{k-1}$, $h(n+1)=h(2n)=h(2n+1)=2^{k}$ and $h(2n+2)=2^{k+1}$. By
(3), the two equalities then reduce to

$\displaystyle F(2n+1,n+1)$ $\displaystyle=$
$\displaystyle\frac{1}{2}F(2n,n+1)+\frac{1}{2}F(2n+2,2n+2)$ $\displaystyle=$
$\displaystyle\frac{1}{2}F(2n,n+1)+\frac{1}{2}F(2n+2,n+1)$ $\displaystyle
F(2n,n+1)$ $\displaystyle=$
$\displaystyle\frac{1}{2}F(n,\frac{n+1}{2})+\frac{1}{2}F(n+1,n+1)+\frac{1}{2}$
$\displaystyle=$
$\displaystyle\frac{1}{2}F(2n,\frac{n+1}{2})+\frac{1}{2}F(n+1,\frac{n+1}{2})$

which are true by (4) and (5).

  * •

$2^{k}<n+1<2^{k+1}$ for some integer $k\geq 1$.
Then $h(n)=h(n+1)=2^{k}$, $h(2n)=h(2n+1)=h(2n+2)=2^{k+1}$ and the two
equalities can be written as

$\displaystyle F(2n+1,2^{k+1})$ $\displaystyle=$
$\displaystyle\frac{1}{2}F(2n,2^{k+1})+\frac{1}{2}F(2n+2,2^{k+1})\quad(n\geq
1)$ $\displaystyle F(2n,2^{k+1})$ $\displaystyle=$
$\displaystyle\frac{1}{2}F(n,2^{k})+\frac{1}{2}F(n+1,2^{k})+\frac{1}{2}\quad(n\geq
1)$

which are also true by (4) and (5). $\Box$

Now $c(73083734)=14\frac{1003590240076691}{1125899906842624}$ can be easily
verified using theorem II and formula (2). But we still have to show that the
camel cannot reach further than this with $73083734$ bananas.

Before proving the optimality of the UWC-strategy, we first derive two more
properties of the UWC-strategy. Let

$s_{n}=e_{1}+2\sum_{k=2}^{n}e_{k}$

(which by definition also includes $s_{1}=e_{1}$).

## Lemma A.

$\begin{array}[]{ll}s_{n}=N-1&\quad(n\geq N/2)\\\
s_{n}=\frac{1}{4}s_{2n-1}+\frac{1}{4}s_{2n}+\frac{2n-1}{2}&\quad(n\leq
N/2)\end{array}$

## Proof:

Suppose that the camel has just eaten its last banana in the UWC-strategy. It
has walked $N-1$ miles in total, of which, say, $f$ miles in forward
direction, and $b$ miles backward. Then $f+b=N-1$ and $f-b=e_{1}$, so
$f=(N-1+e_{1})/2$. Since the camel always had a banana on its back when it
walked forward, the sum $\sum_{n=1}^{N}e_{n}$ of the positions of the banana
skins equals $(N-1+e_{1})/2$. Since $e_{n}=0$ if $n\geq N/2+1$, it follows
that $s_{n}=N-1$ for all $n\geq N/2$.
To prove the remaining part of the lemma, we note that by equation (1)

$\displaystyle 2e_{k}$ $\displaystyle=$
$\displaystyle\frac{1}{2}e_{2k-2}+e_{2k-1}+\frac{1}{2}e_{2k}+1$
$\displaystyle=$
$\displaystyle\frac{1}{4}(2e_{2k-2}+2e_{2k-1})+\frac{1}{4}(2e_{2k-1}+2e_{2k})+1$

for $k=2$, $3$, $\ldots$, $n$. Since also

$e_{1}=\frac{1}{2}e_{1}+\frac{1}{2}e_{2}+\frac{1}{2}=\frac{1}{4}s_{1}+\frac{1}{4}s_{2}+\frac{1}{2}$

the desired result follows by addition. $\Box$

Now let $S$ be any optimal strategy for $N$ bananas. Let $e_{1}^{\prime}$,
$e_{2}^{\prime}$, $\ldots$, $e_{N}^{\prime}$ be the eating positions of the
$N$ bananas (which are all used), numbered in such a way that

$0=e_{N}^{\prime}\leq e_{N-1}^{\prime}\leq\ldots\leq e_{2}^{\prime}\leq
e_{1}^{\prime}$

Note that we do not suppose that the bananas are eaten in the order
$e_{N}^{\prime}$, $e_{N-1}^{\prime}$, $\ldots$, $e_{1}^{\prime}$, although we
may (and shall) assume that the first banana is eaten at $e_{N}^{\prime}$, and
the last one at $e_{1}^{\prime}$. In between, however, the order might be
different.

As above, we define

$s_{n}^{\prime}=e_{1}^{\prime}+2\sum_{k=2}^{n}e_{k}^{\prime}$

and as in the proof of Lemma A, we suppose that the camel has just eaten its
last banana. Again, it has walked $N-1$ miles, of which
$(N-1+e_{1}^{\prime})/2$ miles in forward direction. Since it always had at
most one banana on its back when it walked forward, the sum
$\sum_{n=1}^{N}e_{n}^{\prime}$ of the positions of the banana skins is at most
$(N-1+e_{1}^{\prime})/2$. This implies that $s_{N}^{\prime}\leq N-1$, and
since $s_{n}^{\prime}\leq s_{N}^{\prime}$ for all $n$, we also have
$s_{n}^{\prime}\leq N-1$ for all $n$.
As an analogue of Lemma A, we formulate:

## Lemma B.

$\begin{array}[]{ll}s_{n}^{\prime}\leq N-1&\quad(n\geq N/2)\\\
s_{n}^{\prime}\leq\frac{1}{4}s_{2n-1}^{\prime}+\frac{1}{4}s_{2n}^{\prime}+\frac{2n-1}{2}&\quad(n\leq
N/2)\end{array}$

The second inequality of Lemma B is somewhat more difficult to prove. Before
giving a proof of lemma B, we note that lemmas A and B together yield
$s_{n}^{\prime}\leq s_{n}$ for all $n$ (start with $n=N$ and proceed in
descending order), so in particular $e_{1}^{\prime}+1=s_{1}^{\prime}+1\leq
s_{1}+1=e_{1}+1=c(N)$. Since $S$ is assumed to be an optimal strategy, the
camel reaches as far as $e_{1}^{\prime}+1\geq c(N)$ in $S$. So
$e_{1}^{\prime}+1=c(N)$, which amounts to the optimality of the UWC-strategy.

## Theorem III.

The UWC-strategy is optimal.

## Proof:

We are done when we shall have proved lemma B.

Let $\beta=e^{\prime}_{2n}+\frac{1}{2}$. During the $\frac{1}{2}$ mile before
eating a banana on position $e^{\prime}_{i}$, the camel can maximize the
portion of its walk that is done in the interval $[\beta,\infty)$ by walking
from position $e^{\prime}_{i}+\frac{1}{2}$ to position $e^{\prime}_{i}$. It
walks at most
$\max\\{e^{\prime}_{i}+\frac{1}{2},\beta\\}-\max\\{e^{\prime}_{i},\beta\\}$
miles in $[\beta,\infty)$. During the $\frac{1}{2}$ mile after eating a banana
on position $e^{\prime}_{i}$, the camel can maximize the portion of its walk
that is done in the interval $[\beta,\infty)$ by walking from position
$e^{\prime}_{i}$ to position $e^{\prime}_{i}+\frac{1}{2}$. Again, it walks at
most
$\max\\{e^{\prime}_{i}+\frac{1}{2},\beta\\}-\max\\{e^{\prime}_{i},\beta\\}$
miles in $[\beta,\infty)$.

For $2\leq i\leq n$, we estimate
$\max\\{e^{\prime}_{i}+\frac{1}{2},\beta\\}-\max\\{e^{\prime}_{i},\beta\\}$ by
$\frac{1}{2}$. For $n+1\leq i\leq 2n$, we estimate
$\max\\{e^{\prime}_{i}+\frac{1}{2},\beta\\}-\max\\{e^{\prime}_{i},\beta\\}$ by
$\max\\{e^{\prime}_{i}+\frac{1}{2},\beta\\}-\beta=e^{\prime}_{i}+\frac{1}{2}-\beta$.
So before eating its last banana on position $e^{\prime}_{1}$, the camel walks

$\alpha\leq(e^{\prime}_{1}+\frac{1}{2}-\max\\{e^{\prime}_{1},\beta\\})+2\sum_{i=2}^{n}\frac{1}{2}+2\sum_{i=n+1}^{2n}(e^{\prime}_{i}+\frac{1}{2}-\beta)$

miles in $[\beta,\infty)$. These $\alpha$ miles add up to a walk from position
$\beta$ to position $\max\\{e^{\prime}_{1},\beta\\}$, of which

$\frac{\alpha-(\max\\{e^{\prime}_{1},\beta\\}-\beta)}{2}$

miles are in backward direction and

$\displaystyle\alpha^{\prime}$ $\displaystyle=$
$\displaystyle\frac{\alpha+(\max\\{e^{\prime}_{1},\beta\\}-\beta)}{2}$
$\displaystyle\leq$
$\displaystyle\frac{1}{2}\big{(}e^{\prime}_{1}+\frac{1}{2}-\beta\big{)}+\sum_{i=2}^{n}\frac{1}{2}+\sum_{i=n+1}^{2n}(e^{\prime}_{i}+\frac{1}{2}-\beta)$
$\displaystyle=$
$\displaystyle\frac{1}{2}(e^{\prime}_{1}-e^{\prime}_{2n})+\sum_{i=n+1}^{2n}e^{\prime}_{i}+\frac{2n-1}{2}-n\cdot\beta$

miles are in forward direction.

The camel carries bananas to positions
$e^{\prime}_{1},e^{\prime}_{2},\ldots,e^{\prime}_{n}$, so

$\alpha^{\prime}\geq\sum_{i=1}^{n}(\max\\{e^{\prime}_{i},\beta\\}-\beta)\geq\sum_{i=1}^{n}e^{\prime}_{i}-n\cdot\beta$

Combining the upper bound and the lower bound of $\alpha^{\prime}$, we obtain

$\sum_{i=1}^{n}e^{\prime}_{i}\leq\frac{1}{2}(e^{\prime}_{1}-e^{\prime}_{2n})+\sum_{i=n+1}^{2n}e^{\prime}_{i}+\frac{2n-1}{2}$

Consequently

$\displaystyle\frac{1}{2}s^{\prime}_{n}$ $\displaystyle\leq$
$\displaystyle-\frac{1}{2}e^{\prime}_{2n}+\sum_{i=n+1}^{2n}e_{i}+\frac{2n-1}{2}$
$\displaystyle=$
$\displaystyle(\frac{1}{4}s^{\prime}_{2n-1}-\frac{1}{4}s^{\prime}_{2n})+(\frac{1}{2}s^{\prime}_{2n}-\frac{1}{2}s^{\prime}_{n})+\frac{2n-1}{2}$

This proves lemma B, and, as a consequence, theorem III. $\Box$

In some cases it is possible to exchange certain steps in the UWC-strategy
without affecting the final result. Take, e.g., $N=7$, where the first two
steps may be interchanged. In general, it may be shown that any optimal
strategy $S$ is equivalent to a permutation of the steps of the UWC-strategy.
The proof is left as an exercise to the reader.