11institutetext: University of Tokyo
11email<EMAIL_ADDRESS>
# Conflict-free Collaborative Set Sharing
for Distributed Systems

Masato Takeichi

###### Abstract

Collaborative Data Sharing is widely noticed to be essential for distributed
systems. Among several proposed strategies, conflict-free techniques are
considered useful for serverless concurrent systems.

They aim at making shared data be consistent between peers in such a way that
their local data do not become equal at once, but they arrive at the same data
eventually when no updates occur in any peer.

Although the Conflict-free Replicated Data Type (CRDT) approach could be used
in data sharing as well, it puts restrictions on available operations so as to
concurrent updates never cause conflicts. Even for sets, popular operations
such as insertion and deletion are not freely used, for example.

We propose a novel scheme for Conflict-free Collaborative Set Sharing that
allows both insertion and deletion operations. It will provide a new
synchronization method for data sharing and gives a fresh insight into
designing conflict-free replicated data types. We might consider that this
becomes a substitute for CRDTs.

##  1 Introduction

In the server-client system, clients can easily share data on the server. This
is a traditional style of data sharing. However, in distributed systems where
each site, or peer, has its own exclusive property of the contents and the
policy, data sharing between peers for collaborative work raises several
substantial problems.

We have been discussing “What should be shared” in collaborative data sharing,
but not so much talking about “How should be shared”.

Concerning the “what”, a seminal work on Collaborative Data Sharing [9, 10]
brought several issues upon specification of data to be shared. An approach
based on the view-updating technique with Bidirectional Transformation [4, 2,
5, 6, 7] has been proved promissing. Among others and aside from data
transformation, we observe different approaches on the “how”: The Dejima 1.0
implementation [8, 1] uses the PostgreSQL synchronization mechanism with
strong consistency between distributed data. And the BCDS Agent [15]
implementation applies a “happy-go-lucky” technique for eventual consistency
based on the property of Bidirectional Function Composition [14], but we face
some difficulty to foresee the final result because of its global nature.

In collaborative data sharing, each peer has its local data and it provides
some of them to other peers and receives some data from peers for reflecting
updates on these shared data.

From the other side of data sharing, peers may start with the common data as
shared and locate its replicas as their own local data. And then each peer
performs local operations on the replica and does any way to synchronize it
with other peers. In this course, how to share data between peers is same as
how to synchronize distributed replicas to be the same. Thus, they are almost
equivalent except original intentions. And our problem to be solved is how to
synchronize distributed replicas in serverless distributed systems.

We have various kinds of Conflict-free Replicated Data Types (CRDTs) [12]. The
CRDT approach restricts available operations acted on replicated data; the
Grow-Only-Set (G-Set) CRDT allows only the insertion operation on the set
data, for example.

We can observe another kind of collaborative systems in daily life, i.e.,
Realtime Collaborative Document Editors. Most systems are implemented with the
use of the Operational Transformation (OT) technique [3, 13]. The OT for text
editing deals with a string as the replica and the operations on the replica
should be aware of the position in the string. The synchronization process is
known to be rather complex and error-prone. And most of these systems use the
server for synchronization. So, it is not appropriate for us to add emphasis
on OT for data sharing in general, while we come across its basic idea in our
scheme.

In this paper, we will explore a novel scheme for set data sharing between
distributed replicas. The set data is the base of various data types and it is
ubiquetous in that it spreads over many applications and it can be extended in
many ways.

Our Conflict-free Collaborative Set Sharing (CCSS) allows general set
operations, i.e., insertion and deletion of an element, and avoids any
conflicts between concurrent operations to realizes eventual consistency. This
is the most distinguished feature of our CCSS compared with CRDTs.

##  2 Whereabouts of Conflicts in Distributed Systems

Consider a data sharing example of distributed systems: Peers $P$ and $Q$ have
their local data $D_{P}$ and $D_{Q}$ to be appropriately synchronized. That
is, $P$ and $Q$ have replicas $D_{P}$ and $D_{Q}$ respectively as instances of
the same set. $P$ and $Q$ update $D_{P}$ and $D_{Q}$ respectively whether or
not the network connection is alive, and they try to synchronize them during
the connection is alive.

Each peer inserts element $x$ into its local data (written as $\cup\\{x\\}$)
and deletes element from it (written as $\setminus\\{x\\}$), and sends the
operations thus performed to the partner peer. This is the client function of
the peer. The peer as the server receives remote operations from the partner
peer and puts them on the local data so that it becomes same as that of the
partner peer.

What happens in the events?

  1. 1.

Start with $D_{P}=D_{Q}=\\{1,2\\}$.

  2. 2.

Network connection fails.

  3. 3.

$P$ does $\cup\\{3\\}$ and then $\setminus\\{3\\}$.

  4. 4.

$Q$ does $\setminus\\{2\\}$ and then $\cup\\{3\\}$.

  5. 5.

Connection is restored.

How are $D_{P}$ and $D_{Q}$ synchronized? And what is the result after Step 5?
Is $D_{P}=\\{1,2\\}{\rm~{}or~{}}\\{1,3\\}$? Is
$D_{Q}=\\{1,3\\}{\rm~{}or~{}}\\{1,2,3\\}$?

It would be reasonable to answer this question with expectation as “It should
be $D_{P}=D_{Q}=\\{1,3\\}$.”

This small example may remind us of conflict resolutions for data sharing in
distributed systems.

###  2.1 How CRDT Solves the Problem

The Conflict-free Replicated Data Type (CRDT) approach [12] follows “When in
Rome do as the Romans do”. That is, the local data $D$ of type CRDT is defined
by restricting operations on $D$ so that it never becomes inconsistent with
others upon updates.

There are two types of CRDT approaches: operation-based CRDTs and state-based
CRDTs. It is known that the above two are equivalent. Since we will propose a
scheme based on operations, we give here an overview of operation-based CRDTs.

Operation-based (op-based) CRDTs [11] places data type operations into
messages, which are sent to all replicas in order. The peers apply received
operations to their replica so that they all arrive at the same state, even if
they receive concurrent messages in different orders.

The Grow-Only-Set (G-Set) allows only the insertion operation $\cup\\{x\\}$111
The operation is applied from the left of the operand $D$, i.e.,
$D\cup\\{x\\}$ represents the set data obtained by inserting $x$ into $D$.
Thus, all the operations in this paper are postfixed after the operand data. .

The local data of $P$ and $Q$ were synchronized before connection failure and
they have been modified with local operations
$\langle\cup\\{p_{1}\\},\cup\\{p_{2}\\},\cdots,\cup\\{p_{m}\\}\rangle$ and
$\langle\cup\\{q_{1}\\},\cup\\{q_{2}\\},\cdots,\cup\\{q_{n}\\}\rangle$
respectively during the connection failure period.

After the connection is established again, $P$ and $Q$ send their local
operations to each other for synchronization. Then, $P$ as the server applies
the remote operations received from $Q$ to the current local data
$D_{P}\cup\\{p_{1}\\}\cup\\{p_{2}\\}\cdots\cup\\{p_{m}\\}$ to obtain
$D_{P}\cup\\{p_{1}\\}\cup\\{p_{2}\\}\cdots\cup\\{p_{m}\\}\cup\\{q_{1}\\}\cup\\{q_{2}\\}\cdots\cup\\{q_{n}\\}$.
Similarly $Q$ has now the new local data
$D_{Q}\cup\\{q_{1}\\}\cup\\{q_{2}\\}\cdots\cup\\{q_{n}\\}\cup\\{p_{1}\\}\cup\\{p_{2}\\}\cdots\cup\\{p_{m}\\}$.
It is easy to show that these are same provided that $D_{P}=D_{Q}$ before the
connection failure. This is because the commutative property
$D\cup\\{x\\}\cup\\{y\\}=D\cup\\{y\\}\cup\\{x\\}$ holds for any $x$ and $y$.

