#  Joseph Carter Corbin: Arkansas’s “Profound Mathematician”

Jesse Leo Kass  Jesse Leo Kass is an assistant professor at UC Santa Cruz. His
email address is<EMAIL_ADDRESS>
While Joseph Carter Corbin (1833–1911) is a celebrated figure remembered for
his impact in higher education and politics within the state of
Arkansas,111Corbin’s life is the subject of book [corbinBioBook] and an
article [rothrock]. The present account of Corbin’s life draws heavily from
those publications, and we provide citations only for those facts not
documented in those sources. he is absent from many modern historical accounts
of American mathematicians.222Two notable exceptions which discuss Corbin’s
publications in the American Mathematical Monthly are [means59,
MAA_article15]. However, during his lifetime Corbin was very much part of the
mathematical community. He was described as a “Profound Mathematician” in Men
of Mark, an influential anthology of accomplished Black men [menOfMark]*pp.
829–832. He regularly contributed to mathematical periodicals like the
American Mathematical Monthly. Upon his death, the Monthly commemorated him by
publishing his obituary [corbinObit].

Corbin’s omission from historical accounts of American mathematicians is
neither surprising nor unusual. Most mathematicians of his generation are
omitted because accounts tend to focus on research activities. Only towards
the end of Corbin’s life did significant numbers of American math professors
begin to do research.

Certainly Corbin is worthy of inclusion in the history of American
mathematics. His life was remarkable. The son of freed slaves, Corbin was the
founding head of the University of Arkansas at Pine Bluff, Arkansas’s public
Historically Black University. While working there, for over three decades, he
regularly published in mathematical periodicals.

With the goal of introducing Corbin to modern mathematicians, we survey his
life in this article. We focus on his experiences in higher education and
mathematics and, in particular, give an overview of his mathematical
publications.

## Early Life

Corbin was born in Ohio in 1833. His parents had been enslaved in Virginia but
had moved to Ohio about a decade before Corbin’s birth. Little is known about
their move, but it was a common one: most Black Ohioans333We will use the
adjective “Black” to refer to enslaved Americans and their descendants. This
is somewhat ahistorical. Corbin was often regarded as being of mixed race even
though both parents had been enslaved. For example, federal census takers
recorded Corbin’s race as “mulatto” in every census between 1850 and 1910
except for 1900 (when it was recorded as “Black”) and possibly 1890 (this
record is unavailable). See also the discussion of Corbin’s time at Ohio
University in the section titled “Education.” had come from the bordering
slave states of Virginia and Kentucky. Corbin’s mother, Susan, had moved after
being emancipated by her enslaver. It is unknown whether the father, William,
was also emancipated or if he had fled enslavement.

Even though Corbin never personally experienced enslavement, his life was
significantly constrained by state laws and social practice. For example,
Black Ohioans were not allowed to allowed to attend public schools, and many
private schools were racially segregated. Despite the obstacles facing the
family, Corbin’s parents were able to achieve considerable personal success;
both were literate, and William worked as a “sewer of clothes” (a skilled
profession).444See William’s entry in the 1850 U.S. census. He was described
as a “porter” in the 1860 census.

## Education

When Corbin was growing up, his family lived in Chillicothe, a mid-sized town
of a few thousand people in southern Ohio which was a regional center for
Black life (Blacks residents made up 10% of Chillicothe’s population but only
1% of the state’s). Corbin attended school in Chillicothe until he was fifteen
years old (around 1848). He then moved to Louisville, Kentucky to take
advantage of the greater educational opportunities afforded by a larger city.
He returned to Ohio in 1850 to attend Ohio University in Athens.

Black students had studied at OU since the 1820s, and Corbin was the third
student to enroll. While the presence of Black students on college campuses
was sometimes a source of tension, Corbin did not seem to have attracted any
special attention. It is unclear whether Corbin was even regarded as Black by
faculty and students. For example, an 1853 newspaper article on the annual
commencement exercises at Ohio University mentions Corbin by name but makes no
reference to his race, a standard journalistic practice at this time
[newspaper53]. Similarly, an 1885 list of university alumni
[catalogue18885]*p. 86 describes Corbin simply as a teacher in
Louisville555The description of Corbin as a teacher in Louisville suggests
that his entry in the list was based on old information collected shortly
after Corbin graduated (during the 1850s or 1860s, when he was in Louisville).
At the time the list was published, Corbin had been living in Arkansas for
over a decade. but describes another alumnus (John Newton Templeton) as “the
only Alumnus . . . of African descent” [catalogue18885]*p. 78.

When Corbin arrived at OU, the university was functioning as a standard 19th
century U.S. university. It offered a B.A. degree for students who completed a
4-year sequence of college courses. The university also maintained a
Preparatory Department which offered a 2-year sequence designed to prepare
students for the college courses.666While uncommon today, many 19th century
universities maintained similar departments. Indeed, doing so was often
necessary as schooling along the lines of modern K–12 education was often only
available on a limited basis. At the start of Corbin’s first semester,
enrollment stood at 64 students, divided more or less evenly between college
and preparatory students. They were taught by five professors, each being
responsible for all coursework in a given subject. The graduation requirements
differed from those of a modern American university in that students did not
select majors. Instead, all college students took the same fixed sequence of
courses.

The required coursework heavily emphasized the study of Greek and Roman
literature, but it also included a mathematics curriculum that covered algebra
and elementary geometry in the first year; trigonometry, analytic geometry,
and differential calculus in the second year; and integral calculus in the
third year.777Corbin’s analytic geometry and calculus classes were taught
using Albert E. Church’s books Elements of the Differential and Integral
Calculus and Elements of Analytical Geometry, while the algebra and geometry
classes were taught using textbooks by Charles Davies [OUCatalogue51,
OUCatalogue53]. Algebra was taught from Elements of Algebra: Translated from
the French of M. Bourdon. It is not entirely clear which geometry textbook
were used as Davies wrote several. The assigned text is listed as “Davies’
Legendre” in the 1851-50 university catalogue and as “Davies” in 1852-53
university catalogue. The first reference is to Elements of Geometry and
Trigonometry from the works of A. M. Legendre, but the second reference could
either be to that book or to another one such as Elements of Descriptive
Geometry.

At OU, Corbin was taught by two different math professors, William J. Hoge and
Addison Ballard. As was common for American math professors at the time,
neither Hoge nor Ballard had any specialized training in math.888See
[butonBook]*pp. 659-669 for a more detailed discussion of the education of a
typical math professor in nineteenth century America. Formal advanced
education in mathematics was out of reach for most as it typically
necessitated studying abroad. American universities only began awarding earned
doctorate degrees in 1861. Corbin’s first math classes were taught by Hoge, an
alumnus of the university who had graduated with an undergraduate degree in
1843 [catalogue18885, p. 84]. Hoge left the university while Corbin was still
a student (in 1851), and he was replaced by Ballard. Ballard had received a
bachelor’s degree from Williams College and had been serving as OU’s Latin
Professor since 1848 [williamsBook, pp. 213-214].

## Career

When Corbin graduated from Ohio University in 1853, his formal education came
to an end,999Corbin would later receive two A.M. degrees from OU and a Ph.D.
from an unknown Baptist college, but these were honorary degrees. and he spent
the next two decades working as a teacher, bank clerk, and newspaper editor in
Louisville and Cincinnati.

In 1872, Corbin moved to the former slave state of Arkansas. This was not an
uncommon move for talented Black men like Corbin, as the political changes
brought about by the Civil War created unprecedented opportunities for change.
After working briefly as a newspaper reporter and a post office clerk, Corbin
was elected to oversee Arkansas’s public education system as superintendent of
public instruction.101010Corbin defeated the incumbent, Thomas Smith, a white
Union army veteran from Pennsylvania. Both Smith and Corbin were Republicans,
but they were aligned with rival groups within the party [Kennan61]. His
election made Corbin the head of the board of trustees for the state’s newly
founded public university — Arkansas Industrial University (now the University
of Arkansas).111111Prior to the Civil War, Arkansas did not maintain a public
university, although there were a few private universities. During the war,
U.S. Congress encouraged state governments to create public universities by
passing the Morrill Land-Grants Acts, which provided states with funding for
public universities through land sales. Arkansas Industrial University was
created to fulfill the terms of the act so that the state could receive
funding.

The university was technically “open to all, without regard to race, sex, or
sect,”121212The quotation is taken from a statement by the chair of the
executive committee of the board of trustees in an April 1873 report. Corbin
probably did not play a major role in the decision to open the university to
Black students. He was not on the executive committee, and the committee was
charged with writing the report before he joined the board. but Black students
were not allowed to attend classes with white students. Instead, they received
private tutoring.131313It is unclear exactly how many Black students attended,
although the numbers were certainly small. A 1910 history of the university
states that only one Black student applied for admission [ARhistoryBook, p.
97], but a 1922 letter by the interim president’s wife states that two or
three applied [nichols, p. 3]. At least one Black student, James McGahee,
attended the university from 1872-73. To address the issue of college
education for Black Arkansans, the board of trustees, including Corbin,
petitioned the state legislature to create a school for educating Black
teachers. The legislature responded favorably to the petition and created the
Branch Normal College (now the University of Arkansas at Pine Bluff).141414The
legislative act made no explicit reference to race, but it was tacitly
understood that only Black students would be allowed to attend the college.
For example, the act directed the board to select a site for the college in
the southeastern part of the state (where most of Arkansas’s Black population
lived) that was convenient for the “poorer classes” (understood to be a
euphemism for Blacks Arkansans).

Corbin’s term in office was cut short when Conservative Democrats, who were
largely hostile towards Black Arkansans, gained control over the state
government and vacated many political offices, including Corbin’s. Corbin left
the state and moved to Jefferson City, Missouri, where he taught at the newly
founded Lincoln Institute (now University).151515At the time, Lincoln was a
small school of about 50 students, mostly the children of freedpersons
[newspaper74, newspaper75a, newspaper75b]. However, after a brief time there,
he returned to Arkansas to serve as the first principal of the Branch Normal
College.

Since the 1873 legislative act, no real progress had been made in establishing
the college. Under state law, the Branch Normal College was supposed to
provide the same education as the Normal Department at Arkansas Industrial
University. A normal department or school was a common 19th-century
institution that offered postsecondary education for school teachers which
typically involved a truncated college curriculum along with specialized
coursework in pedagogy. However, achieving parity with Arkansas Industrial
University was an unrealistic goal for the Branch Normal College as many of
the college’s students were facing rural poverty and political
disenfranchisement. To further complicate the situation, Corbin was given few
resources — the college had no permanent facilities and no faculty aside from
Corbin, who was even responsible for menial tasks like cleaning classrooms.
Nevertheless, Corbin was able to make major improvements. By the 1880s, a
college building and dormitories had been constructed, and the faculty had
increased to three. By 1883, student enrollment had reached over 200 students.

The Branch Normal College offered an academic education through three
different departments: (a) the Preparatory Department which offered remedial
classes to prepare students for college work, (b) the Normal Department which
awarded a Licentiate of Instruction (a teaching certificate), and (c) the
Collegiate Department which awarded a Bachelors of Arts. The majority of
students were enrolled in the Preparatory Department. The preparatory
curriculum consisted of three years of courses on subjects such as grammar,
geography, drawing, and math. The math education consisted of six terms of
elementary arithmetic and one of algebra.161616According to the 1882 college
catalogue [UofArkansasCatalogue82]*p. 91-92, arithmetic was taught using books
from Robinson’s Series of Mathematics, a popular series of textbooks. It is
unclear precisely which books were used as they are only described as
“Arithmetic, Robinson’s Shorter Course” and “Arithmetic, Robinson’s.” Algebra
was taught from William G. Peck’s Manual of Algebra.

