text:
Universal and Robust Distributed Network Codes

# Universal and Robust Distributed Network Codes

\authorblockNTracey Ho†, Sidharth Jaggi‡, Svitlana Vyetrenko† and Lingxiao Xia‡ \authorblockA† California Institute of Technology, ‡ The Chinese University of Hong Kong
†{tho, svitlana}@caltech.edu, ‡{jaggi, lingxiao}@ie.cuhk.edu.hk
###### Abstract

Random linear network codes can be designed and implemented in a distributed manner, with low computational complexity. However, these codes are classically implemented [1] over finite fields whose size depends on some global network parameters (size of the network, the number of sinks) that may not be known prior to code design. Also, if new nodes join the entire network code may have to be redesigned.

In this work, we present the first universal and robust distributed linear network coding schemes. Our schemes are universal since they are independent of all network parameters. They are robust since if nodes join or leave, the remaining nodes do not need to change their coding operations and the receivers can still decode. They are distributed since nodes need only have topological information about the part of the network upstream of them, which can be naturally streamed as part of the communication protocol.

We present both probabilistic and deterministic schemes that are all asymptotically rate-optimal in the coding block-length, and have guarantees of correctness. Our probabilistic designs are computationally efficient, with order-optimal complexity. Our deterministic designs guarantee zero error decoding, albeit via codes with high computational complexity in general. Our coding schemes are based on network codes over “scalable fields”. Instead of choosing coding coefficients from one field at every node as in [1], each node uses linear coding operations over an “effective field-size” that depends on the node’s distance from the source node. The analysis of our schemes requires technical tools that may be of independent interest. In particular, we generalize the Schwartz-Zippel lemma [2] by proving a non-uniform version, wherein variables are chosen from sets of possibly different sizes. We also provide a novel robust distributed algorithm to assign unique IDs to network nodes.

## I Introduction

The paradigm of network coding allows each node in a network to process information in a non-trivial manner. As shown in [3, 4, 5], even if intermediate nodes simply perform linear operations over some finite field, the resulting network codes can be information-theoretically rate-optimal for a large class of communication problems. In particular algorithms that design codes for multicast communication problems, wherein each of multiple sinks requires the same information from a source node, have been well-studied. The design algorithms in [6, 7] are deterministic and centralized, and result in network codes with zero-error. In contrast the algorithms in [1, 8] are decentralized and probabilistic, and for any result in network codes that “fail” with probability at most . Both these types of design algorithms (and the resulting network codes) are computationally tractable.

However, for all current network code design algorithms, some information network parameters is necessary prior to the code design, to determine the size of the finite field over which linear network coding is performed. In particular, the centralized algorithms in [6, 7] require prior knowledge of the entire network, and even the decentralized algorithms in [1, 8] require knowledge of the network size and the number of sinks – if these parameters are unavailable, code design cannot proceed with any guarantees of correctness, hence prior designs are not universal. Also, in the case of dynamically changing network topologies, if even one new node joins the network the entire network code may need to be updated due to a change in the field-size required, hence such codes are also not robust.

In this work we develop the first universal and robust distributed linear codes that are independent of all network parameters, and are designed to satisfy a pre-specified tolerance on the error-probability (defined as the probability that the linear transform from the source to some sink is not invertible). The essential idea behind our design is that of using “scalable fields”111Scalable fields do not mean embeddings of, for example, into , since arithmetic operations are defined differently over different fields, and hence the overall transform would not be linear. . Linear coding operations are chosen from nested finite subsets of an appropriate infinite field – in particular we choose the field of rational functions over , i.e., the field whose elements are ratios of binary polynomials. Operations over this field can be implemented via binary filters (or equivalently, convolutional codes) at each node. For instance, a node that chooses to implment the operation on an incoming binary sequence to generate an outgoing binary sequence would set . Convolutional network coding as a model of linear network coding has been well-studied (see for example [9]).

As information percolates down the network, each node makes its own estimate of the “effective field size”, i.e., the size of the subset of from which that node should choose its coding operations, so as to meet the guarantee on the pre-specified tolerance on the overall error-probability. Our codes are able to perform this book-keeping despite having access only to information that can be percolated down the network at rates that are asymptotically negligible in the block-length – like standard distributed network codes, our codes are also asymptotically rate-optimal.

Our results are as follows. In Section III we prove a generalization of the Schwartz-Zippel lemma [2] that is useful as a technical tool in some of our code constructions; it may also be of independent interest for other universal algorithms.

In Section IV we present probabilistic universal and robust codes. That is, given any and any network, we present codes that guarantee that the linear transform from the source to each sink is invertible with probability at least – hence our codes are universal. Further, even if nodes join or leave, pre-existing nodes do not need to change their coding operations to preserve the same guarantee of correctness – hence our codes are robust. We present two such codes. The first code is independent of network size, but does depend on the number of sinks. We present it primarily for expository purposes, since its presentation is simpler than that of our second set of codes, which are independent of all network parameters, including the number of sinks. Both these sets of codes base their choices of coding operations based on their distance from the source node. While the effective field-size over which our codes operate, and hence the computational complexity of our codes, are larger than those of prior distributed designs [1, 8], the complexity of implementing them is still polynomial in network parameters. Also, we present in Theorem 3 a class of networks that demonstrates that our codes have essentially order-optimal computational complexity for universal codes.

In Section V we consider deterministic universal and robust codes. As a technical tool we first discuss a decentralized algorithm to distribute unique IDs to each node in a robust manner – even if a new node joins we guarantee that it too can be given an ID that is distinct from all others in the network. Building on this tool, and a novel use of Cantor’s classical mapping between and for any finite , we design zero-error decentralized codes that are independent of all network parameters, and robust to changes in network topology. We provide two constructions. Our first construction, also primarily expository, is just for codes of rate , and is computationally efficient to design and implement. Our second construction is for arbitrary rate codes. This generalization comes at the cost of exponentially increasing the implementation complexity, compared to our other constructions222We distinguish between the computational complexity of design and that of implementation. The former refers to the the computational cost of designing the coding operations at each node, and is a one-time cost. The latter corresponds to the computational cost incurred by each node as it implements the pre-designed coding operations, and is a repeated cost for each packet transmitted by that node. All our codes have design complexity that is at most polynomial in the network parameters. Further, most of our designed codes codes have implementation complexity that is also polynomial in network parameters; the only exception is the last of the proposed designs corresponding to the general design for zero-error universal and robust distributed linear codes. .

We note that all our algorithms provide guarantees of correctness as long as the source transmits information at a rate no greater than can be supported by the network, i.e., its min-cut. We view the process of determining this rate as a rate-control issue – our code designs are independent of the size of the min-cut.

### I-a Related work

The distributed random linear codes of [1, 8] require field-sizes to scale roughly as . As shown in [10], even with centralized design of network codes, the field size over which coding must be performed as at least .

As to universal codes (codes independent of some problem parameters), they have been well-studied in the classical information-theory setting (for instance in source coding [11] and channel coding [12]).

In the network coding setting, however, the literature is much sparser. The work of [5] proposes “robust network codes” that are resilient to network failure patterns. However, the field-size over which coding is performed depends on the number of failure patterns, and hence these codes are not truly universal. Further, the computational complexity of designing such codes is prohibitive. There is also significant work on network coding for packet erasure networks (for instance [13]). Our codes can tolerate all such errors.

The work of [14] examines “decentralized network coding” in which new nodes can join a network without disrupting pre-designed coding operations. Here, too, the field-size choice for the initial design depends on the size of the network. Further, the code designs are for special cases – either for rate- codes (analogous to the codes we present in Section V-C) or for networks with only two sink nodes.

A preliminary version of the work in Section V was previously in the thesis [15], and presented (but not published) in [16].

## Ii Notation and definitions

### Ii-a Network Model

In this paper, we adopt the single-source multicast network model of [5]. Let the network be represented by a directed acyclic333The work can be directly extended to multi-source multicast networks, and over networks that may contain cycles, as long as each source has a unique identifier. To ease notational and description complexity we omit details here graph . Here represents the set of nodes and the set of edges. The graph has a pre-specified source node and sink nodes . A directed edge from node to node is said to have tail (denoted ) and head (denoted ). The link is then said to be an incident outgoing link of and an incident incoming link of .

### Ii-B Communication Model

The communication goal is for the source to communicate identical information to each sink.

As is standard [5], we assume that each link carries one packet of information per time-step. This is reasonable since if some link’s capacity is less we may consider the link’s communication to be over multiple successive time-steps, and if the link’s capacity is greater we can subdivide it into multiple links. The packet-length in bits is denoted by .

The network capacity, denoted by , is the time-average of the maximum number of packets that can be delivered from the source to each sink simultaneously. It can be also expressed as the minimum of the min-cut from the source to each sink . The rate is the average number of information packets that the source generates per time-step, to be delivered to each sink over the network . Without loss of generality we assume that . Lastly, let denote the maximum capacity of any single link in the network.

### Ii-C Code Model

#### Ii-C1 Network code

The network code comprises of the encoders at the source and each node inside the network, and the decoders at each of the sinks. In particular we focus on linear network codes, i.e., codes where the source node, each internal node, and each sink performs linear combinations of information in packets on incident incoming links to generate packets on incident outgoing links. Specifically we consider the class of convolutional linear operations, well-studied in classical coding theory, that we reprise below. The base-field for arithmetic is chosen to be , hence all operations described below are binary.

#### Ii-C2 Convolutional network code

Recall that the -transform [17] of any sequence of bits is given by the polynomial , denoted . Further, recall that the output of the convolution operation between two sequences444Terms and are respectively set to zero for and . and is defined as the length- sequence whose th term equals . Lastly, it is well-known that the -transform of equals .

Convolutional codes [17] have long been used in point-to-point communication scenarios. The idea of using convolutional codes for network coding (in networks with cycles) was foreshadowed in [3], and made explicit in [5] (who also noted that such an algebraic model for coding operations can help kill two birds with one stone, i.e., it can also help model delays in networks). The work of Erez et al. (see for example [9]) gave the first efficient designs for convolutional network codes, i.e., codes over . In our work, affords the advantage that it allows for coding operations to be chosen from a potentially unbounded set, which helps us circumvent the difficulty that we do not know the network’s parameters in advance.

The source’s packets are denoted by – each is a length- bit-vector. The corresponding -transforms are denoted . Collectively they are represented by the length- vector of polynomials . Each edge carries the packet , and its -transform is denoted . Lastly, the -transform of the packets on incident incoming links to any sink are denoted by the vector . We henceforth refer to a sequence and its -transform interchangeably.