As illustrated above in the G-Set CRDT, CRDTs solve consistency problems by
only allowing monotonic updating operations; any operation must make the
structure larger.

To define a Set CRDT with insertion and deletion, we have to do something for
deletion since deletion breaks monotonicity. A simple idea called Two-Phase-
Set (2P-Set) CRDT is to use a pair $(A,R)$ of two G-Sets for the local data
$D$: $A$ for inserted (added) elements and $R$ for deleted (removed) elements.
Deletion never actually removes elements, but does mark them as deleted and
keep them in the second G-Set $R$ of “tombstones”. When an element $x$ in the
local data $D=(A,R)$ is “deleted”, $A$ remains unchanged, i.e., $A$ does not
become $A\setminus\\{x\\}$, while $R$ grows to $R\cup\\{x\\}$. Thus, the
deletion operation is also monotonic and $D$ does not shrink.

Then, how can we answer the question: “What is the actual elements of the
local data $D$?” In this CRDT, we should answer that “It is $A\setminus R$”.
That is, all the elements of $A$ not included in $R$, are the actual existent
elements.

We cannot effectively insert elements again into the 2P-Set after they have
been deleted sometime before, since $A\setminus R$ always excludes elements
ever deleted from $A$.

As an oft-cited example of a shopping basket in an online shop:

  * •

The G-Set cannot be used, for we cannot remove items once added to the cart.

  * •

The 2P-Set cannot be practical, for we might finally want to add items that
were once added to the cart but deleted sometime before.

For the example above in this Section, the 2P-Set CRDT may cause difficulties.
If we use 2P-Sets for $D_{P}$ and $D_{Q}$, starting from
$D_{P}=D_{Q}=\\{1,2\\}$, after $P$ does $\cup\\{3\\}$ and then
$\setminus\\{3\\}$ and $Q$ does $\setminus\\{2\\}$ and then $\cup\\{3\\}$, we
see that $3$ is never included actually in $D_{P}$ and $D_{Q}$ since $P$’s
operation $\setminus\\{3\\}$ rejects actual $3$ whether it precedes or follows
$Q$’s operation $\cup\\{3\\}$.

From these observations, we note that we should develop another schema for
sharing set data with useful operations available, insertion and deletion,
under our usual interpretation.

##  3 Conflict-free Collaborative Set Sharing

The basic idea behind our Conflict-free Collaborative Set Sharing (CCSS) is to
take particular note on the fact that our object data is mutable and
operations on that data should be closely related to the current state (value)
of the data.

Usual mathematical definitions of operations $\odot x$ on set $D$ refers to
the operator $\odot$ that maps as $(D,x)\mapsto D^{\prime}$ independently of
$D$ with $x$. But we define here $\odot x$ itself by making full use of the
relationship between $D$ and $x$ like $x\in D$, for example.

Consider another small example using usual set operators:

  * •

Assume that $P$ and $Q$ have local data $D_{P}$ and $D_{Q}$ which have been
synchronized as $D_{P}=D_{Q}=\\{1,2\\}$.

  * •

And then, $P$ wants to “insert $2$” into $D_{P}$ by a postfix operation
$\cup\\{2\\}$ and $Q$ tries to “delete $2$” from $D_{Q}$ by operation
$\setminus\\{2\\}$.

  * •

When both operations finish, $D_{P}$ remains unchanged while $D_{Q}$ has been
changed into $\\{1\\}$.

How can we make $D_{P}$ and $D_{Q}$ be synchronized, i.e., are made the same?
We have no clue for synchronization unless something is given other than the
current data. If we are given the operations $\cup\\{2\\}$ on $D_{P}$ and
$\setminus\\{2\\}$ on $D_{Q}$, we can use them for understanding the
intenstions.

Since $D_{P}=D_{Q}$ when $P$ and $Q$ began to perform concurrent operations,
we should observe that $\cup\\{2\\}$ and $\setminus\\{2\\}$ cause a conflict
of effective update: Which should be taken for obtaining consistent $D_{P}$
and $D_{Q}$?

To answer this question, consider the reason why $P$ wanted to “insert $2$”
into $D_{P}$. Supposedly, $P$ wanted to share $2$ with $Q$ by means of and at
the time of the next synchronization. As it were, what happened if $P$ had
checked before taking the operation whether “$2\in D_{P}$”? If $P$ noticed
that $2$ was already in $D_{P}$, $P$ had nothing to do for that purpose
because the intended state had already been there.

If it were, no conflict occurs!

This is what leads us to the idea of using effectful set operations for our
Conflict-free Collaborative Set Sharing.

###  3.1 Effectful Set Operations

We assume that our mutable data $D$ is a set of elements $x$ of any type, and
operations $\oplus x$ and $\ominus x$ on $D$ change the value $D$ into
$D\oplus x$ and $D\ominus x$, respectively. Of course, we can read this
mathematically as $D$ is mapped to $D\odot x$, i.e., $(D,x)\mapsto D\odot x$
by $\odot x$. We are using a generic operator symbol $\odot$ for representing
$\oplus$ or $\ominus$.

We call insertion operation $\oplus x$ effectful if it gives $D\oplus x\neq
D$. That is, the effectful operation $\oplus x$ is defined and it can be
applied to $D$ only if $x\not\in D$. Similarly the effectful $\ominus x$ is
defined and it can be applied to $D$ only if $x\in D$, and then $D\ominus
x\neq D$.

In short, the effectful operations always change $D$ when they are defined and
applied to $D$, while usual set operation $D\cup\\{x\\}$ and
$D\setminus\\{x\\}$ do not always.

For convenience, we introduce a postfix identity operation “$!$” which does
not change the value, i.e., $D!=D$ for any $D$. In fact the operation “$!$” is
not effectful according to the above intuitive meaning, but we will use this
for the “do nothing” operation.

#### Properties of effectful set operations

For the operations $\oplus x$ and $\ominus x$,

  * •

$D\oplus x\oplus x$ and $D\ominus x\ominus x$ never appear since the second
occurences of $\oplus x$ and $\ominus x$ after the first same operation are
not defined. Thus, the validity of using the effectful operations depends on
the context.

  * •

$D\ominus x\oplus x=D$ and $D\oplus x\ominus x$ hold as long as they are
valid, i.e, $x\in D$ in the first case, and $x\not\in D$ in the second case.
We can read this as effectful $\oplus x$ and $\ominus x$ cancel each other.

  * •

For $x\neq y$, hold

$\begin{split}D\oplus x\oplus y&=D\oplus y\oplus x\\\ D\oplus x\ominus
y&=D\ominus y\oplus x\\\ D\ominus x\ominus y&=D\ominus y\ominus x\end{split}$

This means that $(\oplus x,\oplus y)$, $(\oplus x,\ominus y)$ and $(\ominus
x,\ominus x)$ are commutative.

###  3.2 Normalization of Operation Sequence

We write a sequence of operations as $\langle\odot x_{1},\odot
x_{2},\cdots\rangle$ where each $\odot$ may not be the same; so it represents
$\langle\oplus x_{1},\oplus x_{2},\cdots\rangle$, $\langle\oplus x_{1},\ominus
x_{2},\cdots\rangle$, …, etc.

From the above canceling rule $D\oplus x\ominus x$ and the commutativity rule
of $\oplus x$ and $\ominus x$, if $\oplus x$ and $\ominus x$ appear in this
order with no $\odot x$ in-between,

$D\odot\cdots\oplus x\cdots\ominus x\cdots=D\odot\cdots!\cdots!\cdots$

holds. In fact, the occurences of $\oplus x$ and $\ominus x$ may be removed
from the sequence. But we use the identity operation “$!$” to fill the
positions to keep the length of the sequence.