Students in the Normal Department completed two years of remedial work
followed by two years of college courses. In addition to classes on Latin,
English grammar, and pedagogy, students studied algebra and geometry in their
third year and then plane trigonometry in their fourth.171717The 1882 college
catalogue [UofArkansasCatalogue82]*p. 91-92 states that geometry was taught
from Wentworth’s Solid Geometry by George Wentworth, and trigonometry from
Edward Olney’s Elements of Trigonometry, Plane and Spherical. The algebra
textbook is described as “Thompson’s Algebra,” but the present author has been
unable to identify this book. Students in the Collegiate Department completed
the courses taken by the normal students and then two additional years of
college classes in subjects like foreign languages, English literature, and
mathematics. The math classes offered in the last two years were a class on
analytic geometry and an optional course on calculus.181818The description of
courses is taken from the 1893 college catalogue [UofArkansasCatalogue93]. The
textbooks used are not listed.

The curriculum that Corbin promoted at the Branch Normal College came into
conflict with an increasingly influential educational philosophy that focused
on industrial education. This philosophy endorsed only a very limited academic
education for Black students and instead emphasized the value of manual labor
as a means to impart values like self-discipline and self-reliance. Many of
those who promoted industrial education scorned Black students who saw
academics as a way of obtaining personal advancement or fulfillment. Booker T.
Washington, the most prominent promotor of industrial education, expressed the
views of many in his autobiography. In an account of teaching in Alabama, he
wrote that, “The students who came [to his school] first seemed to be fond of
memorizing long and complicated ‘rules’ in grammar and mathematics, but had
little thought or knowledge of applying these rules to the everyday affairs of
their life” [bookerBook]*p. 122. To illustrate his point, he offered the
example of a student whose fondness for math led him to study methods for
computing cubic roots. Washington set students like him to activities that he
deemed more appropriate: farm work and learning how to properly set a dinner-
table.

Seeking to implement industrial education in Arkansas, state legislators in
the 1890s created a Department of Mechanical Arts at the Branch Normal and
hired as department head William S. Harris, a white man from Virginia. He was
effectively made head of the college by the board of trustees when they
transferred key responsibilities191919For example, Harris was made responsible
for admitting students and collecting fees. from Corbin to Harris.

Corbin nominally remained the principal of the Branch Normal for approximately
another decade. In 1902, the board of trustees replaced him by hiring Isaac
Fisher, a recent graduate of Booker T. Washington’s Tuskegee Institute.
Fisher’s hire was part of a plan to expand industrial education at the Branch
Normal, but Fisher’s efforts to the transform the college faltered in the face
of mixed support from trustees and strong opposition by the Black community.
While Corbin’s removal was a major set-back to efforts to run the Branch
Normal as an academic institution, the college continued to offer advanced
courses taught by Corbin’s former student James C. Smith.

After his removal from the college, Corbin remained in Pine
Bluff202020Corbin’s obituary in [corbinObit] states that, from 1902 to January
1904, he served as president of Ouachita Baptist College (now University) in
Camden. While newspaper records from the time record Corbin’s presence in
Camden, the rest of this statement seems to be erroneous. During this period,
the college’s president was one John W. Conger, not Corbin. The college was
also not located in Camden. It has always been located in Arkadelphia, a town
about 40 miles away. In fact, the college has no record of an association with
Corbin. His employment, in any capacity, would have been highly unusual as
Ouachita was a whites-only college during the 19th century. The author thanks
Ouachita Professor and University Archivist Lisa Speer for correspondence on
this issue. and served as principal of Merrill Public School (the local Black
high school) until his death in 1911, at the age of seventy-seven.

## Corbin’s mathematical work

Corbin first published in a mathematical periodical in 1882, when he was
almost fifty years old. At this point in his life, Corbin had achieved
remarkable success in politics and education, but this publication is the
first record of his intellectual engagement with mathematics. This was a point
of pride for Corbin, but it is unclear if these publications were the
expression of a life-long interest or one developed late in life. His
publication record shows both a level of sophistication and a depth of
knowledge that extended beyond both what he’d been taught at university and
what he was teaching at the Branch Normal College. For example, the calculus
textbook he used as a student contained essentially no proofs and even omitted
basic definitions like the definition of the definite integral as a limit of
Riemann sums. Only the geometry courses he took went beyond mechanical work
and included detailed proofs as part of a treatment of plane geometry.

The periodicals that Corbin contributed to were similar to, and in fact
included, the American Mathematical Monthly which is currently published by
the Mathematical Association of America.212121The MAA did not exist during
Corbin’s lifetime, and the Monthly was privately published by the math
professor Benjamin Finkel. A typical periodical included a problems and
solutions section together with book reviews and expository articles. Compared
to today’s research journals, these periodicals served a very different
audience and performed a different function. They were not intended as long-
term records of original mathematical research. Instead, they were published
to stimulate activity among people who otherwise had few outlets for their
mathematical interests. Most readers were individuals studying math in
relative isolation, with only limited access to mathematical literature and
other resources. They included both amateur mathematicians and math
professors, who were often the sole mathematicians at their
universities.222222For example, in addition to university professors, the
contributors to the first volume of the Monthly included a counsellor at law
(John Doman) and an examiner for the U.S. Civil Service Commission (Theodore
L. DeLand). In an era when mathematicians were only beginning to organize
themselves into professional societies, these periodicals performed a similar
function in fostering a mathematical community.232323While the MAA did not
exist during Corbin’s lifetime, the American Mathematical Society was formed
six years after Corbin’s first publication, in 1888. It was originally a New
York-based society named the New York Mathematical Society, but it was given
its current name and reorganized as a national society in 1894. Corbin was
never an AMS member, and in general, the AMS was run as an elite and exclusive
organization during his lifetime. Admission to the society required receiving
a majority of ballots by members in an election after being proposed by two
members and recommended by the AMS Council. In contrast, the periodicals
Corbin published in were run in a democratic spirit. For example, in the
introduction to the inaugural issue of the Mathematical Visitor, the editor
wrote that he aimed to produce an “unpretending periodical” that inspires a
love of mathematics, and he invited contributions from “professors, teachers,
students, and all lovers of the ‘bewitching science’” [mathVisitor78]’

Corbin’s first published problem is the following one:

> Separate the fraction $a/b$ into two parts, $c/d$ and $e/f$ such that
> $c+e=d+f$.

This problem appeared in a 1882 issue of The Mathematical Magazine [corbin82].
The subsequent issue contained two methods for finding the solution
$c/d=(a-b-1)/(b-1)$ and $e/f=(b^{2}+b-a)/(b^{2}-b)$.242424Although this is the
only solution that was published, there are others. For example, $c/d=(an-
bn-1)/(nb-1)$ and $e/d=(nb^{2}+b-a)/(nb^{2}-b)$ is a solution for any integer
$n\in\mathbf{Z}$. Close consideration of the solutions suggests that caution
needs to be taken when assigning authorship. Each solution was attributed to
two different men, but these men (four in total) probably did not write the
published text describing the methods. Consider the first method.252525The
method is to solve for $e/f$ as $a/b-c/d=(ad-bc)/(ad)$, substitute this
expression into the equation $c+e=d+f$, and then solve for $c/d$
[corbin82b]*p. 65. Although it is attributed to P. M. McKay and William E.
Heal, it is unlikely that they jointly wrote the text (one lived in Arkansas,
the other in Indiana; there is also no other record indicating collaboration).
It is more likely the case that the editor simply summarized two submissions
that he received.

Even when authorship of a work is clear, it did not always represent original
ideas. It was not uncommon to submit routine problems taken from textbooks. In
the context of the intellectual environment of the 1890s, this is
unsurprising. Textbook problems were interesting to readers as many had little
or no access to the books themselves. For example, the following problem,
which Corbin published in a 1898 issue of the Monthly [corbin98a], appears to
have been taken from the textbook Treatise of Ordinary and Partial
Differential Equations262626Compare the text of Corbin’s problem with Example
IX.7 on page 104 in the chapter “Linear Equations: Constant Coefficients” of
Johnson’s book. This first observation was made by Walter Hugh Drane in his
published solution [corbin98b]. by William Woolsey Johnson:

> Form the differential equation of the third order, of which
> $y=c_{1}e^{2x}+c_{2}e^{-3x}+c_{3}e^{x}$ is the complete primitive.

The differential equation is $y^{(3)}-7y^{\prime}+6y=0$, and it can be solved
using the techniques from Johnson’s book — standard techniques still taught to
undergraduate students. Despite its routine nature, this problem appears to
have interested readers (a number of solutions were submitted [corbin98b,
corbin98c]). Among those whose solutions were published was Princeton
University professor Edgar Odell Lovett, who gave a complete solution even
though he remarked that it was “a familiar one to students of differential
equations.”

Lovett’s solution is particularly notable as it demonstrates that, despite
their elementary nature, Corbin’s publications were even reaching American
research mathematicians with an international reputation. Lovett had completed
a doctorate in Germany, published in research journals, and was a member of
several European professional societies.

Corbin’s differential equation problem must have been the product of
significant self-study as the subject was not taught at Ohio University when
Corbin was a student. Other problems drew on the plane geometry that Corbin
had been taught at Ohio University. One such example is the following problem
[corbin07] which Corbin published in a 1907 issue of the Monthly:

> In triangle $ABC$, the triangle $DEF$ is formed by joining the feet of the
> medians and four [sic] parallelograms are also formed, viz., $AEFD$, $BFED$,
> and $CEDF$. Let $a$, $b$, $c$; $d$, $e$, $f$ represent the three medians of
> $ABC$, and the three sides of $DEF$. Then the sum of the squares of the six
> diagonals equals the sum of the squares of the twelve sides of the
> parallelograms, which are equal in sets of four. That is,
> $a^{2}+b^{2}+c^{2}+d^{2}+e^{2}+f^{2}=4(d^{2}+e^{2}+f^{2})$ or
> $a^{2}+b^{2}+c^{2}=3(d^{2}+e^{2}+f^{2})=3/4(AB^{2}+BC^{2}+CA^{2})$.

The configuration of triangles is displayed in Figure 5. The problem is solved
using the fact that, in a parallelogram, the sum of the squares of the lengths
of the two diagonals equals twice the squares of the two side lengths.

One of the most advanced topics treated in Corbin’s published work is the
theory of matrices and determinants, a topic that was not usually taught at
American universities in the 19th century. This topic is the subject of
Corbin’s only expository article, “Note on Elimination.” This 1896 Monthly
publication [corbin96e] is a short one-page note in which Corbin explains a
method for solving a system of two linear equations in two variables, $x$ and
$y$. The method is essentially Gaussian elimination, i.e. solve for one
variable by eliminating the other. He summarizes the rule by: “The difference
(sum) of the products containing $x$ ($y$) is equal to the difference (sum) of
the numerical products.” While this method was certainly not original to
Corbin, it appears that it was not well known to American mathematicians as he
presents it as an alternative to the “determinant method” (perhaps a version
of Cramer’s rule).