Let , and be three nodes such that there is at least one edge from to and at least one edge from to . We use a -tuple to denote a coding choice for such nodes – specifically, refers to the local coding coefficient of the convolutional operation on the information on the th edge from to to the th edge from to . The choices of values of the local coding coefficients are code design parameters whose specifications are the primary objective of subsequent sections. Let be a specific edge from to , and denote a dummy variable that ranges over all edges incoming to (and hence is indexed by the pair ). Thus the convolutional operation that is performed at node comprises of taking linear combinations of the information with the appropriate over all edges incident incoming to node , to generate the information on the edge incident outgoing from . To simplify notation, we henceforth write simply as with the understanding that index the appropriate -tuple. Thus the linear transform at each node can be written symbolically as

 Ye(z)=∑e′βe′,e(z)Ye′(z).

Since all the linear operations performed by the network can be represented via operations over polynomials over the binary field, we henceforth consider all arithmetic to be over the field of rational functions [5] over , denoted by . The elements of this field are of the form , where both and are binary polynomials. Linear codes over this field have been well-studied in the convolutional coding literature [17].

As in classical distributed network codes [1], the codes in this work are distributed, i.e., the choice of a value for at node can depend only on its local parameters , and the corresponding parameters of the nodes upstream of node . Since we consider only directed acyclic networks in this work, this imposes a significant design constraint, since nodes that cannot directly communicate with each other over the network cannot coordinate their coding choices.

One idea of [1] that we too use is the idea of having “short headers” in each transmitted packet. Specifically, each packet (containing bits) transmitted by the source, also contains the linear transformation induced by the network from the source to that packet – as in [1] these transforms are computed in a distributed manner and percolated down the network along with the payload information at an asymptotically negligible rate. For every , let be the network transfer matrix from to – these too can be computed in a distributed manner. Let be the overall network transfer matrix from to formed as . Let and denote the determinants of and respectively.

Our codes are either probabilistic or deterministic depending on whether local coding coefficients are chosen probabilistically or deterministically. The error probability is the probability over choices of local coding coefficients that for each source message, at least one sink’s reconstruction of at least one possible message from the source is inaccurate. For linear network codes this happens if and only if the transfer matrix from the source to each sink is invertible. Rate is said to be achievable if for any and there exists a coding scheme of block length with rate and error probability . In particular, we require our deterministic network codes to be zero-error, i.e., to have error probability be zero.

## Iii The Generalized Schwartz-Zippel Lemma

The classical Schwartz-Zippel lemma [2] provides an upper bound on the probability that when variables of a polynomial are chosen uniformly at random from a field, then the polynomial evaluates to zero.

Recall that the degree of a variable in a polynomial is the maximal exponents of in its non-zero terms. Further, recall that the degree of a polynomial itself is the maximal value among the sum of the exponents of all its non-zero terms. Note that .

###### Lemma 1 (Schwartz-Zippel lemma [2]).

Let be a non-zero polynomial of degree over a field . Let be a finite subset of , and the value of each be selected independently and uniformly at random from . Then the probability that the polynomial equals zero is at most

The Schwartz-Zippel lemma is a useful tool in the analysis of random linear network codes (for instance [1]). A random linear network code causes an error if and only if one of the transfer matrices from the source to the destination is singular. This in turn happens if and only if the product of the determinants of these transfer matrices equals zero. But this product of determinants may be viewed as a polynomial whose variables consist of the local coding coefficients at each node. Hence the Schwartz-Zippel lemma provides an upper bound on the probability of error of a random linear network code.

In this work we are interested in a generalization of the Schwartz-Zippel lemma, for polynomials whose variables are chosen from different subsets of . We prove:

###### Lemma 2.

Let be a non-zero polynomial over a field . For all , let be a finite subset of , the degree of in be , and the value of each be selected independently and uniformly at random from . Then the probability that the polynomial equals zero is at most

Proof: Given in Appendix -A
Note : Neither Lemma 1 nor Lemma 2 put any restriction on the size of the field , as long as the appropriate subsets from which variables chosen are finite.
Note : A related but inequivalent generalization of the Schwartz-Zippel lemma was proved in [18].
The utility of this proof is that it allows for the variables comprising the polynomial to be chosen non-uniformly. This is integral to the proof techniques in this work, wherein we choose local coding coefficients over progressively larger sets, depending on how far from the source they are.

## Iv Probabilistic designs

In this section we describe two probabilistic designs of universal distributed robust network codes. In particular, given any , we present schemes such that the overall error probability of the code is at most .

Our first scheme is independent of the size (number of nodes/edges) of the network, but does requires that the source has a priori knowledge of the number of sinks it shall be required to service. Hence we say it is only weakly universal. Our purpose in presenting this scheme is primarily expository, since the proof is significantly easier than that of the second scheme – it helps set the stage for the second scheme.

The second scheme is strongly universal and is independent of all network parameters, including the number of sinks.

We first describe some useful preprocessing steps relevant for both of our schemes.

### Iv-a Graph transformation

We find it desirable to work over a transformed graph () rather than the original graph (). This transformation can be done locally at each node, and results in a graph with some useful properties. In particular, we use the work of [7] which demonstrates the equivalence between general network coding problems and those over “low-degree” networks where each node has degree at most three. In particular, nodes in the reduced network either have one incident incoming edge and at most two incident outgoing edges (in which case they broadcast the incoming information on incident outgoing edges, and hence are called broadcasting nodes). Otherwise, they have two incident incoming edges and one incident outgoing edge (in which case they code the information on the incident incoming edges to generate information transmitted on the incident outgoing edge, and hence are called coding nodes). (See Figure 3(b).) This equivalence is useful for our probabilistic algorithms since it allows us to effectively enumerate networks. We change the equivalence relationship of [7] slightly as described below so as to make it robust to nodes joining the original network. That is, in our equivalence relationship, nodes can join the original network while only locally perturbing the “low-degree” network.

The transformation is as follows. For every node we construct a virtual robust gadget (see Figure 1 for an example555We thank Michael Langberg for providing the template for Figures 1 and 2).

Suppose has incoming links and outgoing links. Corresponding each incoming link we construct a binary tree whose root is connected to that incoming link, and which has leaves. Similarly, corresponding to each outgoing link we construct an inverted binary tree whose root is connected to that outgoing link, and which has leaves. The last leaf node of each binary tree is called a virtual node, and the other leaf nodes are called connection nodes. We then connect connection nodes so that there is exactly one path from each incoming link to each outgoing link (the connection order does not matter).

Henceforth, all algorithms in Section IV shall convert the original graph to the virtual graph above as a pre-processing step, and all computations shall be over this virtual graph. Also, as part of normal communication each node in the virtual graph estimates its depth , i.e., the length of the shortest path from the source to itself. This can be done by any of a variety of distributed shortest-path algorithms over acyclic graphs, such as the Bellman-Ford algorithm [19].

### Iv-B Weakly universal design

The essential idea behind our first scheme is as follows. Each node having estimated its depth, it then chooses a subset of whose size scales exponentially in this depth from which it pick its coding coefficients uniformly at random. We then show that the probability of error due to information being lost at any depth decays geometrically in the depth, and hence by the union bound the overall probability of error can be controlled so as not to exceed any desired .

WUP() (Weakly Universal Probabilistic) Code:

• Each coding node in the vertex-set of the virtual graph chooses two local coding coefficients corresponding to the two incoming links uniformly at random from the set of polynomials of degree at most .888This choice of the degree bound is simply to ease the analysis of Theorem 1. All logarithms are binary. Also, for simplicity of presentation we assume that is an integer – if not, we may round up to the nearest integer with negligible error in our estimate of parameters.

###### Theorem 1.

For any , WUP() has error probability at most .

Proof: Recall that represents the determinant of the transfer matrix from the source to sink . As noted in [5], the network code is error-free if and only if the polynomial comprising of the product of the determinants over all sinks (with the network’s local coding coefficients as variables) is non-zero. To evaluate the probability that this is the case given the random assignment of local coding coefficients in WUP() , we use Lemma 2. Specifically, Each variable in Lemma 2 corresponds to a local coding coefficient. We group the coding coefficients in terms of the depths of the nodes at which they are used. But there are at most coding nodes at any depth in the virtual graph, since after the transformation in Section IV-A the fast possible growth-rate for the new graph would be if it corresponded to parallel binary trees – one for each of the source’s messages. Hence there are at most local coding coefficients at that depth. Also, Corollary in [1] shows that the degree of each local coding coefficient in is bounded from above by . By construction in WUP() each virtual node in the network chooses local coding coefficients uniformly at random from the set of polynomials of degree at most . This set is a subset of of size at most . Summing over all possible local coding coefficients at all possible (possibly infinite) depths and substituting the appropriate parameters into Lemma 2, the error probability of the network code is bounded from above by

 Pr(∏t∈T|Tt|)=0) ≤ ∞∑Δ=12R2Δ|T|ϵ2R|T|22Δ = ∞∑Δ=1ϵ2Δ = ϵ. □

The computational complexity of WUP() codes is polynomial in network parameters and , and the achievable rates approach the network capacity asymptotically in the block-length. Further, our codes are robust to links joining and leaving. Since the analysis of these properties is very similar to that of the codes in Section IV-C, we delay discussion to the end of that section.

### Iv-C Strongly universal design

We now present design of probabilistic robust linear network codes that are strongly universal, i.e., independent of all network parameters. This obviates the requirement of knowledge of of the codes in Section IV-B. The idea underlying the construction in this section is as follows. For the purpose of analysis, for each sink we identify a set of edge-disjoint paths, and estimate the probability that the information on these edge-disjoint paths remains invertible as information flows through the network. In particular, for any sink and any depth in the network we identify the set of edges in these edge-disjoint paths that must contain linearly independent combinations of the source’s information. We call such sets of edges flow-cuts. It turns out that the number of flow-cuts at any depth is in fact independent of the number of sinks, and further, a bound on this number at each depth can be computed locally. Thus sinks can be classified according flow-cuts. Hence, instead of trying to ensure that the linear transform to each sink is invertible as in Theorem 1, nodes at each depth simply try to ensure that the linear transform to each flow-cut is invertible. To analyze the probability of non-invertibility at each flow-set an alternative to the end-to-end analysis of the probability of error used in [1, 8] is required. Here we use the proof technique of [20], which analyzes the probability that information gets lost from one set of edges in the network to a neighbouring set of edges.

SUP() (Strongly Universal Probabilistic) Code

• Each coding node at depth in the vertex-set of the virtual graph chooses two local coding coefficients corresponding to the two incoming links uniformly at random from the set of polynomials of degree at most .

Recall that by assumption the capacity of the network is at least . Hence there is a set of at least edge-disjoint paths that go from the source to each .

