text:
Coset

In mathematics, specifically group theory, a subgroup $G$ of a group $H$ may be used to decompose the underlying set of $H$ into disjoint, equal-size subsets called cosets. There are left cosets and right cosets. Cosets (both left and right) have the same number of elements (cardinality) as does $H$. Furthermore, $G$ itself is both a left coset and a right coset. The number of left cosets of $H$ in $G$ is equal to the number of right cosets of $G$ in $H$. This common value is called the index of $H$ in $H$ and is usually denoted by $1 + H$.

Cosets are a basic tool in the study of groups; for example, they play a central role in Lagrange's theorem that states that for any finite group $G$, the number of elements of every subgroup $H$ of $G$ divides the number of elements of $H$. Cosets of a particular type of subgroup (a normal subgroup) can be used as the elements of another group called a quotient group or factor group. Cosets also appear in other areas of mathematics such as vector spaces and error-correcting codes.

Definition
Let $G$ be a subgroup of the group $G$ whose operation is written multiplicatively (juxtaposition denotes the group operation). Given an element $H$ of $G$, the left cosets of $G$ in $H$ are the sets obtained by multiplying each element of $G$ by a fixed element $g$ of $G$ (where $H$ is the left factor). In symbols these are,

The right cosets are defined similarly, except that the element $G$ is now a right factor, that is,

As $H$ varies through the group, it would appear that many cosets (right or left) would be generated. Nevertheless, it turns out that any two left cosets (respectively right cosets) are either disjoint or are identical as sets.

If the group operation is written additively, as is often the case when the group is abelian, the notation used changes to $2 + H$ or $3 + H$, respectively.

The symbol G/H is sometimes used for the set of (left) cosets {gH : g an element of G} (see below for a extension to right cosets and double cosets). However, some authors (including Dummit & Foote and Rotman) reserve this notation specifically for representing the quotient group formed from the cosets in the case where H is a normal subgroup of G.

First example
Let $g$ be the dihedral group of order six. Its elements may be represented by $[G : H]$. In this group, $[G : H]$ and $gH = \{gh : h an element of H\}$. This is enough information to fill in the entire Cayley table:

Let $G$ be the subgroup $Hg = \{hg : h an element of H\}$. The (distinct) left cosets of $g$ are: Since all the elements of $g$ have now appeared in one of these cosets, generating any more can not give new cosets; any new coset would have to have an element in common with one of these and therefore would be identical to one of these cosets. For instance, $g + H$.
 * $H + g$, and
 * $\{I, a, a^{2}, b, ab, a^{2}b\}$, and

The right cosets of $G$ are:
 * $a^{3} = b^{2} = I$, and
 * $ba = a^{2}b$, and

In this example, except for $g$, no left coset is also a right coset.

Let $g$ be the subgroup $a^{2}$. The left cosets of $G$ are $a^{2}b$ and $a^{2}$. The right cosets of $g$ are $a^{2}b$ and $a^{2}$. In this case, every left coset of $G$ is also a right coset of $I$.

Let $a$ be a subgroup of a group $b$ and suppose that $a^{2}b$, $a^{2}$. The following statements are equivalent:

Properties
The disjointness of non-identical cosets is a result of the fact that if $ab$ belongs to $a^{2}$ then $a^{2}b$. For if $a^{2}b$ then there must exist an $a^{2}$ such that $a^{2}b$. Thus $a^{2}$. Moreover, since $a^{2}b$ is a group, left multiplication by $I$ is a bijection, and $a^{2}b$.

Thus every element of $a^{2}$ belongs to exactly one left coset of the subgroup $\{I, b\}$, and $IT = T = \{I, b\}$ is itself a left coset (and the one that contains the identity).

Two elements being in the same left coset also provide a natural equivalence relation. Define two elements of $I$, $a$ and $b$, to be equivalent with respect to the subgroup $ab$ if $aT = \{a, ab\}$ (or equivalently if $a^{2}T = \{a^{2}, a^{2}b\}$ belongs to $a$). The equivalence classes of this relation are the left cosets of $a$. As with any set of equivalence classes, they form a partition of the underlying set. A coset representative is a representative in the equivalence class sense. A set of representatives of all the cosets is called a transversal. There are other types of equivalence relations in a group, such as conjugacy, that form different classes which do not have the properties discussed here.

Similar statements apply to right cosets.

If $abT = \{ab, a\} = aT$ is an abelian group, then $TI = T = \{I, b\}$ for every subgroup $Ta = \{a, ba\} = \{a, a^{2}b\}$ of $Ta^{2} = \{a^{2}, ba^{2}\} = \{a^{2}, ab\}$ and every element $I$ of $\{I, a, a^{2}\}$. For general groups, given an element $ab$ and a subgroup $IH = H$ of a group $bH = \{b, ba, ba^{2}\}$, the right coset of $HI = H$ with respect to $b$ is also the left coset of the conjugate subgroup $Hb = \{b, ab, a^{2}b\} = \{b, ba^{2}, ba\}$ with respect to $I$, that is, $g_{1}$.

Normal subgroups
A subgroup $g_{2} ∈ G$ of a group $g_{1}H = g_{2}H$ is a normal subgroup of $Hg_{1}^{−1} = Hg_{2}^{−1}$ if and only if for all elements $a$ of $g_{1}H ⊂ g_{2}H$ the corresponding left and right cosets are equal, that is, $g_{2} ∈ g_{1}H$. This is the case for the subgroup $b$ in the first example above. Furthermore, the cosets of $g_{1}^{−1}g_{2} ∈ H$ in $gH$ form a group called the quotient group or factor group $gH = xH$.

If $x ∈ gH$ is not normal in $a ∈ H$, then its left cosets are different from its right cosets. That is, there is an $ab$ in $ga = x$ such that no element $b$ satisfies $xH = (ga)H = g(aH)$. This means that the partition of $H$ into the left cosets of $aH = H$ is a different partition than the partition of $G$ into right cosets of $H$. This is illustrated by the subgroup $b$ in the first example above. (Some cosets may coincide. For example, if $ab$ is in the center of $H$, then $xH = yH$.)

On the other hand, if the subgroup $x^{−1}y$ is normal the set of all cosets forms a group called the quotient group $G$ with the operation $g + H = H + g$ defined by $H$. Since every right coset is a left coset, there is no need to distinguish "left cosets" from "right cosets".

Index of a subgroup
Every left or right coset of $G$ has the same number of elements (or cardinality in the case of an infinite $G$) as $H$ itself. Furthermore, the number of left cosets is equal to the number of right cosets and is known as the index of $G$ in G, written as $H$. Lagrange's theorem allows us to compute the index in the case where $g^{−1}Hg$ and $Hg = g(g^{−1}Hg)$ are finite: $$|G| = [G : H]|H|.$$ This equation also holds in the case where the groups are infinite, although the meaning may be less clear.

Integers
Let $N$ be the additive group of the integers, $G$ and $G$ the subgroup $G$. Then the cosets of $gN = Ng$ in $N$ are the three sets $G$, $G/N$, and $H$, where $G$. These three sets partition the set $G$, so there are no other right cosets of $I$. Due to the commutivity of addition $aH = Hb$ and $G$. That is, every left coset of $a$ is also a right coset, so $ab$ is a normal subgroup. (The same argument shows that every subgroup of an Abelian group is normal. )

This example may be generalized. Again let $H$ be the additive group of the integers, $G$, and now let $H$ the subgroup $G$, where $ab$ is a positive integer. Then the cosets of $aH = Ha$ in $N$ are the $b$ sets $G/N$, $∗$, ..., $(aN) ∗ (bN) = abN$, where $H$. There are no more than $a$ cosets, because $H$. The coset $H$ is the congruence class of $I$ modulo $ab$. The subgroup $H$ is normal in $[G : H]$, and so, can be used to form the quotient group $G$ the group of integers mod $H$.

