# Distributed Training for Deep Learning Models On An Edge Computing Network
Using Shielded Reinforcement Learning

Tanmoy Sen and Haiying Shen  Department of Computer Science, University of
Virginia
Email: {ts5xm<EMAIL_ADDRESS>
###### Abstract

With the emergence of edge devices along with their local computation
advantage over the cloud, distributed deep learning (DL) training on edge
nodes becomes promising. In such a method, the cluster head of a cluster of
edge nodes schedules all the DL training jobs from the cluster nodes. Using
such a centralized scheduling method, the cluster head knows all the loads of
the cluster nodes, which can avoid overloading the cluster nodes, but the head
itself may become overloaded. To handle this problem, we first propose a
multi-agent RL (MARL) system that enables each edge node to schedule its own
jobs using RL. However, without the coordination between the nodes, action
collision may occur, in which multiple nodes may schedule tasks to the same
node and make it overloaded. To avoid these problems, we propose a system
called Shielded ReinfOrcement learning (RL) based DL training on Edges
(SROLE). In SROLE, each edge node schedules its own jobs using multi-agent RL.
The shield deployed in a node checks action collisions and provides
alternative actions to avoid the collisions. As the central shield node for
the entire cluster may become a bottleneck, we further propose a decentralized
shielding method, in which different shields are responsible for different
regions in the cluster and they coordinate to avoid action collisions on the
region boundaries. Our container-based emulation experiments show that SROLE
reduces training time by up to 59% with 29% lower median resource utilization
and reduces the number of action collisions by up to 48% compared to multi-
agent RL and the centralized RL. Our real device experiments show that SROLE
still reduces the training time by up to 53% with 28% lower median resource
utilization than multi-agent RL and the centralized RL.

††publicationid: pubid: XXX-X-XXXX-XXXX-X/XX/$31.00 ©2022 IEEE

##  I Introduction

Edge devices are currently used for various applications in many areas
including transportation and healthcare [1, 2, 3, 4]. These applications often
deploy machine learning (ML) frameworks using data collected by the edge
devices’ sensors. ML models have transformed into more complex and larger Deep
Neural Networks (DNNs). These DNNs are memory and computationally expensive in
training due to their complexity and size. On the contrary, an edge device
usually does not have sufficient memory or computation resources to conduct
the entire DNN model training job. Thus, a DNN is usually trained (or updated)
in the cloud, then compressed and deployed on the edge nodes for inference.
Such cloud-based training can generate significant delays when the network is
intermittent (e.g., disaster, network congestion), and cannot provide data
privacy protection [5] for sensitive applications (e.g., medical records) as
the data needs to be transferred to the cloud. In this case, distributing the
job of training or updating a DNN model among only edge nodes becomes a
promising solution.

Recent works [6, 5, 7] for distributed training on edges handle either data
parallelism or model parallelism while involving the cloud at a certain stage.
Data parallelism methods [5, 7] deploy replicas of an entire neural network on
the edges, and these edges have their subsets of training data. Each edge
processes its training data subset and synchronizes model parameters in a
parameter server running on an initiator edge or the cloud. Model parallelism
methods [6] divide a neural network and distribute the shallow (earlier)
layers to edges and the deep layers to the cloud and let edges communicate
with cloud for model parameters transfer from the previous layer transfer to
the next layer. The data parallelism methods sometimes may not be feasible as
deploying a large DNN model on a single edge may not be feasible. In contrast,
the model parallelism methods suffer from the long delay of communication and
intermittent network between edges and cloud.

A concurrent data and model parallelism based deep learning (DL) system can
handle these problems. In such a system [8], clusters of edges are created
according to geographical locations, and each cluster trains a replica of the
DL model using model parallelism based on its locally collected data. Each
cluster has a cluster head that has relatively high capacity, and it assigns
the partitions of a DNN model (i.e., tasks) to the cluster edge nodes with a
goal of minimizing training time. Each edge within a cluster collects its own
data and sends the data to the first-layer node, which collects the sensed
data from all cluster edges as the training data of the model replica in the
cluster. The cluster head assigns tasks to the edges based on the resource
demands of the tasks and the available resources of the edges. Thus, the
cluster head needs to continuously observe the workload conditions of all the
edge nodes in its cluster. With this cluster-wide knowledge, the cluster head
can avoid overloading the edges in assigning the tasks. However, such a
centralized scheduling method imposes a significant workload on the cluster
head, which ultimately impacts the performance of the training. Recently, RL
[9, 10] has also been used for such scheduling in the recent times with
similar high load. To lessen this load, we first propose a multi-agent RL
method (MARL) that enables each edge node to schedule its own jobs among its
neighboring edge nodes (i.e., edge nodes in its transmission range) using RL.
In MARL, each edge device works as an independent agent and makes the
scheduling decision among its nearby edges, thus relieving the cluster head
from the extra burden. However, without the coordination between the edge
nodes, action collision may occur, in which multiple nodes may schedule tasks
to the same node and make it overloaded.

To avoid this problem, we propose Shielded ReinfOrcement learning based DL
Training on Edges (SROLE) on top of the MARL-based assignment approach. The
shielding approach [11] works as a separate monitor that suggests alternative
actions to avoid action collision by observing the states and actions that
will be taken by the agents. In SROLE, each edge node schedules its own jobs
using MARL, and the shield, which is deployed on the cluster head, checks the
action collisions among the schedules of the edges in its cluster. Edge nodes
report to the shield their action decisions, and it checks action collisions
and provides alternative actions to avoid the collisions. However, the
computational cost of a centralized shield grows dramatically with the number
of edges in a cluster, and it may become a bottleneck for the entire cluster.
Thus, we further propose a decentralized shielding method, in which different
shields are responsible for different regions in the cluster and they
coordinate to avoid action collisions on the region boundaries. Specifically,
a large cluster is divided into multiple sub-clusters according to the
geographical proximity, and a shield monitors the edges within each sub-
cluster and communicates with its neighboring shields for the edges at the
boundary of the sub-clusters to avoid action collisions, i.e., unsafe actions.
The computational cost of each shield in the decentralized method is lower
than that in the centralized shielding as the centralized shield’s workload is
distributed to a number of shields.

In summary, the contributions of this work are as follows:

  * $\bullet$

To avoid overloading a cluster head due to scheduling DL training jobs in its
cluster, we initially propose a multi-agent RL-based method (MARL) that
enables each edge node to use RL to schedule its own jobs. For a given DL
training job, an edge node makes scheduling decisions for DNN partitions among
its nearby edges depending on their resource availability to minimize training
time.

  * $\bullet$

To avoid action collisions in MARL, we use the shielding approach in each
cluster. The shield in a cluster collects the scheduling decisions of all edge
nodes in the cluster, checks the action collisions and provides alternative
actions to avoid the action collisions.

  * $\bullet$

To avoid overloading a shield in a cluster, we distribute the shielding
workload to multiple shields in a cluster and each shield is responsible for a
sub-cluster. The neighboring shields communicate with each other to avoid
action collisions from the edges on the boundaries of sub-clusters.

  * $\bullet$

We measured the performance of the SROLE system on container based emulation
on Amazon EC2 instances. Our evaluation shows that the SROLE system shows up
to 59% reduction in training time and up to 48% reduction in the number of
action collisions compared to the centralized RL and MARL approach. Our real
device experiments also show up to 53% reduction in training time and up to
46% reduction in the number of action collisions in comparison with the
centralized RL and MARL approach.

The rest of the paper is organized as follows. Section II presents the related
work. Section IV describes our SROLE system. Section V presents the
performance evaluation. Finally, Section VI concludes the paper with remarks
on our future work.

##  II Related Work

Researchers have been studying federated ML training and DNN partition
distribution across cloud/fog and edge devices [6, 7, 12, 13, 14, 15, 16, 17].
In federated learning [7], edge devices update a trained model on the cloud.
Individual edges download a replica of the model and update the models using
their own available datasets. Finally, the updated models from individual
edges are aggregated through averaging or using a control theorem on the cloud
to produce the final model. Many proposed ML inference approaches partition
the ML model distributed edge nodes [18, 19, 20]. The works in [18, 20] simply
consider each or multiple convolution layers as a partition, and the work [19]
vertically divides the convolutional layers in a convolutional neural network
(CNN). The work in [6] distributes DNN partition across cloud/fog and edge
devices to accelerate training or inference. The resource-constraint edge
devices run lighter (earlier) layers of the model and the cloud or fog run
heavier (later) layers of the model. Resilinet [21] achieves failure-resilient
inference in model-parallel ML at the edge. Data parallelism training methods
distribute training data among different edges for training and accumulate
training updates. Wang _et al._ [5] analyzed the convergence rate of replicas
for ML models such as Support Vector Machine (SVM) and K-means, and
accordingly proposed a control method that dynamically adjusts the frequency
of global update from each replica to the ML initiator in real time to
minimize the learning loss under a fixed computation resource budget for the
edges.

To efficiently run ML models on edge devices in terms of inference time,
energy and memory, researchers have introduced techniques for compressing the
neural networks (NNs) [22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34,
35]. For example, the works in [36, 37, 38] find compressed DNN models by
formulating optimization problems that meet resource (memory, energy)
constraints or minimize inference time while maximizing accuracy or reaching a
specified accuracy. Han _et al._ [39] proposed cumulative pruning of the
network connection, weight quantization, and compression through Huffman
coding to decrease the size and inference time of an NN model without
significant loss of accuracy. Ashok _et al._ [26] proposed a reinforcement
learning based policy that first removes layers from the DNN and later reduces
the size of the remaining layers by deleting links. Yao _et al._ [40] used a
pre-trained compressor-critic network to estimate the link weights and drop
out the low-weight links.

However, there are few works on scheduling the partitions of a DNN model in
model parallelism on the edge in an efficient manner. This paper addresses
this problem.

##  III Background

In the model parallelism, a layer is a DNN unit such as convolutional or
fully-connected layer [41]. In each model level, a model partition consists of
one or multiple disjoint layers, which can be executed in parallel. These
partitions are assigned to the edge nodes based on their available resources.
In this paper, we use concurrent data/model parallelism as an example to
explain our proposed methods though they also can be applied to model
parallelism. The problem we handle is how to schedule the different model
partitions (i.e., tasks) to different edge nodes to minimize the training
time. In concurrent data/model parallelism, as shown in Figure 1, each cluster
is formed by proximity-close edge nodes. Each cluster trains an entire DNN
model replica using the cluster’s collected dataset, and partitions the model
among the proximity-close cluster edges. The cluster head is responsible for
initiating the training, partitioning and distributing the layers of the model
to edge nodes, and synchronizing model parameters to generate the final
trained model. In order to conduct task scheduling, the cluster head needs to
continuously check the resource availability of all the edge nodes in its
cluster and also estimate the resource demands of each partition in scheduling
the tasks of a job. The resource availability and resource demands are for
multiple resources, mainly including GPU or CPU, memory, and bandwidth.

Figure 1: Model and data parallel ML on edges.

An edge node is considered overloaded when the sum of the resource demands of
its running tasks is larger than its resource capacity for one type of
resource. If an edge node running a model partition becomes overloaded, the
training process may slow down. Thus, each device $d_{j}$ measures its
resource utilization of each type type-$k$ resource periodically at each
timestep $t$ as follows:

$\small u_{k}(d_{j})=\frac{D_{k}(d_{j})}{C_{k}(d_{j})},$ (1)

where $D_{k}(d_{j})$ denotes the total resource demand of type-$k$ resource of
the tasks running on edge $d_{j}$ and $C_{k}(d_{j})$ denotes the capacity of
type-$k$ resource of edge $d_{j}$. The system pre-defines $\alpha$ (e.g.,
0.95) and if $u_{k}(d_{j})>\alpha$ for any type-$k$ resource, the edge node is
considered as overloaded. We define an edge node’s combined resource
utilization as follows:

$\small u(d_{j})=\prod u_{k}(d_{j}),~{}k=1,2,...$ (2)

It measures the overall resource utilization across different types of
resources of an edge node.

The cluster head can use RL for the task scheduling and functions as the agent
in the RL. RL has three components: state, action and reward. Given the
current state, the agent chooses the action that generates the maximum
expected reward and receives reward for the action it takes. In this task
scheduling scenario, the state is the resource demand of each layer in the DL
model and the resource availability of each edge node in the cluster. The
action is the schedule that assigns each partition to an edge node. The reward
is defined based on the training time of the DNN model; shorter training time
leads to higher reward and vice versa. Thus, using the trained RL, the cluster
head observes the state and makes the scheduling decision for each DL training
job. However, all of these operations create significant overhead on the
cluster head. In this paper, we aim to distribute the overhead among the
cluster edge nodes while decreasing training time increase due to this
decentralized operation.

##  IV System Design of SROLE

###  IV-A Overview

We propose SROLE that consists of the following components.

  * •

Multi-agent RL (Section IV-B). To distribute the job scheduling overhead on
the cluster head among the cluster edge nodes, we propose a multi-agent RL-
based method (MARL). In MARL, each edge node uses RL to schedule the tasks of
its own DL training job without relying on the cluster head.

  * •

Centralized Shielding for MARL (Section IV-C). Edge nodes share their
neighbors since there are overlaps in the transmission ranges of neighboring
edge nodes. Then, edge nodes may schedule their tasks to the same edge node
since they do not know the decisions of other edge nodes, which may overload
the task assigned node. Thus, we propose a centralized shielding method for
MARL, which checks the action collisions and provides alternative actions to
avoid the action collisions in a cluster.

  * •

Decentralized Shielding for MARL (Section IV-D). As the centralized shield is
deployed in one edge node, which may overload it, we propose a decentralized
shielding method for MARL. In this method, multiple shields are deployed to
the sub-clusters in one cluster and each shield is responsible for its own
sub-cluster. Further, the neighboring shields communicate with each other to
avoid the action collisions on the boundaries.

###  IV-B Multi-Agent RL-based Job Scheduling

The MARL method is similar to the above RL-based method, except each edge node
is an agent and the state includes the resource availability of an edge node’s
nearby nodes rather than all the edge nodes in the cluster. The RL is
initially pre-trained and distributed to each edge node. As a result, each
edge node uses the RL to schedule the tasks of its own DL training jobs and
keeps training the RL model. In this method, each edge takes the optimal
action of assignment of the partitions based on its observed state. In
particular, each edge makes its own local decision on where each layer should
be assigned.

Figure 2: The process of multi-agent RL.

Based on the decision made by each edge node, the state of the environment
changes as the available resources change for the edge node where a layer is
assigned. Consequently, based on the local decision taken by one edge or
agent, the global decision of all agents influences the overall state.
Finally, each edge node has its own long-term reward to optimize, which now
becomes a function of the policies of all other agents that are updated based
on the global decision. Figure 2 illustrates the working procedure of the
multi-agent RL. Each edge node observes the state space from the environment
and then takes its own action to assign partitions to itself and its
neighbors, and then it receives reward. The joint action of the actions of all
agents are denoted by $\mathbf{a^{c}_{t}}$:
$\mathbf{a^{c}_{t}}=\mathbf{a^{1}_{t}}\bigcup\mathbf{a^{2}_{t}}...\mathbf{a^{i}_{t}}...\bigcup\mathbf{a^{n}_{t}}$.
After the actions are taken, the state $\mathbf{s}$ and reward $\mathbf{r}$ at
the next timestep $t+1$ (i.e., $\mathbf{s_{t+1}}$ and $\mathbf{r_{t+1}}$)
become the state and reward at this timestep $t$ (as indicated with arrows)
for the agents to make decisions again.

Now, we explain the corresponding state (S), action (A) and reward (R) for our
proposed MARL model by each agent.

State space. The state space ($\mathbf{s_{t}}\in S$) consists of the resource
demands of all the layers of a DNN model, and the available resources of all
of a node’s nearby edge nodes. For each layer, the state includes the CPU
resource demand, memory demand, and its data transfer size to each layer in
the next level in the DNN model. Besides, the state also includes the
utilization of the CPU, memory and bandwidth resource for each device. The
state of edges includes the available CPU and memory of each edge, and
available bandwidth across each pair of edges at each time $t$. As the
continuous values of these resource characteristics result in infinite size of
the state space, we discretize the continuous space by dividing their value
range into a number (e.g., three) of equal-width ranges: low, medium and high.

We varied the structural parameters of a particular DNN layer structure within
reasonable ranges as indicated in [42] and profile the CPU and memory usage in
the forward and the backward pass. We use the TensorFlow benchmark tool [43]
to profile the usage of all DL components on an edge node. The available
resources on an edge device keeps changing accordingly to the layers assigned
to the device.

Action space. We use $\mathbf{a_{t}}$ to denote $\mathbf{a^{i}_{t}}$ for
simplicity. The action space represented by
$\mathbf{a_{t}}$$=\\{a^{i,j}_{t}\\}\in
A,~{}$($i=1,2,...,|M|,~{}j=1,2,...,|E|$) defines the schedule for all the
layers at time $t$, where $M$ denotes the set of the layers in the DNN model,
$E$ denotes the set of all nearby edges and $|\cdot|$ means the size of a set.
Each element of the action space $A$ defines which edge should be assigned
with a certain layer. Action $a^{i,j}_{t}$ is defined as follows for each pair
of layer $l_{i}$ and edge device $d_{j}$.

$a^{i,j}_{t}=\begin{cases}1,&\text{if layer $l_{i}$ is placed in edge $d_{j}$
at $t$}\vspace{-0.0in}\\\
0,&\text{otherwise}\vspace{-0.0in}\end{cases}\vspace{-0.1in}$

After $\mathbf{a_{t}}$ is determined, the available resources of edges are
updated with the available resources at $t+1$, and then $\mathbf{a_{t+1}}$ is
determined, and so on until the last layer is assigned.

Reward. Let $\mathbf{a}_{t}$ be the action taken (schedule is made) at time
$t$, then the reward function is given by:

${\mathbf{r_{t}}}(\mathbf{s_{t}},\mathbf{a_{t}})=\begin{cases}-\gamma,&\text{\small{if
memory is violated}}\\\
\frac{\rho}{\sqrt{O}},&\text{otherwise}\end{cases}\vspace{-0.05in}$

where $\rho$ is a coefficient to control the reward, $\gamma$ is a large
constant reward to ensure that a schedule violating the memory limit
requirement is not valid. Furthermore, and $O$ denotes the training time of
the DNN model. After the job assignment, the states change for the next
assignment and the reward is updated for all agents.

###  IV-C Centralized Shielding for MARL

The MARL method cannot ensure that none of the edge nodes get overloaded since
different edge nodes may assign tasks to the same node simultaneously based on
its original available resources. To handle this problem, we propose a
shielding approach on top of the multi-agent RL scheme. Each cluster has a
shield deployed in the cluster head that has high resource capacity. It
ensures that none of the edges get overloaded by the task assignment from all
edge nodes in the cluster. In the centralized shielding method, the shield
enforces the safety specification (i.e., avoiding decisions that overload an
edge before being sent to the environment) during the RL learning process.
After an edge node makes a scheduling decision for its job, it reports its
decision to the shield in its cluster. The shield collects the decisions of
all edge nodes in its cluster and checks action collisions, i.e., the actions
that will make an edge node overloaded by hosting the tasks from multiple edge
nodes, and then provides alternative actions to avoid the action collisions.

Figure 3: Centralized shielding.

We hope that the shield restricts MARL agents as less as possible via the
minimal interference criteria. These criteria are as follows: (1) the shield
only corrects joint action $\mathbf{a^{c}_{t}}$ if it violates the safety
specification, and (2) the shield seeks a safe joint action
$\mathbf{\tilde{a}^{c}_{t}}$ that changes as a few of the agents’ actions as
possible in $\mathbf{a^{c}_{t}}$. Figure 3 shows the working procedure of the
centralized shielding built on top of the multi-agent RL scheme. The
centralized shield observes the joint action and current state before the
action is implemented. If it leads to an unsafe action, i.e., overloading of
any edge, the shield suggests a safe action that will be implemented. At the
same time, the shield also notifies the edges within the cluster of the safe
action and assigns a constant negative reward ($\kappa$) for their originally
decided action that leads to the overload of one device. Accordingly, the
reward is redefined as below:

${\mathbf{r_{t}}}(\mathbf{s_{t}},\mathbf{a_{t}})=\begin{cases}-\gamma,&\text{\small{if
memory is violated}}\\\ -\kappa,&\text{suggested by the shield}\\\
\frac{\rho}{\sqrt{O}},&\text{otherwise}\end{cases}\vspace{-0.05in}$

In the meantime, the environment changes based on the suggested safe action by
the shield and the states and rewards are updated accordingly.

The shield makes a judgement about the potential violations of safety
specifications. In details, the shield observes whether the joint action
actually changes the resource utilization of any type of resource of an edge
to a value higher than the threshold, i.e., $u_{k}(d_{j})>\alpha$. If this
condition is true (criterion (1)), there exists an action collision and the
shield will choose alternative safe actions to replace the original actions in
the joint action to make the edge node (say $d_{j}$) not overloaded. For each
layer $l_{i}$ that is assigned to edge node $d_{j}$, we define its resource
demand weight as follows:

$\small\omega(l_{i})=\prod_{k}(b_{k}(l_{i})/C_{k}(d_{j})),~{}k=1,2,...\vspace{-0.07in}$
(3)

where $b_{k}(l_{i})$ is the resource demand of type-$k$ resource of layer
$l_{i}$ and $C_{k}(d_{j})$ is the capacity of type-$k$ resource of edge device
$d_{j}$. While choosing the safe action, the shield first ranks the layers
that are planned to be assigned to the edge node based on their resource
demand weights. Then, it picks up the layer with the highest weight and finds
a new host edge for it that will not be overloaded after hosting this layer.
The purpose of choosing the layer of the highest weight to be rescheduled is
to reduce the interference to the original joint action (criterion (2)). The
shield repeats this process until the remaining layers will not overload the
edge. Specifically, it searches for nearby edge nodes with high resource
availability from edge node $d_{j}$, and then checks whether any of these
edges can host this layer after it accepts other layers that are planned to
assign to it in other actions. To quickly find such an edge node, the shield
calculates the combined resource utilizations of the nearby edge nodes after
they accept other planned layers assigned to them. Next, it orders the nearby
edge nodes in the ascending order of their combined resource utilizations and
then sequentially picks up the top node to check until it finds such an edge
node. The edge node on the top generally has a high available resources and
hence is more likely to be able to host the layer. After finding the new host
edge, the shield creates an alternative action that assigns the layer to this
edge device. As we limit our safe action from the nearby edges of the original
edge node in the decided original action and ensure this newly suggested
action won’t overload the edge, this new action will not deviate from the
previous optimal action greatly.

1

2for  _each timestep_ do

3 Collect actions from all edge nodes in the cluster

4 Virtually take the actions to assign layers to edges

5 foreach  _each edge node $d_{j}$_ do

6 Calculate resource utilization $u_{k}(d_{j})$ of each resource

7

8 Rank the assigned layers on $d_{j}$ in descending order of resource demand
weight

9 Punishment $\kappa\leftarrow 0$

10 while  _any $u_{k}(d_{j})>\alpha$, $k=1,2,...$_ do

11

12 Choose the top layer which is in action $\mathbf{a_{t}}$

13 $\mathbf{\tilde{a}_{t}}\leftarrow$ safe action by the shield

14 Replace $\mathbf{a_{t}}$ by $\mathbf{\tilde{a}_{t}}$

15 $\kappa\leftarrow\kappa+$ constant negative reward

16 Notify the layer’s scheduling edge about $\kappa$ and
$\mathbf{\tilde{a}_{t}}$

17

18 end while

19

20 end foreach

21

22 end for

Algorithm 1 Pseudocode of the centralized shielding executed by the shield in
a cluster.

Algorithm 1 illustrates the pseudocode for the centralized shielding. At each
timestep $t$ (Line 1), the central shield observes the joint action and joint
state of all the agents or edges in the cluster (Lines 2-3). For each edge
node $d_{j}$, it calculates its resource utilization of each resource type
(Line 5), ranks the assigned layers on $d_{j}$ in descending order of resource
demand weight (Line 6), and initializes $\kappa$ (Line 7). It then checks
whether its resource utilization is greater than the pre-defined threshold
$\alpha$ (Line 8). If yes, the shield picks up the layer on the list top,
finds and suggests a safe action for scheduling the layer and notifies the
layer scheduling edge about the new action and the $\kappa$ reward for the
unsafe action (Lines 9-13). The shield repeats this process until the edge
node will not be overloaded after it hosts all layers assigned to it (Lines
8-14).

###  IV-D Decentralized Shielding for MARL

A shield in a cluster is responsible for all edge nodes in a cluster and may
become overloaded due to the communication and computation overhead in
shielding. Thus, we propose a decentralized shielding method. In the
decentralized shielding method, we first divide a cluster to multiple sub-
clusters and each sub-cluster consists of geographically proximity-close edge
nodes. Then, one shield works for one sub-cluster. Within each sub-cluster,
the shield works in the similar way as described in the centralized shielding.
There is one additional problem we need to handle. The edge nodes in the
boundary of two or more sub-clusters may assign tasks to the same edge node in
one sub-cluster, which may overload it, but the shield in this sub-cluster
will not receive the actions from its neighboring sub-clusters and hence will
not detect the action collision. To solve this problem, the shields of
neighboring sub-clusters need to communicate with each other to avoid such a
case. Specifically, the neighboring shields first select a delegate to check
the action collisions. Then, they send the actions of the edge nodes and the
available resources as well as the resource utilizations of the edge nodes in
the boundary to the delegate. The delegate uses the same method in the
centralized shielding method to check action collision and finds alternative
actions. It sends the alternative actions to the neighboring shields, and the
shields then forward the alternative actions to the corresponding edge nodes.
As a result, the edge nodes take alternative actions instead of previously
determined actions.

##  V Performance Evaluation

(a) VGG-16. (b) GoogleNet.  (c) RNN.

Figure 4: Job completion time for different models from emulation.

(a) VGG-16. (b) GoogleNet.  (c) RNN.

Figure 5: The number of tasks per device for different models from emulation.

###  V-A Experiment Setup

Emulation. Our proposed system runs on Tensorflow for the execution of the
model training through its parameter server strategy. In order to emulate
edges with varying resources, we use 25 docker containers. Each cluster has 5
edge nodes. The resource settings of our emulation and real device experiments
are indicated in Table I and the resources of the devices were assigned in a
round-robin way. The containers are deployed in Amazon EC2 instance of type
m5ad.4xlarge. The CPU and memory are configured using commands from docker and
the bandwidth between different containers is configured using the tcconfig
tool [44].

Real experiments. Our real testbed consists of 10 Raspberry Pis; two Pis have
1 GB memory, four other Pis have 2 GB memory and four other Pi has 4 GB
memory. They roughly have same CPU but we use the cpulimit [45] command to
control the CPU as desired according to Table I. The edges are connected via
2.4 GHz band wireless connection. We use wondershaper [46] tool to control
bandwidth among the edges.

TABLE I: Resource configuration. Environment |  Resource ranges
---|---
Real edge |  Mem$\in\\{1024,2048,4096\\}$MB
|  CPU$\in\\{0.25,0.5,1.0\\}$Host Ratio
|  BW$\in\\{20,100\\}$MBps
Container |  Mem$\in\\{768,1024,1536,2048,4096\\}$MB
|  CPU$\in[0.3,1.0]$Host Ratio
|  BW$\in\\{50,100,200,500,1000\\}$Mbps

ML models and datasets. We run three ML models: GoogleNet Inception, VGG-16,
and RNN [47]. We use the MNIST [48] dataset to run the first two models and
the Air Quality dataset [49] for the RNN model. The MNIST dataset consists of
70,000 images of handwritten digits and is widely used for training CNN
models. The Air Quality dataset contains 9358 instances of hourly averaged
responses from an array of 5 metal oxide chemical sensors. One instance refers
to the sensor values (as the ML inputs) and the AQI value (as the ML output).
Since there are maximally 5 clusters, We divide the dataset to 5 subsets. Each
cluster has a subset as the input training data and the data is randomly
distributed among the edges in the cluster as their sensed data. We run three
DL training jobs of the same type in each cluster initiated by randomly chosen
edge nodes.

RL Training. To train the RL models, we need data related to both DNN models
and edge nodes. To generate the data related different DNN model structures
and we profiled and obtained their resource demands. To generate edge node
configuration data, we consider the number of edge nodes in the range of
[2,10]. For each edge node, CPU is chosen randomly from range [0.5,2] GHz,
memory is randomly chosen from range [64,4096] MB [50] and the bandwidth
across pair of edge nodes is randomly chosen from range [128,1000] MBps [51].
Using these data, we train the RL model offline.

Workload and Settings. In all the cases, we trained one DNN model in each
cluster and add several other non-ML jobs (PageRank [52]) from the HiBench
benchmark to vary available resources on the edges. The workloads were
controlled by running multiple PageRank job on these edges in a distributed
way. We run x=2,3,…,6 PageRank jobs in each cluster throughout the whole
training period to control the workload. Workload of 100% means there are 6
PageRank jobs running simultaneously in the system, and other workloads are
defined similarly in the decreasing order, i.e., 5 is 90%, 4 is 80%, and so
on. These jobs were run simultaneously with DNN training jobs until the run
completes. During these experiments, we either change the number of edge
devices or the workload along the x-axis. Unless otherwise indicated, the
number of edge nodes is 25 and the workload is 100%. Each run for DNN model
experiment was executed for 50 iterations. We repeated each experiment 5 times
and plotted the median with the 5th and 95th percentile error bars. During the
experiment, we measured the resource utilization of the devices every 10
minutes. In both the cases of emulation and real device, we set the value of
the parameters $\alpha=0.9$, $\rho=1$, $\gamma=50$ and $\kappa=-100$.

###  V-B Compared Methods

MARL. This is a simple multi-agent RL-based method CQ-learning [53] without
shielding. In particular, both the evolution of the system state and the
reward received by each agent are influenced by the joint actions of all
agents. That is, each agent has its own long-term reward to optimize, which
now becomes a function of the policies of all other agents.

SROLE-C. This is a multi-agent RL method with an extra centralized shield. In
the centralized shielding, there is a single shield to monitor all agents’
joint actions and correct any unsafe action if necessary. That is, the shield
observes all the agents and prevents any edge node from being overloaded.

SROLE-D. This is an extension of the centralized shielding. It has multiple
shields on multiple sub-clusters in a cluster and each shield is only
responsible for the agents in its sub-cluster or a subset of agents in its
cluster.

Centralized RL. In the following figures, we use _RL_ for simplicity. This is
an RL scheme where the cluster head makes the assignment decision for all the
jobs in its cluster. In this method, we assign a negative reward for
overloading the memory of a certain device and otherwise, the reward is based
on the job completion time.

###  V-C Metrics

Job completion time. This is the training time, which denotes the time period
from the time when a job starts to run after scheduling to the time when the
training of the whole model completes. This time period contains multiple
number of iterations depending on the size of the dataset. In our case, the
training for all the models comprises of 50 iterations.

The number of tasks per device. From different runs, we measure the number of
partitions for a DNN training job and tasks for non-ML jobs running on each
device. This measurement is to show the performance of avoiding overloading
edge nodes.

Computation time overhead. Computation overhead refers to the decision making
time of each method. It is the time period from the time when a job is
initiated to the time when the task assignment schedule of the job is made.

The number of action collisions. We measure the number of action collisions
for the negative reward ($\kappa$) for unsafe actions.

###  V-D Experimental Results from Emulation

(a) VGG-16. (b) GoogleNet.  (c) RNN.

Figure 6: Resource utilization for different models from emulation.

(a) VGG-16. (b) GoogleNet.  (c) RNN.

Figure 7: Computation overhead for different models from emulation.

(a) VGG-16. (b) GoogleNet.  (c) RNN.

Figure 8: The number of action collisions for different models from emulation.

Job completion time. Figures 4a, 4b, and 4c show the job completion time
versus the number of edges for training the VGG-16, GoogleNet, and RNN models,
respectively. MARL and RL have similar job completion times, which indicates
that the performances of their job schedules are similar. The results imply
that MARL still can achieve comparable performance as RL though MARL does not
have global information for job scheduling. Both centralized and decentralized
shielding methods (SROLE-C and SROLE-D) perform better than RL and MARL
without shielding because shielding reduces the number of unsafe actions,
i.e., overloading individual devices. As a result, it reduces the job
completion time. For VGG-16, GoogleNet, and RNN, SROLE-D shows 36-45%, 35-43%,
and 33-44% reduction in job completion time than MARL or RL without shielding.
SROLE-D performs 8-13% less than SROLE-C for all three models because the
action collisions are checked by multiple shields instead of one, adding extra
communication time among the neighboring shields during the DNN training. As a
result, SROLE-C saves job completion time by 49-56% for VGG-16, 48-59% for
GoogleNet, 47-56% for RNN, respectively in comparison with RL and MARL without
shielding. Thus, the shielding can be conducted more efficiently because of
observing the resource state of all the edges together. From all the figures,
we see that as the number of edges increases, the job completion time
increases. This happens because more clusters lead to more time in
transferring the model parameters from the clusters to the parameter server
for synchronization of the model. Also, the figures show the results do not
vary greatly and keep relatively stable.

(a) VGG-16. (b) GoogleNet.  (c) RNN.

Figure 9: Job completion time for different models from a real-device network.

(a) VGG-16. (b) GoogleNet.  (c) RNN.

Figure 10: The number of tasks per device for different models from a real-
device network.

(a) VGG-16. (b) GoogleNet.  (c) RNN.

Figure 11: Resource utilization for different models from a real-device
network.

The number of tasks per edge node. Figures 5a, 5b, and 5c show the number of
tasks per node versus different workloads for training the VGG-16, GoogleNet,
and RNN models, respectively in the scenario with 25 edges. We plot the median
(denoted with different colors) along with the minimum and the maximum number
of tasks (denoted with black bars). SROLE-D shows 42-56%, 46-61%, and 41-56%
reduction in the median number of assigned tasks per device for VGG-16,
GoogleNet, and RNN compared to MARL or RL without shielding, respectively.
However, the SROLE-C outperforms the SROLE-D by 2-11%. As a result, SROLE-C
generates a reduction in the median number of assigned tasks per device by
49-56% for VGG-16, 48-59% for GoogleNet, 47-56% for RNN respectively in
comparison with RL and MARL without shielding. From the figure, we also
observe that both the SROLE-D and SROLE-C methods show less variance than both
MARL and RL without shielding. Both SROLE-C and SROLE-D perform better than
other methods because shielding reduces the number of unsafe actions, i.e.,
overloading on individual devices, and thus distributes the tasks among
devices in a more balanced manner. However, SROLE-D performs less than SROLE-C
shielding because of taking a higher number of unsafe actions. This phenomenon
happens because of not knowing the cluster more completely.

Resource utilization. Figures 6a, 6b, and 6c show the resource utilization of
each type of resources for training the VGG-16, GoogleNet, and RNN models,
respectively in the scenario of total 25 edges. We plot the median along with
the minimum and maximum resource utilizations as error bars.  For VGG-16,
GoogleNet, and RNN, SROLE-D shows 12-19%, 11-17%, and 11-15% reduction in the
median resource utilization compared to MARL or RL without shielding. However,
the SROLE-C outperforms the SROLE-D by 2-14%. As a result, SROLE-C generates a
reduction in the median resource utilization by 21-24% % for VGG-16, 48-59%
for GoogleNet, 22-29% for RNN, respectively in comparison with RL and MARL
without shielding. From the figure, we also observe that both the SROLE-D and
SROLE-C show less variance than both the MARL and RL without shielding in
terms of resource utilization. Both centralized and decentralized shielding
methods perform better than other methods because shielding avoids overloading
individual devices. However, SROLE-D performs less than SROLE-C because of
taking a higher number of unsafe actions. This happens due to not having the
complete knowledge of the cluster, which adds extra computation or
communication for the involvement of multiple shields.

Average computation time overhead. Figures 7a, 7b, and 7c show the computation
overhead for scheduling (blue bar) and shielding (orange bar) of different
methods while training the VGG-16, GoogleNet, and RNN models, respectively.
For all the models, the results for computation overhead (scheduling +
shielding) are as follow: MARL$<$SROLE-D$<$SROLE-C$<$RL. RL needs the longest
decision making time because only one node is responsible for scheduling all
jobs in one cluster. MARL greatly reduces the decision making time of RL since
MARL distributes the scheduling load among the edge nodes in the cluster by
letting each edge node schedule its own job among its neighbors. Both RL and
MARL do not have any shielding time as they do not have the shielding
approach. SROLE-C and SROLE-D are based on MARL, and they have additional
shielding components to detect action collisions, thus generating higher
decision making time. MARL, SROLE-C and SROLE-D have the same scheduling time
since they all use MARL for scheduling. SROLE-D generates 5-8% less shielding
time than SROLE-C for all the models. This is because SROLE-C relies on one
shield in each cluster, so the shield needs to check all the actions, which
needs a long time, and SROLE-D distributes the shielding overload among
multiple shields, which expedites the shielding process and reduces both the
shielding time and the decision making time.

The number of action collisions. Figure 8 shows how the assigned reward of
unsafe action impacts the number of unsafe actions during the training of all
the DNN models. SROLE-C performs 31-48% better than the MARL or RL, while
SROLE-D performs 27-39% better than MARL or RL for all the three models. This
is because the added shield(s) in SROLE-C and SROLE-D coordinate the edges to
avoid unsafe actions, but MARL and RL do not have shields. The SROLE-C
approach performs 4-7% better than SROLE-D. This is because the global shield
in SROLE-C can observe the global environment, compare all actions and suggest
alternative actions accordingly to avoid unsafe actions globally. When
multiple shields are responsible for sub-clusters in SROLE-D, the information
collected by a shield for the boundary nodes may not cover all the unsafe
actions, leading to unsafe actions. Though SROLE-C and SROLE-D use the
shielding approach, they still produce certain unsafe actions. This is because
the resource demands of tasks are time-varying and dynamic and sometimes
cannot be accurately predicted, thus leading to the edge node overload. For
all the three models, as the absolute value of the reward of an unsafe action
increases, the number of unsafe actions during the whole training period in
SROLE-C and SROLE-D decreases and this number in MARL and RL keeps constant.
MARL and RL do not use this reward or shielding approach, so their
performances are not affected by the reward value. A high penalty for the
action collision will help SROLE-C and SROLE-D avoid more unsafe actions.

(a) VGG-16. (b) GoogleNet.  (c) RNN.

Figure 12: Computation overhead for different models from a real-device
network.

(a) VGG-16. (b) GoogleNet.  (c) RNN.

Figure 13: The number of action collisions for different models from a real-
device network.

###  V-E Experimental Results from a Real Device Network

We formed the 10 edge nodes into a network and considered it as a single
cluster, and then ran real experiments on the real-device network. From the
real experiments, we observe similar performances of the different methods as
in the container-based emulation due to the same reasons mentioned above. Job
completion time. Figure 9 shows the the job completion time for training all
models in the real-device cluster. For these models, SROLE-D performs 32-39%
better than MARL or RL without shielding and SROLE-C performs 36-53% better
than MARL or RL. SROLE-D performs 4-7% worse than SROLE-C because SROLE-D has
additional communication operations between neighboring shields for shielding.

The number of tasks per edge. Figure 10 shows the number of tasks per node for
training all the models. Comparing to MARL and RL without shielding, SROLE-D
shows 28-45% reduction and SROLE-C shows 39-52% reduction in the median number
of assigned tasks per device. SROLE-D performs 7-11% worse than SROLE-C
because the shields in SROLE-D do not have global knowledge of the state of
the resources in all edges. Similar to the emulation experiments, the
variances of SROLE-D and SROLE-C are lower than those of MARL and RL without
shielding for all the models.

Resource utilization. Figure 11 shows the resource utilization of each type of
resources for training the three models. SROLE-D shows 18-23% reduction and
SROLE-C shows 21-28% reduction in the median in the median of resource
utilization. SROLE-D performs 3-5% worse than SROLE-C because the shields in
SROLE-D do not have global knowledge of the state of the resources in all
edges. Similar to the emulation experiments, the variances of SROLE-D and
SROLE-C are lower than those of MARL and RL without shielding for all models.

Average computation time overhead. Figure 12 shows the computation overhead
for scheduling and shielding of different methods while training all the
models. For the shielding time, SROLE-D performs 4-7% better than SROLE-C for
real-devices.

The number of action collisions. Figure 13 shows how the assigned reward of
unsafe action impacts the number of unsafe actions during training the DNN
models. SROLE-D shows 27-42% reduction and SROLE-C shows 29-46% reduction in
the median in the median of resource utilization. SROLE-D performs 2-6% worse
than SROLE-C because the shields in SROLE-D do not have global knowledge of
the state of the resources in all edges.

##  VI Conclusion

Fully distributed DNN training on edges utilizing concurrent model and data
parallelism is a promising way to increase the scalability of DNN model
training at resource-constrained edges. However, relying on one edge node to
use RL to schedule the model partitions (i.e., distributing the partitions of
a large DL model to a set of edges to minimize the training time) among edge
nodes is not scalable. In this paper, we propose a multi-agent RL system that
enables each edge node to schedule its own jobs. To ensure such distributed
job scheduling method will not overload an edge node, we propose using
shielding that observes the actions decided by all edge nodes to avoid
overloading edge nodes. Relying on one shield is not scalable. Thus, we
further propose a decentralized shielding method that relies on multiple
shields to conduct shielding in a distributed manner. Our experiments show
that our shielding method performs 59% better than multi-agent RL in training
time with 29% less median resource utilization of an edge device, and also the
multi-agent RL method achieves similar job completion time performance as the
centralized RL method. In the future, we will explore using formal method
approaches to provide a guarantee of action collision avoidance and explore a
method to avoid action collisions caused by decentralized shielding.

## Acknowledgements

This research was supported in part by U.S. NSF grants NSF-1827674,
CCF-1822965, FHWA grant 693JJ31950016, Microsoft Research Faculty Fellowship
8300751, and the Commonwealth Cyber Initiative (CCI), an investment in the
advancement of cyber research, innovation and workforce development. For more
information about CCI, visit cyberinitiative.org. We also thank Ms. Ingy
ElSayed-Aly and Dr. Lu Feng for helping us with our initial understanding of
RL shielding.

## References

  * [1] G. Boateng, V. G. Motti, V. Mishra, J. A. Batsis, J. Hester, and D. Kotz, “Experience: Design, development and evaluation of a wearable device for mhealth applications,” in _Proc. of MobiCom_ , 2019.
  * [2] Y. Huang, X. Ma, X. Fan, J. Liu, and W. Gong, “When deep learning meets edge computing,” in _Proc. of ICNP_ , 2017.
  * [3] J. Wang, Z. Guo, S. Liu, and Y. Xia, “Poster: Maintaining training efficiency and accuracy for edge-assisted online federated learning with abs,” in _Proc. of ICNP_ , 2020.
  * [4] A. Curtis, A. Pai, J. Cao, N. Moukaddam, and A. Sabharwal, “Healthsense: Software-defined mobile-based clinical trials,” in _Proc. of MobiCom_ , 2019\.
  * [5] S. Wang, T. Tuor, T. Salonidis, K. K. Leung, C. Makaya, T. He, and K. Chan, “When edge meets learning: Adaptive control for resource-constrained distributed machine learning,” in _Proc. of INFOCOM_ , 2018.
  * [6] Y. Chen, K. Zhao, B. Li, and M. Zhao, “Exploring the use of synthetic gradients for distributed deep learning across cloud and edge resources,” in _Proc. of HotEdge_ , 2019.
  * [7] K. Bonawitz, H. Eichner, W. Grieskamp, D. Huba, A. Ingerman, V. Ivanov, C. M. Kiddon, J. Konečný, S. Mazzocchi, B. McMahan, T. V. Overveldt, D. Petrou, D. Ramage, and J. Roselander, “Towards federated learning at scale: System design,” in _Proc. of SysML_ , 2019.
  * [8] Tanmoy Sen and Haiying Shen, “A data and model parallelism-based distributed deep learning system in a network of edge devices,” University of Virginia, Tech. Rep., 2021. [Online]. Available: http://dsc.soic.indiana.edu/publications/Manuscript.IJHPCA.Nov2018.pdf
  * [9] M. Yang, Y. Dai, and X. Li, “Bring Reputation System To Social Network in the Maze P2P File-Sharing System,” in _Proc. of the International Symposium on Collaborative Technologies and Systems (CTS)_ , 2006.
  * [10] H. Zhu, V. Gupta, S. S. Ahuja, Y. Tian, Y. Zhang, and X. Jin, “Network planning with deep reinforcement learning,” in _Proceedings of the 2021 ACM SIGCOMM 2021 Conference_ , 2021.
  * [11] I. Elsayed-Aly, S. Bharadwaj, C. Amato, R. Ehlers, U. Topcu, and L. Feng, “Safe multi-agent reinforcement learning via shielding,” _ArXiv_ , vol. abs/2101.11196, 2021.
  * [12] G. Li, L. Liu, X. Wang, X. Dong, P. Zhao, and X. Feng, “Auto-tuning neural network quantization framework for collaborative inference between the cloud and edge,” in _International Conference on Artificial Neural Networks_. Springer, 2018, pp. 402–411.
  * [13] Z. Zhao, Z. Jiang, N. Ling, X. Shuai, and G. Xing, “Ecrt: An edge computing system for real-time image-based object tracking,” in _Proceedings of the 16th ACM Conference on Embedded Networked Sensor Systems_. ACM, 2018, pp. 394–395.
  * [14] H. Li, K. Ota, and M. Dong, “Learning iot in edge: Deep learning for the internet of things with edge computing,” _IEEE Network_ , vol. 32, no. 1, pp. 96–101, 2018.
  * [15] W. Zhang, Z. Zhang, S. Zeadally, H.-C. Chao, and V. Leung, “Masm: A multiple-algorithm service model for energy-delay optimization in edge artificial intelligence,” _IEEE Transactions on Industrial Informatics_ , 2019.
  * [16] H.-J. Jeong, H.-J. Lee, C. H. Shin, and S.-M. Moon, “Ionn: Incremental offloading of neural network computations from mobile devices to edge servers,” in _Proceedings of the ACM Symposium on Cloud Computing_. ACM, 2018, pp. 401–411.
  * [17] S. Wang, T. Tuor, T. Salonidis, K. K. Leung, C. Makaya, T. He, and K. Chan, “When edge meets learning: Adaptive control for resource-constrained distributed machine learning,” in _Proc. of INFOCOM_ , 2018.
  * [18] J. Zhang, S. Chen, B. Liu, Y. Ma, and X. Chen, “A locally distributed mobile computing framework for dnn based android applications,” in _Proceedings of the Tenth Asia-Pacific Symposium on Internetware_. ACM, 2018, p. 17.
  * [19] Z. Zhao, K. M. Barijough, and A. Gerstlauer, “Deepthings: Distributed adaptive deep learning inference on resource-constrained iot edge clusters,” _IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems_ , vol. 37, no. 11, 2018.
  * [20] L. Zhou, H. Wen, R. Teodorescu, and D. H. Du, “Distributing deep neural networks with containerized partitions at the edge,” in _Proc. of HotEdge_ , 2019.
  * [21] A. Yousefpour, B. Q. Nguyen, S. Devic, G. Wang, A. Kreidieh, H. Lobel, A. M. Bayen, and J. P. Jue, “Resilinet: Failure-resilient inference in distributed neural networks,” in _Proc. of FL-ICML_ , 2020.
  * [22] R. Sharma, S. Biookaghazadeh, B. Li, and M. Zhao, “Are existing knowledge transfer techniques effective for deep learning with edge devices?” in _2018 IEEE International Conference on Edge Computing (EDGE)_. IEEE, 2018, pp. 42–49.
  * [23] S. Y. Nikouei, Y. Chen, S. Song, R. Xu, B.-Y. Choi, and T. R. Faughnan, “Real-time human detection as an edge service enabled by a lightweight cnn,” in _2018 IEEE International Conference on Edge Computing (EDGE)_. IEEE, 2018, pp. 125–129.
  * [24] X. Zhang, X. Zhou, M. Lin, and J. Sun, “Shufflenet: An extremely efficient convolutional neural network for mobile devices,” in _Proc. of CVPR_ , 2018\.
  * [25] L. Lai and N. Suda, “Enabling deep learning at the iot edge,” in _Proceedings of the International Conference on Computer-Aided Design_. ACM, 2018, p. 135.
  * [26] A. Ashok, N. Rhinehart, F. N. Beainy, and K. M. Kitani, “N2n learning: Network to network compression via policy gradient reinforcement learning,” in _Proc. of ICLR_ , 2018.
  * [27] A. Kusupati, M. Singh, K. Bhatia, A. Kumar, P. Jain, and M. Varma, “Fastgrnn: A fast, accurate, stable and tiny kilobyte sized gated recurrent neural network,” in _Proc. of NIPS_ , 2018, pp. 9017–9028.
  * [28] X. Zhang, X. Zhou, M. Lin, and J. Sun, “Shufflenet: An extremely efficient convolutional neural network for mobile devices,” in _Proc. of CVPR_ , 2018\.
  * [29] S. Yao, Y. Zhao, H. Shao, S. Liu, D. Liu, L. Su, and T. Abdelzaher, “Fastdeepiot: Towards understanding and optimizing neural network execution time on mobile and embedded devices,” in _Proc. of Sensys_. ACM, 2018, pp. 278–291.
  * [30] A. Polino, R. Pascanu, and D. Alistarh, “Model compression via distillation and quantization,” in _Proc. of ICLR_ , 2018.
  * [31] A. Malinin, B. Mlodozeniec, and M. Gales, “Ensemble distribution distillation,” in _Proc. of ICLR_ , 2020.
  * [32] C. Li, J. Peng, L. Yuan, G. Wang, X. Liang, L. Lin, and X. Chang, “Block-wisely supervised neural architecture search with knowledge distillation,” in _Proc. of CVPR_ , 2020, pp. 1989–1998.
  * [33] V. Nekrasov, H. Chen, C. Shen, and I. Reid, “Fast neural architecture search of compact semantic segmentation models via auxiliary cells,” in _Proc. of CVPR_ , 2019, pp. 9126–9135.
  * [34] Y. Cheng, D. Wang, P. Zhou, and T. Zhang, “Model compression and acceleration for deep neural networks: The principles, progress, and challenges,” _IEEE Signal Processing Magazine_ , vol. 35, no. 1, pp. 126–136, 2018.
  * [35] M. R. U. Saputra, P. P. de Gusmao, Y. Almalioglu, A. Markham, and N. Trigoni, “Distilling knowledge from a deep pose regressor network,” in _Proc. of ICCV_ , 2019, pp. 263–272.
  * [36] S. Yao, Y. Zhao, H. Shao, S. Liu, D. Liu, L. Su, and T. F. Abdelzaher, “Fastdeepiot: Towards understanding and optimizing neural network execution time on mobile and embedded devices,” _CoRR_ , 2018.
  * [37] H. Yang, Y. Zhu, and J. Liu, “End-to-end learning of energy-constrained deep neural networks,” in _Proc. of ICLR_ , 2019.
  * [38] S. Liu, Y. Lin, Z. Zhou, K. Nan, H. Liu, and J. Du, “On-demand deep model compression for mobile devices: A usage-driven model selection framework,” in _Proc. of MobiSys_ , 2018.
  * [39] S. Han, H. Mao, and W. J. Dally, “Deep compression: Compressing deep neural network with pruning, trained quantization and huffman coding,” _Proc. of ICLR_ , 2015.
  * [40] S. Yao, Y. Zhao, A. Zhang, L. Su, and T. Abdelzaher, “Deepiot: Compressing deep neural network structures for sensing systems with a compressor-critic framework,” in _Proc. of SenSys_ , 2017.
  * [41] D. Narayanan, A. Harlap, A. Phanishayee, V. Seshadri, N. R. Devanur, G. R. Ganger, P. B. Gibbons, and M. Zaharia, “Pipedream: Generalized pipeline parallelism for dnn training,” in _Proc. of SOSP_ , 2019.
  * [42] S. Yao, Y. Zhao, H. Shao, S. Liu, D. Liu, L. Su, and T. F. Abdelzaher, “FastDeepIoT: Towards understanding and optimizing neural network execution time on mobile and embedded devices,” in _Proc. of Sensys_ , 2018\.
  * [43] “Tensorflow model benchmark tool description,” https://https://github.com/tensorflow/tensorflow/tree/master/tensorflow/tools/benchmark, accessed: 2020-4-27.
  * [44] “tcconfig,” https://github.com/thombashi/tcconfig.
  * [45] “cpulimit,” https://github.com/opsengine/cpulimit.
  * [46] “wondershaper,” https://github.com/magnific0/wondershaper.
  * [47] J. Brownlee, “Sequence classification with lstm recurrent neural networks in python with keras,” 2019, https://machinelearningmastery.com/sequence-classification-lstm-recurrent-neural-networks-python-keras/.
  * [48] “Keras cnn,” https://keras.io/examples/mnist_cnn/.
  * [49] S. D. Vito, E. Massera, M. Piga, L. Martinotto, and G. D. Francia, “On field calibration of an electronic nose for benzene estimation in an urban pollution monitoring scenario,” _Sensors and Actuators B: Chemical_ , vol. 129, no. 2, 2008.
  * [50] J. Fan, X. Wei, T. Wang, T. Lan, and S. Subramaniam, “Deadline-aware task scheduling in a tiered iot infrastructure,” in _Proc. of GLOBECOM_ , 2017.
  * [51] T. Sen and H. Shen, “Machine learning based timeliness-guaranteed and energy-efficient task assignment in edge computing systems,” in _Proc. of ICFEC_ , 2019.
  * [52] S. Huang, J. Huang, J. Dai, T. Xie, and B. Huang, “The hibench benchmark suite: Characterization of the mapreduce-based data analysis,” in _2010 IEEE 26th International Conference on Data Engineering Workshops (ICDEW 2010)_ , 2010.
  * [53] Y.-M. De Hauwere, P. Vrancx, and A. Nowé, “Learning multi-agent state space representations,” in _Proc. of AAMAS_ , 2010.


# Photonic Bound States and Scattering Resonances in Waveguide QED

Bastian Bakkensen  Yu-Xiang Zhang  Johannes Bjerlin  Anders Søndberg Sørensen
Center for Hybrid Quantum Networks (Hy-Q), Niels Bohr Institute, University of
Copenhagen, Blegdamsvej 17, 2100 Copenhagen Ø, Denmark

###### Abstract

We study the emergence of two types of two-photon bounds states in waveguides
of any chirality. Specifically, we present a systematic way of analytically
determining the eigenstates of a system consisting of a waveguide coupled to a
partially chiral, infinite array of equidistant two-level emitters. Using an
effective Hamiltonian approach, we determine the properties of the two-photon
bound states by determining their dispersion relation and internal structure.
The bound states come in two varieties, depending on the two-photon momentum
and emitter spacing. One of these states is a long-lived true bound state,
whereas the other, a scattering resonance, decays in time via coupling to free
two-photon states, leading to resonances and corresponding phase shifts in the
photon-photon scattering.

††preprint: APS/123-QED

### Introduction.

Highly-correlated dynamics induced by the electromagnetic force are ubiquitous
in material systems. In contrast, the inherent interaction between photons,
the carriers of the electromagnetic force, is extremely weak [1]. The
interaction can, however, be increased by coupling the photons to material
systems and this raises fundamental questions about how to understand
effective photon-photon interactions. Recently, effective interactions have
been achieved in multiple systems including atoms in cavities [2, 3],
superconducting circuits [4], molecules [5], Rydberg atoms [6, 7, 8, 9, 10,
11], quantum dots [12, 11] and nanoscale photonic structures [13, 14]. This
has enabled experimental observations of exotic photonic states, such as bound
states in a gas of Rydberg atoms [15], strong bunching or antibunching of
photon transmitted by atomic ensemble-coupled waveguides [16] and optical
transistors gated by a single photon [17]. In addition to their fundamental
importance, strong and controllable photon-photon interactions in the few-
photon regime is also of immense technological importance due to their
applications in quantum information processing [18, 19].

Perhaps the conceptually simplest avenue for photon-photon interaction is a
waveguide QED setup, where an array of equally spaced two-level emitters are
coupled to a one-dimensional (1D) waveguide [20, 21], as illustrated in Fig.
1. Despite its simplicity this system exhibits rich and complex physics due to
the interplay between scattering by the emitters and effective optical
nonlinearities induced by the inability for two photons to excite the same
emitter. Detailed understanding of the dynamics has only been obtained for the
special case of chiral interactions, where the emitters are only coupled to
light propagating in one of the two directions [22, 23, 24, 25]. Several
interesting effects including photon bound states have been predicted in this
case [23, 24, 25], but it remains an open question to which degree such
phenomena are present in the more generic situation of partially-chiral or
completely non-chiral interactions. Understanding these limits is of utmost
importance for the experimental exploration of these effects since these only
achieve partially-chiral or completely non-chiral interactions [26].

Recent works have made significant improvements in understanding the few-
photon sectors of non-chiral waveguide QED, with predictions of subradiant
bound states [27, 28], and other peculiar multi-excitation states [29, 30, 31,
32, 33, 34] including free-fermion features [35, 36, 37, 38], quantum Hall
phases [39], etc. These approaches have, however, been restricted to finite
systems. Although natural for realistic considerations, this also introduces
boundary effects that blur the intrinsic physics of the photon-photon
interaction.

Figure 1: A waveguide coupled to an infinite 1D array of equidistant two level
emitters. We identify two types of solutions for two photons: true bound state
where the photons bind together indefinitely, illustrated by the blue curve,
and scattering resonances, marked with yellow, where the photons bind together
for a finite time.

In this Letter, we find exact solutions of the two-photon eigenstates of an
infinite array of two-level emitters coupled to a waveguide with any degree of
chirality. These solutions prove the existence of exact photon bound states
for any degree of chirality. In addition we identify a new family of
eigenstates which are not present in the chiral system. These represent
scattering resonances with contributions from both a localised state and free
propagating states, as depicted in Fig. 1. Similar _resonance states_ have
previously only been identified for an array of three-level emitters with
chiral interactions operated near conditions of electromagnetic induced
transparency, and were shown to have technological applications for achieving
anti-bunched light fields [40]. Our result shows that such resonances are more
ubiquitous and we provide an intuitive physical picture for the parameter
regimes where eigenstates are true bound states or scattering resonances.

The main results of this Letter are shown in Fig. 2. For single photons, the
dispersion relation exhibits a gap, except for the completely chiral case, as
shown in Fig. 2(a). This leads to a similar gap for certain momenta in the
spectrum of two free single photons: In Fig. 2(c,d) the shaded regions show
the possible energies obtained by combining the single particle energies,
$\Omega(K,q)=\omega_{K+q/2}+\omega_{K-q/2}$, where $K$ is the center of mass
momentum per photon, $q$ is the relative momentum between the two photons and
$\omega_{k}$ is the energy of a single photon state with wave number $k$. In
the gapped region we find two-photon bound states. Outside this region the
states become scattering resonances as illustrated in Fig. 2(b). These
resonances come in a number of different branches. For the nonchiral case
shown in Fig. 2(c), one of these branches connects to the previously
identified bound state at $K=0$ [27], where the lifetime becomes infinite
because the density of states vanishes. A second branch is located in the
vicinity of the gapped region and connects to the bound states. The third
branch appears in the continuum beneath the gapped region and corresponds to
the continuation of left and right moving bound states from the gapped region.
As the system becomes more chiral, these branches start to merge in nontrivial
ways, beginning to align with the chiral bound state dispersion, as
illustrated in Fig. 2(d).

Figure 2:  (a) Dispersion relation of single photon states for non-chiral
$\Gamma_{R}=\Gamma_{L}$ (blue), partially chiral
$\Gamma_{R}=0.1\Gamma_{\textrm{tot}}$ (green) and chiral $\Gamma_{R}=0$ (red).
As the system approaches the chiral regime, the band gap narrows until it
completely disappears for chiral systems. (b) Amplitude and phase of the
scattering resonance for $\Gamma_{L}=\Gamma_{R}$, and $K=0.2$. The phase
switches at the peak of the resonance. (c) Dispersion relation of two-photon
bound states for non-chiral systems $\Gamma_{R}=\Gamma_{L}$. The shaded blue
(orange) area indicates the energy range with a continuum of two free states
from the upper (lower) branch of the single excitation dispersion relation.
The shaded green area indicates the region accessible by photon states
combining upper and lower branch and green dots indicate the density of state
in a given area. Lines in the unshaded region are the dispersion relation or
the bound states. Lines in the shaded area indicate the resonance states with
widths indicated by the bars. (d) Same as (c), but for
$\Gamma_{R}=0.25\Gamma_{\textrm{tot}}$. The dashed black line is the
dispersion relation for the bound state in the completely chiral case,
$\Gamma_{R}=0$. As the system becomes more chiral, the branches merge together
on one side of the gap, approaching the chiral dispersion relation. All graphs
are for $k_{0}=1.2$.

### Model.

We consider an infinite array of two-level emitters separated by a distance
$d$. Taking the Born-Markov approximation, we eliminate the waveguide modes
while retaining their effects in an effective Hamiltonian, $H_{\textrm{eff}}$,
for the emitters [41],

$\displaystyle\begin{split}H_{\textrm{eff}}=&-i\Gamma_{R}\sum_{j<i}e^{ik_{0}|i-j|d}\sigma_{i}^{\dagger}\sigma_{j}-i\Gamma_{L}\sum_{i<j}e^{ik_{0}|i-j|d}\sigma_{i}^{\dagger}\sigma_{j}\\\
&-i\sum_{i=-\infty}^{\infty}\frac{\Gamma_{R}+\Gamma_{L}}{2}\sigma_{i}^{\dagger}\sigma_{i},\end{split}$
(1)

where $\Gamma_{L}$ ($\Gamma_{R}$) is the rate of decay from an individual
emitter to the left (right) propagating modes, $k_{0}$ is the wave number
resonant to the emitter transition, and $\sigma_{i}^{\dagger}$ ($\sigma_{i}$)
is the spin creation (annihilation) operator for an excitation of the $i$’th
emitter. The distance $d$ is set to $d=1$ throughout the remaining text with
the understanding that all wavenumbers $k$ and $k_{0}$ denote $kd$ and
$k_{0}d$. The coupling is non-chiral if $\Gamma_{R}=\Gamma_{L}$, partially
chiral if $\Gamma_{R}\neq\Gamma_{L}$ and chiral if one of the coupling rates
is zero. The chirality can be quantified by $\Gamma_{R}/\Gamma_{\textrm{tot}}$
with $\Gamma_{\textrm{tot}}=\Gamma_{R}+\Gamma_{L}$.

For the single-photon eigenstates, translation invariance implies that they
have the form of Bloch states
$\ket{k}=\sum_{j}e^{ikj}\sigma_{j}^{\dagger}\ket{0}$ with $k\in[-\pi,\pi]$,
i.e., within the Brillouin zone. The eigenenergy of $\ket{k}$ is found to be

$\omega_{k}=\frac{\Gamma_{R}}{2}\cot\frac{k_{0}-k}{2}+\frac{\Gamma_{L}}{2}\cot\frac{k_{0}+k}{2}.$
(2)

This is plotted for three different levels of chirality in Fig. 2$(a)$. A
notable feature is the energy gap between the connected bands separated by the
singularities at $k=\pm k_{0}$ (the superradiant modes) [37], unless the
system is completely chiral. This feature is crucial for the two-photon bound
states.

For two-photon states, we exploit the translation invariance by working with
basis states

$|K,\Delta\rangle=\sum_{x}e^{2iKx}\sigma_{x-\Delta/2}^{\dagger}\sigma_{x+\Delta/2}^{\dagger}|0\rangle$
(3)

which are eigenstates of both center of mass momentum ($2K$) and relative
distance $\Delta$. Again, translation invariance prevents the couplings
between states of different momentum $K$. We therefore restrict
$H_{\textrm{eff}}$ to the subspace of fixed $K$ and write it as
$H_{\textrm{eff}}^{K}=\sum_{\Delta,\Delta^{\prime}}\mathcal{H}_{\Delta\Delta^{\prime}}^{K}|K,\Delta\rangle\langle
K,\Delta^{\prime}|$ where

$\displaystyle\begin{split}\mathcal{H}_{\Delta,\Delta^{\prime}}^{K}=&-i\Gamma_{R}\sum_{\varepsilon=\pm
1}e^{i(k_{0}-K)|\Delta+\varepsilon\Delta^{\prime}|}\\\
&-i\Gamma_{L}\sum_{\varepsilon=\pm
1}e^{i(k_{0}+K)|\Delta+\varepsilon\Delta^{\prime}|}.\end{split}$ (4)

This Hamiltonian reduces the “two-body” problem to a “one body” one. This
paves the way for a clean analytical solution to the bound and resonance
states.

Figure 3:  (a) Three examples of two-photon bound states in the gapped region
for non-chiral interactions with $k_{0}=1.2$. (b) Value of $z_{1,2}$ in the
gapped region for the non-chiral case. As one approaches the edges, one of the
two values tends towards 1, indicating the transition to a scattering
resonance at the boundary. Here $k_{0}=1.2$.

### Analytical Solutions.

To obtain the eigenstates of $H^{K}_{\textrm{eff}}$, we consider the following
ansatz

$|z\rangle=\sum_{\Delta=1}^{\infty}z^{\Delta}|\Delta\rangle.$ (5)

Here $z$ is a complex number that must satisfy $\mathinner{\\!\left\lvert
z\right\rvert}\leq 1$ to have physical meaning. We here use the abbreviation
$\ket{\Delta}\equiv\ket{K,\Delta}$. For $\mathinner{\\!\left\lvert
z\right\rvert}<1$, $\ket{z}$ decays exponentially with $\Delta$, hence is
expected to capture the properties of bound states. $\ket{z}$ with
$\mathinner{\\!\left\lvert z\right\rvert}=1$ is a spin-wave like Bloch state
representing free particles.

Applying $H^{K}_{\textrm{eff}}$ to $\ket{z}$ yields

$H^{K}_{\textrm{eff}}|z\rangle=\omega^{K}(z)|z\rangle+ig_{+}(z)|z^{0}_{+}\rangle+ig_{-}(z)|z^{0}_{-}\rangle$
(6)

where $z^{0}_{\pm}=e^{i(k_{0}\pm K)}$ and

$\displaystyle\begin{split}\omega^{K}(z)=&\frac{2z\Gamma_{L}\sin(k_{0}+K)}{1+z^{2}-2z\cos(k_{0}+K)}\\\
+&\frac{2z\Gamma_{R}\sin(k_{0}-K)}{1+z^{2}-2z\cos(k_{0}-K)}.\end{split}$ (7)

Expressions for $g_{\pm}(z)$ are given in the Supplemental Material [42], but
we note that both functions are real.

It is important to realize that $\ket{z^{0}_{\pm}}$ is independent of $z$. By
exploiting this feature, we can find eigenstates of $H^{K}_{\textrm{eff}}$
with eigenvalue $\omega$ by first collecting roots $\\{z_{i}\\}$ satisfying
$\omega^{K}(z_{i})=\omega$, and then finding a proper set of coefficients
$\\{a_{i}\\}$ so that the superposition
$|\psi\rangle=\sum_{i}a_{i}|z_{i}\rangle$ is the desired eigenstate. Applying
the Hamiltonian to $\ket{\psi}$ yields

$H^{K}_{\textrm{eff}}|\psi\rangle=\omega|\psi\rangle+i\sum_{\epsilon=\pm}\sum_{i}a_{i}g_{\epsilon}(z_{i})|z^{0}_{\epsilon}\rangle.$
(8)

Thus $\ket{\psi}$ is the desired eigenstate if $\\{a_{i}\\}$ fulfills

$\sum_{i}a_{i}g_{\epsilon}(z_{i})=0,$ (9)

for $\epsilon=\pm$ simultaneously.

To proceed, we note that the size of the root set $\\{z_{i}\\}$ is exactly
four because $\omega^{K}(z)=\omega$ can be reduced to a polynomial equation of
degree four, see the Supplemental Material [42]. Moreover, it can be verified
that if $z$ is a solution, so is $1/z$. Since roots with
$\mathinner{\\!\left\lvert z\right\rvert}>1$ must be excluded from the ansatz
the two-photon states can be grouped according to the number of roots with
magnitude less than one. This leads to three families of state: (1) the
scattering states, (2) the bound states, and (3) the resonance states.

### The scattering states.

If all of the four roots of $\omega^{K}(z)=\omega$ have unit magnitude
$\mathinner{\\!\left\lvert z\right\rvert}=1$ for a given $K$ and $\omega$, the
superposition of them, $\ket{\psi}=\sum_{i}a_{i}\ket{z_{i}}$, is a scattering
eigenstate [43]. Note that Eq. (9) only provides two constraints but we have
three independent parameters (recall the normalization of states). Hence
nontrivial solutions for the coefficients $\\{a_{i}\\}_{i=1}^{4}$ typically
exist. Such scattering states form the majority of eigenstates, but are not
the focus of this Letter.

### The bound states.

If the equation $\omega^{K}(z)=\omega$ has no roots of unit magnitude, but two
roots $z_{1,2}$ satisfying $\mathinner{\\!\left\lvert z_{1,2}\right\rvert}<1$
(the conjugate roots $z_{1,2}^{-1}$ are excluded since they have magnitudes
larger than one), the corresponding eigenstate consists entirely of localized
states and is thus a bound state

$|\psi\rangle=A|z_{1}\rangle+B|z_{2}\rangle.$ (10)

According to Eq. (9) solutions for $A$ and $B$ exist if and only if $z_{1,2}$
fulfill

$g_{-}(z_{1})g_{+}(z_{2})-g_{+}(z_{1})g_{-}(z_{2})=0$ (11)

We can now determine the dispersion relation of the bound states by searching
for frequencies $\omega$ fulfilling this relation for a certain value of $K$.
We find such bound states in the regime $k_{0}<K<\pi-k_{0}$ for $k_{0}<\pi/2$
and $k_{0}>K>\pi-k_{0}$ for $k_{0}>\pi/2$. The solution in the former regime
is show in Fig 2(c,d). As shown in the figure, the bound states appear in an
energy gap within the spectrum of free particle states. This provides a simple
explanation for the stability of the bound states: there are simply no
scattering states that match in both energy and momentum.

For the bound state $z_{1,2}$ are always real but have opposite signs. Thus,
the bound states have real wavefunctions when expressed in terms of $\Delta$.
We plot the wavefunctions for a few bound states in Fig. 3(a). These clearly
shows that the amplitude decays exponentially with increasing $\Delta$. As the
bound state approach the border of the gapped region, we find that
$|z_{1,2}|\rightarrow 1$ for one of the two values, as shown in Fig. 3(b).
This means that one of the components becomes delocalized and signifies the
cross-over into a delocalized resonance state.

In addition to the bound states in the gap, we find two different types of
bound states. For $K=0$ or $K=\pi$ we find a bound state given by
$\ket{z=\cos(k_{0})}$. As opposed to those protected by energy gaps, this
bound state has a different physical interpretation: it appears because at
this particular $K$ the density of states for two free photons vanishes.
Another exception is found in the chiral limit. Here the bound states are
given by $\ket{z}$ with $z=\cos(k_{0}\pm K)$, corresponding to the bound
states identified in Ref. [23, 24, 25]. Here the plus sign is for
$\Gamma_{R}=0$ and minus for $\Gamma_{L}=0$.

Figure 4: (a) Disapperance of the branch connecting to the gapped region. The
peak is a well-defined for $K$ near the gapped region, but disappear as $K$
decreases, rendering the resonance ambiguous. (b) Resonances in the vicinity
of $K=0$. As $K\rightarrow 0$ the peak of the resonance converges the
theoretical value at $K=0$, marked with a dashed line. The width of the
resonance increases linearly with $K$. All curves have been normalized to a
peak value of 1. For both plots $\Gamma_{L}/\Gamma_{R}=1$ and $k_{0}=1.2$.

### The resonance states.

A different family of states is obtained if $\omega^{K}(z)=\omega$ has a
single solution, $z_{b}$, with $\mathinner{\\!\left\lvert
z_{b}\right\rvert}<1$ (the conjugate root $z_{b}^{-1}$ is excluded) and two
roots of unit magnitude denoted by $e^{\pm iq}$. In this case, it is
impossible to construct an eigenstate out of just two of the three states. By
combining all three states we are, however, always able to find a proper
superposition that fulfills the two restrictions imposed by Eq. (9). These
solutions we write in the form

$|\psi\rangle=C|z_{b}\rangle_{\textrm{N}}+|e^{iq}\rangle+e^{i\phi}|e^{-iq}\rangle$
(12)

where $|z_{b}\rangle_{\textrm{N}}=\sqrt{|z_{b}|^{-2}-1}|z_{b}\rangle$ is the
normalized version of $|z_{b}\rangle$. $C$ is a factor that measures how much
weight the localized state has relative to the propagating states and $\phi$
is a phase shift. When we vary $\omega$ we see a clear peak in $|C|^{2}$ and a
change of in $\phi$ by $2\pi$ around the peak, as shown in Fig 2(b). This
behaviour matches a scattering resonance, and we shall therefore refer to
these states as resonance states.

For any given $K$, the range in energy bounded by $\omega^{K}(\pm 1)$, where
$\mathinner{\\!\left\lvert z_{b}\right\rvert}<1$, allows resonance states. In
Fig. 2(c,d) we show the location of the peaks of $|C|^{2}$ and also mark the
width of the peaks. These resonances come in a number of different branches.
For concreteness we discuss these for the non-chiral case in Fig. 2(c).

One branch of resonances connects to the bound state at $K=0$. For these
states the width of the resonance approach zero for $K\rightarrow 0$, see Fig.
4 (b). The energy of this branch diverges for $K\rightarrow k_{0}$ (and $\pi-
k_{0}$), approaching the lower border of the blue region in Fig. 2(c). In this
limit, we find that $z_{b}$ tends towards unity while the width goes to zero.
These scattering resonances thus become weakly localized but long-lived.

Another branch directly connects to the bound states in the gapped region at
$k_{0}$. This branch displays clear features of scattering resonances, with a
width going to zero, when $K$ is close to the bound state regime. However,
this feature becomes ambiguous when $K$ moves further away. To illustrate
this, we focus on the region $K<k_{0}$. We consider three examples
$K=0.4,0.5,$ and $0.6$ with $k_{0}=1.2$ and plot $|C|^{2}$ as a function of
$\omega$ in Fig. 4 (a). For $K=0.6$, $|C|^{2}$ exhibits a peak. As $K$
decreases, however, the peak becomes increasingly ill-defined, until it has
completely disappeared at $K=0.4$, illustrating the fading of the resonance
states in Fig. 2(c). Additionally, Fig. 4 (a) also shows a divergence of
$\mathinner{\\!\left\lvert C\right\rvert}^{2}$ near the edge. This divergence
is accompanied by $\mathinner{\\!\left\lvert z_{b}\right\rvert}\rightarrow 1$,
and hence does not signify strong binding.

A third type of branches appears in the region below the gap. If we consider
the stable bound states to have a left and a right moving branch, these
resonances represent the continuation of each of these branches. Unlike the
branch discussed above, these do not connect to the bound state, but fade away
as they approach.

At last, we consider the situation as we approach the chiral limit. The chiral
case is special also for the single-photon states. As shown in Fig. 2(a) the
upper and lower bands of the single particle states tend to merge together
when the chirality increases and finally close the gap in the chiral limit.
Consequently, the different two-photon branches also tend to merge and the
resonances become narrower, until finally they reduce to the bound states of
the chiral limit, see Fig. 2 (d). Seen from this perspective, the non-chiral
limit [Fig. 2 (c)] can also be understood as the interplay between a left and
a right moving branch from the chiral case.

###  Conclusion and Outlook.

We have identified the essential physics of photon-bound states for emitters
of arbitrary chirality. The bound state solutions come in two categories: true
photonic bound states and scattering resonances. The latter represent a novel
phenomena for two-level systems, not present in the chiral case. Our extension
to the non-chiral regime paves the way for explorations of photon bound states
in a much wider range of physical system, including, e.g. the microwave regime
with superconducting systems. Furthermore, our results represents the first
steps towards more general explorations of many-body dynamics of photons, e.g.
strongly interacting photon fluids.

### Note added.

During the final stages a related preprint reported numerical results
reminiscent of the result reported her [44].

###### Acknowledgements.

We are grateful to Björn Schrinski, Sahand Mahmoodian, Thomas Pohl, Giuseppe
Calajo, Darrick E. Chang and Klemens Hammerer for useful discussion. We
acknowledge the support of Danmarks Grund- forskningsfond (DNRF 139, Hy-Q
Center for Hybrid Quantum Networks).

## References

  * d’Enterria and da Silveira [2013] D. d’Enterria and G. G. da Silveira, Observing light-by-light scattering at the large hadron collider, Phys. Rev. Lett. 111, 080405 (2013).
  * Hacker  _et al._ [2016] B. Hacker, S. Welte, G. Rempe, and S. Ritter, A photon–photon quantum gate based on a single atom in an optical resonator, Nature 536, 193 (2016).
  * Turchette  _et al._ [1995] Q. A. Turchette, C. J. Hood, W. Lange, H. Mabuchi, and H. J. Kimble, Measurement of conditional phase shifts for quantum logic, Phys. Rev. Lett. 75, 4710 (1995).
  * Bishop  _et al._ [2009] L. S. Bishop, J. Chow, J. Koch, A. Houck, M. Devoret, E. Thuneberg, S. Girvin, and R. Schoelkopf, Nonlinear response of the vacuum rabi resonance, Nature Physics 5, 105 (2009).
  * Maser  _et al._ [2016] A. Maser, B. Gmeiner, T. Utikal, S. Götzinger, and V. Sandoghdar, Few-photon coherent nonlinear optics with a single molecule, Nature Photonics 10, 450 (2016).
  * Tiarks  _et al._ [2018] D. Tiarks, S. Schmidt-Eberle, T. Stolz, G. Rempe, and S. Dürr, A photon–photon quantum gate based on rydberg interactions, Nature Physics 15, 124 (2018).
  * Thompson  _et al._ [2017] J. D. Thompson, T. L. Nicholson, Q.-Y. Liang, S. H. Cantu, A. V. Venkatramani, S. Choi, I. A. Fedorov, D. Viscor, T. Pohl, M. D. Lukin, and V. Vuletić, Symmetry-protected collisions between strongly interacting photons, Nature 542, 206 (2017).
  * Le Jeannic  _et al._ [2021] H. Le Jeannic, T. Ramos, S. F. Simonsen, T. Pregnolato, Z. Liu, R. Schott, A. D. Wieck, A. Ludwig, N. Rotenberg, J. J. García-Ripoll, and P. Lodahl, Experimental reconstruction of the few-photon nonlinear scattering matrix from a single quantum dot in a nanophotonic waveguide, Phys. Rev. Lett. 126, 023603 (2021).
  * Tresp  _et al._ [2016] C. Tresp, C. Zimmer, I. Mirgorodskiy, H. Gorniaczyk, A. Paris-Mandoki, and S. Hofferberth, Single-photon absorber based on strongly interacting rydberg atoms, Phys. Rev. Lett. 117, 223001 (2016).
  * Firstenberg  _et al._ [2013] O. Firstenberg, T. Peyronel, Q.-Y. Liang, A. V. Gorshkov, M. D. Lukin, and V. Vuletić, Attractive photons in a quantum nonlinear medium, Nature 502, 71 (2013).
  * Sun  _et al._ [2018] S. Sun, H. Kim, Z. Luo, G. S. Solomon, and E. Waks, A single-photon switch and transistor enabled by a solid-state quantum memory, Science 361, 57 (2018).
  * Lodahl  _et al._ [2015] P. Lodahl, S. Mahmoodian, and S. Stobbe, Interfacing single photons and single quantum dots with photonic nanostructures, Rev. Mod. Phys. 87, 347 (2015).
  * Thompson  _et al._ [2013] J. D. Thompson, T. G. Tiecke, N. P. de Leon, J. Feist, A. V. Akimov, M. Gullans, A. S. Zibrov, V. Vuletić, and M. D. Lukin, Coupling a single trapped atom to a nanoscale optical cavity., Science 340, 1202 (2013).
  * Yu  _et al._ [2019] S.-P. Yu, J. Muniz, C.-L. Hung, and H. Kimble, Two-dimensional photonic crystals for engineering atom–light interactions, PNAS; Proceedings of the National Academy of Sciences 116, 12743 (2019).
  * Liang  _et al._ [2018] Q.-Y. Liang, A. V. Venkatramani, S. H. Cantu, T. L. Nicholson, M. J. Gullans, A. V. Gorshkov, J. D. Thompson, C. Chin, M. D. Lukin, and V. Vuletić, Observation of three-photon bound states in a quantum nonlinear medium, Science 359, 783 (2018).
  * Prasad  _et al._ [2020] A. S. Prasad, J. Hinney, S. Mahmoodian, K. Hammerer, S. Rind, P. Schneeweiss, A. S. Sørensen, J. Volz, and A. Rauschenbeutel, Correlating photons using the collective nonlinear response of atoms weakly coupled to an optical mode, Nature Photonics 14, 719 (2020).
  * Chen  _et al._ [2013] W. Chen, K. M. Beck, R. Bücker, M. Gullans, M. D. Lukin, H. Tanji-Suzuki, and V. Vuletić, All-optical switch and transistor gated by one stored photon, Science 341, 768 (2013).
  * Chang  _et al._ [2014] D. E. Chang, V. Vuletić, and M. D. Lukin, Quantum nonlinear optics — photon by photon, Nature Photonics 8, 685 (2014).
  * Duan  _et al._ [2001] L.-M. Duan, M. D. Lukin, J. I. Cirac, and P. Zoller, Long-distance quantum communication with atomic ensembles and linear optics, Nature 414, 413 (2001).
  * Roy  _et al._ [2017] D. Roy, C. M. Wilson, and O. Firstenberg, Colloquium: Strongly interacting photons in one-dimensional continuum, Rev. Mod. Phys. 89, 021001 (2017).
  * Sheremet  _et al._ [2021] A. S. Sheremet, M. I. Petrov, I. V. Iorsh, A. V. Poshakinskiy, and A. N. Poddubny, Waveguide quantum electrodynamics: collective radiance and photon-photon correlations (2021), arXiv:2103.06824 [quant-ph] .
  * Mahmoodian  _et al._ [2020] S. Mahmoodian, G. Calajó, D. E. Chang, K. Hammerer, and A. S. Sørensen, Dynamics of many-body photon bound states in chiral waveguide qed, Physical Review X 10, 031011 (2020).
  * Yudson [1985] V. Yudson, Dynamics of integrable quantum systems, Zh. Eksp. Teor. Fiz 88, 1757 (1985).
  * Shen and Fan [2007a] J.-T. Shen and S. Fan, Strongly correlated two-photon transport in a one-dimensional waveguide coupled to a two-level system, Physical review letters 98, 153003 (2007a).
  * Shen and Fan [2007b] J.-T. Shen and S. Fan, Strongly correlated multiparticle transport in one dimension through a quantum impurity, Physical Review A 76, 062709 (2007b).
  * Lodahl  _et al._ [2017] P. Lodahl, S. Mahmoodian, S. Stobbe, A. Rauschenbeutel, P. Schneeweiss, J. Volz, H. Pichler, and P. Zoller, Chiral quantum optics, Nature 541, 473 (2017).
  * Zhang  _et al._ [2020] Y.-X. Zhang, C. Yu, and K. Mølmer, Subradiant bound dimer excited states of emitter chains coupled to a one dimensional waveguide, Phys. Rev. Research 2, 013173 (2020).
  * Poddubny [2020] A. N. Poddubny, Quasiflat band enabling subradiant two-photon bound states, Physical Review A 101, 043845 (2020).
  * Douglas  _et al._ [2016] J. S. Douglas, T. Caneva, and D. E. Chang, Photon molecules in atomic gases trapped near photonic crystal waveguides, Phys. Rev. X 6, 031017 (2016).
  * Zhong  _et al._ [2020] J. Zhong, N. A. Olekhno, Y. Ke, A. V. Poshakinskiy, C. Lee, Y. S. Kivshar, and A. N. Poddubny, Photon-mediated localization in two-level qubit arrays, Phys. Rev. Lett. 124, 093604 (2020).
  * Ke  _et al._ [2019] Y. Ke, A. V. Poshakinskiy, C. Lee, Y. S. Kivshar, and A. N. Poddubny, Inelastic scattering of photon pairs in qubit arrays with subradiant states, Phys. Rev. Lett. 123, 253601 (2019).
  * Ke  _et al._ [2020] Y. Ke, J. Zhong, A. V. Poshakinskiy, Y. S. Kivshar, A. N. Poddubny, and C. Lee, Radiative topological biphoton states in modulated qubit arrays, Phys. Rev. Research 2, 033190 (2020).
  * Iorsh  _et al._ [2020] I. Iorsh, A. Poshakinskiy, and A. Poddubny, Waveguide quantum optomechanics: Parity-time phase transitions in ultrastrong coupling regime, Phys. Rev. Lett. 125, 183601 (2020).
  * Lang  _et al._ [2020] J. Lang, D. Chang, and F. Piazza, Interaction-induced transparency for strong-coupling polaritons, Phys. Rev. Lett. 125, 133604 (2020).
  * Asenjo-Garcia  _et al._ [2017] A. Asenjo-Garcia, M. Moreno-Cardoner, A. Albrecht, H. J. Kimble, and D. E. Chang, Exponential improvement in photon storage fidelities using subradiance and “selective radiance” in atomic arrays, Phys. Rev. X 7, 031024 (2017).
  * Albrecht  _et al._ [2019] A. Albrecht, L. Henriet, A. Asenjo-Garcia, P. B. Dieterle, O. Painter, and D. E. Chang, Subradiant states of quantum bits coupled to a one-dimensional waveguide, New J. Phys. 21, 025003 (2019).
  * Zhang and Mølmer [2019] Y.-X. Zhang and K. Mølmer, Theory of subradiant states of a one-dimensional two-level atom chain, Phys. Rev. Lett. 122, 203605 (2019).
  * Zhang and Mølmer [2021] Y.-X. Zhang and K. Mølmer, Universal free-fermion multiply-excited eigenstates and their experimental signatures in 1d arrays of two-level atoms (2021), arXiv:2109.04540 [quant-ph] .
  * Poshakinskiy  _et al._ [2021] A. V. Poshakinskiy, J. Zhong, Y. Ke, N. A. Olekhno, C. Lee, Y. S. Kivshar, and A. N. Poddubny, Quantum hall phases emerging from atom–photon interactions, npj Quantum Information 7, 10.1038/s41534-021-00372-8 (2021).
  * Iversen and Pohl [2021] O. A. Iversen and T. Pohl, Strongly correlated states of light and repulsive photons in chiral chains of three-level quantum emitters, Physical Review Letters 126, 083605 (2021).
  * Caneva  _et al._ [2015] T. Caneva, M. T. Manzoni, T. Shi, J. S. Douglas, J. I. Cirac, and D. E. Chang, Quantum dynamics of propagating photons with strong interactions: a generalized input–output formalism, New Journal of Physics 17, 113001 (2015).
  * [42] _Supplemental Material_.
  * Schrinski and Sørensen [2021] B. Schrinski and A. S. Sørensen, In preparation, (2021).
  * Calajo and Chang [2021] G. Calajo and D. E. Chang, Few- and many-body photon bound states in quantum nonlinear media: a spin-model approach (2021), arXiv:2110.00050 [quant-ph] .

Supplemental Materials: Photonic Bound States and Scattering Resonances in
Waveguide QED

## Solving $\omega^{K}$ as a Quartic Equation

The necessary functions defined in the main text have the explicit forms

$\displaystyle\begin{split}\omega^{K}(z)=&\frac{2z\Gamma_{L}\sin(k_{0}+K)}{1+z^{2}-2z\cos(k_{0}+K)}+\frac{2z\Gamma_{R}\sin(k_{0}-K)}{1+z^{2}-2z\cos(k_{0}-K)}\\\
g_{+}(z)=&2z\Gamma_{L}\frac{z-\cos(k_{0}+K)}{1+z^{2}-2z\cos(k_{0}+K)}\\\
g_{-}(z)=&2z\Gamma_{R}\frac{z-\cos(k_{0}-K)}{1+z^{2}-2z\cos(k_{0}-K)}\end{split}$
(S1)

We are able to recast the equation $\omega^{K}(z)=\omega$ as a quartic
polynomial equation by multiplying both sides by the two denominators. It
leads to a quartic equation in the general form of

$c_{4}z^{4}+c_{3}z^{3}+c_{2}z^{2}+c_{1}z+c_{0}=0$ (S2)

where the coefficients are

$\displaystyle\begin{split}c_{4}&=c_{0}=\omega,\\\
c_{3}&=c_{1}=-2\bigg{[}\omega(c_{+}+c_{-})+\Gamma_{L}s_{+}+\Gamma_{R}s_{-}\bigg{]},\\\
c_{2}&=2\bigg{[}\omega(1+2c_{+}c_{-})+2(\Gamma_{L}s_{+}c_{-}+\Gamma_{R}s_{-}c_{+})\bigg{]},\end{split}$
(S3)

with $s_{\pm}=\sin(k_{0}\pm K)$ and $c_{\pm}=\cos(k_{0}\pm K)$. The
fundamental theorem of algebra implies that a quartic equation has four
solutions. Formulae for these solutions are well known for almost four
centuries.

The symmetry of the coefficients implies that if $z_{1}$ is a solution, so is
$z^{-1}_{1}$. Therefore, the four solutions can be denoted by $z_{1,2}$ and
$z^{-1}_{1,2}$. We define $z_{1}+z_{1}^{-1}=u_{1}$ and
$z_{2}+z_{2}^{-1}=u_{2}$, and obtain that

$\displaystyle u_{1}+u_{2}$ $\displaystyle=-c_{3}/\omega$ (S4) $\displaystyle
u_{1}u_{2}$ $\displaystyle=c_{2}/\omega-2$

Then it is straightforward to firstly solve for $u_{1/2}$, and hence for
$z_{1/2}$ as well.