Corresponding to each such set of edge-disjoint paths, we define flow-cuts. A flow-cut is defined as a set of edges that have the property that each edge in the flow-cut is from a distinct edge-disjoint path in . These flow-cuts are useful since we intend to analyze the linear (in)dependence of information flowing through the edges in each flow-cut – if the information on each edge in a flow-cut is linearly independent, then the source’s information can be retrieved from that flow-cut. Hence, we only need to inductively prove that no information is lost from one flow-cut to the “next” flow-cut, appropriately defined as below999Similar intuition was used in the proofs of [6] and  [20], where they were called “frontier edge-sets”.Note that a flow-cut need not be a cut or a subset of it – for instance, it may include two edges on two edge-disjoint paths, such that one is incoming to a node, and the other is outgoing from it..

We define the depth of a flow-cut as the maximum depth of the head of any edge in it, i.e., . Further, we denote a flow-cut of depth by .

We then define a flow-set as an ordered set of flow-cuts with some properties. In particular, each flow-cut in a flow-set differs from the successive flow-cut in exactly one edge. Specifically, if one flow-cut in differs from the next flow-cut in in that some edge is replaced by another , then it must be the case that is the edge preceding in some path in the set of edge-disjoint paths . Intuitively, each flow-set captures successive snapshots of how information flow from the source to the sink .

Examples of flow-cuts and flow-sets are provided in Figure  4(b), based on the butterfly network in Figure 4(a).

Let be some flow-cut of depth to sink , and be the flow-cut immediately preceding101010Note that the depth of might be either or , since two successive flow-cuts differ in exactly one edge, which may or may not be the deepest edge in a flow-cut (if not, then both flow-cuts have the same depth; if so, the depth of the flow-cut can change by at most one). in flow-set . Let be the linear transform that the network imposes from the source to the edges in the flow-cut , and let be the rank of this transform. Correspondingly, let be the linear transform from to , and let be the rank of this transform. Then the following lemma gives an upper bound on the probability that choosing local coding coefficients according to the dictates of WUP() results in a loss of information in going from to .

###### Theorem 2.

For every , SUP() has error probability at most .

Proof: Note that of the two types of nodes in the virtual graph, the broadcasting nodes induce no additional error – if a flow-cut contains linearly independent packets, and one of the edges in the flow-cut is replaced with another edge at a broadcasting node, the information in the succeeding flow-cut remains unchanged. Thus from now on we focus only on coding nodes.

By construction the structure of the virtual graph is such that each node can have at most two outgoing edges, and further the source node is replicated times. Hence the maximum possible number of edges in the virtual graph up to a depth occurs when it comprises of parallel binary trees. But each binary tree has at most edges, hence the total number of edges in the virtual graph up to depth is at most . Also, the total number of flow-sets of depth is at most , which is bounded from above111111Since . Also, all exponents are base . by .

We use these bounds to bound from above the number of distinct type of coding choices a coding node at a certain depth faces. All our analysis now focuses on the specific following coding node . Let its incoming edges be and , and the outgoing edge be . Let edge belong to a flow-cut in flow-set going towards sink , and edge be an arbitrary other edge. Then the outgoing edge replaces in the flow-cut to produce flow-cut . Suppose is of depth . Then by the bounds in the preceding paragraph, the number of ways an arbitrary flow-cut of depth can result from the merger of a preceding flow-cut and an arbitrary edge of depth at most is at most , which equals

 exp((R+1)(Δ+1+logR)). (1)

Next, we estimate the probability that a coding node “loses information”. That is, we bound from above the probability that the number of linearly independent packets on the edges of a flow-cut is less than even though the immediately preceding flow-cut has linearly independent packets.

Say represents the matrix whose th row represents the linear combinations of the source’s messages on the th link in the flow-cut of depth . Correspondingly, let represent the matrix representing the linear transform from the source to the flow-cut immediately preceding in the flow-set , and suppose it is of full rank . Then the message on edge in flow-cut may be written as . (Recall that and are the edges incoming to , and are the corresponding messages carried by them, and and represent the local coding coefficients at node .) But by assumption is of full-rank, and hence the message may be written as a linear combination of the messages on the edges in flow-set . Thus the message on edge may be written as

 βe′,e(z)Ye′(z)+∑e(i)∈F′(t)γe(i),e(z)Ye′′(z),

for some . This in turn equals

 (βe′,e(z)+γe′′,e(z))Ye′(z)+∑e(i)∈F′(t):e(i)≠e′γe(i),e(z)Ye′′(z).

But the information on the links in other than is unchanged, and hence the only manner in which the messages on the edges in are linearly dependent is if the coefficient equals zero. But by the choice specified in SUP() the coding coefficients are chosen from the set of polynomials of degree at most – this set is of size . Lemma 2 then implies that the probability that the degree polynomial equals zero, is at most . Analogously to Theorem 1, taking the union bound over all possible coding operations at depth (for which (1) is an upper bound), and summing over all (possibly infinite) depths gives us that the overall probability of error is at most

 ∞∑Δ=12(R+1)(Δ+1+logR)ϵ2Δ+([(R+1)(Δ+1+logR)]) =∞∑Δ=1ϵ2Δ % = ϵ. □

### Iv-D Robustness

Due to the robust graph transformation described in Section IV-A, neither the addition nor the deletion of edges or nodes in the network causes problems with our proof. If new nodes are added to the network, the actual depth of some nodes in the network, say in particular, may decrease. However, we require each node to use in perpetuity the value of the depth it estimates in the first round of communication. This ensures that the bound on the number of coding nodes at a particular depth is not violated. Conversely, if nodes leave the network, the actual depth of may increase. Nonetheless, the bound on the number of coding nodes at a particular depth is still not violated, since the total number of nodes in a network has only decreased.

### Iv-E Complexity analysis

The complexity of both WUP() and SUP() scale with the corresponding degree of the polynomials chosen by nodes as coding coefficients.

For WUP() , by construction, the degree of the polynomials used as coding coefficients (as noted in [21] is a good proxy for the implementation complexity of codes) scales as the maximum depth of the virtual graph plus . But in the virtual graph each original node is replaced with a gadget with depth that is approximately the logarithm of the degree of the node, which in the worst case is at most121212Recall that denotes the maximum value for any edge’s capacity in the network. . Hence the maximum depth of the virtual graph is at most times the number of vertices in the original graph. Pulling it all together, the complexity of implementation scales as .

The corresponding redundancy the network introduces in the codes, arising from the delays introduced by each coding node, then scales at worst as the maximum depth of the virtual graph times the maximum degree of the polynomials used by any node, since each coding node in a path can introduce at most the maximal delay and delays along a path add up. Using the bounds above, this scales as .

A similar analysis shows that the complexity of implementation of SUP() scales as , and that the redundancy introduced by such codes scales as .

We now demonstrate that the implementation complexity of WUP() and SUP() is in fact order-optimal by demonstrating a class of networks for why any universal design requires computational complexity which is similar in order of magnitude to that of WUP() and SUP() . Our construction is inspired by that of [10]. Consider any universal -error linear network code, i.e., any network code that requires that each sink be able to reconstruct the source’s information with probability of error at most , even if the network topology is not known in advance.

###### Theorem 3.

There exists a class of networks for which the implementation complexity for any -error universal network code is .

Proof:

We construct a single-source multicast network that requires that for any universal code, coding operations must be chosen from a set that must be exponentially larger than would actually be needed if the topology were known in advance. Consider the “binary-tree-like” network demonstrated in Figure 5. The upper part of this graph comprises of a binary tree of depth , with the source located at the root of the tree, and hence leaf nodes. Each link of this binary tree has capacity . Next, each leaf node of this binary tree has a link of unit capacity leaving it to a corresponding forwarding node. Finally, we consider two possibilities. Either there are sinks, such that each sink is connected to a distinct subset of size two of the set of forwarding nodes, via unit capacity links to each of the two nodes in the subset (this is in the spirit of the combination networks examined in [10]). Or, there is only one sink node in the network, which is connected to two of these forwarding nodes (say and ) via links of unit capacity each.

As to coding strategies, each node in the binary tree part of the network can forward two linearly independent messages and on each of its outgoing links. Hence at depth each of the leaves of the binary tree have both and . Since neither of the two leaf node corresponding to or (say we call them and respectively) is aware of which of the two configurations the network is in, to be universal they must use coding operations that work for both configurations.

First we consider the case of , i.e., every message must be decoded correctly. Suppose the leaf nodes and choose to transmit the linear combinations and , or equivalently and (by setting for ). But the messages on each of the forwarding links must be linearly independent (to take into account the eventuality that the network is in the first configuration with sinks). Hence there must be at least choices for the s (one for each of the leaf nodes, minus one for the case when , which can be handled separately.) But if the set of possible coding operations is , then its implementation complexity must be at least . But this is . In contrast, if the network happened to be in the configuration with only one sink and this was known in advance, then each of and could simply forward one bit, for an implementation complexity of .

The case with -errors can be similarly analyzed, by allowing sinks to make errors a fraction of the time. A direct counting argument gives the required result.

## V Deterministic designs

In this section we describe two deterministic designs of universal distributed robust network codes that are zero-error131313Preliminary versions of the proofs in this section were in the thesis [15].

Our first scheme is only for codes of rate . It is related to a construction of [14], but generalizes it so that the choice of coding operations is independent of the size of the network. We call our scheme the Rate Deterministic Design R2- for short. Our purpose in presenting this first scheme is primarily expository, since the proof is significantly easier than that of the second scheme – it helps set the stage for the second scheme.

Our second scheme is for general rates and is independent of all network parameters, including the number of sinks. We call this scheme the Capacity or more, Probability of error scheme, or C3- for short. However, C3- is more of an existence result than a practical code since the computational complexity of its implementation is exponential in network parameters.

We first describe some useful preprocessing steps relevant for both of our schemes.

### V-a Robust distributed unique ID assignment

While the codes in Section IV only required nodes to estimated their depth, the zero-error codes in presented in this section require nodes to obtain a unique ID, i.e., an ID that is distinct for each node in the network. Such an ID allows nodes to loosely coordinate coding choices even if they are unable to communicate directly with each other, and thereby ensure that the overall code is “good”. Such IDs might be pre-assigned to nodes (for example via factory stamps, or GPS coordinates, or IP addresses), or be assigned on the fly, as described below.

The task of distributing unique IDs to nodes over a directed graph was considered in [22]. The essential idea of their algorithm is to pretend that the graph is a tree directed from the root to the leaves (if not, extra edges are removed for the ID assignment protocol), and to assign IDs so that the binary expansion of each node’s ID is a prefix to the binary expansion of all nodes downstream from it. This ID distribution can be carried out with communication cost that is asymptotically negligible in the packet length, in conjunction with the normal flow of information through the network, for instance in the header. Here, as in Section IV-A, we need to change the unique ID distribution protocol slightly to make it robust to network changes, so that new nodes are still ensured that IDs assigned to them do not clash with previously assigned IDs. In the same spirit as the robust virtual gadgets in Section IV-A, at each node we reserve a virtual ID for the event that a new node might in the future connect to ; if so, this virtual ID is again split into another virtual ID, and an ID that is assigned to the new node. As noted in [22] the worst-case growth rate of the largest node ID with the network size is exponential in , for reasons similar to those outlined in Theorem 3 – nodes might be unable to distinguish between a full binary tree, and a very sparse graph.