Vectors
Another example of a coset comes from the theory of vector spaces. The elements (vectors) of a vector space form an abelian group under vector addition. The subspaces of the vector space are subgroups of this group. For a vector space $G$, a subspace $Z = ({..., −2, −1, 0, 1, 2, ...}, +)$, and a fixed vector $H$ in $(3Z, +) = ({..., −6, −3, 0, 3, 6, ...}, +)$, the sets $$\{\mathbf{x} \in V \mid \mathbf{x} = \mathbf{a} + \mathbf{w}, \mathbf{w} \in W\}$$ are called affine subspaces, and are cosets (both left and right, since the group is abelian). In terms of 3-dimensional geometric vectors, these affine subspaces are all the "lines" or "planes" parallel to the subspace, which is a line or plane going through the origin. For example, consider the plane $H$. If $b$ is a line through the origin $a$, then $I$ is a subgroup of the abelian group $G$. If $T$ is in $3Z$, then the coset $3Z + 1$ is a line $3Z + 2$ parallel to $T$ and passing through $G$.

Matrices
Let $T$ be the multiplicative group of matrices, $$G = \left \{\begin{bmatrix} a & 0 \\ b & 1 \end{bmatrix} \colon a, b \in \R, a \neq 0 \right\},$$ and the subgroup $T$ of $H$, $$H= \left \{\begin{bmatrix} 1 & 0 \\ c & 1 \end{bmatrix} \colon c \in \mathbb{R} \right\}.$$ For a fixed element of $H$ consider the left coset $$\begin{align} \begin{bmatrix} a & 0 \\ b & 1 \end{bmatrix} H = &~ \left \{\begin{bmatrix} a & 0 \\ b & 1 \end{bmatrix}\begin{bmatrix} 1 & 0 \\ c & 1 \end{bmatrix} \colon c \in \R \right\} \\ =&~ \left \{\begin{bmatrix} a & 0 \\ b + c & 1 \end{bmatrix} \colon c \in \mathbb{R}\right\} \\ =&~ \left \{\begin{bmatrix} a & 0 \\ d & 1 \end{bmatrix} \colon d \in \mathbb{R}\right\}. \end{align}$$ That is, the left cosets consist of all the matrices in $H$ having the same upper-left entry. This subgroup $H$ is normal in $H$, but the subgroup $$T= \left \{\begin{bmatrix} a & 0 \\ 0 & 1 \end{bmatrix} \colon a \in \mathbb{R} - \{0\} \right\}$$ is not normal in $H$.

As orbits of a group action
A subgroup $G$ of a group $x$ can be used to define an action of $a$ on $G$ in two natural ways. A right action, $3Z + a = \{..., −6 + a, −3 + a, a, 3 + a, 6 + a, ...\}$ given by $Z$ or a left action, $H + 1 = 1 + H$ given by $H + 2 = 2 + H$. The orbit of $x$ under the right action is the left coset $y$, while the orbit under the left action is the right coset $H$.

History
The concept of a coset dates back to Galois's work of 1830–31. He introduced a notation but did not provide a name for the concept. The term "co-set" apparently appears for the first time in 1910 in a paper by G. A. Miller in the Quarterly Journal of Pure and Applied Mathematics (vol. 41, p. 382). Various other terms have been used including the German Nebengruppen (Weber) and conjugate group (Burnside). (Note that Miller abbreviated his self-citation to the Quarterly Journal of Mathematics; this does not refer to the journal of the same name, which did not start publication until 1930.)

Galois was concerned with deciding when a given polynomial equation was solvable by radicals. A tool that he developed was in noting that a subgroup $H$ of a group of permutations $H$ induced two decompositions of $g$ (what we now call left and right cosets). If these decompositions coincided, that is, if the left cosets are the same as the right cosets, then there was a way to reduce the problem to one of working over $g$ instead of $g$. Camille Jordan in his commentaries on Galois's work in 1865 and 1869 elaborated on these ideas and defined normal subgroups as we have above, although he did not use this term.

Calling the coset $g$ the left coset of $g$ with respect to $H$, while most common today, has not been universally true in the past. For instance, would call $a$ a right coset, emphasizing the subgroup being on the right.

An application from coding theory
A binary linear code is an $b$-dimensional subspace $T$ of an $a$-dimensional vector space $H$ over the binary field $G$. As $H$ is an additive abelian group, $H$ is a subgroup of this group. Codes can be used to correct errors that can occur in transmission. When a codeword (element of $m$) is transmitted some of its bits may be altered in the process and the task of the receiver is to determine the most likely codeword that the corrupted received word could have started out as. This procedure is called decoding and if only a few errors are made in transmission it can be done effectively with only a very few mistakes. One method used for decoding uses an arrangement of the elements of $m$ (a received word could be any element of $m$) into a standard array. A standard array is a coset decomposition of $a$ put into tabular form in a certain way. Namely, the top row of the array consists of the elements of $m$, written in any order, except that the zero vector should be written first. Then, an element of $m$ with a minimal number of ones that does not already appear in the top row is selected and the coset of $O$ containing this element is written as the second row (namely, the row is formed by taking the sum of this element with each element of $m$ directly above it). This element is called a coset leader and there may be some choice in selecting it. Now the process is repeated, a new vector with a minimal number of ones that does not already appear is selected as a new coset leader and the coset of $P$ containing it is the next row. The process ends when all the vectors of $m$ have been sorted into the cosets.

An example of a standard array for the 2-dimensional code $Z = ({..., −2, −1, 0, 1, 2, ...}, +)$ in the 5-dimensional space $P$ (with 32 vectors) is as follows:

The decoding procedure is to find the received word in the table and then add to it the coset leader of the row it is in. Since in binary arithmetic adding is the same operation as subtracting, this always results in an element of $G$. In the event that the transmission errors occurred in precisely the non-zero positions of the coset leader the result will be the right codeword. In this example, if a single error occurs, the method will always correct it, since all possible coset leaders with a single one appear in the array.

Syndrome decoding can be used to improve the efficiency of this method. It is a method of computing the correct coset (row) that a received word will be in. For an $H$-dimensional code $G$ in an $G$-dimensional binary vector space, a parity check matrix is an $H$ matrix $G$ having the property that $(mZ, +) = ({..., −2m, −m, 0, m, 2m, ...}, +)$ if and only if $H$ is in $H$. The vector $G$ is called the syndrome of $mZ$, and by linearity, every vector in the same coset will have the same syndrome. To decode, the search is now reduced to finding the coset leader that has the same syndrome as the received word.

Double cosets
Given two subgroups, $mZ + 1$ and $mZ + (m − 1)$ (which need not be distinct) of a group $mZ + a = \{..., −2m + a, −m + a, a, m + a, 2m + a, ...\}$, the double cosets of $mZ + m = m(Z + 1) = mZ$ and $(mZ + a, +)$ in $mZ$ are the sets of the form $Z$. These are the left cosets of $Z/mZ$ and right cosets of $m$ when $V$ and $W$ respectively.

Two double cosets $a$ and $V$ are either disjoint or identical. The set of all double cosets for fixed $G$ and $G$ form a partition of $H$.

A double coset $R^{2}$ contains the complete right cosets of $G$ (in $H$) of the form $R^{2}$, with $G$ an element of $g$ and the complete left cosets of $gH$ (in $Hg$) of the form $R^{2}$, with $H$ in $G$.

Notation
Let $P + m$ be a group with subgroups $m′$ and $G × H → G$. Several authors working with these sets have developed a specialized notation for their work, where
 * $(g, h) → gh$ denotes the set of left cosets $H × G → G$ of $(h, g) → hg$ in $GF(2)$.
 * $C = \{00000, 01101, 10110, 11011\}$ denotes the set of right cosets $(m − n) × m$ of $xH^{T} = 0$ in $x$.
 * $xH^{T}$ denotes the set of double cosets $x$ of $H$ and $K$ in $G$, sometimes referred to as double coset space.
 * $H$ denotes the double coset space $K$ of the subgroup $G$ in $H$.