Same for the case that $\ominus x$ and $\oplus x$ appear in this order.

Thus, we can normalize the operation sequence into one that does not contain
cancel-able pairs of $\oplus x$ and $\ominus x$, and they are replaced with
“$!$”. This does not cause any effect on the data.

And from now on, we assume that the operation sequence has been normalized.

As a consequence of normilization, no duplicate appears in the normalized
sequence $\langle\odot x_{1},\odot x_{2},\cdots\rangle$. This is because that
if ever there were pairs of operations satisfying $x_{i}=x_{j}$, i.e., the
same operation appear at different positions, they must be $(\oplus
x_{i},\ominus x_{j})$ or $(\ominus x_{i},\oplus x_{j})$, since neither
$(\oplus x_{i},\oplus x_{j})$ nor $(\ominus x_{i},\ominus x_{j})$ appears from
the definition of effectful operations. But this contradicts the assumption
that the operation sequence has been normalized.

###  3.3 Synchronization of Effectful Operations

Assume that $P$ and $Q$ share data $D$ by locating its replicas $D_{P}$ and
$D_{Q}$ as their local data. And they independently and concurrently perform
local operations $\odot p$ and $\odot q$ respectively on their replicas.

Also assume that $P$ as the client has performed local operations $\odot
p_{1}$, $\odot p_{2}$, …, $\odot p_{m}$ on local data $D_{P}$ to get the
current data $D_{P}\odot p_{1}\odot p_{2}\odot\cdots\odot p_{m}$. Similarly
$Q$ has got $D_{Q}\odot q_{1}\odot q_{2}\odot\cdots\odot q_{n}$ by operations
$\odot q_{1}$, $\odot q_{2}$, …, $\odot q_{n}$.

Then, what should be done for synchronizing $P$’s replica and $Q$’s replica so
that they contain the same data?

$P$ as the server receives remote operations $\odot q_{1}$, $\odot q_{2}$, …,
$\odot q_{n}$ from $Q$ to make the local data reflect these remote operations.
A simple-minded way to do this might be applying remote operations to the
current data as

$D_{P}\odot p_{1}\odot p_{2}\odot\cdots\odot p_{m}\odot q_{1}\odot
q_{2}\odot\cdots\odot q_{n}.$

However, this sometimes fails because the effectful operation $\odot q_{j}$
($j=1,2,\cdots,n$) is not always valid in this expression. Recall that the
effectful $\oplus x$ can be applied to $D$ only if $x\not\in D$ and $\ominus
x$ can be applied to $D$ only if $x\in D$, but $\odot q_{j}$ may violate these
side conditions when it is applied to $P$’s replica, while $\odot q_{j}$ is
valid in $Q$’s replica.

Therefore we need to transform each remote operation $q_{j}$ into an effectful
$q_{j}^{\prime}$ that reflects the effect of $\odot q_{j}$ on the current
data.

#### Confluence of updates by synchronization

Given normalized operation sequences $\boldsymbol{ps}=\langle\odot p_{1},\odot
p_{2},\cdots,\odot p_{m}\rangle$ and $\boldsymbol{qs}=\langle\odot q_{1},\odot
q_{2},\cdots,\odot q_{n}\rangle$, $P$ as the server calculates
$\boldsymbol{qs}^{\prime}=\langle\odot q_{1}^{\prime},\odot
q_{2}^{\prime},\cdots,\odot q_{n}^{\prime}\rangle$ according to the following
rule: For each $j=1,2,\cdots,n$, if operation $q_{j}$ appears in
$\boldsymbol{ps}$, then set $q_{j}^{\prime}:=!$ else set
$q_{j}^{\prime}:=q_{j}$.

Using this $\boldsymbol{qs^{\prime}}$, the current data in $P$ is updated into

$D_{P}\odot p_{1}\odot p_{2}\odot\cdots\odot p_{m}\odot q_{1}^{\prime}\odot
q_{2}^{\prime}\odot\cdots\odot q_{n}^{\prime}.$ (1)

This expression does not violate the validity of effectful operations.

It is almost the same in $Q$. We can apply the same algorithm by exchanging
$\boldsymbol{ps}$ and $\boldsymbol{qs}$ and calculating
$\boldsymbol{ps^{\prime}}$. The current data in $Q$ is now updated into

$D_{Q}\odot q_{1}\odot q_{2}\odot\cdots\odot q_{n}\odot p_{1}^{\prime}\odot
p_{2}^{\prime}\odot\cdots\odot p_{m}^{\prime}.$ (2)

Apart from procedural operations, we can do another transformation in $P$ as
if its local data were not yet updated by $\boldsymbol{ps}$. The above
algorithm for $P$ can be rewritten for obtaining $\boldsymbol{ps^{\prime}}$
as: For each $j=1,2,\cdots,n$, if operation $q_{j}$ appears at some position,
say $k$ in $\boldsymbol{ps}$, then set $p_{k}^{\prime}:=!$ else set
$p_{k}^{\prime}:=p_{k}$.

As long as the final value is concerned, we have

$D_{P}\odot p_{1}^{\prime}\odot p_{2}^{\prime}\odot\cdots\odot
p_{m}^{\prime}\odot q_{1}\odot q_{2}\odot\cdots\odot q_{n}.$ (3)

by first applying operations $\boldsymbol{ps^{\prime}}$ and then applying
operations $\boldsymbol{qs}$.

From the commutative property of the effectful operations, and the fact that
the operation sequences $\boldsymbol{ps}$ and $\boldsymbol{qs}$ have been
normalized, we conclude that

  * •

The data value (3) is equivalent to (1). This is because that by exchanging
the role of $q_{j}^{\prime}$ in (1) and $p_{k}^{\prime}$ (3), we can get the
same data value.

  * •

The data value (3) is equivalent to (2) provided $D_{P}=D_{Q}=D$. This is
because that by moving $q_{j}$ in (3) to the left before $p_{i}^{\prime}$ we
have (2).

Hence, the replicas after independent synchronization by $P$ and $Q$ have the
same data value. That is, our transformation assures the confluence property
of the effectful set operations (Fig.1).

Figure 1: Confluence of Updates by Synchronization

Recall the small example in Section 2: $P$ and $Q$ start with
$D_{P}=D_{Q}=\\{1,2\\}$, and $P$ does $\cup\\{3\\}$ and then
$\setminus\\{3\\}$, and $Q$ does $\setminus\\{2\\}$ and then $\cup\\{3\\}$. We
see that operations $\cup\\{x\\}$ and $\setminus\\{x\\}$ here are in fact
effectful. So, $P$ performs operations $\boldsymbol{ps}=\langle\oplus
3,\ominus 3\rangle$ to have $D_{P}^{\prime}=\\{1,2\\}\oplus 3\ominus
3=\\{1,2\\}$, and $Q$ performs concurrentry $\boldsymbol{qs}=\langle\ominus
2,\oplus 3\rangle$ to have $D_{Q}^{\prime}=\\{1,2\\}\ominus 2\oplus
3=\\{1,3\\}$. As our first step to do is to normalize the operation sequences:
$\boldsymbol{ps}$ becomes $\langle!,!\rangle$ and $\boldsymbol{qs}$ remains as
it is. The above synchronization procedure derives
$\boldsymbol{qs^{\prime}}=\boldsymbol{qs}$ since there is no elements in
$\boldsymbol{ps}$ that is equal to $q_{j}$. Hence, $P$’s local data becomes
$D_{P}^{\prime}\ominus 2\oplus 3=\\{1,2\\}\ominus 2\oplus 3=\\{1,3\\}$. $Q$
produces $\boldsymbol{ps^{\prime}}=\langle!,!\rangle$ from $\boldsymbol{ps}$,
and gives local data $D_{Q}^{\prime}~{}!~{}!=\\{1,3\\}~{}!~{}!=\\{1,3\\}$.
Thus our synchronization gives a confulence $\\{1,3\\}$ as expected.