### V-B Cantor labeling

The well-known Cantor diagonal argument [23] makes an unexpected cameo in this work. One version states that the cardinality of the set of integers is the same as that of the set of finite dimensional vectors with integer components, and further gives an effective bijection between the two sets. Further, this bijection guarantees that any vector in with maximum component is mapped to an integer of size . This mapping is useful since, given a unique ID for each node , we then need to produce unique coding coefficients for each pair of edges such that one is incoming to and the other is outgoing for . Prior to code design, the number of such coefficients that each node might need to choose is unknown. However, each coefficient can be labeled by at most the five indices , each of which is an integer. Hence given a node’s unique ID, one can produce unique integral labels for each vector that are not too much larger (at most the fifth power) than any of the five parameters in . This mapping, denoted , can then be used to select distinct local coding coefficients as needed in Sections V-C and V-D

### V-C Rate 2 zero-error codes

For the case when the transmission rate equals , note that there are essentially just two non-trivial scenarios for each node – either a node receives one linearly independent message on incoming links, or it receives two. In the former case, it can only broadcast incoming information on outgoing links. In the latter case, it can reconstruct the source’s information, and thereby can fully control the linear combinations on outgoing links. Our construction for R2- rests on analysis of these cases.

R2- (Rate Deterministic Design)

• The source has two linearly independent messages and .

• Depending on its connectivity to the source, on incoming edges each node receives either one or two linearly independent combinations of the source messages .

• If a node receives only one linearly independent message on incoming links, it broadcasts it down all outgoing edges.

• If a node receives two linearly independent combinations of , this enables it to reconstruct both and . For each th directed edge connecting each pair of nodes , (connected possibly by multiple parallel edges), we use the Cantor labeling algorithm141414In Section V-B we assume that and are also variable, but in this section they are fixed. in Section V-B to assign a distinct local coding coefficient. In particular, let denote the -dimensional Cantor mapping. Then the node then transmits down the th edge connecting to (here is chosen to be distinct for each ).

###### Theorem 4.

For any network with min-cut capacity at least , R2- succeeds with zero error.

Proof: For any such that the mincut between the source and is at least , there are at least two edge-disjoint paths from the source to . By the statement of our R2- algorithm, for any such nodes and , the linear combinations of and on all their outgoing links must be distinct, and linearly independent (since the vectors and are linearly independent if and only if and are distinct).

### V-D General zero-error codes

The challenge in extending the results of Section V-C to rates greater than lies in the fact that there might be nodes receiving two or more linearly independent pieces of information, and yet are unable to decode the source messages. In this case, they do not have full control over the messages they are able to send out, and hence the argument of Theorem 4 fails. In this section, we get around this challenge by examining a different invariant of linear convolutional network codes. In particular, we choose coding coefficients in a distributed manner so that the delay of the source messages on every path in the network is distinct. This means that the source messages never cancel out at the sinks, and hence can be reconstructed.

C3- (Capacity or more, Probability of error ) codes

• For each -tuple , let be the -dimensional Cantor mapping defined in Section V-B. We define the local coding coefficient as

 z2K(u,i,v,j,w),

i.e., the monomial in with degree (here the exponent is base ).

###### Theorem 5.

For any network , C3- succeeds with zero error.

Proof: Theorem in [1] demonstrates that , the determinant of the transfer matrix from the source to any sink , can be written as , where the product is over all the local coding coefficients on a particular path from to , is a non-zero constant corresponding to , and the outer summation is over all paths from to . Our choice of local coding coefficients along any path in C3- implies that equals

 ∑cP∏Pzexp(K(u,i,v,j,w))=∑cPz(∑Pexp(K(u,i,v,j,w))). (2)

But by choice, each of the terms is distinct, and hence the binary expansion of has a single in a distinct location. But if two paths in the summation (2) differ, then they must differ in at least one of the local coding coefficients, and therefore the exponent of the power of along the two paths must differ – hence each path corresponds to a distinct power of . This implies that as long as there is at least one path from to each , each of the corresponding transforms must be invertible.

### V-E Complexity Analysis

The complexity of both R2- and C3- scale with the corresponding Cantor labeling and node assignments.

For R2- the size of the set any node chooses its coding coefficients from scales as the third power of the largest node ID or the largest link-capacity in the network. But as noted in Section V-B, the largest node ID can scale exponentially in . Hence the degree of the polynomials used as coding coefficients scales logarithmically in the size of the sets from which local coding coefficients are chosen, which in turn scales as . The corresponding redundancy the network introduces in the codes, arising from the delays introduced by each coding node, then scales as , since each coding node in a path can introduce at most the maximal delay and delays along a path add up.

A similar analysis shows that the complexity of implementation of C3- scales as , and that the redundancy introduced by such codes scales as .

The problem of polynomial identity testing (PIT) [24] examines the question of deterministically determining whether a polynomial with a succinct but non-standard representation (such as the determinant of a matrix of polynomials) identically equals zero. The deterministic complexity of such problems is a long-standing open problem in theoretical computer science. Given this context, we are unable to provide intuition on whether our codes in Section V-D have order-optimal computational complexity – indeed, answering this question in either direction would represent significant progress in resolving the complexity of PIT problems.

## Vi Implementation issues

As noted in [21], the complexity of implementation of network codes scales polynomially in the logarithm of the field-size over which operations are performed, or in the case of convolutional network codes, polynomially in the degree of the polynomials used at each node. By this measure, the implementation complexity of the codes in [1, 8] is poly-logarithmic in network parameters, whereas the implementation complexity of the first three of the four codes in this work is polynomial in network parameters. While this is an exponential blow-up, we note that the resulting codes are still computationally tractable, and further, as noted in Section IV-E, such a blow-up is in fact necessary for codes to be universal.

While the schemes in this work have been presented in the context of convolutional network coding operations at each node, they also go through for other infinite fields such as – the only requirement is that the field be unbounded in size, and that an infinite subset of it have a succinct representation.

Also, despite presenting all messages at the source and each link as bit-streams of possibly unbounded length, the schemes described in prior sections can also be implemented by packetization, by chopping up the bit-streams into packets of a standard size .

In our codes the header of each packet contains low-rate control information used by each node to decide on its coding operations. However, by design, the size of this header changes as information flows down the network – the rate of change depends on the network topology, and hence is unpredictable in advance. One challenge in the implementation of our codes is thus to ensure that the intermediate nodes are able to distinguish between header information and payload information. One standard trick for such scenarios is used in Theorem of [25] – each bit of the header is doubled, and the final such double-bit is followed by a to signify the end of the header. Since the length of the header is asymptotically negligible in the packet-size, the communication cost of this bit-doubling is still asymptotically negligible.

## Vii Discussion

In this work we provide the first rate-optimal network code designs that have guaranteed decodability performance, and yet are independent of all network parameters. While requiring such universality makes us pay a price in the computational complexity and redundancy, (all but one of) our codes are computationally efficient to implement. The analytical tools we derive may well be of independent interest.

## References

• [1] T. Ho., R. Kötter, M. Médard, D. Karger, and M. Effros, “The benefits of coding over routing in a randomized setting,” in IEEE International Symposium on Information Theory (ISIT), Yokohama, July 2003, p. 442.
• [2] J. Motwani and P. Raghavan, Randomized Algorithms.   Cambridge University Press, 1995.
• [3] R. Ahlswede, N. Cai, S.-Y. R. Li, and R. W. Yeung, “Network information flow,” IEEE Transactions on Information Theory, vol. 46, no. 4, pp. 1204–1216, Jul. 2000.
• [4] S.-Y. R. Li, R. W. Yeung, and N. Cai, “Linear network coding,” IEEE Transactions on Information Theory, vol. 49, no. 2, pp. 371–381, Feb. 2003.
• [5] R. Kötter and M. Médard, “Beyond routing: An algebraic approach to network coding,” in Proceedings of the 21st Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM), vol. 1, 2002, pp. 122–130.
• [6] S. Jaggi, P. Sanders, P. A. Chou, M. Effros, S. Egner, K. Jain, and L. Tolhuizen, “Polynomial time algorithms for multicast network code construction,” IEEE Transactions on Information Theory, vol. 51, no. 6, pp. 1973–1982, June 2005.
• [7] M. Langberg, A. Sprintson, and S. Bruck, “The encoding complexity of network coding,” in International Symposium on Information Theory, Sept. 2005.
• [8] S. Jaggi, P. A. Chou, and K. Jain, “Low complexity algebraic multicast network codes,” in IEEE International Symposium on Information Theory (ISIT), Yokohama, July 2003, p. 368.
• [9] E. Erez and M. Feder, “Convolutional network codes,” in IEEE International Symposium on Information Theory, 2004.
• [10] A. Lehman and E. Lehman, “Complexity classification of network information flow problems,” in Proceedings of SODA, 2004.
• [11] J. Rissanen, “A universal data compression system,” IEEE Transactions on Information Theory, vol. 29, no. 5, pp. 656–664, Sep. 1983.
• [12] I. Csiszár and J. Körner, Information Theory: Coding Theorems for Discrete Memoryless Systems.   Akadémiai Kiadó, 1981.
• [13] A. F. Dana, R. Gowaikar, R. Palanki, B. Hassibi, and M. Effros, “Capacity of wireless erasure networks,” IEEE Transactions on Information Theory, vol. 52, no. 6, pp. 789–804, Mar. 2006.
• [14] C. Fragouli and E. Soljanin, “Decentralized network coding,” in Information Theory Workshop, San Antonio, TX, USA, 2004, pp. 310–314.
• [15] S. Jaggi, “Design and analysis of network codes,” Dissertation, California Institute of Technology, 2006.
• [16] S. Jaggi, T. Ho, and M. Effros, “Zero-error distributed network codes,” in Information Theory and Applications Workshop (unpublished), UCSD, San Diego, CA, Jan 2007.
• [17] D. J. C. MacKay, Information Theory, Inference, and Learning Algorithms.   Cambridge University Press, 2003.
• [18] N. Alon, “Combinatorial nullstellensatz,” Combinatorics, Probability and Computing, vol. 8, pp. 7–29, 1999.
• [19] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, 2nd Edition.   MIT Press and McGraw-Hill, 2001.
• [20] S. Jaggi, Y. Cassuto, and M. Effros, “Low complexity encoding for network codes,” in Proc. of the International Symposium on Information Theory, Seattle, WA, USA, Sep 2006.
• [21] S. Jaggi, M. Effros, T. Ho, and M. Médard, “On linear network coding,” in Proceedings of 42nd Annual Allerton Conference on Communication, Control, and Computing, Monticello, IL, 2004.
• [22] J. Bruck, M. Langberg, and M. Schwartz, “Distributed broadcasting and mapping protocols in directed anonymous networks,” in The proceedings of the Twenty-Sixth Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC), 2007, pp. 383–383.
• [23] G. Cantor, “Eigenschaft des inbegriffes aller reelen algebraischen zahlen,” Crelles Journal, vol. 77, pp. 258–262, 1874.
• [24] M. Agrawal and R. Saptharishi, “Classifying polynomials and identitytesting,” Current Trends in Science, 2009, 2009.
• [25] T. Cover and J. Thomas, Elements of Information Theory.   John Wiley and Sons, 2nd Edition, 2006.
• [26] M. Mitzenmacher and E. Upfal, Probability and Computing : Randomized Algorithms and Probabilistic Analysis.   Cambridge University Press, New York (NY), 2005.