More applications

 * Cosets of $G$ in $HgK = \{hgk : h an element of H, k an element of K\}$ are used in the construction of Vitali sets, a type of non-measurable set.
 * Cosets are central in the definition of the transfer.
 * Cosets are important in computational group theory. For example, Thistlethwaite's algorithm for solving Rubik's Cube relies heavily on cosets.
 * In geometry, a Clifford–Klein form is a double coset space $K$, where $H$ is a reductive Lie group, $H = 1$ is a closed subgroup, and $K = 1$ is a discrete subgroup (of $HxK$) that acts properly discontinuously on the homogeneous space $HyK$.

title: Coset


text:
Spanning Tree Protocol

The Spanning Tree Protocol (STP) is a network protocol that builds a loop-free logical topology for Ethernet networks. The basic function of STP is to prevent bridge loops and the broadcast radiation that results from them. Spanning tree also allows a network design to include backup links providing fault tolerance if an active link fails.

As the name suggests, STP creates a spanning tree that characterizes the relationship of nodes within a network of connected layer-2 bridges, and disables those links that are not part of the spanning tree, leaving a single active path between any two network nodes. STP is based on an algorithm that was invented by Radia Perlman while she was working for Digital Equipment Corporation.

In 2001, the IEEE introduced Rapid Spanning Tree Protocol (RSTP) as 802.1w. RSTP provides significantly faster recovery in response to network changes or failures, introducing new convergence behaviors and bridge port roles to do this. RSTP was designed to be backwards-compatible with standard STP.

STP was originally standardized as IEEE 802.1D but the functionality of spanning tree (802.1D), rapid spanning tree (802.1w), and multiple spanning tree (802.1s) has since been incorporated into IEEE 802.1Q-2014.

While STP is still in use today, in most modern networks its primary use is as a loop-protection mechanism rather than a fault tolerance mechanism. Link aggregation protocols such as LACP will bond two or more links to provide fault tolerance while simultaneously increasing overall link capacity.

Protocol operation
The need for the Spanning Tree Protocol (STP) arose because switches in local area networks (LANs) are often interconnected using redundant links to improve resilience should one connection fail. However, this connection configuration creates a switching loop resulting in broadcast radiations and MAC table instability. If redundant links are used to connect switches, then switching loops need to be avoided.

To avoid the problems associated with redundant links in a switched LAN, STP is implemented on switches to monitor the network topology. Every link between switches, and in particular redundant links, are catalogued. The spanning-tree algorithm then blocks forwarding on redundant links by setting up one preferred link between switches in the LAN. This preferred link is used for all Ethernet frames unless it fails, in which case a non-preferred redundant link is enabled. When implemented in a network, STP designates one layer-2 switch as root bridge. All switches then select their best connection towards the root bridge for forwarding and block other redundant links. All switches constantly communicate with their neighbors in the LAN using (BPDUs).

Provided there is more than one link between two switches, the STP root bridge calculates the cost of each path based on bandwidth. STP will select the path with the lowest cost, that is the highest bandwidth, as the preferred link. STP will enable this preferred link as the only path to be used for Ethernet frames between the two switches, and disable all other possible links by designating the switch ports that connect the preferred path as root port.

After STP enabled switches in a LAN have elected the root bridge, all non-root bridges assign one of their ports as root port. This is either the port that connects the switch to the root bridge, or if there are several paths, the port with the preferred path as calculated by the root bridge. Because not all switches are directly connected to the root bridge they communicate amongst each other using STP BPDUs. Each switch adds the cost of its own path to the cost received from the neighboring switches to determine the total cost of a given path to the root bridge. Once the cost of all possible paths to the root bridge have been added up, each switch assigns a port as root port which connects to the path with the lowest cost, or highest bandwidth, that will eventually lead to the root bridge.

Path cost
The STP path cost default was originally calculated by the formula $1 Gbit/s⁄bandwidth$. When faster speeds became available, the default values were adjusted as otherwise speeds above 1 Gbit/s would have been indistinguishable by STP. Its successor RSTP uses a similar formula with a larger numerator: $20 Tbit/s⁄bandwidth$. These formulas lead to the sample values in the table.

Port states
All switch ports in the LAN where STP is enabled are categorized.
 * Blocking: A port that would cause a switching loop if it were active. To prevent the use of looped paths, no user data is sent or received over a blocking port. BPDU data is still received in blocking state. A blocked port may go into forwarding mode if the other links in use fail and the spanning tree algorithm determines the port may transition to the forwarding state.
 * Listening: The switch processes BPDUs and awaits possible new information that would cause it to return to the blocking state. It does not populate the MAC table and it does not forward frames.
 * Learning: While the port does not yet forward frames, it does learn source addresses from frames received and adds them to the MAC table.
 * Forwarding: A port in normal operation receiving and forwarding frames. The port monitors incoming BPDUs that would indicate it should return to the blocking state to prevent a loop.
 * Disabled: A network administrator has manually disabled the switch port.

When a device is first attached to a switch port, it will not immediately start to forward data. It will instead go through a number of states while it processes BPDUs and determines the topology of the network. The port attached to a host such as a computer, printer or server always goes into the forwarding state, albeit after a delay of about 30 seconds while it goes through the listening and learning states. The time spent in the listening and learning states is determined by a value known as the forward delay (default 15 seconds and set by the root bridge). If another switch is connected, the port may remain in blocking mode if it is determined that it would cause a loop in the network. Topology change notification (TCN) BPDUs are used to inform other switches of port changes. TCNs are injected into the network by a non-root switch and propagated to the root. Upon receipt of the TCN, the root switch will set the topology change flag in its normal BPDUs. This flag is propagated to all other switches and instructs them to rapidly age out their forwarding table entries.

Configuration
Before configuring STP, the network topology should be carefully planned. Basic configuration requires that STP be enabled on all switches in the LAN and the same version of STP chosen on each. The administrator may determine which switch will be the root bridge and configure the switches appropriately. If the root bridge goes down, the protocol will automatically assign a new root bridge based on bridge ID. If all switches have the same bridge ID, such as the default ID, and the root bridge goes down, a tie situation arises and the protocol will assign one switch as root bridge based on the switch MAC addresses. Once the switches have been assigned a bridge ID and the protocol has chosen the root bridge switch, the best path to the root bridge is calculated based on port cost, path cost and port priority. Ultimately STP calculates the path cost on the basis of the bandwidth of a link, however links between switches may have the same bandwidth. Administrators can influence the protocol's choice of the preferred path by configuring the port cost, the lower the port cost the more likely it is that the protocol will choose the connected link as root port for the preferred path. The selection of how other switches in the topology choose their root port, or the least cost path to the root bridge, can be influenced by the port priority. The highest priority will mean the path will ultimately be less preferred. If all ports of a switch have the same priority, the port with the lowest number is chosen to forward frames.

Root bridge and the bridge ID

The root bridge of the spanning tree is the bridge with the smallest (lowest) bridge ID. Each bridge has a configurable priority number and a MAC address; the bridge ID is the concatenation of the bridge priority and the MAC address. For example, the ID of a bridge with priority 32,768 and MAC is. The bridge priority default is 32,768 and can be configured only in multiples of 4096. When comparing two bridge IDs, the priority portions are compared first and the MAC addresses are compared only if the priorities are equal. The switch with the lowest priority of all the switches will be the root; if there is a tie, then the switch with the lowest priority and lowest MAC address will be the root. For example, if switches A (MAC = ) and B (MAC = ) both have a priority of 32,768 then switch A will be selected as the root bridge. If the network administrators would like switch B to become the root bridge, they must set its priority to be less than 32,768.

Path to the root bridge
The sequence of events to determine the best received BPDU (which is the best path to the root) is:

 * 1) Lowest root bridge ID (BID) - Determines the root bridge.
 * 2) Lowest cost to the root bridge - Favors the upstream switch with the least cost to root
 * 3) Lowest sender bridge ID - Serves as a tiebreaker if multiple upstream switches have equal cost to root
 * 4) Lowest sender port ID - Serves as a tiebreaker if a switch has multiple (non-EtherChannel) links to a single upstream switch, where:
 * 5) *Bridge ID = priority (4 bits) + locally assigned system ID extension (12 bits) + ID [MAC address] (48 bits); the default bridge priority is 32,768, and
 * 6) *Port ID = priority (4 bits) + ID (Interface number) (12 bits); the default port priority is 128.