Corbin also published two problems on determinants. The first appeared in a
1895 issue [corbin95f] of the Monthly:272727The expression we give corrects a
typo in [corbin95f]. In the original printed version, the bottom right-most
entry in the first matrix is $s-a_{n}^{2}$, and we have changed this to
$(s-a_{n})^{2}$. To see that the entry $s-a_{n}^{2}$ is a typo, see the
published solution in the April 1896 issue of the Monthly.

> Find the quotient of
>
> $\displaystyle\begin{pmatrix}(s-a_{1})^{2}&a_{1}^{2}&\dots&a_{1}^{2}\\\
> a_{2}^{2}&(s-a_{2})^{2}&\dots&a_{2}^{2}\\\
> a_{3}^{2}&a_{3}^{2}&\dots&a_{3}^{2}\\\ \vdots&\vdots&\vdots&\vdots\\\
> a_{n}^{2}&a_{n}^{2}&\dots&(s-a_{n})^{2}\end{pmatrix}$
> $\displaystyle\div\begin{pmatrix}s-a_{1}&a_{1}&a_{1}&\dots&a_{1}\\\
> a_{2}&s-a_{2}&a_{2}&\dots&a_{2}\\\ a_{3}&a_{3}&s-a_{3}&\dots&a_{3}\\\
> \vdots&\vdots&\vdots&\vdots&\vdots\\\
> a_{n}&a_{n}&a_{n}&\dots&s-a_{n}\end{pmatrix}$

The desired expression for the quotient is

$s^{n-1}\cdot\left(s+\sum\frac{a_{i}^{2}}{s-2a_{i}}\right)\cdot\frac{1}{1+\sum\frac{a_{i}}{s-2a_{i}}}.$

The solution is obtained by applying matrix manipulations that preserve the
determinant. First, observe that the given ratio of determinants equals:

$\displaystyle\begin{pmatrix}1&0&0&\dots&0\\\
1&(s-a_{1})^{2}&a_{2}^{2}&\dots&a_{n}^{2}\\\
1&a_{1}^{2}&(s-a_{2})^{2}&\dots&a_{n}^{2}\\\
1&a_{1}^{2}&a_{2}^{2}&\dots&a_{n}^{2}\\\ \vdots&\vdots&\vdots&\vdots&\vdots\\\
1&a_{1}^{2}&a_{2}^{2}&\dots&(s-a_{n})^{2}\end{pmatrix}$
$\displaystyle\div\begin{pmatrix}1&0&0&0&\dots&0\\\
1&s-a_{1}&a_{2}&a_{3}&\dots&a_{n}\\\ 1&a_{1}&s-a_{2}&a_{3}&\dots&a_{n}\\\
1&a_{1}&a_{2}&s-a_{3}&\dots&a_{n}\\\
\vdots&\vdots&\vdots&\vdots&\vdots&\vdots\\\
1&a_{1}&a_{2}&a_{3}&\dots&s-a_{n}\end{pmatrix}$

Each column now has the property that almost all entries are the same, and
thus it can be simplified by subtracting a suitable multiple of the first
column. This yields:

$\displaystyle\begin{pmatrix}1&-a_{1}^{2}&-a_{2}^{2}&\dots&-a_{n}^{2}\\\
1&s(s-2a_{1})&0&\dots&0\\\ 1&0&s(s-2a_{2})&\dots&0\\\ 1&0&0&\dots&0\\\
\vdots&\vdots&\vdots&\vdots&\vdots\\\ 1&0&0&\dots&s(s-2a_{n})\end{pmatrix}$
$\displaystyle\div\begin{pmatrix}1&-a_{1}&-a_{2}&-a_{3}&\dots&-a_{n}\\\
1&s-2a_{1}&0&0&\dots&0\\\ 1&0&s-2a_{2}&0&\dots&0\\\ 1&0&0&s-2a_{3}&\dots&0\\\
\vdots&\vdots&\vdots&\vdots&\vdots&\vdots\\\
1&0&0&0&\dots&s-2a_{n}\end{pmatrix}$

Computing each determinant as the Laplace expansion along the first row, we
get that the first determinant is

$s^{n}\prod(s-2a_{i})+a_{1}^{2}s^{n-1}\prod_{i\neq 1}(s-2a_{i})+\dots{\\\
}+a_{j}^{2}s^{n-1}\prod_{i\neq j}(s-2a_{i})+\dots+a_{n}^{2}s^{n-1}\prod_{i\neq
n}(s-2a_{i}),$

and the second is

$\prod(s-2a_{i})+a_{1}\prod_{i\neq 1}(s-2a_{i})+a_{2}\prod_{i\neq
2}(s-2a_{i})\\\ +\dots+a_{j}\prod_{i\neq j}(s-2a_{i})+\dots+a_{n}\prod_{i\neq
n}(s-2a_{i}).$

Factoring out $\prod(s-2a_{i})$, we get the desired solution.

Corbin’s second published problem on determinants was his last publication. In
[corbin08], Corbin asked:

> Muir gives the following problem: Prove:
>
> $\begin{vmatrix}1&a&a&a^{2}\\\ 1&b&b&b^{2}\\\ 1&c&c^{\prime}&cc^{\prime}\\\
> 1&d&d^{\prime}&dd^{\prime}\end{vmatrix}=(a-b)\begin{vmatrix}1&ab&a+b\\\
> 1&cd^{\prime}&c+d^{\prime}\\\ 1&c^{\prime}d&c^{\prime}+d\end{vmatrix}$
>
> which, of course, can be solved by finding the terms of both determinants.
> Is there any method of changing from one form to the other which is direct?

The reference to “Muir” is a reference to Thomas Muir’s book A Treatise on the
Theory of Determinants. The problem appears as one of the exercises in the
chapter “Determinants in general” on the general properties of the
determinant.282828Specifically, it appears on page 66 of Muir’s book as
Exercise 27 in Exercise Set IX in Chapter II. The solution is similar to the
one for the previous problem. The first matrix is manipulated using operations
that preserve the determinant until its determinant is visibly equal to the
determinant of the second matrix.

## Corbin’s Legacy

American mathematical culture underwent major changes around the time Corbin’s
career came to an end. Four years after his death, the Mathematical
Association of America was formed, in large part to provide a permanent
institution to support the American Mathematical Monthly. The Monthly became
an official journal of the MAA, and the loosely knit readership of math
enthusiasts, which Corbin had been a part of, began to transform into an
organized group of professionals. Black mathematicians continued to be members
of this community. The inaugural charter members of the MAA included James T.
Cater, a graduate of the HBCU Atlanta University and a math professor at
Straight University (now part of Dillard University) [monthly16].

At the Branch Normal College, events like Corbin’s removal were major setbacks
to efforts to run the college as an institute of higher education. However,
they did not end those efforts. Faculty continued participate in national
mathematical culture. In 1938, faculty at the college (then renamed the
Arkansas Agricultural, Mechanical & Normal College) joined the ranks of the
American Mathematical Society when college professor William Louis Fields was
elected to membership [AMSBull39].292929Other Branch Normal faculty who were
later elected to AMS membership include Morris Edward Mosley [AMSBull48] and
Willie E. Clark [AMSBull50]. Fields joined the MAA three years later
[monthly41, p. 60].303030By 1951, four additional Branch Normal faculty
members (Mrs. Willie E. Clark, Garland D. Kyle, Nathan T. Seely, Jr., and H.
B. Young [monthly50, monthly51]) had joined the MAA.

In 1903, a year after he was removed from the Branch Normal College, Corbin
delivered an address at the annual meeting of the Arkansas Negro State
Teachers’ Association. The meeting was attended by over 100 school teachers
and was reported in the press [newspaper03], so it provided Corbin an
important forum for voicing his views on education. His speech reads as a
rebuke of the educational philosophy represented by the decision to make Isaac
Fischer principal of the Branch Normal College. Corbin said

> [A] need of the negro is a supply of men with the necessary equipment and
> capacity to carry on his vast national enterprises. It may be a surprising
> thing to many that I claim that the negro has any enterprises of this
> nature; but the claim is easily verified.

As evidence for his claim, Corbin proceeded to give examples of achievements
in professions like law, education, and farming. Were Corbin to give the
speech today, one imagines that he would also include mathematics.

## Added after publication

This article was originally published as [kass23]. The present version
includes a more extensive bibliography. We also provide additional information
on two different issues.

First, in footnote 20, we observed that an obituary for Corbin states that he
served as president of “the Ouachita Baptist College” in Camden, Arkansas, but
we remarked that this appears to be an error as the college (now renamed
Ouachita Baptist University) was a whites-only institute located in
Arkadelphia, not Camden. It is likely that there was some confusion over the
name of the institute Corbin taught at. Camden was home to a different school
called the “Ouachita Academy” or “Ouachita Industrial Academy” that was
maintained by the Black Baptist church. This is likely the school that Corbin
worked at. See [jonesBook]*p. 135 or [workBook]*p. 159 for basic details about
the academy.

Second, we stated at the beginning of the section “Corbin’s mathematical work”
that Corbin’s first mathematical publication appeared in a 1882 issue of the
Mathematical Magazine. In fact, his name appears in a 1879 issue of the
periodical Educational Notes and Queries [queries79b]. There he is credited
with submitting a solution to a problem [queries79a] that had been posed
earlier that year by Franklin Pierce Matz, a professor living a in King’s
Mountain, North Carolina. Matz asked the following, “Given

$\displaystyle m^{2}/x^{2}+a=$ $\displaystyle m^{2}/y^{2}+b$ $\displaystyle=$
$\displaystyle\sqrt{1-m^{2}(1/x^{2}+1/y^{2})+m^{4}/x^{2}y^{2}}$

to find the values of $x$ and $y$ on the plan of quadratics.” In the published
solution, the answer is obtained by eliminating $y$ and then solving for $x$.
This yields the answer

$\displaystyle x=$ $\displaystyle\pm m\sqrt{(2+a+b)/(1+b-a-a^{2})},$
$\displaystyle y=$ $\displaystyle\pm m\sqrt{(2+a+b)/(1+a-b-b^{2})}.$

## References


# Tolerating Adversarial Attacks and Byzantine Faults in Distributed Machine
Learning