### -a Proof of Lemma 2

We proceed by mathematical induction. In the base case when , Lemma 2 is equivalent to the Schwartz-Zippel lemma in one variable.

As the inductive hypothesis, suppose that Lemma 2 is true for variables in the polynomial .

Now consider the case when the polynomial has variables. The polynomial can be rewritten so that

 P(x1,x2,…,xN)=xdNNP1(x1,x2,…,xN−1)+R1(x1,x2,…,xN)

for some polynomials and over the appropriate variables.

The probability that equals zero can be bounded from above by

 Pr[P(.)=0] = Pr[P(.)=0,P1(.)=0]+Pr[P(.)=0,P1(.)≠0] (3) = Pr[P1(.)=0]Pr[P(.)=0|P1(.)=0] +Pr[P1(.)≠0]Pr[P(.)=0|P1(.)≠0] ≤ Pr[P1(.)=0]+Pr[P(.)=0|P1(.)≠0]

But by the inductive hypothesis

 Pr[P1(.)=0]≤N−1∑i=1di|Si|. (4)

Also, by the Principle of Deferred Decisions [26] the probability is unaffected if the value of is chosen after the values of all the other variables have been fixed. In this case, if , then is a polynomial of degree over . By the Schwartz-Zippel lemma

 Pr[P(.)=0|P1(.)≠0]≤dN|SN|. (5)

Substituting (4) and (5) into (3) gives the required result.

You are adding the first comment!
How to quickly get a good reply:
• Give credit where it’s due by listing out the positive aspects of a paper before getting into which changes should be made.
• Be specific in your critique, and provide supporting evidence with appropriate references to substantiate general statements.
• Your comment should inspire ideas to flow and help the author improves the paper.

The better we are at sharing our knowledge with each other, the faster we move forward.
The feedback must be of minimum 40 characters and the title a minimum of 5 characters


text:
# Average codeword length in a Huffman tree is $\Omega(\log n)$

Prove that the average codeword length in a Huffman tree is $$\Omega(\log n)$$, where $$n$$ is the number of characters.

My try:

I think that the worst case is when the tree is full and all the characters are in the highest level.

Therefore: $$n=2^h \to h=\log n$$, and the average codeword length is $$\Omega(\log n)$$.

Am I missing something?

• You did not use the probabilities of the characters? Most probable characters have the shortest code. Jun 1 '19 at 12:11

This answer assumes that by average you mean just that – the sum of all codeword lengths divided by $$n$$.

Let us show that any prefix code satisfies your property. Consider any prefix code whose codewords have lengths $$\ell_1,\ldots,\ell_n$$. Kraft's inequality shows that $$2^{-\ell_1} + \cdots + 2^{-\ell_n} \leq 1.$$ The function $$x \mapsto 2^{-x}$$ is convex, hence $$\frac{1}{n} \geq \frac{2^{-\ell_1} + \cdots + 2^{-\ell_n}}{n} \geq 2^{-(\ell_1+\cdots+\ell_n)/n}.$$ It follows that $$\frac{\ell_1 + \cdots + \ell_n}{n} \geq \log_2 n.$$ Since $$x \mapsto 2^{-x}$$ is strictly convex, there can be equality only if $$\ell_1 = \cdots = \ell_n$$, that is, only if all codewords are of length exactly $$\log_2 n$$. That can only happen if $$n$$ is a power of 2. This leaves open the following question:

What is the minimum average codeword length of a prefix code on $$n$$ symbols?