Tiebreakers

 * Root ports
 * When multiple paths from a bridge are least-cost paths, the chosen path uses the neighbor bridge with the lower bridge ID. The root port is thus the one connecting to the bridge with the lowest bridge ID. For example, in the figures, if switch 4 were connected to network segment d instead of segment f, there would be two paths of length 2 to the root, one path going through bridge 24 and the other through bridge 92. Because there are two least-cost paths, the lower bridge ID (24) would be used as the tiebreaker in choosing which path to use.

 * Paths
 * When more than one bridge on a segment leads to a least-cost path to the root, the bridge with the lower bridge ID is used to forward messages to the root. The port attaching that bridge to the network segment is the designated port for the segment. In the figures, there are two least-cost paths from network segment d to the root, one going through bridge 24 and the other through bridge 92. The lower bridge ID is 24, so the tiebreaker dictates that the designated port is the port through which network segment d is connected to bridge 24. If bridge IDs were equal, then the bridge with the lowest MAC address would have the designated port. In either case, the loser sets the port as being blocked.

 * Designated ports
 * When the root bridge has more than one port on a single network segment, the bridge ID is effectively tied, as are all root path costs (all equal zero). The port on that network segment with the lowest port ID becomes the designated port. It is put into forwarding mode while all other ports on the root bridge on that same network segment become non-designated ports and are put into blocking mode. Not all bridge manufacturers follow this rule, instead making all root bridge ports designated ports, and putting them all in forwarding mode.

 * Final tiebreaker
 * In some cases, there may still be a tie, as when the root bridge has multiple active ports on the same network segment (see above) with equally low root path costs and bridge IDs, or, in other cases, multiple bridges are connected by multiple cables and multiple ports. In each case, a single bridge may have multiple candidates for its root port. In these cases, candidates for the root port have already received BPDUs offering equally-low (i.e. the "best") root path costs and equally-low (i.e. the "best") bridge IDs, and the final tiebreaker goes to the port that received the lowest (i.e. the "best") port priority ID, or port ID.

Bridge protocol data units
The above rules describe one way of determining what spanning tree will be computed by the algorithm, but the rules as written require knowledge of the entire network. The bridges have to determine the root bridge and compute the port roles (root, designated, or blocked) with only the information that they have. To ensure that each bridge has enough information, the bridges use special data frames called bridge protocol data units (BPDUs) to exchange information about the spanning tree protocol, bridge IDs, and root path costs.

A bridge sends a BPDU frame using the unique MAC address of the port itself as a source address, and a destination address of the STP multicast address with destination MAC, or for Cisco proprietary Per-VLAN Spanning Tree.

There are two types of BPDUs in the original STP specification (802.1D) (the Rapid Spanning Tree (RSTP) extension uses a specific RSTP BPDU):
 * Configuration BPDU (CBPDU), used for spanning tree computation and sent by root bridges to provide information to all switches.
 * Topology change notification (TCN) BPDU, used to announce changes in the network topology, such as port up or port down.

BPDUs are exchanged regularly (every 2 seconds by default) and enable switches to keep track of network changes and to start and stop forwarding at ports as required. To prevent the delay when connecting hosts to a switch and during some topology changes, Rapid STP was developed, which allows a switch port to rapidly transition into the forwarding state during these situations.

Bridge protocol data unit fields
IEEE 802.1D and IEEE 802.1aq BPDUs have the following format:

1. Protocol ID:   2 bytes (0x0000 IEEE 802.1D) 2. Version ID:    1 byte (0x00 Config & TCN / 0x02 RST / 0x03 MST / 0x04 SPT  BPDU) 3. BPDU Type:     1 byte (0x00 STP Config BPDU, 0x80 TCN BPDU, 0x02 RST/MST Config BPDU) 4. Flags:         1 byte bits : usage 1 : 0 or 1 for Topology Change 2 : 0 (unused) or 1 for Proposal in RST/MST/SPT BPDU 3–4 : 00 (unused) or           01 for Port Role Alternate/Backup in RST/MST/SPT BPDU 10 for Port Role Root in RST/MST/SPT BPDU 11 for Port Role Designated in RST/MST/SPT BPDU 5 : 0 (unused) or 1 for Learning in RST/MST/SPT BPDU 6 : 0 (unused) or 1 for Forwarding in RST/MST/SPT BPDU 7 : 0 (unused) or 1 for Agreement in RST/MST/SPT BPDU 8 : 0 or 1 for Topology Change Acknowledgement 5. Root ID:       8 bytes (CIST Root ID in MST/SPT BPDU) bits : usage 1–4 : Root Bridge Priority 5–16 : Root Bridge System ID Extension 17–64 : Root Bridge MAC Address 6. Root Path Cost: 4 bytes (CIST External Path Cost in MST/SPT BPDU) 7. Bridge ID:     8 bytes (CIST Regional Root ID in MST/SPT BPDU) bits : usage 1–4 : Bridge Priority 5–16 : Bridge System ID Extension 17–64 : Bridge MAC Address 8. Port ID:      2 bytes 9. Message Age:  2 bytes in 1/256 secs 10. Max Age:      2 bytes in 1/256 secs 11. Hello Time:   2 bytes in 1/256 secs 12. Forward Delay: 2 bytes in 1/256 secs 13. Version 1 Length: 1 byte (0x00 no ver 1 protocol info present. RST, MST, SPT BPDU only) 14. Version 3 Length: 2 bytes (MST, SPT BPDU only) The TCN BPDU includes fields 1–3 only.

Spanning Tree Protocol standards
The first spanning tree protocol was invented in 1985 at the Digital Equipment Corporation by Radia Perlman. In 1990, the IEEE published the first standard for the protocol as 802.1D, based on the algorithm designed by Perlman. Subsequent versions were published in 1998 and 2004, incorporating various extensions. The original Perlman-inspired Spanning Tree Protocol, called DEC STP, is not a standard and differs from the IEEE version in message format as well as timer settings. Some bridges implement both the IEEE and the DEC versions of the Spanning Tree Protocol, but their interworking can create issues for the network administrator.

Different implementations of a standard are not guaranteed to interoperate, due for example to differences in default timer settings. The IEEE encourages vendors to provide a Protocol Implementation Conformance Statement, declaring which capabilities and options have been implemented, to help users determine whether different implementations will interoperate correctly.

Rapid Spanning Tree Protocol
In 2001, the IEEE introduced Rapid Spanning Tree Protocol (RSTP) as IEEE 802.1w. RSTP was then incorporated into IEEE 802.1D-2004 making the original STP standard obsolete. RSTP was designed to be backward-compatible with standard STP.

RSTP provides significantly faster spanning tree convergence after a topology change, introducing new convergence behaviors and bridge port roles to accomplish this. While STP can take 30 to 50 seconds to respond to a topology change, RSTP is typically able to respond to changes within 3 × hello times (default: 3 2 seconds) or within a few milliseconds of a physical link failure. The hello time is an important and configurable time interval that is used by RSTP for several purposes; its default value is 2 seconds.

Rapid Spanning Tree operation
RSTP adds new bridge port roles in order to speed convergence following a link failure:
 * Root - A forwarding port that is the best port from non-root bridge to root bridge
 * Designated - A forwarding port for every network segment
 * Alternate - An alternate path to the root bridge. This path is different from using the root port
 * Backup - A backup/redundant path to a segment where another bridge port already connects
 * Disabled - Not strictly part of STP, a network administrator can manually disable a port

The number of switch port states a port can be in has been reduced to three instead of STP's original five:
 * Discarding - No user data is sent over the port
 * Learning - The port is not forwarding frames yet, but is populating its MAC address table
 * Forwarding - The port is fully operational