Yusen Wu1, Hao Chen1, Xin Wang1, Chao Liu1, Phuong Nguyen1,2, Yelena Yesha1,3
1University of Maryland, Baltimore County, Baltimore, MD, USA
2OpenKneck Inc, Halethorpe, MD, USA
3University of Miami, FL, USA
{ywu5, chenhao1, xinwang11, chaoliu717, phuong3<EMAIL_ADDRESS>
###### Abstract

Adversarial attacks attempt to disrupt the training, retraining, and utilizing
of artificial intelligent and machine learning models in large-scale
distributed machine learning systems. This causes security risks on its
prediction outcome. For example, attackers attempt to poison the model by
either presenting inaccurate misrepresentative data or altering the models’
parameters. In addition, Byzantine faults including software, hardware,
network issues occur in distributed systems which also lead to a negative
impact on the prediction outcome. In this paper, we propose a novel
distributed training algorithm, partial synchronous stochastic gradient
descent (ParSGD), which defends adversarial attacks and/or tolerates Byzantine
faults. We demonstrate the effectiveness of our algorithm under three common
adversarial attacks again the ML models and a Byzantine fault during the
training phase. Our results show that using ParSGD, ML models can still
produce accurate predictions as if it is not being attacked nor having
failures at all when almost half of the nodes are being compromised or failed.
We will report the experimental evaluations of ParSGD in comparison with other
algorithms.

###### Index Terms:

Data security, Byzantine-resilient SGD, Distributed ML

Byzantine-resilient GARs |  Fault Tolerance |  Mode |  Assumption |  Time Complexity
---|---|---|---|---
Median and Trimmed-mean [36] | $n>=2f+2$ | ○ | weak assumption | $\mathcal{O}(n\cdot d)$
Krum [6] | $n>=2f+1$ | ○ | strong assumption | $\mathcal{O}(n^{2}\cdot d)$
multi-Krum [10] | $n>=2f+3$ | ○ | strong assumption | $\mathcal{O}(n^{2}\cdot d)$
Bulyan [24] | $n>=4f+3$ | ○ | strong assumption | $\mathcal{O}(n^{2}\cdot d)$
Kardam [11] | $n>=3f+1$ | ● | strong assumption | $\mathcal{O}(d+n\cdot f)$
Zeno [34] | unbounded | ○ | weak assumption | $\mathcal{O}(n\cdot d)$
Zeno+ and Zeno++ [35] | unbounded | ● | weak assumption | $\mathcal{O}(n\cdot d)$
Draco [9] | $n>=2f+1$ | ○ | strong assumption |  $\mathcal{O}(n\cdot d)$, run twice
Hogwild! [26] | unbounded | ● | strong assumption | $\mathcal{O}(n\cdot d)$
ByzSGD [15] |  | $n>=2f+1$
---
$n>=3f+2$
● | strong assumption | $\mathcal{O}(n^{2}\cdot d)$
ParSGD | $n>=2f+1$ | ◐ | weak assumption | $\mathcal{O}(n\cdot d)$
TABLE I: Comparison of Byzantine-resilient GARs. ○ synchronous ● asynchronous
◐ partial synchronous.

##  I Introduction

Adversarial attacks against AI and ML attempt to disrupt the training and
retraining process by either injecting inaccurate misrepresentative data
samples or altering the models’ parameters. In distributed machine learning,
each participant trains the global model using its own local data and shares
the model’s updates only with central servers or one server. An adversary may
compromise workers during the training phase with malicious data samples such
as false labels or input. For example, attackers can compromise the mobile
devices by sending the junk gradients and parameter updates to the server
which severely impact the predicted outcome of the model.

Distributed Machine Learning (ML) or Federated Learning (FL) [23, 18] provides
solutions for scaling ML models when training with real-world big data.
Usually, with traditional single-data center or distributed data across a
range of geographic places, multiple computation parties include the cluster
of CPUs, multiple GPUs, or TPUs are aggregated for speed-up and
collaboratively train a global model. For advanced distributed ML, the
frameworks like Parameter Servers [22], MapReduce [12], Graph-parallel [19],
and All-reduce [4] are widely used in popular open-source machine learning
library including Tensorflow [2], Horovod [31], Pytorch [28], Spark[37], etc.

In distributed training, synchronous and asynchronous modes are used in the
above frameworks for data parallelism. Most approaches use stochastic gradient
descent (SGD) based algorithms [7], which are the iterative algorithms for
optimizing loss functions to train ML models. For the synchronous method, all
workers train the same target model using the different portions of the
dataset then take the average of gradients at each iteration (epoch) via All-
reduce communication. In asynchronous mode, all workers train the model using
their local batch of data independently, then send the updates to a parameter
server asynchronously. Several security concerns arise in such a distributed
environment since malicious attacks or failures are involved.

Previous works have been studied to mitigate the adversarial attacks in
collaborative and distributed learning, [36],[6],[24],[11],[34],[35],[9],[26],
and [15]. As we said, in distributed training settings, workers will send
updates (gradients) to the server, the server will aggregate all the
gradients, calculate the updates, and then return the updated value to all the
workers for the next round of training. Workers can be compromised by
malicious adversaries or are vulnerable to failures such as software,
hardware, and network faults (Byzantine failures). What’s more, the averaging
aggregation rule like Federated Averaging (FedAvg) [23], can not tolerate even
one outlier because a Byzantine worker can simply tamper its gradient with a
wrong direction, leading the averaging vector far away from the correct
direction. Current approaches like Krum [6] are easy to tolerate outliers if
the bad gradients are far away from the correct ones. But usually, the
malicious workers may pretend they are correct nodes among the system. Some
algorithms are not efficient to tolerate the bad gradients that are hidden
among the correct ones. To sum up, building a privacy-preserving and
Byzantine-resilient distributed machine learning system becomes extremely
important and challenging.

In this paper, we analyze and address three main questions: (i), are there any
reasonable solutions to tolerate at most half Byzantine workers in a proper
and explainable way? (ii), if some of the workers are to be crashed, how can
we detect and extract them from the total gradients so that the ML models can
converge resiliently during the training? (iii), some Byzantine-resilient
gradient aggregation rules (GARs) have been proposed and tested under the
strong or weak byzantine assumption, but we found some of them may reach good
accuracy in strong assumption and bad in weak assumption, and vise versa. Can
we create a new aggregation rule which works in both strong and weak
assumptions?

We propose a new GAR solution which is based on the mean of $f$ nearest
neighbors to the median among all gradients submitted by workers. We will show
that this solution can tolerate at most $f\simeq\frac{n}{2}-1$ Byzantine
workers and degrade the time complexity from $\mathcal{O}(d\cdot n^{2})$ to
$\mathcal{O}(d\cdot n)$ in comparison with Krum, Multi-Krum and so on. Our
GAR, ParSGD, can find $g$ as a new median when $f\leq\frac{n-1}{2}$ workers
are attacked. After finding this new median, we try to find $f$ gradients
closest to this new median and return the mean of $f+1$ gradients (including
the median) as a new parameter for the next epoch training. We define both
strong Byzantine resilience and weak Byzantine resilience based on the ParSGD
and the formal definitions are listed in Section IV. In short, if $f$ nodes
are Byzantine workers and their gradients are far away from the median, we
define it as strong Byzantine resilience because the aggregation rule will
never choose the Byzantine gradients. However, if some Byzantine nodes are
pretending to be correct workers and mix up with correct ones, we define it as
weak Byzantine resilience. Accuracy will be used as a performance metric for
evaluating our ParSGD in comparison with other algorithms. We also propose to
use an unknown bounded time $\delta t$ for excluding the crash workers compare
the results to other solutions.

Contribution. In summary, the three primary contributions of this work are as
follows:

  * •

We propose a new aggregation rule, named ParSGD, to tolerate Byzantine
failures in distributed ML systems. Our experimental results show that the
accuracy of ParSGD can reach near $f\simeq\frac{n}{2}-1$ Byzantine workers
among $n$ workers with $\mathcal{O}(n\cdot d)$ time complexity. Compared with
Mean, Median, and Krum, we get the best accuracy under three common attacks
with two different datasets.

  * •

Theoretically, we redefine strong and weak Byzantine resilience definitions
based on ParSGD, and proved ParSGD can reach a relatively stable accuracy
under both of these two assumptions.

  * •

Our ParSGD is a new partial synchronous GAR based on an unknown bounded time
$\delta t$ which can efficiently exclude crash workers to make the training
converge faster. Both theoretical and experimental analyses are also provided.

Paper Organization. Section II discusses related work. Section III introduces
the motivations and some background definitions. Section IV introduces our new
proposed aggregation rule ParSGD, definitions of strong and weak Byzantine
resilience in partial synchronous SGD, time complexity analysis, and proof of
its Byzantine resilience. Section V analyzes the convergence of a distributed
SGD using ParSGD. Section VI presents our experimental evaluation of ParSGD
and some discussion. We summarize our conclusion in Section VII.

##  II Related Work

###  II-A Byzantine fault tolerance.

In previous studies on Byzantine fault tolerate (BFT), several consensus
protocols and systems have been proposed to tolerate arbitrary faults in
distributed system (e.g., PBFT [8], Raft [27], BFT-Smart [5], Honey Badger
[25], Chios [13], etc). All of them need to make a consensus before delivery;
however, it is costly in terms of communication overhead for employing
consensus in distributed ML architecture. Because it may have thousands of
workers processing very large datasets and all workers need to reach a
consensus. On the other hand, the design of ParSGD is inspired by the concept
of BFT to tolerate Byzantine workers which may submit malicious updates.
However, we do not directly adopt BFT since we achieve a slightly different
goal: BFT achieves the total order of events while we seek to tolerate
malicious updates from the workers.

###  II-B Byzantine-resilient SGD.

To tolerate the outliers, robust statistics have been proposed. We summarize
them in Table I. Yin et al. [36] proposed Median 111In the paper, we define
the uppercase Median as a GAR solution and the lowercase median as the middle
value. and Trimmed-mean solutions, in which the server sorts all of the
gradients and takes median as the global parameter for next round training,
same as the Trimmed-mean which needs to remove a percentage of outliers after
sorting the gradients. However, a recent paper proved that the Median
aggregation rule is still under an order-optimal error rate [16]. Blanchard et
al. [6] proposed Krum for selecting a valid vector update. This rule has local
time complexity $\mathcal{O}(d\cdot n^{2})$ which makes it relatively
expensive to compute when the $d$ and $n$ are large. If Krum can fully
tolerate Byzantine workers, time can be a good trade-off; however, the Krum
assumes only one neighbor pretends as a valid vector among the correct
vectors, and in each iteration, the algorithm chooses $n-f-2$ neighbors which
are not reasonable because Byzantine workers may corrode more workers to
pretend they are correct. What’s more, Chen et al.[9] proposed Draco which
leverages a gradient-coding based algorithm for robust learning. EI Mahdi et
al. [24] proposed a strong Byzantine algorithm, named Bulyan, which needs
$n>=4f+3$ for tolerating fewer Byzantine workers and convergence requires
strong assumptions. To preserve training convergence, Sohn et al. [32]
proposed a voting-based authentication to tolerate inaccurate training
results. Alistarh et al. [3] utilize historical information to achieve the
best sample complexity of training. Xie et al. [34] proposed Zeno to tolerate
the cases where the majority of workers are not fully trusted during training.
Xie et al. [33] also demonstrated that Median and Krum exhibit poor
performance. Other asynchronous algorithms also have been proposed (e.g.,
Zeno++ [35], Kardam [11], Hogwild! [26], ByzSGD [15]), but inevitably the lack
of information on the descent directions will cause a low training accuracy
since asynchronous models do not depend on strict arrival times of messages
for reliable operations.

##  III Problem Settings and Background

We consider a large-scale distributed machine learning system with Byzantine-
resilient GARs. At the core of our proposed gradient aggregation rule (GAR)
ParSGD is to find a new vector $\bm{g}$ as correct medians after
$f\leq\frac{n-1}{2}$ workers are attacked in $d$-dimensional vectors. And
calculate the mean of $f$ gradients near the median. To better understand our
algorithm, in this section, we first compare available approaches of
Byzantine-resilient GARs. Then we describe problem settings, relevant attacks,
and some background definitions of our ParSGD.

###  III-A Byzantine-resilient GARs.

Several distributed ML aggregation rules $F(\cdot)$ have been proposed to
tolerate Byzantine faults. We summarize some of them in Table I. Median [36]
and Krum [6] have become the most efficient and effective ones for tolerating
Byzantine faults. Authors showed that in theory, both of them can tolerate at
most $\frac{1}{2}$ Byzantine workers, we say their breakdown points [17] can
reach $\frac{1}{2}$. We will show that the sample median is an unbiased
estimator which can also reach the breakdown point in Section 4. Krum proposed
a solution using $n-f-2$ squared-distance-based GAR to find a vector that is
closest to the $barycenter$222https://en.wikipedia.org/wiki/Barycenter among
$n$ vectors. The algorithm is resilient under random Gaussian attack when the
$f$ vectors are far from the correct vectors with a small variance. Fig1(a)
shows $f$ Byzantine workers are at a distance far away from the correct
workers. As long as the number of correct workers is more than Byzantine
workers, then the Krum can always find a correct gradient and sum up its
nearby $n-f-2$ neighbors to find a minimum vector among the correct workers.
But it can hardly tolerate the Bit-flipping attack which may change all the
gradients to opposite directions when there are 50% Byzantine workers. Fig1(b)
shows under Bit-flipping attack where $B$ can never find enough correct
neighbors and would to count Byzantine gradients instead, and Krum will return
$B$ as the final vector for next round training. Our ParSGD will find the
median first, then take the mean of $f$ gradients near the median, as shown in
Fig1(c). The Median solution has the same issue, if $n>2f$, and the variance
is large enough, the real median still can be changed to an imprecise gradient
even there is only one Byzantine worker, although the new median is among the
correct workers. In addition, both Krum and Median are just in search of one
optimal vector among $n$ vectors and this vector is vulnerable to be attacked.
We will show that these two solutions are not available and have not enough
training accuracy under around $\frac{1}{3}$ of Byzantine workers in the
evaluation section, even both of their breakdown points can reach
$\frac{1}{2}$ as shown in Section 6. Furthermore, none of these synchronous
GARs can tolerate crash-stop failure. Except one of the GARs, named Hogwild!
[26], employs a coordinator to monitor the number of workers which is time-
consuming.

Figure 1: (a) the number of correct gradients larger than Byzantine gradients,
(b) some Byzantine gradients pretend they are correct, $B$ becomes the one
closest to the $barycenter$ among $n$ gradients, (c) $f$ gradients close to
median.

###  III-B Problem settings

We consider the problem of minimizing an loss function that has the form of a
sum, $Q(w)=\frac{1}{n}\sum_{i=1}^{n}Q_{i}(w)$. Each of function $Q_{i}$ is
associated with the $i$-th training set. The sum-minimization problem also
arises for empirical risk minimization (ERM) [38]. In this case, $Q_{i}(w)$ is
the value of the loss function, and $Q(w)$ is the empirical risk. When used to
minimize the above function, a standard gradient descent method would perform
the following iterations:

$\displaystyle\bm{w}^{t+1}:=\bm{w}^{t}-\gamma\nabla
Q(\bm{w}^{t})=\bm{w}^{t}-\frac{\gamma}{n}\sum_{i=1}^{n}\nabla
Q_{i}(\bm{w}^{t})$ (1)

where $t$ is the index of epoch, $\gamma$ is learning rate, and the
aggregation rule $F=\frac{1}{n}\sum_{i=1}^{n}\nabla Q_{i}(\bm{w}^{t})$.

We assume that $\alpha$ fraction of the $n$ workers are Byzantine and 1 -
$\alpha$ fraction are correct workers. The Byzantine workers will not obey the
rule of GARs by sending arbitrary messages or pretending they are valid among
$n$ correct workers. In addition, correct workers can be crashed down due to
software, hardware, or communication issues. In our assumption, we assume that
a system can only tolerate at most 50% of Byzantine workers. If $f$ workers
are Byzantine, then $n-f$ correct workers must be larger than $f$, we then get
$n>2f$. When $n\leq 2f$, the GARs still can choose the minority group of
gradients and aggregate them for an update, but the result is not under
Byzantine resilience assumptions because it breaks the principle of minority
versus majority. Under this premise, median is the most appealing unbiased
estimator, however, it can be maliciously altered to a new one and no longer
be accurate.

###  III-C Relevant Attacks

####  III-C1 Crash-stop failure

A crash failure [30] occurs when a node suffers from an omission failure once,
and then continues to not respond.

####  III-C2 Bit-flipping Attack

Bit-flipping attack [29] is an attack which the attacker can change the
ciphertext to result in a predictable change of the plaintext.

####  III-C3 Random Gaussian Attack

Random Gaussian Attack also known as Gaussian Noise [1], it’s a statistical
noise having a probability density function equal to normal distribution.

###  III-D Relevant Definitions

We introduce the coordinate-wise median and some other relevant definitions as
follows, which serve as cornerstones for our algorithms.

Definition 1 (Coordinate-wise median): For vectors $\bm{V}_{i}$ in
$\mathbb{R}^{d}$, $i\in[1,n]$, the coordinate-wise median
$\bm{g}=med\\{\bm{V}_{i}:i\in[1,n]\\}$ is a vector with its $k$-$th$
coordinate being $g_{k}=med\\{V_{i}^{k}:i\in[1,n]\\}$ for each $k\in[d]$,
where $med$ is a one-dimensional median and $\bm{g}_{k}$ is one column of k
medians.
Definition 2 (Bounded variance) $\forall i\in\\{1,..,n\\}$,
$diag(\mathbb{E}[(\mathbb{E}\bm{V}_{i}-\bm{\mu})(\mathbb{E}\bm{V}_{i}-\bm{\mu})^{T}])\leq\sigma^{2}$.
Definition 3 (Absolute skewness): For one-dimensional random variable
$\bm{X}$, define the absolute skewness as $\gamma(X)$ $=$
$\mathbb{E}[(\frac{X-\mu}{\sigma})^{3}]$ $=$
$\frac{\mathbb{E}[(X-\mu)^{3}]}{\sigma^{3}}$ $=$
$\frac{\mathbb{E}[(X-\mu)^{3}]}{(\mathbb{E}[(X-\mu)^{2}])^{3/2}}$ $=$
$\frac{K_{3}}{K_{2}^{3/2}}$, and let $S_{k}$ be the skewness of random
distribution, say
$S_{k}=\frac{m_{3}}{m_{2}^{3/2}}=\frac{\frac{1}{n}\sum_{i=1}^{i=n}{(x_{i}-\bar{x})^{3}}}{[\frac{1}{n}\sum_{i=1}^{i=n}{(x_{i}-\bar{x})^{2}}]^{3/2}}$,
where $\bar{x}$ defined as sample mean, $m_{2}$ as the second central
moment(variance), and $m_{3}$ defined as third central moment.
Definition 4 (Lipschitz continuity): $\forall(w,w^{\prime})$, $h$ is
$L$-Lipschitz if $\|h(w)-h(w^{\prime})\|\leq L\|w-w^{\prime})\|_{2}$
Definition 5 (Smoothness): $h$ is $L^{\prime}$-smooth if and only if
$\forall(w,w^{\prime})$, $\|h^{\prime}(w)-h^{\prime}(w^{\prime})\|_{2}\leq
L^{\prime}\|w-w^{\prime})\|_{2}$
Definition 6 (Strong convexity): $h$ is $\mu$-strongly convex if and only if
$\forall(w,w^{\prime})$, $h(w^{\prime})$ $\geq$
$h(w)+h^{\prime}(w)^{\top}(w^{\prime}-w)+\frac{\mu}{2}\|w^{\prime}-w\|_{2}^{2}.$