(We note in passing that every prefix code satisfying Kraft's inequality tightly is a minimum redundancy code for some distribution, namely the one in which the probability of the $$i$$th symbol is $$2^{-\ell_i}$$.)

To answer this, let us note that convexity implies that if $$a < b$$ then $$2^{-a} + 2^{-b} \geq 2^{-(a+1)} + 2^{-(b-1)}.$$ (We can also see this directly: without loss of generality $$a=0$$, and then we need to prove $$1 + 2^{-b} \geq 1/2 + 2 \cdot 2^{-b}$$, that is, $$1/2 \geq 2^{-b}$$, which follows from $$b \geq 1$$.)

Applying this operation repeatedly starting at some arbitrary integer solution of Kraft's equation, we eventually reach a solution which involves at most two different values $$\ell,\ell+1$$. If $$n = 2^k + m$$, where $$0 \leq m < 2^k$$, then this solution must consist of $$2^k - m$$ many $$k$$'s and $$2m$$ many $$k+1$$'s. Hence the optimal average codeword length is $$\frac{k(2^k-m)+(k+1)2m}{2^k+m} = k + \frac{2m}{2^k+m}.$$

• You can describe any prefix code as a binary tree, where the root-to-leaf path of element $x$ spells the code of $x$. The binary tree corresponding to a Huffman code is a Huffman tree. Jan 3 at 20:44

If by average you mean the average length of the n codewords, then if the k-th symbol has probability $$2^{-k}$$, the length of the code words ranges from 1 to n-1, with average about n/2.

If by average you mean the average length of a codeword in a compressed message, then if the first symbol has probability 1-eps, and the others all have probability (1 - eps) / (n - 1), then the average length of a codeword in a compressed message is just a bit more than 1.

format: plain


text:
Thank you for visiting nature.com. You are using a browser version with limited support for CSS. To obtain the best experience, we recommend you use a more up to date browser (or turn off compatibility mode in Internet Explorer). In the meantime, to ensure continued support, we are displaying the site without styles and JavaScript.

# Universal optical conductivity of a disordered Weyl semimetal

## Abstract

Topological Weyl semimetals, besides manifesting chiral anomaly, can also accommodate a disorder-driven unconventional quantum phase transition into a metallic phase. A fundamentally and practically important question in this regard concerns an experimentally measurable quantity that can clearly distinguish these two phases. We show that the optical conductivity while serving this purpose can also play the role of a bonafide order parameter across such disorder-driven semimetal-metal quantum phase transition by virtue of displaying distinct scaling behavior in the semimetallic and metallic phases, as well as inside the quantum critical fan supporting a non-Fermi liquid. We demonstrate that the correction to the dielectric constant and optical conductivity in a dirty Weyl semimetal due to weak disorder is independent of the actual nature of point-like impurity scatterers. Therefore, optical conductivity can be used as an experimentally measurable quantity to study the critical properties and to pin the universality class of the disorder-driven quantum phase transition in Weyl semimetals.

## Introduction

Understanding and characterizing phase transitions is one of the most important problems in condensed matter physics. Identification of distinct phases of matter and the possible phase transitions among them necessarily rely on the existence of a physical quantity that behaves differently in two phases and as such can potentially serve as a bonafide order parameter (OP) across the transition. The notion of an OP is as germane near a zero-temperature quantum phase transition (QPT), driven by quantum fluctuations, as near the finite-temperature classical phase transition, where thermal fluctuations dominate1,2. With increasing complexity of various phases, the horizon of OPs has expanded enormously and topological OPs, which globally characterize a phase of matter, have recently emerged3,4. Moreover, the landscape of topological states has been extended to gapless systems featuring quasiparticles at arbitrarily low energies in the bulk, with Weyl semimetal (WSM), discovered in various three-dimensional gapless semiconductors5,6,7,8,9,10,11,12,13,14, standing as the paradigmatic representative. The constituting Weyl nodes are topologically protected and act as a source (monopole) and a sink (anti-monopole) of Berry flux in the momentum space, manifesting through Adler-Bell-Jackiw chiral anomaly and surface Fermi arcs15,16.

In addition to its topological properties, WSM can also support a disorder-tuned unconventional QPT toward a diffusive metallic phase at a finite disorder strength17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32, see Fig. 1 and we propose that optical conductivity (OC) can expose the rich phase diagram of a dirty WSM at finite frequencies. Unveiling such novel quantum critical phenomena in real materials, however, necessarily encounters technical difficulties. For example, the average density of states at the Weyl points, although has been proposed as a possible OP across such semimetal-metal QPT25,27,29,30,31, its measurement through compressibility in three-dimensional systems is extremely challenging and may become even more complicated due to unwanted but likely presence of charged puddles33,34, Lifshitz tail and rare region effects35,36 in vicinity of the Weyl nodes, as well as due to pinning of the Fermi energy away from the Weyl points. These mechanisms can musk the WSM-metal quantum critical point (QCP)33,34 or perhaps even convert it into a hidden QCP35,36, therefore demanding the search of a measurable quantity that can unearth the underlying QCP by exposing the wide quantum-critical regime away from the pristine QCP [see Fig. 1]. While its inter-band component is capable of bypassing these barriers, we show here that the OC can also display a single parameter scaling across the WSM-metal QPT, thus being suitable as a promising candidate for an experimentally viable OP in a dirty WSM.

We establish that while the OC vanishes linearly with frequency (Ω) in a clean WSM, weak disorder leads to a nontrivial but universal (up to a sign) correction, irrespective of the actual nature of elastic scatterers. Thus both clean and weakly disordered WSMs behave as power-law insulators. It is worth mentioning that OC (σ) has been experimentally measured in the three-dimensional materials featuring linearly dispersing quasiparticles in the bulk, suggesting that σ(Ω) ~ Ω37,38,39. On the other hand, in the metallic phase the zero-frequency OC becomes finite, displaying a universal power-law dependence on disorder strength (measured from the critical one), set only by the correlation length exponent (ν). Inside the quantum critical regime, constituted by disorder-induced strongly coupled gapless critical modes supporting a non-Fermi liquid, the OC vanishes as σ(Ω) ~ Ω1/z when frequency Ω → 0, with z being the dynamic scaling exponent that together with correlation length exponent (ν) defines the universality class of the WSM-metal QPT. As we show here, measurement of OC in a wide frequency range in fact offers a unique opportunity to unearth the universality class of the WSM-metal QPT, besides exposing a rich phase diagram of dirty WSMs. Although we here analyze the scaling behavior of OC at T = 0, its jurisdiction covers the entire collisionless regime .

## Results

### Model

Quintessential properties of a WSM can be captured by the effective low-energy Hamiltonian

where v is the the Fermi velocity of Weyl fermions, assumed here to be isotropic for simplicity and pj are components of momentum. Three mutually anticommuting matrices are defined as Γj = τ3 αj with two sets of Pauli matrices τ and α respectively acting in the chiral (valley) and spin spaces. The spinor is defined as , where cp,σ,τ is the fermion annihilation operator with momentum p (measured from the Weyl nodes), spin projection α = ↑/↓ and chirality τ = +/− (left/right). As shown in the Supplementary Information (SI), the above low-energy Hamiltonian for WSM can be realized from a simple tight-binding model on a cubic lattice. Integrals over momentum run up to an ultraviolet cutoff Λ ~ 1/a, with a being the lattice spacing. The above Hamiltonian enjoys a global chiral U(1) symmetry, generated by γ5 = τ3 α0, which in the continuum limit also stands as the generator of translational symmetry40.

### Disorder

Weyl fermions are susceptible to various disorder and the scattering processes by different types of impurities41, represented by potential terms coupled to appropriate fermion bilinears. Effects of randomness are captured by the Euclidean action , where VN(x) for simplicity assumes a Gaussian white noise distribution, with disorder average 〈〈VN(x)VN(x′)〉〉 = ΔNδ(x − x′). As shown in the SI, various types of disorder can be described by an appropriate choice of the 4 × 4 matrix and the scaling dimension of disorder coupling [ΔN] = 2z − d. The clean WSM features linearly dispersing quasiparticles and is thus characterized by dynamic scaling exponent z = 1. Therefore, sufficiently weak disorder is an irrelevant perturbation, since [ΔN] = −1 and low energy excitations retain their ballistic nature in weakly disordered WSMs.

The fact that weak disorder is an irrelevant perturbation in three-dimensional WSM gives rise to the possibility of a disorder-driven QPT to a metallic phase for strong disorder17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32. In light of this, we next show that OC exhibits a single parameter scaling and therefore can serve as a bonafide OP across the WSM-metal QPT. For extremely strong disorder, the three-dimensional metal eventually undergoes the Anderson transition into an insulating phase17,27, which is, however, outside the scope of the current work.

### Scaling

The scaling of conductivity (σ) with the system size (L) follows from the gauge invariance, leading to σ ~ L2−d, see SI. As the system approaches the QCP located at , the correlation length (ξ) diverges according to ξ ~ |δ|−ν, while the corresponding energy (ε0) vanishes as ε0 ~ |δ|νz, where measures the distance from the QCP. Therefore, semimetallic and metallic phases are respectively realized for and . In the proximity to a QCP, the universal scaling of any physical observable depends on two dimensionless parameters L/ξ and Ω/ε0. Thus general scaling theory and gauge invariance dictate the following scaling ansatz for the OC (in units of e2/h) in a dirty WSM

where and are two unknown, but universal scaling functions. Although the explicit forms for these scaling functions are generally unknown and can only be determined experimentally, their salient features can be deduced from the behavior of OC in various phases of a dirty WSM. Since we are interested in the optical properties of a WSM in the thermodynamic limit (L → ∞), for brevity we drop the explicit L-dependence in σ(Ω, δ, L). Although we here exploit the gauge invariance and scaling theory to obtain the scaling ansatz in Eq. (2), this can also be achieved from the renormalization group analysis of the disorder coupling, as shown in the SI. When the Fermi energy (EF) is pinned away from the Weyl points (see red dashed line in Fig. 1), the system behaves as a diffusive metal at the lowest energy scale for arbitrary strength of impurity scatterers and our discussion on the scaling of OC is germane only for Ω > EF.

First we focus on the QCP (δ = 0), where the OC must be devoid of any δ-dependence, dictating . Its scaling with frequency is then given by

Therefore, within the critical regime OC vanishes with a peculiar power-law dependence when frequency Ω > ε0 ~ |δ|νz, which in turn roughly determines the extent of the critical regime at finite frequencies (see Fig. 1). Notice that as the QCP is approached from the WSM phase the residue of quasiparticle pole vanishes smoothly21, while approaching it from the metallic side the diffusion coefficient diverges25. Therefore, the critical regime constitutes a non-Fermi liquid phase of strongly coupled gapless critical modes, due to quantum fluctuations driven by disorder, where the OC scales as Ω1/z.

Next we consider the metallic phase, where average density of states at zero energy is finite and thus OC as Ω → 0 also becomes finite due to a finite lifetime of diffusive fermions. Hence, inside the metallic phase (to the leading order) and OC scales as

OC in the metallic phase thus depends only on ν as Ω → 0, which together with the dependence of σQ(Ω) solely on z endows a unique opportunity to extract the correlation length and the dynamic critical exponents near the WSM-metal QCP independently and that way pin the universality class of this transition. Hence, in the presence of strong disorder , as the frequency is gradually lowered the intra-band component of OC starts to dominate over the inter-band counterpart and in the limit Ω → 0, only the former contribution survives. Therefore, in the super-critical regime, OC displays a smooth crossover from Ω1/z dependence (high frequency) toward a constant value as Ω → 0 (low frequency) around Ω ~ δνz [see Fig. 1]. The Drude-peak (arising from the intraband contribution) inside the metallic phase gets broadened due to a finite transport lifetime of quasiparticles and its width increases with the strength of disorder. By contrast, inside the WSM phase and quantum critical regime the Drude-peak remains sharp.

Finally, we delve into the scaling of OC on the WSM side of the transition. In the clean limit, on dimensional grounds, we expect inter-band OC σ(Ω) ~ Ωd−2. Such scaling of OC remains valid in the weakly disordered WSM, at least when , indicating that for δ < 0, leading to

which vanishes linearly with frequency Ω. With increasing strength of disorder, the system becomes more metallic and typically at the WSM-metal QCP z > 117,20,21,22,25,27,28,29,30,31. Consequently, as one approaches the WSM-metal QCP from the semimetallic side, σW(Ω) increases monotonically. In the weak disorder regime, the inter-band component of OC dominates over intra-band piece until Ω ~ EF, with EF being the Fermi energy (typically unknown) in a WSM and with increasing frequency OC displays a smooth crossover from Ω to Ω1/z dependence. As disorder increases the frequency range over which OC scales linearly with the frequency shrinks, while the region with Ω1/z scaling increases. Finally, at the WSM-metal QCP σ ~ Ω1/z over the entire range of frequency [see Fig. 1], at least when .

### Optical response in a WSM

Since weak disorder flows toward smaller values with increasing RG time l ~ log(vΛ/Ω) or decreasing frequency, the lowest energy excitations are described by ballistic chiral fermions in a weakly disordered WSM. Thus, we can rely on the Kubo formalism in this regime to compute OC of a WSM diagramatically and directly test the validity of its scaling ansatz for weak enough randomness. To set the stage, we first focus on the OC in a clean WSM (ΔN = 0), which at zero temperature can be extracted from the current-current correlation function. In what follows and as shown in the SI, we compute the integrals over the internal momentum in d = 3 − ε spatial dimensions and at the end send ε → 0, closely following the spirit of dimensional regularization that manifestly preserves the gauge invariance42,43. The OC in a clean WSM is , with Nf as the number of Weyl pairs. In this limit (ΔN = 0), σW(Ω) = σ(Ω), in agreement with the above scaling form. Therefore, inter-band component of OC scales linearly with the frequency20,44,45,46, as has been observed in Nd2(IrxRh1−x)2O737 and Eu2Ir2O739, which possibly through an “all-in all-out” magnetic ordering in pyrochlore lattice enter into a WSM phase47.

By now it is well established that random charge impurities (ΔV) can drive WSM-metal transition17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32 or at least can support a large crossover regime if rare regions dominate at the lowest energy scale36. As described in depth in the SI, elastic scatterer of any other nature (magnetic, spin-orbit, mass disorder, etc.) generates random axial chemical potential through quantum corrections. The axial disorder (ΔA) causes random but equal and opposite shifts of the Fermi level for left and right chiral fermions, while maintaining the overall charge neutrality of the system. Strong axial disorder also gives rise to semimetal-metal QPT20,21,27,29. Hence, to anchor the scaling behavior of OC in weak disorder regime, it is sufficient to focus on these two disorder couplings, ΔV and ΔA, respectively characterized by two matrices and . After accounting for the correction to OC to the lowest order in disorder coupling the total OC is given by (see SI for details)

for N = V, A, where is the dimensionless bare disorder strength and the function . The above form of the OC is also compatible with the scaling form of σW(Ω) after substituting z = 3/2, ν = 1, as predicted from one-loop RG calculation20,21,22 and also reasonably consistent with recent numerical works25,29,30,31, with being the non-universal critical strength of disorder for the WSM-metal QPT. Such a striking agreement between scaling theory [see Eq. (2) and σW(Ω)], perturbative correction to OC in the weak disorder limit [see Eq. (3)], RG and numerical analyses indicates internal consistency of our analysis and puts forward OC as a bonafide OP across the unconventional QPT from WSM to a metallic phase. With one-loop result for the critical exponents ν and z, OC in the critical regime σQ(Ω) ~ Ω2/3 and inside the metallic phase σM(Ω → 0) ~ δ. However, as our scaling analysis suggests, these critical exponents can be determined independently from the scaling of OC in numerical studies and experiments to precisely determine the universality class of the WSM-metal transition. Furthermore, as shown in the SI, scaling of OC as Ω → 0 with system size (L) inside the metallic phase allows one to extract the correlation length exponent (ν) independently.

The imaginary part of OC in a weakly disordered WSM also receives a correction yielding the total dielectric constant in the presence of the chemical potential (N = V) or axial disorder (N = A)

which displays a logarithmic enhancement as Ω → 0. It is worth mentioning that recent experiment has observed enhancement of ε(Ω) in Eu2Ir2O7 as Ω → 039.

Furthermore, in the presence of arbitrary disorder the OC in three-dimensional WSM exhibits a remarkably universal dependence on frequency and disorder, but up to a sign, depending on the type of elastic scatterer, as shown in Table I of the SI. Correction to the OC due to any disorder (such as the spin-orbit one with ΔN = ΔSO and , where j = 1, 2, 3) that together with the axial disorder also drives a WSM-metal QPT through a QCP that, however, belongs to a different universality class (with ν = 1, but z = 11/2 to one-loop order20,48), also conforms to the critical scaling form shown in Eq. (3). Furthermore, in the presence of both potential and axial disorders, WSM-metal QPT takes place through a line of QCPs in the (ΔV, ΔA) plane along which ν = 1 and z = 3/2 (to one-loop order)20,48. The OC then reads as , which also conforms to the universal scaling form of the OC, since the line of QCPs is given by . Finally, the dielectric constant also receives a universal (up to a sign) correction due to disorder that scales linearly with frequency, as shown in Eq. (4).

## Discussion

We establish OC as an experimentally accessible OP across the disorder-driven WSM-metal QPT. In particular, we show that it can uncover signatures of an underlying dirty QCP by exposing the associated quantum critical regime at finite frequencies. While the scaling analysis is performed here strictly at T = 0 in the ballistic (collisionless) regime, it remains operative also at finite temperature as long as 49. The finite conductivity in the metallic phase as Ω → 0 for stronger disorder should match the dc conductivity when T ≠ 050,51; the value of the former is, however, expected to be different if temperature is set to be zero first. Nevertheless, irrespective of these two limits σM(Ω → 0) follows the announced scaling behavior. Our scaling arguments can also be applied to the dc conductivity20,22,26 in the collision-dominated regime , for which the scaling behavior qualitatively follows Eq. (2) upon taking Ω → T49.

Even though we primarily focused on WSMs5,6,7,8,9,10,11,12,13,14, our results are consequential to a vast number of materials, such as the topological Dirac semimetal that has recently been discovered in Cd2As352 and Na3Bi53, conventional Dirac semimetals that can be found at the QCP separating two topologically distinct (for example, strong, weak, crystalline and trivial) insulating phases in various three-dimensional strong spin-orbit coupled materials, such as Bi1−xSbx, Bi2Se3, Bi2Te2, Sb2Te33,4 and quasi-crystals supporting Dirac fermions38. From the extent of the critical regime and semimetalic phase at finite frequencies (see Fig. 1), we expect that the critical scaling of OC and its correction due to random impurities can be observed in a broad class of disordered Weyl and Dirac semimetals.

How to cite this article: Roy, B. et al. Universal optical conductivity of a disordered Weyl semimetal. Sci. Rep. 6, 32446; doi: 10.1038/srep32446 (2016).

## References

1. Sachdev, S. Quantum Phase Transitions (Cambridge University Press, 2nd ed., 2007).

2. Herbut, I. F. A Modern Approach to Critical Phenomena (Cambridge University Press, Cambridge, 2007).

3. Hassan, M. Z. & Kane, C. L. Colloquium: Topological insulators. Rev. Mod. Phys. 82, 3045 (2010).

4. Qi, X. L. & Zhang, S.-C. Topological insulators and superconductors. Rev. Mod. Phys. 83, 1057 (2011).

5. Zhang, C. et al. Tantalum Monoarsenide: an Exotic Compensated Semimetal. arXiv:1502.00251.

6. Xu, S.-Y. et al. Discovery of a Weyl fermion semimetal and topological Fermi arcs. Science 349, 613 (2015).

7. Lv, B. Q. et al. Experimental Discovery of Weyl Semimetal TaAs. Phys. Rev. X 5, 031013 (2015).

8. Xu, S.-Y. et al. Discovery of a Weyl fermion state with Fermi arcs in niobium arsenide. Nature Physics 11, 748 (2015).

9. Xu, N. et al. Observation of Weyl nodes and Fermi arcs in tantalum phosphide. Nature Communications 7, 11006 (2016).

10. Shekhar, C. et al. Extremely large magnetoresistance and ultrahigh mobility in the topological Weyl semimetal candidate NbP. Nature Physics 11, 645 (2015).

11. Wang, Z. et al. Helicity-protected ultrahigh mobility Weyl fermions in NbP. Phys. Rev. B 93, 121112(R) (2016).

12. Chang, G. et al. A strongly robust Weyl fermion semimetal state in Ta3S2. arXiv:1512.08781.

13. Borisenko, S. et al. Time-Reversal Symmetry Breaking Type-II Weyl State in YbMnBi2. arXiv:1507.04847.

14. Liu, J. Y. et al. Discovery of a topological semimetal phase coexisting with ferromagnetic behavior in Sr1−yMnSb2 (y ~ 0.08). arXiv:1507.07978.

15. Burkov, A. A. Chiral anomaly and transport in Weyl metals. J. Phys.: Condens. Matter 27, 113201 (2015).

16. Bansil, A., Lin, H. & Das, T. Colloquium: Topological band theory. Rev. Mod. Phys. 88, 021004 (2016).

17. Fradkin, E. Critical behavior of disordered degenerate semiconductors. II. Spectrum and transport properties in mean-field theory. Phys. Rev. B 33, 3263 (1986).

18. Shindou, R. & Murakami, S. Effects of disorder in three-dimensional Z2 quantum spin Hall systems. Phys. Rev. B 79, 045321 (2009).

19. Ominato, Y. & Koshino, M. Quantum transport in a three-dimensional Weyl electron system. Phys. Rev. B 89, 054202 (2014).

20. Goswami, P. & Chakravarty, S. Quantum Criticality between Topological and Band Insulators in 3 + 1 Dimensions. Phys. Rev. Lett. 107, 196803 (2011).

21. Roy, B. & Das Sarma, S. Diffusive quantum criticality in three-dimensional disordered Dirac semimetals. Phys. Rev. B 90, 241112(R) (2014).

22. Syzranov, S. V., Radzihovsky, L. & Gurarie, V. Critical Transport in Weakly Disordered Semiconductors and Semimetals. Phys. Rev. Lett. 114, 166601 (2015).

23. Altland, A. & Bagrets, D. Effective Field Theory of the Disordered Weyl Semimetal. Phys. Rev. Lett. 114, 257201 (2015).

24. Kobayashi, K., Ohtsuki, T. & Imura, K.-I. Disordered Weak and Strong Topological Insulators. Phys. Rev. Lett. 110, 236803 (2013).

25. Kobayashi, K., Ohtsuki, T., Imura, K.-I. & Herbut, I. F. Density of States Scaling at the Semimetal to Metal Transition in Three Dimensional Topological Insulators. Phys. Rev. Lett. 112, 016402 (2014).

26. Sbierski, B., Pohl, G., Bergholtz, E. J. & Brouwer, P. W. Quantum Transport of Disordered Weyl Semimetals at the Nodal Point. Phys. Rev. Lett. 113, 026602 (2014).

27. Pixley, J. H., Goswami, P. & Das Sarma, S. Anderson Localization and the Quantum Phase Diagram of Three Dimensional Disordered Dirac Semimetals. Phys. Rev. Lett. 115, 076601 (2015).

28. Sbierski, B., Bergholtz, E. J. & Brouwer, P. W. Quantum critical exponents for a disordered three-dimensional Weyl node. Phys. Rev. B 92, 115145 (2015).

29. Pixley, J. H., Goswami, P. & Das Sarma, S. Disorder-driven itinerant quantum criticality of three-dimensional massless Dirac fermions. Phys. Rev. B 93, 085103 (2016).

30. Liu, S., Ohtsuki, T. & Shindou, R. Effect of Disorder in a Three-Dimensional Layered Chern Insulator. Phys. Rev. Lett. 116, 066401 (2016).

31. Bera, S., Sau, J. D. & Roy, B. Dirty Weyl semimetals: stability, phase transition and quantum criticality. Phys. Rev. B 93, 201302 (2016).

32. Shapourian, H. & Hughes, T. L. Phase diagrams of disordered Weyl semimetals. Phys. Rev. B 93, 075108 (2016).

33. Adam, S., Hwang, E. H., Galitski, V. M. & Das Sarma, S. A self-consistent theory for graphene transport. Proc. Natl. Acad. Sci. USA 104, 18392 (2007).

34. Das Sarma, S., Adam, S., Hwang, E. H. & Rossi, E. Electronic transport in two-dimensional graphene. Rev. Mod. Phys. 83, 407 (2011).

35. Nandkishore, R., Huse, D. A. & Sondhi, S. L. Rare region effects dominate weakly disordered three-dimensional Dirac points. Phys. Rev. B 89, 245110 (2014).

36. Pixley, J. H., Huse, D. A. & Das Sarma, S. Rare region induced avoided quantum criticality in disordered three-dimensional Dirac and Weyl semimetals. Phys. Rev. X 6, 021042 (2012).

37. Ueda, K. et al. Variation of Charge Dynamics in the Course of Metal-Insulator Transition for Pyrochlore-Type Nd2Ir2O7 . Phys. Rev. Lett. 109, 136402 (2012).

38. Timusk, T., Carbotte, J. P., Homes, C. C., Basov, D. N. & Sharapov, S. G. Three-dimensional Dirac fermions in quasicrystals as seen via optical conductivity. Phys. Rev. B 87, 235121 (2013).

39. Sushkov, A. B. et al. Optical evidence for a Weyl semimetal state in pyrochlore Eu2Ir2O7 . Phys. Rev. B 92, 241108(R) (2015).

40. Roy, B. & Sau, J. D. Magnetic catalysis and axionic charge-density-wave in Weyl semimetals. Phys. Rev. B 92, 125141 (2015).

41. Huang, Z., Das, T., Balatsky, A. V. & Arovas, D. P. Stability of Weyl metals under impurity scattering. Phys. Rev. B 87, 155123 (2013).

42. Juričić, V., Vafek, O. & Herbut, I. F. Conductivity of interacting massless Dirac particles in graphene: Collisionless regime. Phys. Rev. B 82, 235402 (2010).

43. Herbut, I. F., Juričić, V. & Vafek, O. Coulomb interaction, ripples and the minimal conductivity of graphene. Phys. Rev. Lett. 100, 046403 (2008).

44. Hosur, P., Parameswaran, S. A. & Vishwanath, A. Charge Transport in Weyl Semimetals. Phys. Rev. Lett. 108, 046602 (2012).

45. Rosenstein, B. & Lewkowicz, M. Dynamics of electric transport in interacting Weyl semimetals. Phys. Rev. B 88, 045108 (2013).

46. Mastropietro, V., Interacting Weyl semimetals on a lattice. J. Phys. A: Math. Theor. 47, 465003 (2014).

47. Wan, X., Turner, A. M., Vishwanath, A. & Savrasov, S. Y. Topological semimetal and Fermi-arc surface states in the electronic structure of pyrochlore iridates. Phys. Rev. B 83, 205101 (2011).

48. Roy, B. & Das Sarma, S. Quantum phases of interacting electrons in three-dimensional dirty Dirac semimetals. arXiv:1511.06367.

49. Wegner, F. Electrons in disordered systems. Scaling near the mobility edge. Z. Phys. B 25, 327 (1976).

50. Das Sarma, S. & Hwang, E. H. Charge transport in gapless electron-hole systems with arbitrary band dispersion. Phys. Rev. B 91, 195104 (2015).

51. Das Sarma, S., Hwang, E. H. & Min, H. Carrier screening, transport and relaxation in three-dimensional Dirac semimetals. Phys. Rev. B 91, 035201 (2015).

52. Borisenko, S. et al. Experimental Realization of a Three-Dimensional Dirac Semimetal. Phys. Rev. Lett. 113, 027603 (2014).

53. Liu, Z. K. et al. Discovery of a Three-Dimensional Topological Dirac Semimetal, Na3Bi. Science 343, 864 (2014).

## Acknowledgements

B.R. and S.D.S. are supported by NSF-JQI-PFC and LPS-MPO-CMTC. B.R. is thankful to H. Dennis Drew, Pallab Goswami and Igor Herbut for stimulating discussions and Aspen Center for Physics for hospitality during the Summer Program (2015), where part of this work was finalized.

## Author information

Authors

### Contributions

All authors contributed equally to the conceptual development of the problem and participated in writing the manuscript. B.R. and V.J. performed the calculations.

## Ethics declarations

### Competing interests

The authors declare no competing financial interests.

## Rights and permissions

Reprints and Permissions

Roy, B., Juričić, V. & Das Sarma, S. Universal optical conductivity of a disordered Weyl semimetal. Sci Rep 6, 32446 (2016). https://doi.org/10.1038/srep32446

• Accepted:

• Published:

• ### Fermi arcs and surface criticality in dirty Dirac materials

• Eric Brillaux
•  & Andrei A. Fedorenko

Physical Review B (2021)

• ### Critical scaling of the ac conductivity and momentum dissipation

• Nikolaos Angelinos
• , Elias Kiritsis
•  & Francisco Peña-Benitez

Physical Review Research (2021)

• ### Stability of Weyl semimetals with quasiperiodic disorder

• Vieri Mastropietro

Physical Review B (2020)

• ### Effects of fermion-fermion interactions and impurity scatterings on fermion velocities in the line-nodal superconductors

• Ya-Hui Zhai
•  & Jing Wang

The European Physical Journal B (2020)

• ### Chiral Hall effect in strained Weyl semimetals

• Shiva Heidari
•  & Reza Asgari

Physical Review B (2020)


text:
# Levene's test assumptions

Does the Levene's test have any assumptions? If so, what are they?

To my surprise, neither my textbooks or Wikipedia, mention any assumptions for this test. But I seriously doubt that the test doesn't assume anything about the population. Since it is used so widely, I thought that knowing for sure couldn't hurt.

Levene's test is just a $t$-test of the absolute values of the deviations of the data from their group means. (If you have more than 2 groups, you use the ANOVA; you can also use Brown-Forsythe version of the test, which takes the absolute values of the deviations from the group medians instead.)

At any rate, it is a $t$-test, so the assumptions are based on that. Specifically, you are assuming that the absolute values of the deviations are independent, normally distributed and with equal variances between the groups. It's worth noting that these can't really be quite true. For instance, the normal distribution extends to negative infinity, but absolute values do not. That said, if those assumptions hold for the original data, and your sample size is sufficient, they may be close enough for Levene's test to be reliable.


text:
# Introduction

If you’ve been keeping up with this blog, you might be familiar with Causal profiling, a profiling method that aims to bridge the gap between spending cycles on something and that something actually helping improve performance. I’ve ported this profiling method to Go and figured I’d turn it loose on a real piece of software, The HTTP/2 implementation in the standard library.

# HTTP/2

HTTP/2 is a new version of the old HTTP/1 protocol which we know and begrudgingly tolerate. It takes a single connection and multiplexes requests onto it, reducing connection establishing overhead. The Go implementation uses one goroutine per request and a couple more per connection to handle asynchronous communications, having them all coordinate to determine who writes to the connection when.

This structure is a perfect fit for causal profiling. If there is something implicitly blocking progress for a request, it should pop up red hot on the causal profiler, while it might not on the conventional one.

# Experiment setup

To grab measurements, I set up an synthetic benchmark with an HTTP/2 server and client. The server takes the headers and body from the Google home page and just writes it for every request it sees. The client asks for the root document, using the client headers from firefox. The client limits itself to 10 requests running concurrently. This number was chosen arbitrarily, but should be enough to keep the CPU saturated.

Causal profiling requires us to instrument the program. We do this by setting Progress markers, which measure the time between 2 points in the code. The HTTP/2 server uses a function called runHandler that runs the HTTP handler in a goroutine. Because we want to measure scheduler latency as well as handler runtime, we set the start of the progress marker before we spawn the goroutine. The end marker is put after the handler has written all its data to the wire.

To get a baseline, let’s grab a traditional CPU profile from the server, yielding this profiling graph:

OK, that’s mostly what you’d expect from a large well-optimized program, a wide callgraph with not that many obvious places to sink our effort into. The big red box is the syscall leaf, a function we’re unlikely to optimize.

The text gives us a few more places to look, but nothing substantial

(pprof) topShowing nodes accounting for 40.32s, 49.44% of 81.55s totalDropped 453 nodes (cum <= 0.41s)Showing top 10 nodes out of 186      flat  flat%   sum%        cum   cum%    18.09s 22.18% 22.18%     18.84s 23.10%  syscall.Syscall     4.69s  5.75% 27.93%      4.69s  5.75%  crypto/aes.gcmAesEnc     3.88s  4.76% 32.69%      3.88s  4.76%  runtime.futex     3.49s  4.28% 36.97%      3.49s  4.28%  runtime.epollwait     2.10s  2.58% 39.55%      6.28s  7.70%  runtime.selectgo     2.02s  2.48% 42.02%      2.02s  2.48%  runtime.memmove     1.84s  2.26% 44.28%      2.13s  2.61%  runtime.step     1.69s  2.07% 46.35%      3.97s  4.87%  runtime.pcvalue     1.26s  1.55% 47.90%      1.39s  1.70%  runtime.lock     1.26s  1.55% 49.44%      1.26s  1.55%  runtime.usleep

Mostly runtime and cryptography functions. Let’s set aside cryptography, since it will already have been optimized a lot.

# Causal Profiling to the rescue

Before we get to the profiling results from causal profiling, it’d be good to have a refresher on how it works. When causal profiling is enabled, a series of experiments are performed. An experiment starts by picking a call-site and some amount of virtual speed-up to apply. Whenever that call-site is executed (which we detect with the profiling infrastructure), we slow down every other executing thread by the virtual speed-up amount.

This would seem counter-intuitive, but since we know how much we slowed down a program when we take our measurement from the Progress marker, we can undo the effect, which gives us the time it would have taken if the chosen call-site was sped up. For a more in-depth look at causal profiling, I suggest you read my other causal profiling posts and the original paper.

The end result is that a causal profile looks like a collection of call-sites, which were sped up by some amount and as a result changed the runtime between Progress markers. For the HTTP/2 server, a call-site might look like:

0x4401ec /home/daniel/go/src/runtime/select.go:73  0%    2550294ns 20%    2605900ns    +2.18%    0.122% 35%    2532253ns    -0.707%    0.368% 40%    2673712ns    +4.84%    0.419% 75%    2722614ns    +6.76%    0.886% 95%    2685311ns    +5.29%    0.74%

For this example, we’re looking at an unlock call within the select runtime code. We have the amount that we virtually sped up this call-site, the time it took, the percent difference from the baseline. This call-site doesn’t show us much potential for speed-up. It actually shows that if we speed up the select code, we might end up making our program slower.

The fourth column is a bit tricky. It is the percentage of samples that were detected within this call-site, scaled by the virtual speed-up. Roughly, it shows us the amount of speed-up we should expect if we were seeing this as a traditional profile.

Now for a more interesting call-site:

0x4478aa /home/daniel/go/src/runtime/stack.go:881  0%    2650250ns  5%    2659303ns    +0.342%    0.84% 15%    2526251ns    -4.68%    1.97% 45%    2434132ns    -8.15%    6.65% 50%    2587378ns    -2.37%    8.12% 55%    2405998ns    -9.22%    8.31% 70%    2394923ns    -9.63%    10.1% 85%    2501800ns    -5.6%    11.7%

This call-site is within the stack growth code and shows that speeding it up might give us some decent results. The fourth column shows that we’re essentially running this code as a critical section. With this in mind, let’s look back at the traditional profile we collected, now focused on the stack growth code.

(pprof) top -cum newstackActive filters:   focus=newstackShowing nodes accounting for 1.44s, 1.77% of 81.55s totalDropped 36 nodes (cum <= 0.41s)Showing top 10 nodes out of 65      flat  flat%   sum%        cum   cum%     0.10s  0.12%  0.12%      8.47s 10.39%  runtime.newstack     0.09s  0.11%  0.23%      8.25s 10.12%  runtime.copystack     0.80s  0.98%  1.21%      7.17s  8.79%  runtime.gentraceback         0     0%  1.21%      6.38s  7.82%  net/http.(*http2serverConn).writeFrameAsync         0     0%  1.21%      4.32s  5.30%  crypto/tls.(*Conn).Write         0     0%  1.21%      4.32s  5.30%  crypto/tls.(*Conn).writeRecordLocked         0     0%  1.21%      4.32s  5.30%  crypto/tls.(*halfConn).encrypt     0.45s  0.55%  1.77%      4.23s  5.19%  runtime.adjustframe         0     0%  1.77%      3.90s  4.78%  bufio.(*Writer).Write         0     0%  1.77%      3.90s  4.78%  net/http.(*http2Framer).WriteData

This shows us that newstack is being called from writeFrameAsync. It is called in the goroutine that’s spawned every time the HTTP/2 server wants to send a frame to the client. Only one writeFrameAsync can run at any given time and if a handler is trying to send more frames down the wire, it will be blocked until writeFrameAsync returns.

Because writeFrameAsync goes through several logical layers, it uses a lot of stack and stack growth is inevitable.

# Speeding up the HTTP/2 server by 28.2% because I felt like it

If stack growth is slowing us down, then we should find some way of avoiding it. writeFrameAsync gets called on a new goroutine every time, so we pay the price of the stack growth on every frame write.

Instead, if we reuse the goroutine, we only pay the price of stack growth once and every subsequent write will reuse the now bigger stack. I made this modification to server and the causal profiling baseline turned from 2.650ms to 1.901ms, a reduction of 28.2%.

A bit caveat here is that HTTP/2 servers usually don’t run full speed on localhost. I suspect if this was hooked up to the internet, the gains would be a lot less because the stack growth CPU time would get hidden in the network latency.

# Conclusion

It’s early days for causal profiling, but I think this small example does show off the potential it holds. If you want to play with causal profiling, you can check out my branch of the Go project with causal profiling added. You can also suggest other benchmarks for me to look at and we can see what comes from it.

P.S. I am currently between jobs and looking for work. If you’d be interested in working with low-level knowledge of Go internals and distributed systems engineering, check out my CV and send me an email on daniel@lasagna.horse.