RSTP operational details:
 * Detection of root switch failure is done in 3 hello times, which is 6 seconds if the default hello times have not been changed.
 * Ports may be configured as edge ports if they are attached to a LAN that has no other bridges attached (depending on vendor, admin-edge or portfast mode). These edge ports transition directly to the forwarding state, avoiding problems with hosts expecting an upcoming link to work right away, e.g. with DHCP. RSTP still continues to monitor the port for BPDUs in case a bridge is connected. RSTP can also be configured to automatically detect edge ports. As soon as the bridge detects a BPDU coming to an edge port, the port becomes a non-edge port.
 * RSTP calls the connection between two or more switches as a "link-type" connection. A port that operates in full-duplex mode is assumed to be point-to-point link, whereas a half-duplex port (through a hub) is considered a shared port by default. This automatic link type setting can be overridden by explicit configuration. RSTP improves convergence on point-to-point links by reducing the Max-Age time to 3 times Hello interval, removing the STP listening state, and exchanging a handshake between two switches to quickly transition the port to forwarding state. RSTP does not do anything differently from STP on shared links.
 * Unlike in STP, RSTP will respond to BPDUs sent from the direction of the root bridge. An RSTP bridge will propose its spanning tree information to its designated ports. If another RSTP bridge receives this information and determines this is the superior root information, it sets all its other ports to discarding. The bridge may send an agreement to the first bridge confirming its superior spanning tree information. The first bridge, upon receiving this agreement, knows it can rapidly transition that port to the forwarding state bypassing the listening/learning state transition. This essentially creates a cascading effect away from the root bridge where each designated bridge proposes to its neighbors to determine if it can make a rapid transition. This is one of the major elements that allows RSTP to achieve faster convergence times than STP.
 * As discussed in the port role details above, RSTP maintains backup details regarding the discarding status of ports. This avoids timeouts if the current forwarding ports were to fail or BPDUs were not received on the root port in a certain interval.
 * RSTP will revert to legacy STP on an interface if a legacy version of an STP BPDU is detected on that port.

Standards for VLANs
STP and RSTP do not segregate switch ports by VLAN. However, in Ethernet switched environments where multiple VLANs exist, it is often desirable to create multiple spanning trees so that traffic on different VLANs uses different links.

Proprietary standards
Before the IEEE published a Spanning Tree Protocol standard for VLANs, a number of vendors who sold VLAN capable switches developed their own Spanning Tree Protocol versions that were VLAN capable. Cisco developed, implemented and published the Per-VLAN Spanning Tree (PVST) proprietary protocol using its own proprietary Inter-Switch Link (ISL) for VLAN encapsulation, and PVST+ which uses 802.1Q VLAN encapsulation. Both standards implement a separate spanning tree for every VLAN. Cisco switches now commonly implement PVST+ and can only implement Spanning Trees for VLANs if the other switches in the LAN implement the same VLAN STP protocol. HP provides PVST and PVST+ compatibility in some of its network switches. Some devices from Force10 Networks, Alcatel-Lucent, Extreme Networks, Avaya, Brocade Communications Systems and BLADE Network Technologies support PVST+. Extreme Networks does so with two limitations: Lack of support on ports where the VLAN is untagged/native, and also on the VLAN with ID 1. PVST+ can tunnel across an MSTP Region.

The switch vendor Juniper Networks in turn developed and implemented its VLAN Spanning Tree Protocol (VSTP) to provide compatibility with Cisco's PVST, so that the switches from both vendors can be included in one LAN. The VSTP protocol is only supported by the EX and MX Series from Juniper Networks. There are two restrictions to the compatibility of VSTP:
 * 1) VSTP supports only 253 different spanning-tree topologies. If there are more than 253 VLANs, it is recommended to configure RSTP in addition to VSTP, and VLANs beyond 253 will be handled by RSTP.
 * 2) MVRP does not support VSTP. If this protocol is in use, VLAN membership for trunk interfaces must be statically configured.

By default, VSTP uses the RSTP protocol as its core spanning-tree protocol, but usage of STP can be forced if the network includes old bridges. More information about configuring VSTP on Juniper Networks switches was published in the official documentation.

Cisco also published a proprietary version of Rapid Spanning Tree Protocol. It creates a spanning tree for each VLAN, just like PVST. Cisco refers to this as Rapid Per-VLAN Spanning Tree (RPVST).

Multiple Spanning Tree Protocol
The Multiple Spanning Tree Protocol (MSTP), originally defined in IEEE 802.1s-2002 and later merged into IEEE 802.1Q-2005, defines an extension to RSTP to further develop the usefulness of VLANs.

In the standard, a spanning tree that maps one or more VLANs is called a multiple spanning tree (MST). Under MSTP, a spanning tree can be defined for individual VLANs or for groups of VLANs. Furthermore, the administrator can define alternate paths within a spanning tree. Switches are first assigned to an MST region, then VLANs are mapped against or assigned to this MST. A common spanning tree (CST) is an MST to which several VLANs are mapped, this group of VLANs is called MST instance (MSTI). CSTs are backward compatible with the STP and RSTP standard. A MST that has only one VLAN assigned to it is an internal spanning tree (IST).

Unlike some proprietary per-VLAN spanning tree implementations, MSTP includes all of its spanning tree information in a single BPDU format. Not only does this reduce the number of BPDUs required to communicate spanning tree information for each VLAN, but it also ensures backward compatibility with RSTP and, in effect, classic STP too. MSTP does this by encoding an additional region of information after the standard RSTP BPDU as well as a number of MSTI messages (from 0 to 64 instances, although in practice many bridges support fewer). Each of these MSTI configuration messages conveys the spanning tree information for each instance. Each instance can be assigned a number of configured VLANs and frames assigned to these VLANs operate in this spanning tree instance whenever they are inside the MST region. In order to avoid conveying their entire VLAN to spanning tree mapping in each BPDU, bridges encode an MD5 digest of their VLAN to instance table in the MSTP BPDU. This digest is then used by other MSTP bridges, along with other administratively configured values, to determine if the neighboring bridge is in the same MST region as itself.

MSTP is fully compatible with RSTP bridges in that an MSTP BPDU can be interpreted by an RSTP bridge as an RSTP BPDU. This not only allows compatibility with RSTP bridges without configuration changes but also causes any RSTP bridges outside of an MSTP region to see the region as a single RSTP bridge regardless of the number of MSTP bridges inside the region itself. In order to further facilitate this view of an MSTP region as a single RSTP bridge, the MSTP protocol uses a variable known as remaining hops as a time to live counter instead of the message age timer used by RSTP. The message age time is only incremented once when spanning-tree information enters an MST region, and therefore RSTP bridges will see a region as only one hop in the spanning tree. Ports at the edge of an MSTP region connected to either an RSTP or STP bridge or an endpoint are known as boundary ports. As in RSTP, these ports can be configured as edge ports to facilitate rapid changes to the forwarding state when connected to endpoints.

Shortest path bridging
IEEE 802.1aq, also known as Shortest Path Bridging (SPB), allows redundant links between switches to be active through multiple equal cost paths, and provides much larger layer-2 topologies, faster convergence, and improves the use of the mesh topologies through increased bandwidth between all devices by allowing traffic to load share across all paths on a mesh network. SPB consolidates multiple existing functionalities, including Spanning Tree Protocol (STP), Multiple Spanning Tree Protocol (MSTP), Rapid Spanning Tree Protocol (RSTP), Link aggregation, and Multiple MAC Registration Protocol (MMRP) into a one link state protocol.

System ID Extension
The bridge ID (BID) is a field inside a BPDU packet. It is eight bytes in length. The first two bytes are the bridge priority, an unsigned integer of 0–65,535. The last six bytes are a MAC address supplied by the bridge. Prior to IEEE 802.1D-2004, the first two bytes gave a 16-bit bridge priority. Since IEEE 802.1D-2004, the first four bits are a configurable priority, and the last twelve bits carry the bridge system ID extension. In the case of MST, the bridge system ID extension carries the MSTP instance number. Some vendors set the bridge system ID extension to carry a VLAN ID allowing a different spanning tree per VLAN, such as Cisco's PVST.