#### A Digression

Given lists of integers $xs=[x_{1},x_{2},...,x_{m}]$ and
$ys=[y_{1},y_{2},...,y_{n}]$ each has no duplicate elements in itself, but
with possible duplicates between $xs$ and $ys$. Then, how can we calculate the
sum of different integers in concatenated list $xs+\\!+ys$? For example,
$xs=[3,1,4,5,9,2]$ and $ys=[8,2,7,6,1]$ have no duplicates in themselves, but
$1$ and $2$ appear in $xs+\\!+ys$.

We may write code222 Haskellers may solve this quiz by $sum\cdot nub$.
Haskell’s standard library provides function $nub$ for removing duplicates in
a list. But this does not help us here to understand our synchronization. :

  * •

Compute first $ys^{\prime}=[y_{1}^{\prime},y_{2}^{\prime},...y_{n}^{\prime}]$
by replacing $y_{j}$ with $0$ if it appears in $xs$ or keeping it in
$ys^{\prime}$ for $j=1,2,\cdots$.

  * •

And then compute $sum(xs+\\!+ys^{\prime})$.

For the example above, $sum([3,1,4,5,9,2]+\\!+[8,0,7,6,0])$ gives the answer.
Note that by computing $xs^{\prime}$ from $xs$ and $ys$,
$sum([3,0,4,5,9,0]+\\!+[8,2,7,6,1])$ gives the same result.

This algorithm helps us to understand our procedure for our conflict-free
synchronization of set operations.

###  3.4 Eventual Consistency over Distributed Peers

Note that update synchronization in each peer does not necessarily processed
at the same time, rather each peer does it when convenient. We can see that
independent update synchronization eventually arrives at the same data after
no more local operations are performed in both under the conditions:

  * •

$D_{P}$ and $D_{Q}$ have been synchronized at least once, and

  * •

All the local operations $\boldsymbol{ps}$ in $P$ and $\boldsymbol{qs}$ in $Q$
performed since the last synchronization are sent to and received from each
other with the order kept and no element lost.

The above observation comes from the fact that our procedure for
synchronization to compute

$D_{P}\odot p_{1}\odot p_{2}\odot\cdots\odot p_{m}\odot q_{1}^{\prime}\odot
q_{2}^{\prime}\odot\cdots\odot q_{n}^{\prime}.$

from $\boldsymbol{ps}$ and $\boldsymbol{qs}$ can be divided into segments in
any ways such as

$D_{P}\odot p_{1}\odot q_{1}^{\prime}\odot p_{2}\odot\cdots\odot p_{m}\odot
q_{2}^{\prime}\odot\cdots\odot q_{n}^{\prime}.$

#### Managament of Local and Remote Operations

To synchronize the local data, or replicas of independent peers, we have to
know the shared data which are synchronized last time. These are the roots to
which local operations performed and then followed by remote operationsfor
synchronization.

Since $P$ and $Q$ concurrently run, they do not always perform updates at the
same time. So, they need to keep operations since the last synchronization
until the next. Then, when and how can we shorten the operation sequence?

The revision number $\\#D$ of the local data $D$ helps us to recognize the
state of synchronization. It is incremented every time a local operation
$p_{i}$ is performed including transformed remote operations $q_{j}^{\prime}$.
By maintaining the pair of local and revision numbers
$\langle\\#D_{P},\\#D_{Q}\rangle$ of $P$ and sending this with operations to
the partner $Q$, we can recognize which part of local operations are no more
needed (Fig.2)

Figure 2: Revision Numbers with Local and Remote Operations

#### Synchronization of Distributed Peers

So far, we have seen solely how synchronization works between $P$ and $Q$.

If $P$ has another connection to peer $R$, $P$ needs to synchronize $P$’s
local data and $R$’s local data as $P$ has done with $Q$.

Consider $P$ begins to synchronize its current local data just after the
synchronization with $Q$. The synchronization with $Q$ began with revision
numbers $\langle\\#D_{P},\\#D_{Q}\rangle$ and local data
$D_{P}\odot\boldsymbol{ps}$ and produced the local data
$D_{P}\odot\boldsymbol{ps}\odot\boldsymbol{qs^{\prime}}$, where
$\odot\boldsymbol{ps}$ represents applying operations of $\boldsymbol{ps}$.

The last synchronized data of $P$ with $R$ is not necessarily the same as with
$Q$. And operation sequence $\boldsymbol{qs^{\prime}}$ performed in the
synchronization with $Q$ has been sent to $R$ as the propagation of $Q$’s
updates to other peers.

Let $D_{P}^{\prime}$ and $D_{R}$ has been synchronized, and $\boldsymbol{ps*}$
is the operations performed in $P$ satisfying
$D_{P}^{\prime}\odot\boldsymbol{ps*}=D_{P}\odot\boldsymbol{ps}\odot\boldsymbol{qs^{\prime}}$.

Then, the synchronization process starts from $D_{P}^{\prime}$ and local
operations $\boldsymbol{ps*}$ already performed on $D_{P}^{\prime}$ and remote
operations $\boldsymbol{rs}$ sent from $R$. This proceeds the same as $P$ did
for $Q$ with $D_{P}$, $\boldsymbol{ps}$ and $\boldsymbol{qs}$. This time, $P$
produces $D_{P}^{\prime}\odot\boldsymbol{ps*}\odot\boldsymbol{rs^{\prime}}$
with new operations $\boldsymbol{rs^{\prime}}$ from $\boldsymbol{rs}$ as shown
in Fig.3. The operations $\boldsymbol{rs^{\prime}}$ are also propagated to
other peers including $Q$.

Figure 3: Synchronization of Distributed Peers

Thus, we conclude that our synchronization scheme works over distributed
peers, and this leads to the eventual consistency of the whole system.

##  4 Remarks

We can enjoy Conflict-free Collaborative Set Sharing (CCSS) simply by

  * •

When inserting data, first check whether it is not there yet, and

  * •

When deleting data, first check whether it really is there already.

When we use these operations for updates on the local data, failure of the
check tells us that the operation is invalid and should not be done, or rather
it tells us that it is not necessary for our intended updates.

It is very simple to do whatever data with ubiquitous set semantics. As a
matter of course, the oft-used SQL table is the case.

We can easily extend our CCSS to place transformations at the gateway of the
peer for sending and receiving operations for controlling shared data. Data
sharing with the Dejima in BISCUITS Project is an example [8].

Also we can extend our CCSS to include mechanisms for choosing one from
grouped data according to preferences, e.g., when or who inserts the data. We
may call such a strategy Semantic Resolution. For example, the LWW Set (Last-
Write-Win) CRDT can be realized by attaching the logical time stamp as
metadata to the data value with the key for grouping data. A process is
provided for choosing one from candidates inserted by $\oplus(v,k,t)$,
$\oplus(v^{\prime},k,t^{\prime})$, $\cdots$. We can choose $(v,k,t)$ if
$t>t^{\prime}$ by performing local operation
$\ominus(v^{\prime},k,t^{\prime})$ for LWW.

Implementation of CCSS peers would be straightforward and an exercise of
standard network programming.