##  IV Partial Synchronous Byzantine-resilient SGD

We now introduce our partial gradient aggregation rule, ParSGD, which
satisfies both weak and strong Byzantine resilience. The detailed distributed
synchronous SGD is shown in Algorithm 1.

In a normal distribution, the median equals to mean. Namely, if
$|g_{k}-\mu_{k}|$ is relatively small, then we can achieve good training
accuracy. Theorem 1 proved that the breakdown point of median can reach 50%,
but it doesn’t mean it will always be 50% because it can easily be altered if
Byzantine workers are pretending. In this section, we proposed two
corollaries, Corollary 1&2, which help explain why to take the mean of closest
gradients near median is an excellent solution.

Theorem 1. With the fraction of Byzantine workers as $\alpha$ and the sample
median as the estimator, the asymptotic breakdown point [17] for $\alpha$ is
$1/2$.

###### Proof.

If we have $m$ data points and we let a minority of
$\lfloor\frac{m-1}{2}\rfloor$ points become outliers leaving the rest of the
fixed points, and the median stays with the majority. Usually median may
change, but it does not become arbitrarily bad, then the sample breakdown
point is

$\displaystyle\frac{\lfloor\frac{m-1}{2}\rfloor}{m}=\lfloor\frac{m-1}{2m}\rfloor$
$\displaystyle\Rightarrow\frac{1-\frac{1}{m}}{2},$

the more $m$ we have, the breakdown point will be closer to one-half. The
asymptotic breakdown point is one-half. ∎

###  IV-A Important Notations

The notations used in this paper is summarized in Table 2.

Notation | Meaning
---|---
$i$ | index of worker
$n$ | number of total workers
$T$ | number of epochs
$t$ | index of epochs
$\delta t$ | unknown bounded time
c | number of crash workers
$f$ | number of Byzantine workers
$\gamma$ | learning rate
$\bm{V}$ | all vector of d-dimensional gradients
$\bm{U}_{f+1}$ |  $f$ vectors near median, including the median
$\bm{\bar{U}}$ |  take the mean of $\bm{U}_{f+1}$
$g_{k}$ |  the value of median in $k$-th dimension
$\bm{g}$ | a vector of selected median
$\mu_{k}$ |  average value in $k$-th dimension
$F$ | gradient aggregation function
TABLE II: Important Notations

Workers: $i=1,...,n$

for  _$t=1,...,T$_ do

Waiting and receive $\bm{w}^{t}$ from the server;

Training, compute, and send the new gradients $\bm{V}_{i}^{t+1}=\nabla
Q_{i}^{t}(\bm{w}^{t})$ to the server

end for

Server:

input: $\delta t$ (Empirically and manually initialize a enough time $\delta
t$) ;

for  _$t=1,...,T$_ do

Broadcast $\bm{w}^{t}$ to all the workers;

Wait only $2*\delta t$ bounded time for $n-c$ gradients
$\\{\bm{V}^{t}_{i}:i\in[n-c]\\}$ arrive;

Recalculate and update the $\delta t$ if all the gradients are being
collected;

Calculate $f$ as defined in Definition 7, $f=\frac{n-c-1}{2}$;

Compute $\bm{\bar{U}}$ as defined in Corollary 1 and 2;

Update the parameter $\bm{w}^{t+1}=\bm{w}^{t}-\gamma^{t}\bm{\bar{U}}$;

end for

Algorithm 1 Partial Synchronous Byzantine SGD

###  IV-B Partial Synchrony

We first consider timing assumption in partial synchronous SGD. In a
synchronous system, there is a known fixed upper bound $\delta t$333We define
$t$ represents the index of an epoch, and $\delta t$ represents a bounded
time. on the time required for a message to be sent from one worker to
another. In an asynchronous system, no fixed upper bound $\delta t$ exists.
And partial synchrony [14], fixed bound $\delta t$ exists, but it’s not known
a priori444https://en.wikipedia.org/wiki/A_priori_and_a_posteriori.

Proposition 1. If a trusted GAR executes aggregation $F(\cdot)$ during a
bounded and not-a-priori time $\delta t$, then $n-c$ active vectors are
eventually collected, where $n$ refers to the number of workers, and $c$
refers to the crash nodes.