Disadvantages and current practice
Spanning tree is an older protocol with a longer convergence time. Improper use or implementation can contribute to network disruptions. Blocking links is a crude approach to high availability and preventing loops. Modern networks can make use of all connected links by use of protocols that inhibit, control or suppress the natural behavior of logical or physical topology loops.

Newer, more robust protocols include the TRILL (Transparent Interconnection of Lots of Links) protocol, also created by Perlman, and Shortest Path Bridging from the IEEE.

Configuring connections between network equipment as layer-3 IP links and relying on IP routing for resiliency and to prevent loops is a popular alternative.

Switch virtualization techniques like Cisco Virtual Switching System and Virtual PortChannel and HP Intelligent Resilient Framework combine multiple switches into a single logical entity. Such a multi-chassis link aggregation group works like a normal port trunk, only distributed through multiple switches. Conversely, partitioning technologies compartmentalize a single physical chassis into multiple logical entities.

On the edge of the network, loop-detection is configured to prevent accidental loops by users.

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/

title: Spanning Tree Protocol


text:
Serialism

In music, serialism is a method of composition using series of pitches, rhythms, dynamics, timbres or other musical elements. Serialism began primarily with Arnold Schoenberg's twelve-tone technique, though some of his contemporaries were also working to establish serialism as a form of post-tonal thinking. Twelve-tone technique orders the twelve notes of the chromatic scale, forming a row or series and providing a unifying basis for a composition's melody, harmony, structural progressions, and variations. Other types of serialism also work with sets, collections of objects, but not necessarily with fixed-order series, and extend the technique to other musical dimensions (often called "parameters"), such as duration, dynamics, and timbre.

The idea of serialism is also applied in various ways in the visual arts, design, and architecture, and the musical concept has also been adapted in literature.

Integral serialism or total serialism is the use of series for aspects such as duration, dynamics, and register as well as pitch. Other terms, used especially in Europe to distinguish post-World War II serial music from twelve-tone music and its American extensions, are general serialism and multiple serialism.

Composers such as Arnold Schoenberg, Anton Webern, Alban Berg, Karlheinz Stockhausen, Pierre Boulez, Luigi Nono, Milton Babbitt, Elisabeth Lutyens, Henri Pousseur, Charles Wuorinen and Jean Barraqué used serial techniques of one sort or another in most of their music. Other composers such as Tadeusz Baird, Béla Bartók, Luciano Berio, Bruno Maderna, Franco Donatoni, Benjamin Britten, John Cage, Aaron Copland, Ernst Krenek, György Ligeti, Olivier Messiaen, Arvo Pärt, Walter Piston, Ned Rorem, Alfred Schnittke, Ruth Crawford Seeger, Dmitri Shostakovich, and Igor Stravinsky used serialism only in some of their compositions or only in some sections of pieces, as did some jazz composers, such as Bill Evans, Yusef Lateef, Bill Smith, and even rock musicians like Frank Zappa.

Basic definitions
Serialism is a method, "highly specialized technique", or "way" of composition. It may also be considered "a philosophy of life (Weltanschauung), a way of relating the human mind to the world and creating a completeness when dealing with a subject".

Serialism is not by itself a system of composition or a style. Neither is pitch serialism necessarily incompatible with tonality, though it is most often used as a means of composing atonal music.

"Serial music" is a problematic term because it is used differently in different languages and especially because, shortly after its coinage in French, it underwent essential alterations during its transmission to German. The term's use in connection with music was first introduced in French by René Leibowitz in 1947, and immediately afterward by Humphrey Searle in English, as an alternative translation of the German Zwölftontechnik (twelve-tone technique) or Reihenmusik (row music); it was independently introduced by Stockhausen and Herbert Eimert into German in 1955 as serielle Musik, with a different meaning, but also translated as "serial music".

Twelve-tone serialism
Serialism of the first type is most specifically defined as a structural principle according to which a recurring series of ordered elements (normally a set—or row—of pitches or pitch classes) is used in order or manipulated in particular ways to give a piece unity. "Serial" is often broadly used to describe all music written in what Schoenberg called "The Method of Composing with Twelve Notes related only to one another", or dodecaphony, and methods that evolved from his methods. It is sometimes used more specifically to apply only to music in which at least one element other than pitch is treated as a row or series. Such methods are often called post-Webernian serialism. Other terms used to make the distinction are twelve-note serialism for the former and integral serialism for the latter.

A row may be assembled pre-compositionally (perhaps to embody particular intervallic or symmetrical properties), or derived from a spontaneously invented thematic or motivic idea. The row's structure does not in itself define the structure of a composition, which requires development of a comprehensive strategy. The choice of strategy often depends on the relationships contained in a row class, and rows may be constructed with an eye to producing the relationships needed to form desired strategies.

The basic set may have additional restrictions, such as the requirement that it use each interval only once.

Non-twelve-tone serialism
"The series is not an order of succession, but indeed a hierarchy—which may be independent of this order of succession".

Rules of analysis derived from twelve-tone theory do not apply to serialism of the second type: "in particular the ideas, one, that the series is an intervallic sequence, and two, that the rules are consistent". For example, Stockhausen's early serial works, such as Kreuzspiel and Formel, "advance in unit sections within which a preordained set of pitches is repeatedly reconfigured ... The composer's model for the distributive serial process corresponds to a development of the Zwölftonspiel of Josef Matthias Hauer". Goeyvaerts's Nummer 4 "provides a classic illustration of the distributive function of seriality: 4 times an equal number of elements of equal duration within an equal global time is distributed in the most equable way, unequally with regard to one another, over the temporal space: from the greatest possible coïncidence to the greatest possible dispersion. This provides an exemplary demonstration of that logical principle of seriality: every situation must occur once and only once." Henri Pousseur, after initially working with twelve-tone technique in works like Sept Versets (1950) and Trois Chants sacrés (1951),"evolved away from this bond in Symphonies pour quinze Solistes [1954–55] and in the Quintette [à la mémoire d’Anton Webern, 1955], and from around the time of Impromptu [1955] encounters whole new dimensions of application and new functions." "The twelve-tone series loses its imperative function as a prohibiting, regulating, and patterning authority; its working-out is abandoned through its own constant-frequent presence: all 66 intervallic relations among the 12 pitches being virtually present. Prohibited intervals, like the octave, and prohibited successional relations, such as premature note repetitions, frequently occur, although obscured in the dense contexture. The number twelve no longer plays any governing, defining rôle; the pitch constellations no longer hold to the limitation determined by their formation. The dodecaphonic series loses its significance as a concrete model of shape (or a well-defined collection of concrete shapes) is played out. And the chromatic total remains active only, and provisionally, as a general reference." In the 1960s Pousseur took this a step further, applying a consistent set of predefined transformations to preexisting music. One example is the large orchestral work Couleurs croisées (Crossed Colours, 1967), which performs these transformations on the protest song "We Shall Overcome", creating a succession of different situations that are sometimes chromatic and dissonant and sometimes diatonic and consonant. In his opera Votre Faust (Your Faust, 1960–68) Pousseur used many quotations, themselves arranged into a "scale" for serial treatment. This "generalised" serialism (in the strongest possible sense) aims not to exclude any musical phenomena, no matter how heterogeneous, in order "to control the effects of tonal determinism, dialectize its causal functions, and overcome any academic prohibitions, especially the fixing of an anti-grammar meant to replace some previous one".

At about the same time, Stockhausen began using serial methods to integrate a variety of musical sources from recorded examples of folk and traditional music from around the world in his electronic composition Telemusik (1966), and from national anthems in Hymnen (1966–67). He extended this serial "polyphony of styles" in a series of "process-plan" works in the late 1960s, as well as later in portions of Licht, the cycle of seven operas he composed between 1977 and 2003.