## References

  * [1] Y. Asano, Z. Hu, Y. Ishihara, M. Onizuka, M. Takeichi, and M. Yoshikawa.  Data integration models and architectures for service alliances.  In Proceedings of the 4th Workshop on Software Foundations for Data Interoperability (SFDI2020), CCIS1281, pages 152–164. Springer, 2020.
  * [2] A. Bohannon, J. N. Foster, B. C. Pierce, A. Pilkiewicz, and A. Schmitt.  Boomerang: Resourceful lenses for string data.  In POPL, pages 407–419, 2008.
  * [3] C. Ellis and S. Gibbs.  Concurrency control in groupware systems.  volume 18 of ACM SIGMOD Record, pages 399–407. Association for Computing Machinery, 1989.
  * [4] J. N. Foster, M. B. Greenwald, J. T. Moore, B. C. Pierce, and A. Schmitt.  Combinators for bidirectional tree transformations: A linguistic approach to the view-update problem.  ACM Transactions on Programming Languages and Systems, 29(3):17, 2007.
  * [5] S. Hidaka, Z. Hu, K. Inaba, H. Kato, K. Matsuda, and K. Nakano.  Bidirectionalizing graph transformations.  In ICFP, pages 205–216, 2010.
  * [6] Z. Hu, S.-C. Mu, and M. Takeichi.  A programmable editor for developing structured documents based on bidirectional transformations.  Higher-Order and Symbolic Computation, 21(1-2):89–118, 2008.
  * [7] Z. Hu, A. Schürr, P. Stevens, and J. F. Terwilliger.  Dagstuhl seminar on bidirectional transformations (BX).  SIGMOD Record, 40(1):35–39, 2011.
  * [8] Y. Ishihara, H. Kato, K. Nakano, M. Onizuka, and Y. Sasaki.  Toward BX-based architecture for controlling and sharing distributed data.  In 2019 IEEE International Conference on Big Data and Smart Computing (BigComp), pages 1–5, 2019.
  * [9] Z. Ives, N. Khandelwal, A. Kapur, and M. Cakir.  ORCHESTRA: Rapid, collaborative sharing of dynamic data.  In CIDR, pages 107–118, 2005.
  * [10] G. Karvounarakis, T. J. Green, Z. G. Ives, and V. l Tannen.  Collaborative data sharing via update exchange and provenance.  ACM Transactions on Database Systems, 38(3):19:1–19:42, 2013.
  * [11] N. Preguiça.  Conflict-free replicated data types: An overview.  June 2018.
  * [12] M. Shapiro, N. Preguiça, C. Baquero, and M. Zawirski.  Conflict-free replicated data types.  In 13th International Conference on Stabilization, Safety, and Security of Distributed Systems, SSS 2011, pages 386–400. Springer LNCS volume 6976, Oct. 2011.
  * [13] C. Sun and C. Ellis.  Operational transformation in real-time group editors: Issues, algorithms, and achievements.  Proc. 1998 ACM Conference on Computer Supported Cooperative Work, pages 59–68. ACM Press New York, 1998.
  * [14] M. Takeichi.  Configuring bidirectional programs with functions.  In Draft Proceedings of the 21st International Symposium on Implementation and Application of Functional Languages, pages 224–239, 2009\.
  * [15] M. Takeichi.  BCDS Agent: An architecture for bidirectional collaborative data sharing.  In Computer Software, Japan Society for Software Science and Technology, Vol.38, No.3., pages 41–57, 2021.  Also available at https://www.jstage.jst.go.jp/article/jssst/38/3/38_3_41/_pdf/-char/ja.


# Disorder-dominated quantum criticality in moiré bilayers

Yuting Tan  Department of Physics and National High Magnetic Field Laboratory,
Florida State University, Tallahassee, Florida 32306, USA  Pak Ki Henry Tsang
V. Dobrosavljević  Department of Physics and National High Magnetic Field
Laboratory, Florida State University, Tallahassee, Florida 32306, USA

###### Abstract

Moiré bilayer materials have recently attracted much attention following the
discovery of various correlated insulating states at specific band fillings.
Here we discuss the metal-insulator transitions (MITs) that have been observed
in the same devices, but at fillings far from the strongly correlated regime
dominated by Mott-like physics, displaying many similarities to other examples
of disorder-dominated MITs. We propose a minimal theoretical model describing
the interplay of interactions and disorder, which able to capture most
experimental trends observed on several devices.

Introduction. The field of the metal-insulator transitions Mott (1990); Imada
et al. (1998), which still retains an aura of mystery and mystique
Dobrosavljević et al. (2012), is living a veritable revolution. The principal
obstacle, from the experimental perspective, is the challenge to carefully
tune to the transition point, while avoiding the effects of spurious charge,
spin, or orbital orders, which can mask the genuine mechanisms associated with
the MIT Dobrosavljević et al. (2012).

This difficult quest has suddenly shifted in high gear over the last few
years. An extraordinary flurry of activity was triggered by the recent
discovery of moiré bilayer materials of various kinds, which allows
unprecedented control over the physical properties of the electron systems at
hand. Narrow bands have been engineered Cao et al. (2018a), which can be
carefully tuned both in terms of the bandwidth and the band filling, allowing
precise and systematic studies of several regimes of interest around various
insulating states. A number of correlated insulators have indeed been
discovered Cao et al. (2018b) at partial band fillings, signaling the
dominance of electron-electron interactions in the narrow band limit. While
the intricate interplay of electron correlations and band topology Choi et al.
(2021) remains a fascinating subject of ongoing debate for moiré graphene
bilayers, a somewhat simpler situation is found in moiré TMD bilayers. Here,
genuine Mott-Hubbard physics was theoretically predicted and observed Tang et
al. (2020) close to half filling ($f=1$, one electron per moiré cell).

A remarkable recent paper Li et al. (2021) documented such an approach to the
Mott point, by electric field control of the bandwidth at half filling. The
reported transport behavior, as well as thermodynamic response, displayed all
the characteristic features previously established in other Mott systems, such
as the "spin-liquid" molecular materials Dressel and Tomic (2020); Pustogow et
al. (2018). The same study, on the other hand, demonstrated very different
behavior in a regime far away from half filling, where strong correlation
effects should not play a significant role. Here, the magnetic field response
here indeed proved to be remarkably mild, suggesting the lack of spin
localization, which is the hallmark of Mott physics. Nevertheless, a MIT was
clearly observed upon bandwidth tuning at integer band filling $f=2$ (two
electrons per moiré cell), which so far has not been a subject of much
scrutiny. A closer look at the experimental data reveals several interesting
signatures, which clearly distinguish this regime from the behavior around the
Mott point.

Figure 1: Transport behavior across the MIT at integer band filling. All the
qualitative features found in experiments (upper panel) are captured by our
CPA+DMFT theory (bottom panel). a, Experimental $R(T)$ curves provided by
experimental groupnew , with $0.399\text{V/nm}<E<0.544\text{V/nm}$; d,
theoretical curves for $0<\epsilon_{AB}/t<1.2$. The insets b, e, show the
extrapolated $T=0$ conductivity, the boundary of linear resistivity region
$T^{*}$, and the activation energy $\Delta$, as function of electric field $E$
(experiments) or band separation $\epsilon_{AB}$ (theory). c, f, The slope $A$
describing low-$T$ resistivity $R(T)\approx R_{0}+AT$, displays non-monotonic
behavior as a function of $R_{0}$. Same analyses are also performed on data in
Ref.(Li et al. (2021)), shown in SMsm .