In this proposition, the server only needs to initialize an estimated time
$\delta t$ which is enough for collecting all the gradients in one round. In
the rest of the epochs, the GAR will recalculate the aggregation time $\delta
t$, and only wait for $2*\delta t$ bounded time which is not known a priori.

###### Proof.

We initially set an unknown bounded time $2*\delta t$ to collect $n-c$ active
workers, the proof is simple and straightforward. We assume $c$ number of
workers may be crashed or compromised by malicious failures (crash-stop
failure is also a kind of Byzantine failure). In this case, Byzantine workers
may spend more training time than normal workers because of the extra time for
Byzantine infection. Simply, we only wait for $2*\delta t$ time in aggregation
for the crash nodes, eventually, $n-c$ vectors will be collected. We exclude
$c$ crash workers which may be caused by network delay, malicious attack, or
arbitrary system failures. ∎

###  IV-C Byzantine Resilience

We introduced strong and weak Byzantine resilience in Section 1. In order to
explain how our ParSGD work both in strong and weak Byzantine resilience, we
formally define our strong and weak Byzantine resilience GARs in partial
synchronous SGD and two Corollaries as follows.

Definition 7 (Weak Byzantine Resilience): Given a system of $n$ components,
$b$ of which are Byzantine workers, including $c$ random crash-stop vectors as
$\bm{C}_{1}$,…,$\bm{C}_{c}$ and $f$ malicious workers pretending as corrects
ones as $\bm{B}_{1},...,\bm{B}_{f}$, where $0\leq b\leq n,b=f+c,$ and
$b,c,f\in\mathbb{N}$. Let $\bm{V}_{1}$,…,$\bm{V}_{n-b}$ be the independent
identically distributed(i.i.d.) random in $\mathbb{R}^{d}$, $\bm{V}_{i}$
$\sim\mathcal{N}(\bm{\mu},\,\bm{\Sigma})$, and with
$\mathbb{E}V_{i}^{k}=\mu_{k}$, $k$ refers to dimensional index. $F$ is said to
be weak Byzantine resilience if it satisfies

$F=F\underbrace{(\overbrace{\bm{V}_{1},...,\underbrace{\bm{B}_{1},...,\bm{B}_{f},}_{f}...,\bm{V}_{n-f-c}}^{n-c},\underbrace{\bm{C}_{1},...,\bm{C}_{c}}_{c})}_{n}$

(i) $n>2f+c$, and
$\begin{cases}f=0,\ c=0&\quad\text{if \ Byzantine free}\\\ 0\leq c<n,\ 0\leq
f\leq\lceil\frac{n-c-1}{2}\rceil&\quad\text{if }\text{$f+c>0$}\end{cases}$
(ii) $|g_{k}-\mu_{k}|\leq\epsilon$, where $\epsilon$ is negligible, $g_{k}$
refers to the median.

Definition 8 (Strong Byzantine Resilience): $F$ is said to be strong Byzantine
resilience if it satisfies condition (i) and (ii) in Definition 7, and (iii)
$|g_{k}-V^{far}_{i}|<|g_{k}-B^{close}_{j}|$, where $g_{k}$ is the median,
$V^{far}_{i}$ refers to the farthest correct gradient, and $B^{close}_{j}$
refers to the closest Byzantine gradient.

Theorem 1 proved Median is an unbiased estimator which can tolerate at most
$\frac{1}{2}$ Byzantine workers. Even there are $f\simeq\frac{n}{2}-1$
Byzantine workers, Median can still find a new correct gradient as the new
median to tolerate the arbitrary gradients attack. Based on Theorem 1 and
Definition 7 and 8, we get two corollaries below.

Corollary 1: Under the assumption of Definition 7, 8 and Theorem 1, suppose we
have random vectors $\bm{\tilde{V}}_{i}\in\mathbb{R}^{d},i\in[1,n-c]$
containing normal gradients and malicious ones. The set of $f$-neighbor
vectors of $\bm{g}$ is defined as
$\bm{U}_{f+1}:=\\{\\{\bm{\hat{V}}_{i}\\}_{i=1}^{f},\bm{g}\\}$, where
$\\{\bm{\hat{V}}_{i}\\}_{i=1}^{f}=\arg\min\sum_{i=1}^{f}\sum_{k=1}^{d}|V_{(i)}^{k}-g_{k}|$,
for different $V_{(i)}^{k}\in V_{j}^{k},i\in[1,f],j\in[1,n-f-c]$. Here
$\bm{U}_{f+1}$ is obtained by comparing the distance between each vector and
median per dimension. We can conclude that none of the vectors in
$\bm{U}_{f+1}$ contains Byzantine values. The estimator to update the gradient
is $\bm{\bar{U}}:=\frac{1}{f+1}(\sum_{i=1}^{f+1}\bm{\hat{V}}_{i}+\bm{g})$.

###### Proof.

Suppose we have a set
$S\\!:=\\!\\{\bm{V}_{1},...,\bm{V}_{n-f-c},\bm{B}_{1},...,\bm{B}_{f}\\}$
taking value in $\mathbb{R}^{d}$. In the $k$-th dimension, let
$V_{1}^{k},...,V_{n-f-c}^{k}$ and $B_{1}^{k},...,B_{f}^{k}$ be the reordered
gradients such that $|V_{1}^{k}-g_{k}|\leq...\leq|V_{n-c}^{k}-g_{k}|$ and
$|B_{1}^{k}-g_{k}|\leq...\leq|B_{f}^{k}-g_{k}|$ , where $g_{k}$ refers to the
sample median. Under the assumption of Definition 7 and 8,
$|g_{k}-V^{far}_{i}|<|g_{k}-B^{close}_{j}|$, meaning that

$\displaystyle|V_{1}^{k}\\!-\\!g_{k}|\leq...\leq|V_{n-f-c}^{k}\\!-\\!g_{k}|\leq|B^{k}_{1}\\!-\\!g_{k}|\leq...\leq|B_{f}^{k}\\!-\\!g_{k}|$
(2)

Definition 7(i) limits the $f$ must smaller than $n-f-c$. We defined

$\displaystyle n>2f+c\Rightarrow n>=2f+c+1$ $\displaystyle
then,f<=\lceil\frac{n-c-1}{2}\rceil$

We take the largest $f$ in $n$ workers,

$\displaystyle n=2f+c+1$ $\displaystyle n-f-c=f+1$

Here, $f+1$ equals to $n-f-c$, we get the first $n-f-c$ correct gradients and
append them to the $\bm{U}_{f+1}$. ∎

Corollary 2: Under the assumption of Definition 7 and Theorem 1, suppose we
have random vectors $\bm{\tilde{V}}_{i}\in\mathbb{R}^{d},i\in[1,n-c]$
containing normal gradients and malicious ones. The set of $f$-neighbor
vectors of $\bm{g}$ is defined as
$\bm{U}_{f+1}:=\\{\\{\bm{\hat{V}}_{i}\\}_{i=1}^{f},\bm{g}\\}$, where
$\\{\bm{\hat{V}}_{i}\\}_{i=1}^{f}=\arg\min\sum_{i=1}^{f}\sum_{k=1}^{d}|V_{(i)}^{k}-g_{k}|$,
for different $V_{(i)}^{k}\in V_{j}^{k},i\in[1,f],j\in[1,n-f-c]$. We can
conclude that $V_{(i)}^{k}$ may contain Byzantine vector elements, but all the
vectors in $\bm{U}_{f+1}$ still move in the bounded deviation direction to
make the training converge. The estimator to update the gradient is
$\bm{\bar{U}}:=\frac{1}{f+1}(\sum_{i=1}^{f+1}\bm{\hat{V}}_{i}+\bm{g})$

###### Proof.

Since some Byzantine workers pretend to be correct ones, the median vector
$\bm{g}$ is important for the gradient direction. As we know the breakdown
point of $\alpha$ is $\frac{1}{2}$, we will show the
$\mathbb{E}[\bm{g}]=\bm{\mu}$. Because we perform the median selection per
coordinate, the proof only needs to show $\mathbb{E}[g_{k}]=\mu_{k}$, on the
$k$-th dimension, with $k\in[1,d],k\in\mathbb{N}$.

Considering a set of i.i.d normal variable $\\{X_{j}\\}_{j=1}^{m}$ and
$X_{j}\in\mathbb{R}$, $\mu$ and $\sigma^{2}$ are the mean and variance
respectively. Let $X_{j:n}$ be the $j$-th order in the a sorted sequence
$\\{X_{1:m},...,X_{m:m}\\}=\\{X_{j}\\}_{j=1}^{m}$. Suppose $m$ is odd, the
median of the set is $M:=X_{\frac{m-1}{2}:m}$, which has the probability
density of this order statistics as:

$\displaystyle
f_{med}^{odd}(x)=\frac{m+1}{2}{m\choose\frac{m-1}{2}}f(x)(F(x)(1-F(x)))^{\frac{m-1}{2}}$
(3)

where $f(x)$ and $F(x)$ are the density and cumulative distribution functions
respectively. Since the normal distribution is symmetric, $F(x)=1-F(2\mu-x)$,
we can easily get $f_{med}^{odd}(x)=f_{med}^{odd}(2\mu-x)$, namely

$\displaystyle\mathbb{E}[X_{\frac{m-1}{2}:m}]=\mu$ (4)

When $m$ is a even number, the median is
$M:=\frac{1}{2}(X_{\frac{m-1}{2}:m}+X_{\frac{m-1}{2}:m})$. So the joint
probabily density function is:

$\displaystyle
f_{med}^{even}(x_{1},x_{2})=(\frac{m}{2})^{2}{m\choose\frac{m}{2}}f(x_{1})f(x_{2})(F(x_{1})(1-F(x_{2}))^{m-1}$
(5)

Again, using the symmetric property, we have

$\displaystyle\mathbb{E}[M]=\mathbb{E}[2\mu-M]$ (6)

which means $\mathbb{E}[M]=\mu$, still. From eq.(4) (6), we know that the
sample median of a normal distribution is an unbiased estimator. When
Byzantine samples existing, provided that $\alpha<\frac{1}{2}$, we can easily
see the sample median as the unbiased estimator still holds.

We then prove the weak Byzantine resilience. Under the assumption of
Definition 7(ii) $|g_{k}-\mu_{k}|\leq\epsilon$, where $\epsilon$ is
negligible. The $\bm{V}_{i}$ in a probability distribution is symmetric about
the mean, presuming that data near the mean are more frequent in occurrence
than data far from the mean. Even some Byzantine workers pretend they are
correct among $V_{i}^{k}$, they still have high likelihood values with a given
normal distribution, and we say the sample mean of the set $\bm{U}_{f+1}$
still in the right direction. ∎

###  IV-D Complexity Analysis

Computing the median of a list of $n$ of unordered elements takes
$\mathcal{O}(n)$ time with standard selection algorithms for a $1$-dimensional
vector, and the time complexity to get the median which is only
$\mathcal{O}(1)$. ParSGD has one more step than Median, which is to find $f$
closest gradients, and the time complexity of this step is $\mathcal{O}(n)$.
Usually, there are $d$-dimensional vectors, so the overall time complexity is
$\mathcal{O}(d\cdot n).$

##  V Convergence Analysis

In this section, we analyze the convergence of the SGD using ParSGD algorithm
defined in Section 4. All vectors in $\bm{U}_{f+1}$ are in the normal
distribution, and all the elements of the vectors are from correct values in
strong Byzantine assumption. The absolute value between $k$-th dimension of
$\bm{\bar{U}}$ and $\mu_{k}$ is bounded in a small value ($\eta$) which will
help lead a right direction of gradient descent. Same as the weak Byzantine
assumption, some workers may pretend they are correct gradients in
$\bm{U}_{f+1}$, but the $f+1$ gradients in $\bm{\tilde{V}}_{i}$ are pre-
selected through $f$ closest neighbors near the median, and we proved median
is an unbiased estimator which can tolerate at most $\frac{1}{2}$ Byzantine
workers. In Proposition 2, we bounded $\eta$ and found it is only related to
the maximum of covariance $\sigma$ and $f$.

Proposition 2. Suppose we have random vectors
$\bm{\tilde{V}}_{i}\in\mathbb{R}^{d},i\in[1,n-c]$ containing normal gradients
and malicious ones. We assume that $\bm{V}_{i}$ be any independent and i.i.d
$d$-dimensional vector, $\bm{V}_{i}$ $\sim\mathcal{N}(\bm{\mu},\bm{\Sigma})$,
and $g_{k}$ refers to the median of $\tilde{V}_{i}^{k}$. $\sigma$ is the upper
bound of the variance under Definition 2. If $n-c>2f$ and
$|g_{k}-\mu_{k}|\leq\epsilon$, let $u_{k}=\bm{\bar{U}}^{k}$ be the $k$-th
dimensional sample mean of $\bm{U}_{f+1}$. We defined $\eta$ by

$\displaystyle\mathbb{E}(u_{k}-\mu_{k})^{2}=\frac{f\sigma^{2}}{(f+1)^{2}},\quad\eta=\frac{\sqrt{f}\sigma}{f+1}\leq\frac{\sigma}{2}$

###### Proof.

Under strong Byzantine resilience, $\bm{\tilde{V}}_{i}$ only composes of
$\bm{V}_{i}$. All the computation is under a normal distribution condition.
The bounded variance can be written as

$\displaystyle\mathbb{E}(V_{i}^{k}-\mu_{k})^{2}\leq\sigma^{2}$ (7)
$\displaystyle\mathbb{E}((V_{i}^{k})^{2}+\mu_{k}^{2}-2V_{i}^{k}\mu_{k})\leq\sigma^{2}\Leftrightarrow\mathbb{E}((V_{i}^{k})^{2})\leq\sigma^{2}+\mu_{k}^{2}$
(8)

Also, $u_{k}=\bm{\bar{U}}^{k}$ and $\mathbb{E}(u_{k}-\mu_{k})^{2}$ can be
calculated as

$\displaystyle u_{k}$
$\displaystyle=\frac{1}{f+1}(\sum_{i=1}^{f+1}V_{i}^{k}+g_{k})$
$\displaystyle=\frac{1}{f+1}(\Delta+g_{k}),$ $\displaystyle where,\Delta$
$\displaystyle=\sum_{i=1}^{f+1}V_{i}^{k}$ (9) $\displaystyle
then,\mu^{2}_{k}\\!+\\!u_{k}^{2}\\!-\\!2u_{k}\mu_{k}\\!=\\!\frac{1}{(f+1)^{2}}(\Delta^{2}+g_{k}^{2}$
$\displaystyle+2\Delta
g_{k})\\!+\\!\mu^{2}_{k}\\!+\\!\frac{2}{f+1}(\Delta\\!+\\!g_{k})\mu_{k}$ (10)
$\displaystyle\mathbb{E}(u_{k}-\mu_{k})^{2}\leq\mathbb{E}(\frac{1}{(f+1)^{2}}(\Delta^{2}+g_{k}^{2}+2\Delta
g_{k})$ $\displaystyle+\mu^{2}_{k}+\frac{2}{f+1}(\Delta+g_{k})\mu_{k})$ (11)

As defined condition (ii) in Definition 7, $|g_{k}-\mu_{k}|<\epsilon$, then

$\displaystyle\mathbb{E}(g_{k}\\!-\\!\mu_{k})^{2}\\!=\\!\mathbb{E}[g_{k}^{2}]\\!-\\!\mu_{k}^{2}\leq\epsilon^{2}\Leftrightarrow\mathbb{E}[g_{k}^{2}]\leq\epsilon^{2}+\mu_{k}^{2}$
(12)
$\displaystyle\mathbb{E}{(\Delta)}\\!=\\!f\mu_{k},\quad\mathbb{E}(\Delta)^{2}\\!=\\!f\cdot(\sigma^{2}\\!+\\!\mu_{k}^{2})\\!+\\!\frac{f\cdot(f-1)}{2}\mu_{k}^{2}$
(13)

We finally bounded the $u_{k}$ to mean combined with formula 8, 11, 12 and 13,

$\displaystyle\mathbb{E}(u_{k}-\mu_{k})^{2}\leq\frac{1}{(f+1)^{2}}(f\cdot(\sigma^{2}+\mu_{k}^{2})+f\cdot(f-1)\mu_{k}^{2}$
$\displaystyle+\mu_{k}^{2}+\epsilon^{2}+2f\mu_{k}^{2})-\mu_{k}^{2}$
$\displaystyle\leq\frac{f\sigma^{2}+\epsilon^{2}}{(f+1)^{2}}\Leftrightarrow\frac{f\sigma^{2}}{(f+1)^{2}}$

Figure 2: MNIST: Top-1 Accuracy and Loss under Bit-Flip Attack Figure 3:
MNIST: Top-1 Accuracy and Loss under Random Gaussian Attack

then standard deviation of $\mathbb{E}(u_{k}-\mu_{k})^{2}$ equals to
$\frac{\sqrt{f}\sigma}{f+1}$ and $\eta$ is bounded by $\sigma$ and $f$ in no
more than $1/2\sigma$ when $f=1$, and the more workers we have the smaller
$\eta$ is, then we say $\eta\leq 1/2\sigma$.

For the Weak Byzantine resilience, $\tilde{V}_{i}^{k}$ may contain $V_{i}^{k}$
and $B_{i}^{k}$. However, $B_{i}^{k}$ pretends to be $V_{i}^{k}$, which means
$\mathbb{E}(\tilde{V}_{i}^{k}-\mu_{k})^{2}\leq\sigma^{2}$. Then the $u_{k}$ is
updated as
$u_{k}=\frac{1}{f+1}(\sum_{i=1}^{f+1}\tilde{V}_{i}^{k}+g_{k})=\frac{1}{f+1}(\Delta+g_{k}),$
where$\ \Delta=\sum_{i=1}^{f+1}\tilde{V}_{i}^{k}$. Since $B_{i}^{k}$ pretends
to be correct, we assume $\mathbb{E}B_{i}^{k}=\mu_{k}$. $\mathbb{E}{(\Delta)}$
and $\mathbb{E}(\Delta)^{2}$ remain the same, which means the overall result
remains the same. Now that the proposed gradient estimator $\bm{\bar{U}}$ is
bounded in a small deviation from the ground truth, the proposed algorithm
will converge as the regular gradient descent with mean as the estimator. So
we have proved ParSGD algorithm is Byzantine resilience and the training will
converge even it is a weak Byzantine resilience. ∎

Figure 4: CIFAR10: Top-1, Top-5 Accuracy and Loss under Random Gaussian
Attack.

##  VI Experimental Evaluation

We implemented and evaluated ParSGD in a simulated mode on a Tesla P100 Nvidia
setting. Our algorithm is evaluated by 3 common attacks, Crash-stop [30], Bit-
flipping [29] and Random Gaussian attack. We summarize the results of our
experiment as follows:

  * •

ParSGD does not wait for all workers’ updates because it collects gradients in
partial synchronous mode. It reaches the best training accuracy under the
Crash-stop failure compared with Mean, Median, and Krum.

  * •

Under the attack of Bit-flipping, ParSGD gets the best Top-1 accuracy among
Mean, Median, and Krum in MINST. When the Byzantine workers $f$ reach 22 (44%
Byzantine workers), some fluctuations occur in Top-1 accuracy affected by the
median, but the Loss still converges best. Krum and Mean cannot converge both
in CIFAR10 and MINST when Byzantine workers $f$ reach 20, as shown in Figure 2
and Figure 4.

  * •

With Random Gaussian attack, compared with Krum which has the inherent
advantage of resistance to random Gaussian attack when Byzantine workers
$f<\frac{n}{2}$, ParSGD still achieves the best training accuracy and Loss
benchmarking with both MNIST and CIFAR10.

###  VI-A Overviews

####  VI-A1 Datasets

We conduct experiments on benchmark MNIST [21], handwritten digits for image
processing, which contains 60,000 training images and 10,000 testing images.
We also conduct experiments on benchmark CIFAR10 [20], which consists of
60,000 32x32 colour images in 10 classes, with 6,000 images per class.

####  VI-A2 Evaluation Settings

During the evaluation, we execute 200 epochs with 50 workers. We set the
learning rate to 0.05 and the batch size to 100. In each epoch, we use cross-
entropy loss function with Top-1 and Top-5 accuracy evaluation metrics. For
the distributed ML model, we run a multi-layer convolutional network, which
has four 3x3 convolution layers (the first two layers with 64 channels, the
last two layers with 128, each followed with a 2x2 max pooling), and a fully
connected layer with 128 units and ReLu activation, with a last output layer.

We normalize all data and divide the data into two classes: training data
(eighty of all data), and testing data (twenty of all data).

###  VI-B Crash-stop failure

Crash-stop failure usually happens at a sudden stop in an emergent situation,
and it is a type of failure that causes the component of a system to stop
operating. We tested ParSGD under 5 crashed workers and 22 Byzantine workers.
The result shows that only ParSGD can tolerate Crash-stop failure among
Median, Mean and Krum, because ParSGD is in partial synchronous mode which
only collects $n-c$ vectors from active workers.

###  VI-C Bit-flipping Attack

The formal definition of a Bit-flipping attack is an attack in which the
attacker can change the ciphertext to result in a predictable change of the
plaintext. In our experiment, we simulate the Bit-flipping attack by changing
$f$ vectors to opposite descent directions. More specifically, the adversary
$p_{i}$ first calculates each true gradient vector $\Delta w_{j}$, and then
updates $-c_{i}\Delta w_{j}$ to the server, where $c_{i}$ is a random constant
(or one for simple). The result is shown in Figure 2.

We evaluate the number of Byzantine workers $f$ from 12 to 24. We found Mean
cannot tolerate even one Byzantine worker, while Median and Krum cannot
converge at nearly 18 Byzantine workers. Our ParSGD can still converge when
Byzantine number $f$ reaches up to 22, see the training accuracy of 22
Byzantines in Figure 2. The accuracy of ParSGD is influenced by the median
(median may pretend correctly), but the Loss still converges best even
Byzantine number $f$ reaches up to 24, see the Loss of 24 Byzantines in Figure
2.

###  VI-D Random Gaussian Attack

We simulate using random Gaussian attack to compromise the above 4 aggregation
rules. We take the standard deviation to 0.1, 1, and 200, and take the mean to
$-1e8$ or 0. Our experimental results prove that as long as the majority of
the workers are correct, the accuracy of ParSGD can always be stable. We found
Krum is the best solution here because of its inherent advantage of finding
the minimum vector among $n-f$ vectors in strong Byzantine resilience
(Definition 8), as shown in Figure 3. However, in weak Byzantine resilience
(Definition 7), if all the Byzantine workers pretend they are correct, the
training accuracy of Krum will be increasingly threatened. ParSGD still works
well when there are 24 Byzantine workers and both of their Top-5 accuracies
can reach up to 99%. Due to space limitations, we only show the Top-1 results
here since the Top-5 results have roughly the same conclusion.

We also benchmark ParSGD with CIFAR10 under the random Gaussian attack, as
shown in Figure 4. We only list ParSGD, Krum, and Median here, as we have
proved that Mean can not tolerate even one Byzantine worker. In the meantime,
all the algorithms can tolerate less 30% Byzantine workers except Mean, so we
only show our results for 20, 22, and 24 Byzantine workers here ($n=50$ and
$c=0$). We evaluate both the Top-1 and Top-5 accuracy in this CIFAR10
evaluation.

We compromised $f$ $d$-dimensional vectors by replacing $f$ wrong vectors.
These vectors are in normal distribution by setting mean to 0 and variance to
200, pretending all the generated gradients are correct. The results show that
the accuracy of Median and ParSGD are almost the same in Top-1 and Top-5, but
ParSGD has relatively fewer fluctuations when the Byzantine number reaches up
to 24. In addition, ParSGD converges best as shown in Figure 4, see the Loss
of 24 Byzantines.

In the nutshell, consider all evaluations, we found only Median and ParSGD get
converged correctly. As we said, Krum can hardly converge even Byzantine
number $f$ less than correct workers in weak Byzantine resilience.

###  VI-E Discussion and Limitation

During the evaluation, we find that the training accuracy of ParSGD is easily
affected by the median because our algorithm is finding $f$ nearest neighbors
close to the median. When there are more than 45% Byzantine workers under Bit-
flipping attack and random Gaussian, the median can easily be altered to a
wrong one. Namely, if the median is pretty close to the mean in an unknown
distribution, we can achieve good training accuracy. But in real-world
training settings, the vectors are not completely in a normal distribution,
that’s why the accuracy starts to fluctuate when Byzantine workers near 50%.
For example, under the Gaussian attack when the variance is relatively normal,
$f$ Byzantine workers will pretend they are correct, so a wrong gradient of a
Byzantine node may become be selected to be a new median. The result of
collecting $f$ gradients near median may count a lot of Byzantine workers, but
because they pretend to be normal, the training finally gets converge,
however, it just has some fluctuations during training. Compared with Krum and
Median, our algorithm ParSGD performs a good result when there are more than
$\frac{1}{3}$ Byzantine workers. We demonstrate our algorithm, ParSGD, is
practical and meaningful in an untrusted distributed environment.

##  VII Conclusion

We propose a novel gradient aggregation rule, ParSGD, in partial synchronous
mode, which can tolerate Crash-stop failures and nearly 50% of Byzantine
workers in distributed and collaborative training. Compared with Mean, Median,
and Krum, we get the best accuracy under three common attacks. The algorithm
has a provable convergence analysis in both strong and weak assumptions. We
will try to apply this solution to federated learning settings in the future.

## Acknowledgements

We gratefully acknowledge the support of the NSF through grant IIP-1919159. We
also acknowledge the support of the IBM research team.

## References

  * [1] https://en.wikipedia.org/wiki/gaussian_noise.
  * [2] M. Abadi, P. Barham, J. Chen, Z. Chen, A. Davis, J. Dean, M. Devin, S. Ghemawat, G. Irving, M. Isard, et al.  Tensorflow: A system for large-scale machine learning.  In 12th $\\{$USENIX$\\}$ symposium on operating systems design and implementation ($\\{$OSDI$\\}$ 16), pages 265–283, 2016.
  * [3] D. Alistarh, D. Grubic, J. Li, R. Tomioka, and M. Vojnovic.  Qsgd: Communication-efficient sgd via gradient quantization and encoding.  Advances in Neural Information Processing Systems, 30:1709–1720, 2017.
  * [4] Baidu Research.  Tensorflow allreduce and Baidu allreduce.  https://github.com/baidu-research, 2018.  Accessed: 2017-10-23.
  * [5] A. Bessani, J. Sousa, and E. E. Alchieri.  State machine replication for the masses with bft-smart.  In 2014 44th Annual IEEE/IFIP International Conference on Dependable Systems and Networks, pages 355–362. IEEE, 2014.
  * [6] P. Blanchard, E. M. El Mhamdi, R. Guerraoui, and J. Stainer.  Machine learning with adversaries: Byzantine tolerant gradient descent.  In Proceedings of the 31st International Conference on Neural Information Processing Systems, pages 118–128, 2017.
  * [7] L. Bottou.  Large-scale machine learning with stochastic gradient descent.  In Proceedings of COMPSTAT’2010, pages 177–186. Springer, 2010\.
  * [8] M. Castro and B. Liskov.  Practical byzantine fault tolerance and proactive recovery.  ACM Transactions on Computer Systems (TOCS), 20(4):398–461, 2002\.
  * [9] L. Chen, H. Wang, Z. Charles, and D. Papailiopoulos.  Draco: Byzantine-resilient distributed training via redundant gradients.  In International Conference on Machine Learning, pages 903–912. PMLR, 2018.
  * [10] G. Damaskinos, E. M. El Mhamdi, R. Guerraoui, A. H. A. Guirguis, and S. L. A. Rouault.  Aggregathor: Byzantine machine learning via robust gradient aggregation.  In The Conference on Systems and Machine Learning (SysML), 2019, number CONF, 2019.
  * [11] G. Damaskinos, R. Guerraoui, R. Patra, M. Taziki, et al.  Asynchronous byzantine machine learning (the case of sgd).  In International Conference on Machine Learning, pages 1145–1154. PMLR, 2018.
  * [12] J. Dean and S. Ghemawat.  Mapreduce: simplified data processing on large clusters.  Communications of the ACM, 51(1):107–113, 2008.
  * [13] S. Duan, C. Liu, X. Wang, Y. Wu, S. Xu, Y. Yesha, and H. Zhang.  Intrusion-tolerant and confidentiality-preserving publish/subscribe messaging.  In 2020 International Symposium on Reliable Distributed Systems (SRDS), pages 319–328. IEEE, 2020.
  * [14] C. Dwork, N. Lynch, and L. Stockmeyer.  Consensus in the presence of partial synchrony.  Journal of the ACM (JACM), 35(2):288–323, 1988.
  * [15] E.-M. El-Mhamdi, R. Guerraoui, A. Guirguis, L. N. Hoang, and S. Rouault.  Genuinely distributed byzantine machine learning.  In Proceedings of the 39th Symposium on Principles of Distributed Computing, pages 355–364, 2020.
  * [16] M. Fang, X. Cao, J. Jia, and N. Gong.  Local model poisoning attacks to byzantine-robust federated learning.  In 29th $\\{$USENIX$\\}$ Security Symposium ($\\{$USENIX$\\}$ Security 20), pages 1605–1622, 2020.
  * [17] C. J. Geyer.  Breakdown point theory notes.  Class Notes on Nonparametric Statistics, 2006.
  * [18] P. Kairouz, H. B. McMahan, B. Avent, A. Bellet, M. Bennis, A. N. Bhagoji, K. Bonawitz, Z. Charles, G. Cormode, R. Cummings, et al.  Advances and open problems in federated learning.  arXiv preprint arXiv:1912.04977, 2019.
  * [19] V. Kalavri, V. Vlassov, and S. Haridi.  High-level programming abstractions for distributed graph processing.  IEEE Transactions on Knowledge and Data Engineering, 30(2):305–324, 2017.
  * [20] A. Krizhevsky, G. Hinton, et al.  Learning multiple layers of features from tiny images.  2009\.
  * [21] Y. LeCun, L. Bottou, Y. Bengio, and P. Haffner.  Gradient-based learning applied to document recognition.  Proceedings of the IEEE, 86(11):2278–2324, 1998.
  * [22] M. Li, L. Zhou, Z. Yang, A. Li, F. Xia, D. G. Andersen, and A. Smola.  Parameter server for distributed machine learning.  In Big Learning NIPS Workshop, volume 6, page 2, 2013.
  * [23] B. McMahan, E. Moore, D. Ramage, S. Hampson, and B. A. y Arcas.  Communication-efficient learning of deep networks from decentralized data.  In Artificial intelligence and statistics, pages 1273–1282. PMLR, 2017.
  * [24] E. M. E. Mhamdi, R. Guerraoui, and S. Rouault.  The hidden vulnerability of distributed learning in byzantium.  arXiv preprint arXiv:1802.07927, 2018.
  * [25] A. Miller, Y. Xia, K. Croman, E. Shi, and D. Song.  The honey badger of bft protocols.  In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, pages 31–42, 2016.
  * [26] F. Niu, B. Recht, C. Ré, and S. J. Wright.  Hogwild!: A lock-free approach to parallelizing stochastic gradient descent.  arXiv preprint arXiv:1106.5730, 2011.
  * [27] D. Ongaro and J. Ousterhout.  In search of an understandable consensus algorithm.  In 2014 $\\{$USENIX$\\}$ Annual Technical Conference ($\\{$USENIX$\\}$$\\{$ATC$\\}$ 14), pages 305–319, 2014.
  * [28] A. Paszke, S. Gross, S. Chintala, G. Chanan, E. Yang, Z. DeVito, Z. Lin, A. Desmaison, L. Antiga, and A. Lerer.  Automatic differentiation in pytorch.  2017\.
  * [29] A. S. Rakin, Z. He, and D. Fan.  Bit-flip attack: Crushing neural network with progressive bit search.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 1211–1220, 2019.
  * [30] F. B. Schneider.  Byzantine generals in action: Implementing fail-stop processors.  ACM Transactions on Computer Systems (TOCS), 2(2):145–154, 1984\.
  * [31] A. Sergeev and M. Del Balso.  Horovod: fast and easy distributed deep learning in tensorflow.  arXiv preprint arXiv:1802.05799, 2018.
  * [32] J.-y. Sohn, D.-J. Han, B. Choi, and J. Moon.  Election coding for distributed learning: Protecting signsgd against byzantine attacks.  Advances in Neural Information Processing Systems, 33, 2020.
  * [33] C. Xie, O. Koyejo, and I. Gupta.  Generalized byzantine-tolerant sgd.  arXiv preprint arXiv:1802.10116, 2018.
  * [34] C. Xie, S. Koyejo, and I. Gupta.  Zeno: Distributed stochastic gradient descent with suspicion-based fault-tolerance.  In International Conference on Machine Learning, pages 6893–6901. PMLR, 2019.
  * [35] C. Xie, S. Koyejo, and I. Gupta.  Zeno++: Robust fully asynchronous sgd.  In International Conference on Machine Learning, pages 10495–10503. PMLR, 2020.
  * [36] D. Yin, Y. Chen, R. Kannan, and P. Bartlett.  Byzantine-robust distributed learning: Towards optimal statistical rates.  In International Conference on Machine Learning, pages 5650–5659. PMLR, 2018.
  * [37] M. Zaharia, M. Chowdhury, M. J. Franklin, S. Shenker, I. Stoica, et al.  Spark: Cluster computing with working sets.  HotCloud, 10(10-10):95, 2010.
  * [38] H. Zhang, M. Cisse, Y. N. Dauphin, and D. Lopez-Paz.  mixup: Beyond empirical risk minimization.  arXiv preprint arXiv:1710.09412, 2017.