Before World War II
In the late 19th and early 20th century, composers began to struggle against the ordered system of chords and intervals known as "functional tonality". Composers such as Debussy and Strauss found ways to stretch the limits of the tonal system to accommodate their ideas. After a brief period of free atonality, Schoenberg and others began exploring tone rows, in which an ordering of the 12 pitches of the equal-tempered chromatic scale is used as the source material of a composition. This ordered set, often called a row, allowed for new forms of expression and (unlike free atonality) the expansion of underlying structural organizing principles without recourse to common practice harmony.

Twelve-tone serialism first appeared in the 1920s, with antecedents predating that decade (instances of 12-note passages occur in Liszt's Faust Symphony and in Bach.) Schoenberg was the composer most decisively involved in devising and demonstrating the fundamentals of twelve-tone serialism, though it is clear it is not the work of just one musician. In Schoenberg's own words, his goal of l'invention contrariée was to show constraint in composition. Consequently, some reviewers have jumped to the conclusion that serialism acted as a predetermined method of composing to avoid the subjectivity and ego of a composer in favour of calculated measure and proportion.

After World War II
Along with John Cage's indeterminate music (music composed with the use of chance operations) and Werner Meyer-Eppler's aleatoricism, serialism was enormously influential in postwar music. Theorists such as Milton Babbitt and George Perle codified serial systems, leading to a mode of composition called "total serialism", in which every aspect of a piece, not just pitch, is serially constructed. Perle's 1962 text Serial Composition and Atonality became a standard work on the origins of serial composition in the music of Schoenberg, Berg, and Webern.

The serialization of rhythm, dynamics, and other elements of music was partly fostered by the work of Olivier Messiaen and his analysis students, including Karel Goeyvaerts and Boulez, in postwar Paris. Messiaen first used a chromatic rhythm scale in his Vingt Regards sur l'enfant-Jésus (1944), but he did not employ a rhythmic series until 1946–48, in the seventh movement, "Turangalîla II", of his Turangalîla-Symphonie. The first examples of such integral serialism are Babbitt's Three Compositions for Piano (1947), Composition for Four Instruments (1948), and Composition for Twelve Instruments (1948). He worked independently of the Europeans. Several of the composers associated with Darmstadt, notably Stockhausen, Goeyvaerts, and Pousseur, developed a form of serialism that initially rejected the recurring rows characteristic of twelve-tone technique in order to eradicate any lingering traces of thematicism. Instead of a recurring, referential row, "each musical component is subjected to control by a series of numerical proportions". In Europe, some serial and non-serial music of the early 1950s emphasized the determination of all parameters for each note independently, often resulting in widely spaced, isolated "points" of sound, an effect called first in German "punktuelle Musik" ("pointist" or "punctual music"), then in French "musique ponctuelle", but quickly confused with "pointillistic" (German "pointillistische", French "pointilliste"), the term associated with the densely packed dots in Seurat's paintings, even though the concept was unrelated.

Pieces were structured by closed sets of proportions, a method closely related to certain works from the de Stijl and Bauhaus movements in design and architecture some writers called "serial art", specifically the paintings of Piet Mondrian, Theo van Doesburg, Bart van Leck, Georg van Tongerloo, Richard Paul Lohse, and Burgoyne Diller, who had sought to "avoid repetition and symmetry on all structural levels and working with a limited number of elements".

Stockhausen described the final synthesis in this manner:"So serial thinking is something that's come into our consciousness and will be there forever: it's relativity and nothing else. It just says: Use all the components of any given number of elements, don't leave out individual elements, use them all with equal importance and try to find an equidistant scale so that certain steps are no larger than others. It's a spiritual and democratic attitude toward the world. The stars are organized in a serial way. Whenever you look at a certain star sign you find a limited number of elements with different intervals. If we more thoroughly studied the distances and proportions of the stars we'd probably find certain relationships of multiples based on some logarithmic scale or whatever the scale may be."

Stravinsky's adoption of twelve-tone serial techniques shows the level of influence serialism had after the Second World War. Previously Stravinsky had used series of notes without rhythmic or harmonic implications. Because many of the basic techniques of serial composition have analogs in traditional counterpoint, uses of inversion, retrograde, and retrograde inversion from before the war do not necessarily indicate Stravinsky was adopting Schoenbergian techniques. But after meeting Robert Craft and other younger composers, Stravinsky began to study Schoenberg's music, as well as that of Webern and later composers, and to adapt their techniques in his work, using, for example, serial techniques applied to fewer than twelve notes. During the 1950s he used procedures related to Messiaen, Webern and Berg. While it is inaccurate to call them all "serial" in the strict sense, all his major works of the period have clear serialist elements.

During this period, the concept of serialism influenced not only new compositions but also scholarly analysis of the classical masters. Adding to their professional tools of sonata form and tonality, scholars began to analyze previous works in the light of serial techniques; for example, they found the use of row technique in previous composers going back to Mozart and Beethoven. In particular, the orchestral outburst that introduces the development section halfway through the last movement of Mozart's Symphony No. 40 is a tone row that Mozart punctuates in a very modern and violent way that Michael Steinberg called "rude octaves and frozen silences".

Ruth Crawford Seeger extended serial control to parameters other than pitch and to formal planning as early as 1930–33 in a fashion that goes beyond Webern but was less thoroughgoing than the later practices of Babbitt and European postwar composers. Charles Ives's 1906 song "The Cage" begins with piano chords presented in incrementally decreasing durations, an early example of an overtly arithmetic duration series independent of meter (like Nono's six-element row shown above), and in that sense a precursor to Messiaen's style of integral serialism. The idea of organizing pitch and rhythm according to similar or related principles is also suggested by both Henry Cowell's New Musical Resources (1930) and the work of Joseph Schillinger.

Reactions to serialism
Some music theorists have criticized serialism on the basis that its compositional strategies are often incompatible with the way the human mind processes a piece of music. Nicolas Ruwet (1959) was one of the first to criticise serialism by a comparison with linguistic structures, citing theoretical claims by Boulez and Pousseur, taking as specific examples bars from Stockhausen's Klavierstücke I & II, and calling for a general reexamination of Webern's music. Ruwet specifically names three works as exempt from his criticism: Stockhausen's Zeitmaße and Gruppen, and Boulez's Le marteau sans maître.

In response, Pousseur questioned Ruwet's equivalence between phonemes and notes. He also suggested that, if analysis of Le marteau sans maître and Zeitmaße, "performed with sufficient insight", were to be made from the point of view of wave theory—taking into account the dynamic interaction of the different component phenomena, which creates "waves" that interact in a sort of frequency modulation—the analysis "would accurately reflect the realities of perception". This was because these composers had long since acknowledged the lack of differentiation found in punctual music and, becoming increasingly aware of the laws of perception and complying better with them, "paved the way to a more effective kind of musical communication, without in the least abandoning the emancipation that they had been allowed to achieve by this 'zero state' that was punctual music". One way this was achieved was by developing the concept of "groups", which allows structural relationships to be defined not only between individual notes but also at higher levels, up to the overall form of a piece. This is "a structural method par excellence", and a sufficiently simple conception that it remains easily perceptible. Pousseur also points out that serial composers were the first to recognize and attempt to move beyond the lack of differentiation within certain pointillist works. Pousseur later followed up on his own suggestion by developing his idea of "wave" analysis and applying it to Stockhausen's Zeitmaße in two essays.

Later writers have continued both lines of reasoning. Fred Lerdahl, for example, in his essay "Cognitive Constraints on Compositional Systems", argues that serialism's perceptual opacity ensures its aesthetic inferiority. Lerdahl has in turn been criticized for excluding "the possibility of other, non-hierarchical methods of achieving musical coherence," and for concentrating on the audibility of tone rows, and the portion of his essay focusing on Boulez's "multiplication" technique (exemplified in three movements of Le Marteau sans maître) has been challenged on perceptual grounds by Stephen Heinemann and Ulrich Mosch. Ruwet's critique has also been criticised for making "the fatal mistake of equating visual presentation (a score) with auditive presentation (the music as heard)".