The following features stand out (see Fig.1a): (i) On the metallic side, the
resistivity displays linear-$T$ behavior at low temperatures: $R(T)\approx
R_{0}+AT$, with $A>0$ further away from the transition. This result is in
dramatic contrast to what is found in the same device around the Mott point
($f=1$), where the Fermi Liquid $T^{2}$ law is very clearly seen Li et al.
(2021). Its absence here hints to the lack of strong correlation effects away
from half filling. (ii) As the transition is approached, the slope $A$
initially increases, reaches a maximum, and then decreases again towards the
transition. An (almost) "flat" curve, sometimes called the "separatrix"
Popović (2016) (or the "Mooij point" Ciuchi et al. (2018)) is seen before the
transition is reached. This behavior is similar to what is frequently observed
in disorder-driven MITs Popović (2016); Lee and Ramakrishnan (1985). (iii) A
characteristic temperature scale $T^{*}$ marks the extent of the leading
linear-$T$ regime, and is seen to decrease towards the transition. (iv) The
residual conductivity $\sigma_{0}=1/R_{0}$ also decreases steadily,
extrapolating to zero past the "Mooij point" - exactly as in many other
examples of disorder-driven MITs Dobrosavljević et al. (2012). (v) The
activation gap $\Delta$ displays a similar decrease on the insulating side,
interpolating to zero at precisely the same point where conduction vanishes,
suggesting a continuous transition.

In the rest of this paper, we present a robust physical picture that is able
to capture all the qualitative (and even some quantitative) trends seen in the
experiment. At filling $f=2$, the narrow moiré band is completely full, but
the corresponding band gap shrinks as the bands broaden, eventually leading to
band overlap and metallic behavior Li et al. (2021). When band overlap is
modest, one expects electron and hole pockets with very small Fermi surfaces
for charge carriers, which in this regime become vulnerable to even modest
amounts of disorder. At finite temperature, charge transport is also affected
by additional scattering from thermal excitations, which is further enhanced
in the dilute carrier limit. Thermal and impurity effects, however, cannot be
clearly decoupled in this regime of poor conduction, as generally found also
for many other disorder-driven metal-insulator transitions Di Sante et al.
(2017). This leads to a nontrivial interplay of interactions and disorder, and
the associated change of sign of $A=dR(T)/dT$, the "Temperature Coefficient of
Resistivity" (TCR) preceding the MIT, a widely observed phenomenon sometimes
called the "Mooij correlation" Ciuchi et al. (2018). All these features can be
captured in a self-consistent theory of interactions and disorder Di Sante et
al. (2017); Ciuchi et al. (2018), which can be viewed as the minimal model for
disorder-dominated MITs in (moderately) interacting electron systems. It
describes how certain interaction effects are generally enhanced in presence
of disorder, leading to strong disorder renormalization, which in some cases
also triggers polaron formation. This physical picture differs significantly
Dobrosavljević et al. (2012) from (non-interacting) Anderson localization,
illustrating the seminal ideas of Phil Anderson himself going back to 1970s
Anderson (1972). It also predicts the precise form of the scaling behavior for
the family of resistivity curves (see below), thus formulating a concrete
phenomenology that can be very useful in analyzing future generations of
experiments.

Figure 2: Disorder-averaged single-particle density of states per site
$\rho(\omega)$ for different band separation $\epsilon_{AB}$; here $\omega$ is
measured with respect to the Fermi energy. The bands split beyond critical
separation $\epsilon_{AB}>\epsilon_{AB}^{c}=0.854$, producing a continuous
metal-insulator transition, where all quantities display power-law behavior.

Model of interactions and disorder. Motivated by the experimental setup in
moiré TMD bilayers Li et al. (2021), we consider a two-band model of electrons
at integer band filling, in presence of moderate disorder, and where
interaction effects are represented by the coupling of carriers to a bosonic
field Di Sante et al. (2017). Here we do not specify the physical origin of
the bosonic excitations, which could be soft phonons specific to the bilayer
structure Wu et al. (2019), but could also represent the response of other
collective modes CrÃ©pel and Fu (2021) to single-particle displacements.
Guided by experiments, which clearly demonstrate the absence of Mott-like
physics at integer filling, we ignore the spin degree of freedom and thus any
significant role of the on-site Hubbard $U$. Our model is described by the
following Hamiltonian:

$\displaystyle\mathcal{H}=$ $\displaystyle-$ $\displaystyle t\sum_{\langle
i,j\rangle}c^{{\dagger}}_{i}c_{j}+\sum_{i\in
A}\epsilon_{A}c^{{\dagger}}_{i}c_{i}+\sum_{i\in
B}\epsilon_{B}c^{{\dagger}}_{i}c_{i}$ (1) $\displaystyle+$
$\displaystyle\sum_{i}(\xi_{i}-\mu)c^{{\dagger}}_{i}c_{i}+g\sum_{i}X_{i}(c^{{\dagger}}_{i}c_{i}-n)+H_{b},$

where $c_{i}^{\dagger}\left(c_{i}\right)$ are the creation (annihilation)
operators for spinless electrons hopping between sites $i$ and $j$ of a
triangular lattice, with hopping integrals $t$. The two-band model is obtained
by periodically modulating the site energies within a unit cell consisting of
three sites, with one site in the unit cell (sublattice B) having site energy
$\epsilon_{B}$, while the other two sites (corresponding to the two degenerate
sublattices) have energies $\epsilon_{A}$. We define the "band splitting"
energy $\epsilon_{AB}=\epsilon_{A}-\epsilon_{B}$. Extrinsic disorder is
characterized by a random distribution of site energies $\xi_{i}$, with a
uniform distribution of the form
$P_{o}\left(\xi\right)=\frac{1}{W}\theta\left(\left(\frac{W}{2}\right)^{2}-\xi^{2}\right)$,
where $W$ measures the disorder strength. In addition, the electrons interact
locally with dispersionless bosons of frequency $\omega_{o}=\sqrt{K/M}$,
described by $H_{b}=\sum_{i}KX_{i}^{2}/2+P_{i}^{2}/2M$. We use $t=1$ as our
unit of energy. The strength of electron-boson coupling is measured by the
dimensionless coupling constant $\lambda=\frac{g^{2}}{2KD}$, where $2D=9t$ is
the bare bandwidth of our triangular lattice. In addition, the lattice filling
$n=\frac{1}{N}\left\langle\sum_{i}c_{i}^{\dagger}c_{i}\right\rangle$ is kept
constant at $n=1/3$, giving a band insulator (lowest band fully occupied) in
the split-band limit.

To solve this model we use a self-consistent theory of interactions and
disorder Ciuchi et al. (2018), which combines dynamical mean field theory
(DMFT) for interaction effects together with the coherent potential
approximation (CPA) for electrons in random lattices. Similarly as for the
popular SYK model Chowdhury et al. (2021), the theory becomes an exact
solution both in the limit of infinite range hopping or for large
coordination. Details of the calculations can be found in the Supplementary
Materials, where we also show how to use the Kubo formula to calculate the
corresponding transport properties within this approach.

Because we attribute the linear-$T$ behavior of the resistivity to incoherent
electron-boson scattering above an appropriate Debye scale Wu et al. (2019),
we can ignore the dynamics of the bosons, which in turn enables a fully self-
consistent solution of the problem in the semi-classical (thermal) regime. For
the same reason, the actual form of the boson dispersion is irrelevant to our
purposes and we ignore it. As a matter of fact, a close look at the
experimental data (Fig.1a) reveals that the resisitivity deviates from linear
behavior at the very lowest temperatures($T<1K$), which can be viewed as the
lower boundary for the validity of the semi-classical treatment. Describing
the interplay of thermal bosonic excitations with disorder within a poor metal
is the central goal of our theory. This mechanism should not be confused with
"Strange Metal" behavior Chowdhury et al. (2021) found in many Mott materials
and other examples strongly correlated matter. The latter are not likely to be
of relevance in the regime around integer band filling we consider, where the
strong correlation effects are neither expected nor experimentally detected Li
et al. (2021).