In all these reactions discussed above, the "information extracted", "perceptual opacity", "auditive presentation" (and constraints thereof) pertain to what defines serialism, namely use of a series. And since Schoenberg remarked, "in the later part of a work, when the set [series] had already become familiar to the ear", it has been assumed that serial composers expect their series to be aurally perceived. This principle even became the premise of empirical investigation in the guise of "probe-tone" experiments testing listeners' familiarity with a row after exposure to its various forms (as would occur in a 12-tone work). In other words the supposition in critiques of serialism has been that, if a composition is so intricately structured by and around a series, that series should ultimately be clearly perceived or that a listener ought to become aware of its presence or importance. Babbitt denied this: "That's not the way I conceive of a set [series]. This is not a matter of finding the lost [series]. This is not a matter of cryptoanalysis (where's the hidden [series]?). What I'm interested in is the effect it might have, the way it might assert itself not necessarily explicitly."

Seemingly in accord with Babbitt's statement, but ranging over such issues as perception, aesthetic value, and the "poietic fallacy", Walter Horn offers a more extensive explanation of the serialism (and atonality) controversy.

Within the community of modern music, exactly what constituted serialism was also a matter of debate. The conventional English usage is that the word "serial" applies to all twelve-tone music, which is a subset of serial music, and it is this usage that is generally intended in reference works. Nevertheless, a large body of music exists that is called "serial" but does not employ note-rows at all, let alone twelve-tone technique, e.g., Stockhausen's Klavierstücke I–IV (which use permuted sets), his Stimmung (with pitches from the overtone series, which is also used as the model for the rhythms), and Pousseur's Scambi (where the permuted sounds are made exclusively from filtered white noise).

When serialism is not limited to twelve-tone techniques, a contributing problem is that the word "serial" is seldom if ever defined. In many published analyses of individual pieces the term is used while actual meaning is skated around.

Theory of twelve-tone serial music
Due to Babbitt's work, in the mid-20th century serialist thought became rooted in set theory and began to use a quasi-mathematical vocabulary for the manipulation of the basic sets. Musical set theory is often used to analyze and compose serial music, and is also sometimes used in tonal and nonserial atonal analysis.

The basis for serial composition is Schoenberg's twelve-tone technique, where the 12 notes of the chromatic scale are organized into a row. This "basic" row is then used to create permutations, that is, rows derived from the basic set by reordering its elements. The row may be used to produce a set of intervals, or a composer may derive the row from a particular succession of intervals. A row that uses all of the intervals in their ascending form once is an all-interval row. In addition to permutations, the basic row may have some set of notes derived from it, which is used to create a new row. These are derived sets.

Because there are tonal chord progressions that use all twelve notes, it is possible to create pitch rows with very strong tonal implications, and even to write tonal music using twelve-tone technique. Most tone rows contain subsets that can imply a pitch center; a composer can create music centered on one or more of the row's constituent pitches by emphasizing or avoiding these subsets, respectively, as well as through other, more complex compositional devices.

To serialize other elements of music, a system quantifying an identifiable element must be created or defined (this is called "parametrization", after the term in mathematics). For example, if duration is serialized, a set of durations must be specified; if tone colour (timbre) is serialized, a set of separate tone colours must be identified; and so on.

The selected set or sets, their permutations and derived sets form the composer's basic material.

Composition using twelve-tone serial methods focuses on each appearance of the collection of twelve chromatic notes, called an aggregate. (Sets of more or fewer pitches, or of elements other than pitch, may be treated analogously.) One principle operative in some serial compositions is that no element of the aggregate should be reused in the same contrapuntal strand (statement of a series) until all the other members have been used, and each member must appear only in its place in the series. Yet, since most serial compositions have multiple (at least two, sometimes as many as a few dozen) series statements occurring concurrently, interwoven with each other in time, and feature repetitions of some of their pitches, this principle as stated is more a referential abstraction than a description of the concrete reality of a musical work that is termed "serial".

A series may be divided into subsets, and the members of the aggregate not part of a subset are said to be its complement. A subset is self-complementing if it contains half of the set and its complement is also a permutation of the original subset. This is most commonly seen with hexachords, six-note segments of a tone row. A hexachord that is self-complementing for a particular permutation is called prime combinatorial. A hexachord that is self-complementing for all the canonic operations—inversion, retrograde, and retrograde inversion—is called all-combinatorial.

Notable composers

 * Hans Abrahamsen
 * Gilbert Amy
 * Louis Andriessen
 * Denis ApIvor
 * Hans Erich Apostel
 * Kees van Baaren
 * Milton Babbitt
 * Tadeusz Baird
 * Osvaldas Balakauskas
 * Don Banks
 * Jean Barraqué
 * Jürg Baur
 * Alban Berg
 * Gunnar Berg
 * Arthur Berger
 * Erik Bergman
 * Luciano Berio
 * Karl-Birger Blomdahl
 * Konrad Boehmer
 * Rob du Bois
 * André Boucourechliev
 * Pierre Boulez
 * Martin Boykan
 * Ole Buck
 * Jacques Calonne
 * Niccolò Castiglioni
 * Aldo Clementi
 * Salvador Contreras
 * Aaron Copland
 * Luigi Dallapiccola
 * Franco Donatoni
 * Hanns Eisler
 * Manuel Enríquez
 * Karlheinz Essl
 * Franco Evangelisti
 * Brian Ferneyhough
 * Jacobo Ficher
 * Irving Fine
 * Wolfgang Fortner
 * Roberto Gerhard
 * Frans Geysen
 * Michael Gielen
 * Alberto Ginastera
 * Lucien Goethals
 * Karel Goeyvaerts
 * Jerry Goldsmith
 * Henryk Górecki
 * Glenn Gould
 * Pelle Gudmundsen-Holmgreen
 * César Guerra-Peixe
 * Lou Harrison
 * Jonathan Harvey
 * Josef Matthias Hauer
 * Paavo Heininen
 * Hermann Heiss
 * Hans Werner Henze
 * York Höller
 * Heinz Holliger
 * Bill Hopkins
 * Klaus Huber
 * Karel Husa
 * Hanns Jelinek
 * Ben Johnston
 * Nikolai Karetnikov
 * Rudolf Kelterborn
 * Gottfried Michael Koenig
 * Józef Koffler
 * Ernst Krenek
 * Meyer Kupferman
 * René Leibowitz
 * Ingvar Lidholm
 * Witold Lutosławski
 * Elisabeth Lutyens
 * John McGuire
 * Bruno Maderna
 * Ursula Mamlok
 * Philippe Manoury
 * Donald Martino
 * Paul Méfano
 * Jacques-Louis Monod
 * Robert Morris
 * Luigi Nono
 * Per Nørgård
 * Krzysztof Penderecki
 * Goffredo Petrassi
 * Michel Philippot
 * Walter Piston
 * Henri Pousseur
 * Einojuhani Rautavaara
 * Roger Reynolds
 * Terry Riley
 * George Rochberg
 * Leonard Rosenman
 * Cláudio Santoro
 * Peter Schat
 * Leon Schidlowsky
 * Dieter Schnebel
 * Arnold Schoenberg, considered the founder of serialism
 * Humphrey Searle
 * Ruth Crawford Seeger
 * Mátyás Seiber
 * Roger Sessions
 * Nikos Skalkottas
 * Roger Smalley
 * Ann Southam
 * Leopold Spinner
 * Karlheinz Stockhausen
 * Igor Stravinsky
 * Robert Suderburg
 * Richard Swift
 * Louise Talma
 * Camillo Togni
 * Gilles Tremblay
 * Fartein Valen
 * Wladimir Vogel
 * Anton Webern
 * Hugo Weisgall
 * Peter Westergaard
 * Stefan Wolpe
 * Charles Wuorinen
 * La Monte Young

title: Serialism