Figure 3: a, Scaling analysis for the experimental resistance curves
corresponding to Fig. 1a, for $0.405\text{V/nm}<E<0.453\text{V/nm}$, reveals
near-perfect agreement with the theoretical scaling function (red line), with
no adjustable parameters. b, Critical resistance $R_{c}\sim T^{-x}$ on
experiments displays behavior consistent with the theoretical prediction for
exponent $x=1$ (see SMsm ). c, Crossover temperature $T_{0}(\delta)$ obtained
from the scaling collapse of experimental data (the superscripts M and I
designate respectively the metallic and insulating branch. The estimated
critical exponent $z\nu\approx 1\pm 0.1$ is consistent with the theoretical
value $z\nu=1$.

Results. In the following, we present a detailed solution of our model, which
due to its simplicity can be analytically solved in several limits, while the
corresponding numerical solution can be obtained with any desired accuracy. To
be specific, we select the following values of the model parameters $g=1$,
$K=1$ and $W=1$, corresponding to moderate disorder ($W/2D\approx 0.1$) and
moderate electron-boson coupling ($\lambda\approx 0.1$). The evolution of the
single-particle density of states (DOS) $\rho(\omega)$ at $T=0$, as a function
of band splitting at $\epsilon_{AB}$ is shown in Fig.2. For $\epsilon_{AB}=0$,
it resembles the conventional density of states of the triangular lattice,
however with some rounding introduced by disorder. When $\epsilon_{AB}$
increases, the DOS at the Fermi energy starts to decrease, until a hard
insulating gap forms at $\epsilon_{AB}^{c}=0.854$, indicating the MIT. The
corresponding residual conductivity $\sigma_{0}$ (blue line in Fig.1e)
decreases linearly as the MIT is approached:
$\sigma_{0}=\sigma(T=0)=1/R(T=0)\sim\delta^{\mu}$, where
$\delta=(\epsilon_{AB}^{c}-\epsilon_{AB})/\epsilon_{AB}^{c}$ measures the
distance to the transition and the conductivity exponent is $\mu=1$. Our model
can be further solved at finite temperature, producing the entire family of
resistivity curves (Fig.1d), similar as in the experiments, which we now
analyze in detail.

As in the experiment, the theoretical curves exhibit linear-T behavior at low
temperature on the metallic side of the transition. The evolution of the slope
(TCR) with external field exactly matches the experimentally-observed trends,
as can be seen from (Fig. 1c and 1f). The slope $A$ (and $R_{0}$) initially
increases upon application of the electric field, because the number of
available carriers decreases as the size of the electron (hole) Fermi pockets
shrinks (see SM for details). At larger fields the trend reverses, recovering
the "Mooij correlation" behavior expected when disorder becomes dominant. This
phenomenon, which implies the breakdown of Matthiessen’s rule, generally
precedes the MIT itself Ciuchi et al. (2018), and is caused by the buildup of
correlations between the increasingly inhomogeneous electronic density and the
bosons responsible for thermal scattering.

An additional energy scale characterizing the metallic regime is $T^{*}$, the
boundary of the linear-T region, which decreases linearly towards the
transition as $T^{*}\sim\delta$. Similar behavior is also found for the the
activation gap $\Delta\sim\delta$, which describes the approach to the
transition from the insulating side. Remarkably, all the qualitative trends
and the values of the critical exponent $\mu=1$ predicted by our model
precisely match the experimental findings.

Quantum Critical Scaling. A direct analysis of the resistivity curves (Fig. 1;
see insets), both experimental and theoretical, clearly indicates a continuous
(i.e. quantum critical Sachdev (2011)) character of the MIT. On very general
grounds, the presence of criticality implies scaling behavior of various
observables, and in the specific case of the MITs, we expect Dobrosavljević et
al. (2012) the resistivity $R(T,\delta)$ to take the form

$R(T,\delta)=R_{c}(T)f(T/T_{o}(\delta)).$ (2)

Here $R_{c}(T)=R(T,\delta=0)\sim T^{-x}$ is the critical resistivity curve,
$f(y)$ is a universal scaling function, and $T_{o}\sim\delta^{\nu z}$ is the
crossover temperature associated with the approach to quantum criticality.
Guided by these expectations, we next perform the appropriate scaling analysis
Dobrosavljević et al. (2012) to both the experimental (range:
$0.405\text{V/nm}<E<0.453\text{V/nm}$; dots in Fig.3a) and the theoretical
resistance curves (range: $0.802<\epsilon_{AB}<0.905$)).

We first identify the value of the critical field in the experiments, at which
a simple power-law dependence of $R_{c}(T)$ is observed (Fig.3b), and we find
the exponent $x\approx 1$, consistent with our theory (see SM for details).
Remarkably, this power-law behavior occurs precisely at the same critical
field where $\sigma_{0}$, T∗, and $\Delta$ all extrapolate to zero (see Fig.
1), further confirming the quantum-critical character of our transition, both
in experiment and in theory. We then normalize $R(T,\delta)$ by the critical
resistance $R_{c}(T)$, and after rescaling $T$ by a field-dependent factor
$T_{0}(\delta)$, the curves collapse onto two branches, as shown in Fig.3a
(dots). We emphasize that in implementing such an "unbiased" scaling procedure
Dobrosavljević et al. (2012), we do not assume any specific form for the
field-dependence of the crossover temperature $T_{0}(\delta)$. Instead, we
directly verify that it indeed vanishes at the critical point, by plotting it
as a function of $\delta$ on a log-log scale, as shown in Fig. 3c, giving the
experimental estimate for the critical exponent $z\nu=0.9\pm 0.1$ (here the
error estimate reflects the uncertainty associated with the scaling collapse
procedure for the experimental data).

The scaling of the theoretical resistance curves is performed following an
identical procedure, with $T_{0}(\delta)$ shown in Fig.4 (red dashed line),
giving the theoretical exponent $z\nu=1$. This analysis (see SM for details)
also provides us with the precise quantitative form of the universal scaling
function $f(y)$ for our model (red line in Fig. 3a), which we can directly
compare to the experimental findings without any adjustable parameters.
Although we have used a relatively broad range of fields and temperatures in
analyzing the experimental data, we find a remarkable quality of scaling.
Almost-perfect agreement with the theoretical prediction is found, not only
concerning the estimated values for all critical exponents, but also for the
precise form of the scaling function $f(y)$. We also observe that, both in
experiment and in theory, the metallic and insulating branches are quite
asymmetric with respect to each other. This is precisely what one generally
expects for disorder-driven transitions, where the resistivity displays only
modest temperature dependence on the metallic side, while it is generally
exponentially strong in any insulator. We should mention that such behavior is
in dramatic contrast to what is seen for the Mott transition ($f=1$ curves
experimentally obtained Li et al. (2021) for the same device), which reveals
pronounced "mirror symmetry" of the scaling function Dobrosavljević et al.
(1997), consistent with both microscopic theory H. Terletska et al. (2011) and
careful experiments Furukawa et al. (2015) on other Mott systems.

Figure 4: Theory phase diagram for disorder-driven MIT. Blue dots $T^{*}$
(dashed line obtained by fitting), serving as the boundary of the linear-T
resistivity region, extrapolate linearly to $\epsilon_{AB}^{c}$. The so-called
Mooij region $0.760<\epsilon_{AB}<0.782$ (yellow), where the slope $A\sim
R_{0}$, is sitting around the Mooij point $\epsilon_{AB}^{M}=0.772$. Red dots
are the theory scaling temperatures $T_{o}$, indicating the critical region
$0.802<\epsilon_{AB}<0.905$. The critical exponent $z\nu=1$. Scaling argument
shows that the critical region can not go pass the Mooij point. The respective
color codes of $\text{Log}(R/R_{c})$ are given to the right, which displays a
fan-shape like pattern.

We should emphasize that, on general grounds, a universal scaling behavior
should be expected Goldenfeld (1992) only in the immediate vicinity of the
critical point, and not necessarily over an extended range across the phase
diagram. A natural question, therefore, is how large is the critical region in
the case we consider here, especially concerning the non-monotonic behavior
and the vanishing of the TCR parameter $A$ in the Mooij correlation regime
Ciuchi et al. (2018) (Fig. 1). In the following, we use general scaling
arguments to demonstrate that strictly speaking the critical region cannot
intercept with the Mooij regime, as shown in the theoretical phase diagram in
Fig.4. To start with, the critical resistance has a simple power-law
dependence on temperature: $R_{c}\sim T^{-1}$. It is obvious that, on the
metallic side, the slope $A=\partial R/\partial T\rightarrow-\infty$ as we
approach the transition. On the other hand, the condition of having finite
resistivity $R_{0}$ in the $T\rightarrow 0$ limit (within the metallic phase)
requires that, for $y=T/T_{0}(\delta)\ll 1$, the scaling function must assume
the form $f(y)=y^{\alpha}(1+ay^{\beta}+\cdots)$. It follows that
$R(T,\delta)\sim T_{0}^{-\alpha}T^{\alpha-1}(1+a(T/T_{0})^{\beta}+...)$, and
$a$ is a universal constant. Since $R(T,\delta)\approx R_{0}+AT$ on the
metallic side, we conclude that $\alpha=\beta=1$, and to leading order $A\sim
T_{0}^{-2}\sim\delta^{-2}$. This means that $|A|$ decreases monotonically away
from the transition, but it cannot change sign within the critical region,
where leading power-law scaling is obeyed. Indeed, since $T_{0}\sim\delta^{\nu
z}\sim\xi^{-z}$ (where $\xi$ is the relevant correlation length associated
with the critical point), $|A|$ becoming small indicates that the
corresponding correlation length also becomes short, marking the boundary of
the critical region. All these features are very clearly seen in examining the
details of our theoretical solution, as elaborated in SM. On the other hand,
the relevant violations of scaling, as introduced by the change of sign of
$A$, prove to remain parametrically small in a very broad range of parameters,
much beyond the Mooij point. In this interval approximate scaling behavior is
observed, with the same scaling function describing the strict critical
regime. Exactly the same situation is found in experiments, where the
theoretical scaling function collapses all the experimental data within a
surprisingly broad range of parameters, displaying quantitative agreement with
theory without any adjustable parameters.

Conclusions. We presented and solved a minimal theoretical model for disorder-
driven transitions, as motivated by the experiments on moiré TMD bilayer
materials at integer band filling. It paints a physical picture of bosonic
modes which strongly renormalize the potential energy landscape seen by the
mobile electrons at the verge of band splitting - driving a continuous metal-
insulator transition. We showed that this transition displays all the features
generally expected for a disorder-driven MIT, revealing critical behavior in
striking agreement between theory and experiments. Ours is the first theory
for disorder-driven MITs that is able to fully explain all the universal
aspects of a real experimental system, which represents a significant step
forward for this age-old problem residing at the heart of solid state physics.

##  I acknowledgments

We thank Jie Shan, Kin Fai Mak, and Tingxin Li for very useful discussions and
for kindly sharing with us some unpublished experimental data. We are also
grateful to Simone Fratini and Sergio Ciuchi for useful comments. This work
was supported by the NSF Grant No. 1822258, and the National High Magnetic
Field Laboratory through the NSF Cooperative Agreement No. 1157490 and the
State of Florida.

## References

  * Mott (1990) N. F. Mott, _Metal-Insulator Transition_ (Taylor and Francis, London, 1990).
  * Imada et al. (1998) M. Imada, A. Fujimori, and Y. Tokura, Rev. Mod. Phys. 70, 1039 (1998).
  * Dobrosavljević et al. (2012) V. Dobrosavljević, N. Trivedi, and J. M. Valles Jr, _Conductor Insulator Quantum Phase Transitions_ (Oxford University Press, 2012).
  * Cao et al. (2018a) Y. Cao, V. Fatemi, S. Fang, K. Watanabe, T. Taniguchi, E. Kaxiras, and P. Jarillo-Herrero, Nature 556, 43 (2018a).
  * Cao et al. (2018b) Y. Cao, V. Fatemi, A. Demir, S. Fang, S. L. Tomarken, J. Y. Luo, J. D. Sanchez-Yamagishi, K. Watanabe, T. Taniguchi, E. Kaxiras, et al., Nature 556, 80 (2018b).
  * Choi et al. (2021) Y. Choi, H. Kim, Y. Peng, A. Thomson, C. Lewandowski, R. Polski, Y. Zhang, H. S. Arora, K. Watanabe, T. Taniguchi, et al., Nature (2021).
  * Tang et al. (2020) Y. Tang, L. Li, T. Li, Y. Xu, S. Liu, K. Barmak, K. Watanabe, T. Taniguchi, A. H. MacDonald, J. Shan, et al., Nature 579, 353 (2020).
  * Li et al. (2021) T. Li, S. Jiang, L. Li, Y. Zhang, K. Kang, J. Zhu, K. Watanabe, T. Taniguchi, D. Chowdhury, L. Fu, et al., Nature 597 7876, 350 (2021).
  * Dressel and Tomic (2020) M. Dressel and S. Tomic, Advances in Physics 69, 1 (2020).
  * Pustogow et al. (2018) A. Pustogow, M. Bories, A. Löhle, R. Rösslhuber, E. Zhukova, B. Gorshunov, S. Tomić, J. A. Schlueter, R. Hübner, T. Hiramatsu, et al., Nat. Mater. 17, 773 (2018).
  * (11) _Data of device 2 of moiré tmd materials at $f=2$, provided by shan & mak’s group in cornell university_.
  * (12) _Supplementary materials_.
  * Popović (2016) D. Popović, Chap. 5 in "Strong Correlation Phenomena Around 2D Conductor-Insulator Transitions", edited by S. V. Kravchenko (Pan Stanford Publishing) (2016).
  * Ciuchi et al. (2018) S. Ciuchi, D. D. Sante, V. Dobrosavljević, and S. Fratini, npj Quantum Materials 3, 1 (2018).
  * Lee and Ramakrishnan (1985) P. A. Lee and T. V. Ramakrishnan, Rev. Mod. Phys. 57, 287 (1985).
  * Di Sante et al. (2017) D. Di Sante, S. Fratini, V. Dobrosavljević, and S. Ciuchi, Phys. Rev. Lett. 118, 036602 (2017).
  * Anderson (1972) P. W. Anderson, Nature Physical Science 235, 163 (1972).
  * Wu et al. (2019) F. Wu, E. Hwang, and S. Das Sarma, Phys. Rev. B 99, 165112 (2019).
  * CrÃ©pel and Fu (2021) V. CrÃ©pel and L. Fu, _New mechanism and exact theory of superconductivity from strong repulsive interaction_ (2021), eprint 2012.08528.
  * Chowdhury et al. (2021) D. Chowdhury, A. Georges, O. Parcollet, and S. Sachdev, _Sachdev-Ye-Kitaev models and beyond: A window into non-Fermi liquids_ (2021), eprint 2109.05037.
  * Sachdev (2011) S. Sachdev, _Quantum Phase Transitions_ (Cambridge university press, 2011).
  * Dobrosavljević et al. (1997) V. Dobrosavljević, E. Abrahams, E. Miranda, and S. Chakravarty, Phys. Rev. Lett. 79, 455 (1997).
  * H. Terletska et al. (2011) H. Terletska, J. Vucicević, D. Tanasković, and V. Dobrosavljević, Phys. Rev. Lett 84, 125120 (2011).
  * Furukawa et al. (2015) T. Furukawa, K. Miyagawa, H. Taniguchi, R. Kato, and K. Kanoda, Nat. Phys. 11, 221 (2015).
  * Goldenfeld (1992) N. Goldenfeld, _Lectures on Phase Transitions and the Renormalization Group_ (Addison-Wesley, New York, 1992).