# The Bertini Irreducibility theorem for higher codimensional slices

Philip Kmentt and Alec Shute  IST Austria
Am Campus 1
3400 Klosterneuburg
Austria<EMAIL_ADDRESS><EMAIL_ADDRESS>
(Date: August 2021)

###### Abstract.

In [3], Poonen and Slavov develop a novel approach to Bertini irreducibility
theorems over an arbitrary field, based on random hyperplane slicing. In this
paper, we extend their work by proving an analogous bound for the dimension of
the exceptional locus in the setting of linear subspaces of higher
codimensions.

##  1\. Introduction

Bertini theorems are a family of results which typically state that if a
projective variety $X\subseteq\mathbb{P}^{n}_{F}$ over a field $F$ has a
certain nice property (such as smoothness, or geometric irreducibility), then
a generic hyperplane section of $X$ has this property too. We define

$\displaystyle\widehat{\mathbb{P}}^{n}_{F}$
$\displaystyle=\\{\textrm{hyperplanes }H\subseteq\mathbb{P}^{n}_{F}\\}$
$\displaystyle\mathfrak{M}_{\textrm{bad}}^{(1)}$
$\displaystyle=\\{H\in\widehat{\mathbb{P}}^{n}_{F}:X\cap H\textrm{ is not
geometrically irreducible}\\}.$

The set of bad hyperplanes $\mathfrak{M}_{\textrm{bad}}^{(1)}$ is a
constructible locus in $\mathbb{P}^{n}_{F}$, and so it makes sense to ask
about its dimension. A classical Bertini irreducibility theorem would state
that $\dim\mathfrak{M}_{\textrm{bad}}^{(1)}\leqslant n-1$. However, much more
is true, as demonstrated by the following theorem of Olivier Benoist.

######  Theorem 1.1.

[1, Théorème 1.4] We have $\dim\mathfrak{M}_{\textrm{bad}}^{(1)}\leqslant
n-\dim X+1$.

In 2020, Poonen and Slavov reproved Theorem 1.1 using a novel approach based
on estimates for the mean and variance of random hyperplane slices of $X$ over
a finite field. In this paper, we demonstrate that Poonen and Slavov’s methods
can be generalised to deal with linear subspaces $H$ of a general codimension
$k$. For a fixed $1\leqslant k\leqslant n-1$, we define

$\displaystyle V$ $\displaystyle=\mathbb{G}(n-k,n)=\\{\textrm{linear subspaces
}H\subseteq\mathbb{P}^{n}_{F}\textrm{ of codimension }k\\}$ (1.1)
$\displaystyle\mathfrak{M}_{\textrm{bad}}^{(k)}$ $\displaystyle=\\{H\in
V:X\cap H\textrm{ is not geometrically irreducible}\\}.$ (1.2)

The main result of this paper is the following theorem.

######  Theorem 1.2.

Let $X\subseteq\mathbb{P}^{n}_{F}$ be a geometrically irreducible variety over
an arbitrary field $F$. Let $V$ and $\mathfrak{M}_{\textrm{bad}}^{(k)}$ be as
in (1.1) and (1.2). Then

$\dim\mathfrak{M}_{\textrm{bad}}^{(k)}\leqslant\dim V-\dim X+k.$

We recall that for any $k\leqslant n$, $\dim(\mathbb{G}(n-k,n))=(n-k+1)k$.
Therefore, on taking $k=1$ in Theorem 1.2, we recover the bound
$\dim\mathfrak{M}_{\textrm{bad}}^{(1)}\leqslant n-\dim X+1$ from Theorem 1.1.

######  Remark 1.3.

Suppose that $\dim X\leqslant k$. If $X$ is not linear, then a generic
intersection $X\cap H$ for $H\in V$ will either be empty or a union of at
least two points, and so not irreducible. Hence we cannot expect a Bertini
irreducibility theorem to hold in this setting. This is consistent with the
fact that the bound in Theorem 1.2 becomes trivial when $\dim X\leqslant k$.

In the case $k=1$, Benoist proves in [1, Proposition 3.1] that Theorem 1.1 is
best possible, by exhibiting an irreducible variety $X$ such that
$\dim\mathfrak{M}_{\textrm{bad}}^{(1)}=n-\dim X+1$. The following theorem,
which we prove in Section 4, is a generalisation of this argument, and shows
that Theorem 1.2 is sharp whenever $\dim X\geqslant k$.

######  Theorem 1.4.

Let $1\leqslant k\leqslant r\leqslant n-1$. Then there exists an irreducible
variety $X\subseteq\mathbb{P}^{n}$ of dimension $r$ such that

$\dim\mathfrak{M}_{\textrm{bad}}^{(k)}=\dim V-r+k.$

######  Remark 1.5.

Rather than considering intersections $X\cap H$, Poonen and Slavov work in [3]
with a more general setup, where $\varphi:X\rightarrow\mathbb{P}^{n}$ is a
morphism whose nonempty fibres all have the same dimension. They then study
the exceptional locus of hyperplanes $H\subseteq\mathbb{P}^{n}$ such that
$\varphi^{-1}(H)$ is not geometrically irreducible. We expect that Theorem 1.2
could easily be extended to their setting.

Acknowledgements. The authors would like to thank Tim Browning for suggesting
this project and for many helpful discussions during the development of this
paper.

##  2\. Statistics of random hyperplane slices

In this section, we work over a fixed finite field $\mathbb{F}_{q}$, and
estimate the mean and variance of the number of $\mathbb{F}_{q}$-points on
random hyperplane slices of $X$.

######  Lemma 2.1.

Fix a variety $X\subseteq\mathbb{P}^{n}_{\mathbb{F}_{q}}$. Let
$V=\mathbb{G}(n-k,n)$. For $H\in V(\mathbb{F}_{q})$ chosen uniformly at
random, define the random variable $Z:=\\#(X\cap H)(\mathbb{F}_{q})$. Let
$\mu$ and $\sigma^{2}$ denote the mean and variance of $Z$ respectively. Then

$\displaystyle\mu$ $\displaystyle=\\#X(\mathbb{F}_{q})(q^{-k}+O(q^{-k-1}))$
$\displaystyle\sigma^{2}$ $\displaystyle=O(q^{-k}\\#X(\mathbb{F}_{q})).$

###### Proof.

We begin by considering the mean. We have

$\displaystyle\mu$ $\displaystyle=\frac{1}{\\#V(\mathbb{F}_{q})}\sum_{H\in
V(\mathbb{F}_{q})}\\#(X\cap H)(\mathbb{F}_{q})$
$\displaystyle=\frac{1}{\\#V(\mathbb{F}_{q})}\sum_{H\in
V(\mathbb{F}_{q})}\sum_{x\in(X\cap H)(\mathbb{F}_{q})}1$
$\displaystyle=\frac{1}{\\#V(\mathbb{F}_{q})}\sum_{x\in
X(\mathbb{F}_{q})}\sum_{\begin{subarray}{c}H\in V(\mathbb{F}_{q})\\\ x\in
H(\mathbb{F}_{q})\end{subarray}}1.$ (2.1)

We observe that the inner sum in (2.1) is independent of $x$. Consequently, we
can average the value of this sum over a dummy variable
$w\in\mathbb{P}^{n}(\mathbb{F}_{q})$ to obtain

$\displaystyle\sum_{\begin{subarray}{c}H\in V(\mathbb{F}_{q})\\\ x\in
H(\mathbb{F}_{q})\end{subarray}}1=\frac{1}{\\#\mathbb{P}^{n}(\mathbb{F}_{q})}\sum_{w\in\mathbb{P}^{n}(\mathbb{F}_{q})}\sum_{\begin{subarray}{c}H\in
V(\mathbb{F}_{q})\\\ w\in H(\mathbb{F}_{q})\end{subarray}}1.$

Returning to (2.1), we conclude that

$\displaystyle\mu$
$\displaystyle=\frac{1}{\\#\mathbb{P}^{n}(\mathbb{F}_{q})\\#V(\mathbb{F}_{q})}\sum_{x\in
X(\mathbb{F}_{q})}\sum_{H\in V(\mathbb{F}_{q})}\sum_{w\in H(\mathbb{F}_{q})}1$
$\displaystyle=\frac{\\#X(\mathbb{F}_{q})\\#\mathbb{P}^{n-k}(\mathbb{F}_{q})}{\\#\mathbb{P}^{n}(\mathbb{F}_{q})}$
(2.2) $\displaystyle=\\#X(\mathbb{F}_{q})(q^{-k}+O(q^{-k-1})).$ (2.3)

A similar argument can be applied for the variance. We have

$\displaystyle\sigma^{2}$
$\displaystyle=\left(\frac{1}{\\#V(\mathbb{F}_{q})}\sum_{H\in
V(\mathbb{F}_{q})}(\\#(X\cap H)(\mathbb{F}_{q}))^{2}\right)-\mu^{2}$
$\displaystyle=\left(\frac{1}{\\#V(\mathbb{F}_{q})}\sum_{H\in
V(\mathbb{F}_{q})}\sum_{\begin{subarray}{c}x,y\in(X\cap
H)(\mathbb{F}_{q})\end{subarray}}1\right)-\mu^{2}$
$\displaystyle=\left(\frac{1}{\\#V(\mathbb{F}_{q})}\sum_{x,y\in
X(\mathbb{F}_{q})}\sum_{\begin{subarray}{c}H\in V(\mathbb{F}_{q})\\\ x,y\in
H(\mathbb{F}_{q})\end{subarray}}1\right)-\mu^{2}.$ (2.4)

The contribution to (2.4) from the case $x=y$ is simply $\mu$. Therefore,
$\sigma^{2}=B-\mu^{2}+\mu$, where

$B=\frac{1}{\\#V(\mathbb{F}_{q})}\sum_{\begin{subarray}{c}x,y\in
X(\mathbb{F}_{q})\\\ x\neq y\end{subarray}}\sum_{\begin{subarray}{c}H\in
V(\mathbb{F}_{q})\\\ x,y\in H(\mathbb{F}_{q})\end{subarray}}1.$ (2.5)

A similar trick to above can be applied to the inner sum of (2.5), by
averaging over two dummy variables $u$ and $v$, ranging over the entirety of
$\mathbb{P}^{n}(\mathbb{F}_{q})$, but this time, with the added condition
$u\neq v$. We obtain

$\displaystyle B$
$\displaystyle=\frac{1}{\\#V(\mathbb{F}_{q})\\#\mathbb{P}^{n}(\mathbb{F}_{q})(\\#\mathbb{P}^{n}(\mathbb{F}_{q})-1)}\sum_{\begin{subarray}{c}x,y\in
X(\mathbb{F}_{q})\\\ x\neq
y\end{subarray}}\sum_{\begin{subarray}{c}u,v\in\mathbb{P}^{n}(\mathbb{F}_{q})\\\
u\neq v\end{subarray}}\sum_{\begin{subarray}{c}H\in V(\mathbb{F}_{q})\\\
u,v\in H(\mathbb{F}_{q})\end{subarray}}1$
$\displaystyle=\frac{1}{\\#V(\mathbb{F}_{q})\\#\mathbb{P}^{n}(\mathbb{F}_{q})(\\#\mathbb{P}^{n}(\mathbb{F}_{q})-1)}\sum_{\begin{subarray}{c}x,y\in
X(\mathbb{F}_{q})\\\ x\neq y\end{subarray}}\sum_{{H\in
V(\mathbb{F}_{q})}}\sum_{\begin{subarray}{c}u,v\in H(\mathbb{F}_{q})\\\ u\neq
v\end{subarray}}1$
$\displaystyle=\frac{\\#X(\mathbb{F}_{q})(\\#X(\mathbb{F}_{q})-1)\\#\mathbb{P}^{n-k}(\mathbb{F}_{q})(\\#\mathbb{P}^{n-k}(\mathbb{F}_{q})-1)}{\\#\mathbb{P}^{n}(\mathbb{F}_{q})(\\#\mathbb{P}^{n}(\mathbb{F}_{q})-1)}.$
(2.6)

Now, inspecting every term in (2.6) and comparing it to the corresponding term
in the expression for $\mu^{2}$ obtained from squaring (2.2), we see that
$B\leqslant\mu^{2},$ implying that $\sigma^{2}\leqslant\mu$. Combining with
(2.3), we deduce that in particular,
$\sigma^{2}=O(q^{-k}\\#X(\mathbb{F}_{q}))$. ∎

##  3\. Proof of Theorem 1.2

The following classical theorem of Lang and Weil provides an estimate for the
number of $\mathbb{F}_{q}$-points on a projective variety $X$.

######  Lemma 3.1 ([2]).

Let $X$ be a projective variety over $\mathbb{F}_{q}$ of dimension $r$. Let
$a$ be the number of irreducible components of $X$ that are geometrically
irreducible and have dimension $r$. Then
$\\#X(\mathbb{F}_{q})=aq^{r}+O(q^{r-1/2})$.

We can now deduce Theorem 1.2 from Lemma 2.1 and Lemma 3.1 by following a
similar argument to [3, Sections 5,6]. By applying Poonen and Slavov’s
reduction from [3, Section 3], it suffices to work over a finite ground field
$\mathbb{F}_{q}$. Moreover, by passing to a finite extension if necessary, we
may assume that $q$ is sufficiently large.

We call $H\in V(\mathbb{F}_{q})$ very bad if the number of
$\mathbb{F}_{q}$-irreducible components of $X\cap H$ which are geometrically
irreducible is not 1. Let $\mathscr{A}\subseteq V(\mathbb{F}_{q})$ denote the
set of very bad linear spaces $H$. The strategy will be to deduce Theorem 1.2
from appropriate upper and lower bounds for $\\#\mathscr{A}$. Applying a
similar argument to [3, Lemma 6.2], we have for sufficiently large $q$ that

$\\#\mathscr{A}\gg\\#\mathfrak{M}_{\textrm{bad}}^{(k)}(\mathbb{F}_{q}).$ (3.1)

In order to obtain an upper bound for $\\#\mathscr{A}$, the idea is to show
that if $H\in\mathscr{A}$, then the random variable $Z=\\#(X\cap
H)(\mathbb{F}_{q})$ introduced in Section 2 differs considerably from the mean
$\mu$. Hence there cannot be many such $H$ by the upper bound for the variance
obtained in Lemma 2.1.

Let $r=\dim X$. Combining Lemma 2.1 and Lemma 3.1, we have

$\displaystyle\mu$ $\displaystyle=q^{r-k}+O(q^{r-k-1/2})$
$\displaystyle\sigma^{2}$ $\displaystyle=O(q^{r-k}).$

If $H\in\mathscr{A}$, then by Lemma 3.1, $\\#(X\cap H)(\mathbb{F}_{q})$ is
either $O(q^{r-k-1/2})$ or at least $2q^{r-k}-O(q^{r-k-1/2})$. Consequently,

$\displaystyle\mid\\#(X\cap H)(\mathbb{F}_{q})-\mu\mid\geqslant
q^{r-k}-O(q^{r-k-\frac{1}{2}})\geqslant\frac{1}{2}q^{r-k},$

for sufficiently large $q$. Define $t$ such that $\frac{1}{2}q^{r-k}=t\sigma$.
Then,

$\displaystyle\textrm{Prob}(H\in\mathscr{A})$
$\displaystyle\leqslant\textrm{Prob}(\mid\\#(X\cap
H)(\mathbb{F}_{q})-\mu\mid\geqslant t\sigma)$
$\displaystyle\leqslant\frac{1}{t^{2}}\quad\textrm{ (by Chebyshev's
inequality)}$ $\displaystyle=\frac{4\sigma^{2}}{q^{2(r-k)}}$
$\displaystyle=O(q^{-r+k}).$

Multiplying by $\\#V(\mathbb{F}_{q})$, we obtain

$\\#\mathscr{A}=O(q^{\dim V-r+k}).$ (3.2)

Therefore, combining (3.1) and (3.2), we conclude that

$\displaystyle\dim\mathfrak{M}_{\textrm{bad}}^{(k)}\leqslant\dim V-r+k.$

##  4\. Proof of Theorem 1.4

If $r=1$, then $k=1$, and so by Remark 1.3 it suffices to take $X$ to be any
curve of degree at least $2$. From now on, we assume that $r\geqslant 2$. We
use the same construction of $X$ as in [1, Proposition 3.1], which we now
recall for convenience. Fix an integral curve $C$ of degree at least $2$, and
a linear space $L$ of dimension $r-2$ not containing $C$. Let
$X\subseteq\mathbb{P}^{n}$ be a cone with base $C$ and vertex $L$. Then $X$ is
an irreducible variety of dimension $r$.

Let $\mathscr{H}$ denote the locus of hyperplanes $H$ which contain $L$. We
denote by $\mathscr{U}$ the locus of hyperplanes $H\in\mathscr{H}$ satisfying
the following additional properties.

  1. (1)

$H\cap C$ contains a point $P$ disjoint from $L$.

  2. (2)

$\dim(X\cap H)=r-1$.

  3. (3)

$\deg(X\cap H)\geqslant 2$.

These properties hold for a generic $H\in\mathscr{H}$, so
$\dim\mathscr{U}=\dim\mathscr{H}$. Let $N$ denote the linear span of $L$ and
$P$. Suppose that $H\in\mathscr{U}$. Then $N\subseteq H$. Furthermore, $X$
contains all lines between $P$ and $L$, and hence also contains $N$. Therefore
$N\subseteq X\cap H$. From the above properties, we deduce that $N$ is a
proper closed subset of $X\cap H$ with $\dim N=r-1=\dim(X\cap H)$, and hence
$X\cap H$ is not irreducible. We conclude that

$\dim\mathfrak{M}_{\textrm{bad}}^{(1)}\geqslant\dim\mathscr{U}=\dim\mathscr{H}=n-r+1,$

and in fact, equality holds by Theorem 1.1.

We now generalise to an arbitrary $k\leqslant r$. Fix $H\in\mathscr{U}$. Let
$\mathscr{M}_{H}$ denote the locus of linear spaces $M\in\mathbb{G}(n-k,n)$
satisfying $M\subseteq H$. Then

$\dim\mathscr{M}_{H}=\dim(\mathbb{G}(n-k,n-1))=\dim(\mathbb{G}(n-k,n))-(n-k+1).$
(4.1)

For a generic $M\in\mathscr{M}_{H}$, we have

  1. (1)

$\dim(X\cap M)=r-k=\dim(N\cap M)$.

  2. (2)

$\deg(X\cap M)\geqslant 2$.

  3. (3)

The linear span of $M$ and $L$ is $H$.

For such $M$, we have that $N\cap M$ is a proper closed subset of $X\cap M$
with the same dimension as $X\cap M$, and hence
$M\in\mathfrak{M}_{\textrm{bad}}^{(k)}$. Property (3) ensures that $H$ is the
unique element of $\mathscr{U}$ containing $M$. Combining with (4.1), we
deduce that

$\displaystyle\dim\mathfrak{M}_{\textrm{bad}}^{(k)}$
$\displaystyle\geqslant\dim(\mathbb{G}(n-k,n))-(n-k+1)+\dim\mathscr{U}$ (4.2)
$\displaystyle=\dim(\mathbb{G}(n-k,n))+k-r,$

and from Theorem 1.2, (4.2) is in fact an equality.

## References

  * [1] Benoist O.  Le théorème de Bertini en famille.  Bulletin de la Société Mathématique de France, 139:555–569, 2011.
  * [2] Lang S, and Weil A.  Number of points of varieties in finite fields.  American Journal of Mathematics, 76:819–827, 1954.
  * [3] Poonen B, and Slavov K.  The exceptional locus in the Bertini irreducibility theorem for a morphism.  International Mathematics Research Notices, 2020.


# Poster: Improving Bug Localization with Report Quality Dynamics and Query
Reformulation

Mohammad Masudur Rahman  University of Saskatchewan, Canada
<EMAIL_ADDRESS>and  Chanchal K. Roy  University of Saskatchewan, Canada
<EMAIL_ADDRESS>
(2018)

###### Abstract.

Recent findings from a user study suggest that IR-based bug localization
techniques do not perform well if the bug report lacks rich structured
information such as relevant program entity names. On the contrary, excessive
structured information such as stack traces in the bug report might always not
be helpful for the automated bug localization. In this paper, we conduct a
large empirical study using 5,500 bug reports from eight subject systems and
replicating three existing studies from the literature. Our findings (1)
empirically demonstrate how quality dynamics of bug reports affect the
performances of IR-based bug localization, and (2) suggest potential ways
(e.g., query reformulations) to overcome such limitations.

††copyright: rightsretained††ccs: Software and its engineering Software
verification and validation††ccs: Software and its engineering Software
testing and debugging††ccs: Software and its engineering Software defect
analysis††ccs: Software and its engineering Software maintenance
tools††journalyear: 2018††copyright: rightsretained††conference: 40th
International Conference on Software Engineering Companion; May 27-June 3,
2018; Gothenburg, Sweden††doi: 10.1145/3183440.3195003††isbn:
978-1-4503-5663-3/18/05

##  1\. Introduction

Information Retrieval (IR)-based bug localization techniques rely on shared
terms between a bug report and the project source (Zhou et al., 2012; Moreno
et al., 2014). They are cheap and their performances are reported to be as
good as that of spectra-based techniques (Rao and Kak, 2011). Unfortunately,
Wang et al. (2015) has recently reported two major limitations based on a
qualitative study where they involved human developers. First, IR-based
techniques cannot perform well without the presence of rich structured
information (e.g., program entity names pointing to defects or failures) in
the bug report. Second, they also might not perform well with a bug report
that contains excessive structured information (e.g., stack traces). In this
paper, we conduct a large empirical study, and re-investigate the above
issues. In particular, we demonstrate how quality dynamics of bug reports
(i.e., prevalence of structured information or lack thereof) influence the
performances of three existing IR-based techniques for bug localization (Zhou
et al., 2012; Saha et al., 2013; Moreno et al., 2014), and then also discuss
potential solutions (e.g., query reformulations).

Figure 1. MAP@K of (a) Baseline, (b) BugLocator, (c) BLUiR, and (d) LOBSTER
with bug reports containing stack traces (i.e., BRST)

##  2\. Empirical Study

Wang et al. (2015) investigate IR-based bug localization with a user study and
a limited analytical study where they replicate only one IR-based technique
(Zhou et al., 2012). In order to gather more strong empirical evidences, we
replicate three IR-based bug localization techniques– BugLocator (Zhou et al.,
2012), BLUiR (Saha et al., 2013) and LOBSTER (Moreno et al., 2014), and
conduct experiments using 5,500 bug reports (ics, 2018) from eight open source
systems. We answer the following research question through our study:

RQ: How do existing IR-based techniques perform with the bug reports
containing (a) excessive structured information (e.g., stack traces), and (b)
no structured information (i.e., only regular texts)?

###  2.1. Study Design

Dataset Collection: We collect RESOLVED bug reports from either BugZilla or
JIRA repository of each subject system, extract _changeset_ (i.e., list of
changed files) from their corresponding bug-fixing commits at GitHub, and then
develop bug report-solution pairs (Bachmann and Bernstein, 2009). We also
divide our report collection into three clusters–BRNL, BRST and BRPE–based on
the extent or type of structured information they have (Wang et al., 2015).
Each bug report from BRNL contains only natural language texts whereas a
report from BRST contains one or more stack traces besides other structured
entities. On the contrary, each bug report from BRPE contains regular texts,
and one or more program entity names (e.g., method names) but no stack traces.
We use a semi-automated approach in the report clustering where regular
expressions and manual analysis were applied.

Variables of Study: We collect authors’ implementation of BugLocator and BLUiR
from their online sources, and replicate LOBSTER ourselves which is verified
using the authors’ provided experimental data. We choose three _independent
variables_ involving bug report quality, retrieval engine and text
preprocessing step and one _response variable_ involving bug localization
performance. We adopt a systematic approach using these variables and choose
our baseline approach for bug localization. In short, the baseline uses _whole
texts_ (i.e., preprocessed without stemming) of a bug report as a _query_ ,
and _Lucene_ as the _text retrieval engine_.

Figure 2. Hit@10 of Baseline, BugLocator, BLUiR, and LOBSTER with bug reports
containing only NL texts (i.e., BRNL)

###  2.2. Results and Discussions

Impact of Excessive Structured Information: We conduct experiments using the
bug reports that contain stack traces (i.e., BRST), evaluate four techniques
(i.e., three existing, one baseline), and report our findings. We found that
_BugLocator_ performed the best among all four techniques in terms of Hit@K,
Mean Reciprocal Rank@K, and Mean Average Precision@K. From Fig. 1, we see that
BugLocator achieves $\approx$40% mean average precision for various Top-K
results. However, precision measures of each technique (especially BLUiR and
LOBSTER) for BRST are significantly lower (i.e., all _p-values_ $<$0.05 and
Cliff’s 0.82$\leq$$\Delta\leq$1.00) than that for BRPE (i.e., reports
containing program entities) or BRALL (i.e., all bug reports). That is, the
same technique performs significantly lower than the average (i.e., for BRALL)
when the reports contain stack traces. Such finding supports the conjecture
about negative impacts of noisy queries on the IR-based bug localization (Wang
et al., 2015), and thus also warrants for query refinement prior to the bug
localization.

Impact of the Absence of Structured Information: We also conduct experiments
with the bug reports that contain only natural language texts but no
structured entities (i.e., BRNL), and evaluate four techniques under study. We
found that _BLUiR_ performed the best in terms of several performance metrics.
Fig. 2 shows the Hit@10 of all techniques for BRNL dataset. It is interesting
to note that the Hit@10 of BLUiR is significantly higher (i.e.,  _p-value_
=0.02$<$0.05, $\Delta$=0.50 _(large)_) than that of BugLocator although
BugLocator performed the best with BRST dataset. Furthermore, no existing
technique except BLUiR strangely performs better than the baseline for this
dataset, BRNL, which is a bit counter-intuitive. Such finding might explain
the role of underlying text retrieval engines given that each of the four
techniques used the same query (i.e., from BRNL) for the bug localization.
However, it also should be noted that each technique performed significantly
lower (i.e.,  _p-values_ $<$0.05 and 0.63$\leq$$\Delta\leq$0.84 (_large_)) for
BRNL than their average performance (i.e., for BRALL) irrespective of their
back-end retrieval engines. That is, the queries were possibly not good enough
for the localization due to their lack of relevant structured information, and
thus, they need meaningful expansions.

From Figures 1, 2, we also see that no existing technique is robust enough
against either collection – BRST or BRNL. While BugLocator performs well for
BRST, it does poorly for BRNL. The opposite is true for BLUiR. On the other
hand, every technique performs exceptionally well (i.e., 70%-80% median
Hit@10) with the high quality bug reports, i.e., BRPE. More interestingly,
even the baseline Hit@10 is higher than that of all three competing
techniques. All these findings above suggest that quality dynamics of a bug
report is a major aspect of IR-based bug localization which was possibly
overlooked by the earlier approaches. One could also argue that most of the
existing IR-based techniques (Zhou et al., 2012; Saha et al., 2013; Rao and
Kak, 2011; Nguyen et al., 2011) employ the whole report texts (i.e., title and
description) without major modifications as a _query_ for bug localization.
Hence, their query could be either noisy due to excessive structured
information (e.g., stack traces) or insufficient due to the lack of relevant
structured information (e.g., program entity names). Thus, appropriate
reformulations should be applied to the queries especially generated from BRST
and BRNL report categories before using them for bug localization with
information retrieval.

##  3\. Related Work

Information Retrieval (IR)-based bug localization has been an active area of
research for a while. Several studies employ traditional IR methods such as
Latent Semantic Analysis (LSA), Latent Dirichlet allocation (LDA) (Nguyen et
al., 2011) and Vector Space Model (VSM) (Zhou et al., 2012; Saha et al., 2013;
Moreno et al., 2014) in the bug localization, and they are found to be cheap
and effective (Rao and Kak, 2011). Unfortunately, recent findings (Wang et
al., 2015) suggest two inherent limitations of the IR-based localization
approaches. They are greatly affected by the (low) quality of the bug reports,
i.e., queries. Our work in this paper has empirically re-investigated such
qualitative observations using a much larger dataset and has confirmed their
validity.

##  4\. Conclusion & Future Work

Existing IR-based bug localization techniques are significantly affected both
by the overwhelming presence (e.g., stack traces) and by the total absence of
structured entities (i.e., only regular texts) in the bug reports, i.e.,
queries. In fact, no existing technique is robust enough against either of
these two types of reports simultaneously. Future works should incorporate
quality dynamics of bug reports and query reformulations into the IR-based bug
localization in order to overcome the challenges outlined by this study.

## Acknowledgement

This research is supported by the Natural Sciences and Engineering Research
Council of Canada (NSERC), and by a Canada First Research Excellence Fund
(CFREF) grant coordinated by the Global Institute for Food Security (GIFS) at
University of Saskatchewan.

## References

  * (1)
  * ics (2018) 2018\.  Empirical Dataset.  (2018).  http://www.usask.ca/~mor543/icse2018
  * Bachmann and Bernstein (2009) A. Bachmann and A. Bernstein. 2009.  Software Process Data Quality and Characteristics: A Historical View on Open and Closed Source Projects. In Proc. IWPSE. 119–128.
  * Moreno et al. (2014) L. Moreno, J. J. Treadway, A. Marcus, and W. Shen. 2014\.  On the Use of Stack Traces to Improve Text Retrieval-Based Bug Localization. In Proc. ICSME. 151–160.
  * Nguyen et al. (2011) A. T. Nguyen, T. T. Nguyen, J. Al-Kofahi, H. V. Nguyen, and T. N. Nguyen. 2011.  A Topic-based Approach for Narrowing the Search Space of Buggy Files from a Bug Report. In Proc. ASE. 263–272.
  * Rao and Kak (2011) S. Rao and A. Kak. 2011\.  Retrieval from Software Libraries for Bug Localization: A Comparative Study of Generic and Composite Text Models. In Proc. MSR. 43–52.
  * Saha et al. (2013) R. K. Saha, M. Lease, S. Khurshid, and D. E. Perry. 2013\.  Improving bug localization using structured information retrieval. In Proc. ASE. 345–355.
  * Wang et al. (2015) Q. Wang, C. Parnin, and A. Orso. 2015.  Evaluating the Usefulness of IR-based Fault Localization Techniques. In Proc. ISSTA. 1–11.
  * Zhou et al. (2012) J. Zhou, H. Zhang, and D. Lo. 2012.  Where should the bugs be fixed? More accurate information retrieval-based bug localization based on bug reports. In Proc. ICSE. 14–24.


# Comparison of the FCFS and PS discipline in Redundancy Systems
††thanks: The work in this research abstract is supported by the Netherlands
Organisation for Scientific Research (NWO) through Gravitation grant NETWORKS
024.002.003.

Youri Raaijmakers∗ * Corresponding author<EMAIL_ADDRESS>Department of
Mathematics and Computer Science,Eindhoven University of Technology, The
Netherlands

###### Abstract

We consider the c.o.c. redundancy system with $N$ parallel servers where
incoming jobs are immediately replicated to $d$ servers chosen uniformly at
random (without replacement). A job finishes service as soon as the first
replica is completed, after which all the remaining replicas are abandoned. We
compare the performance of the first-come first-served (FCFS) and processor-
sharing (PS) discipline based on the stability condition, the tail behavior of
the latency and the expected latency.

##  I Introduction

Nowadays, there is an abundance of cloud computing platforms that process vast
numbers of jobs and consist of tens of thousands of servers [5]. Computer
system designers always make an effort to reduce the latency, as it is shown
that only $400$ milliseconds of artificial delay into Google search already
causes the users to perform $0.74$% fewer searches after $4$-$6$ weeks [3].

Redundancy scheduling is proposed as one of the techniques to reduce latency
in applications with many servers. In redundancy scheduling each incoming job
is replicated and allocated to multiple different servers. The job is
completed as soon as the first replica finishes service after which all the
other replicas are abandoned, also known as the cancel-on-completion (c.o.c.)
variant.

Over the last years several papers have been written on the c.o.c. redundancy
system deriving expressions for key performance metrics, such as the stability
condition and expected latency. Closest related to this work is the expression
for the expected latency derived in [4] under the assumption of independent
and identically distributed (i.i.d.) replicas, exponential job sizes and the
FCFS discipline. In the same paper it is proved that the stability condition
is given by $\rho:=\frac{\lambda\mathbb{E}[X]}{N}<1$, where $\lambda$ is the
arrival rate, $N$ the number of servers and $\mathbb{E}[X]$ the expected job
size. In [1], under the same assumptions, the stability condition for the
processor-sharing (PS) discipline is examined. In particular, it is shown that
the FCFS and PS discipline yield the same stability condition. The results
regarding the stability condition for the PS discipline were later extended to
general job size distributions with possible dependence among the replicas [9]
(see also Section III). These results demonstrated that the stability
condition for the FCFS and PS discipline is only the same in the specific case
of exponential i.i.d. replicas.

In this research abstract we compare the FCFS and PS discipline in c.o.c.
redundancy systems with general job size distributions based on key
performance metrics, such as the stability condition, tail behavior of the
latency and the expected latency. It provides an overview of existing results
as well as new insights.

##  II Model description

Consider the system with $N$ parallel servers, where jobs arrive as a Poisson
process of rate $\lambda$. Each of the $N$ parallel servers has its own queue.
We consider two service disciplines, namely FCFS and PS. When a job arrives,
the dispatcher immediately assigns replicas to $d\leq N$ servers selected
uniformly at random (without replacement). We allow the replica sizes
$X_{1},\dots,X_{d}$ to be governed by some joint distribution
$F_{\boldsymbol{X}}(x_{1},\dots,x_{d})$, where $X_{i}$, $i=1,\dots,d$, are
each distributed as a generic random variable $X$, but not necessarily
independent.

Let us define $X_{\mathrm{min}}:=\min\\{X_{1},\dots,X_{d}\\}$ as the minimum
of $d$ job sizes and $\tilde{\rho}:=\frac{\lambda
d\mathbb{E}[X_{\mathrm{min}}]}{N}$ as the load of the system.

In the following sections we provide an overview of the known results for the
stability condition and the tail behavior and present new (numerical) results
for the expected latency.

##  III Stability condition

The exact expression for the stability condition with the FCFS discipline is
still an open problem. However, in [8] it is proved that no replication
($d=1$) gives a larger stability region than replication $(d>1)$ for NBU
distributions, whereas full replication $(d=N)$ gives a larger stability
region than no replication for NWU distributions (for the definition of
NBU/NWU distributions we refer to [8]).

For the PS discipline the stability condition is known and given by
$\tilde{\rho}=\frac{\lambda d\mathbb{E}[X_{\mathrm{min}}]}{N}<1$, see [9].
Observe that in the special case of i.i.d. replicas and a job size
distribution that is NBU (NWU) we have that $d\mathbb{E}[X_{\mathrm{min}}]$ is
increasing (decreasing) in $d$, see [6, Appendix A]. From this it follows that
the stability region decreases (increases) in the number of replicas for job
size distributions that are NBU (NWU). Moreover, in [9] it is conjectured that
for i.i.d. replicas the stability region for the PS discipline is smaller
(larger) than the stability region for the FCFS discipline for job size
distributions that are NBU (NWU).

$0$$1$$2$$3$$4$$5$$6$$0$$2$$4$$6$$8$$10$$\lambda$Expected latency | $2$$4$$6$$8$$10$$0$$1$$2$$3$$4$$5$$d$Expected latencyDistribution:Weibull (NBU)ExponentialWeibull (NWU)
---|---

Figure 1: Expected latency for the FCFS (solid lines) and PS (dashed lines)
discipline in the scenario with $N=3$ servers and $d=2$ (left) and $N=100$
servers and $\lambda=75$ (right) in both cases $\mathbb{E}[X]=1$, homogeneous
servers and various distributions.

##  IV Tail behavior

Let us first introduce two classes of heavy-tailed distributions.

###### Definition 1

$X$ is $\mathcal{O}$-regularly varying, denoted by $X\in ORV$, if

$\displaystyle 0<\liminf_{x\rightarrow\infty}\frac{\bar{F}_{X}(\alpha
x)}{\bar{F}_{X}(x)}\leq\limsup_{x\rightarrow\infty}\frac{\bar{F}_{X}(\alpha
x)}{\bar{F}_{X}(x)}<\infty,~{}~{}~{}\forall\alpha\geq 1,$

where $\bar{F}_{X}(x):=1-F_{X}$ is defined as the complementary cumulative
distribution function. Furthermore, $X\in ORV(-\nu)$ if

$\displaystyle
c_{1}\alpha^{-\nu}<\liminf_{x\rightarrow\infty}\frac{\bar{F}_{X}(\alpha
x)}{\bar{F}_{X}(x)}\leq\limsup_{x\rightarrow\infty}\frac{\bar{F}_{X}(\alpha
x)}{\bar{F}_{X}(x)}<c_{2}\alpha^{-\nu},$

for all $\alpha\geq 1$ with positive constants $c_{1}$ and $c_{2}$.

###### Definition 2

$X$ is regularly varying of index $-\nu$, denoted by $X\in RV(-\nu)$, if

$\displaystyle\bar{F}_{X}(x)=L(x)x^{-\nu},~{}~{}~{}x>0,$

with $L(x)$ a slowly varying function, i.e., $L(\alpha x)/L(x)\rightarrow 1$
for any $\alpha>0$ as $x$ approaches infinity.

Observe that $RV\subset ORV$, see for example [2, Theorem 2.1.8].

For the FCFS discipline we have that if $X_{\mathrm{min}}\in RV(-\tilde{\nu})$
then $R\in ORV(1-\tilde{\nu})$ (see [10]), whereas for the PS discipline we
have that if $X_{\mathrm{min}}\in RV(-\tilde{\nu})$ then $R\in
ORV(-\tilde{\nu})$ (see [11]). These results indicate that for heavy-tailed
job size distributions the PS discipline always has better tail behavior than
the FCFS discipline for all dependency structures between the replicas.

##  V Expected latency

At present almost nothing is known about the expected latency in the case of
generally distributed job sizes. Only for the (trivial) cases of no
replication ($d=1$) and full replication ($d=N$) we can derive expressions for
the expected latency, since in these cases the system is equivalent to an
$M/G/1$ queue.

For no replication ($d=1$) and full replication ($d=N$), the expected latency
for the FCFS discipline is given by

$\displaystyle\mathbb{E}[T_{\mathrm{FCFS}}]=\frac{\tilde{\rho}\mathbb{E}[X_{\mathrm{min}}^{2}]}{2(1-\tilde{\rho})\mathbb{E}[X_{\mathrm{min}}]}+\mathbb{E}[X_{\mathrm{min}}].$
(1)

For no replication ($d=1$) and full replication ($d=N$), the expected latency
for the PS discipline is given by

$\displaystyle\mathbb{E}[T_{\mathrm{PS}}]=\frac{\mathbb{E}[X_{\mathrm{min}}]}{1-\tilde{\rho}}.$
(2)

###### Remark 1

When comparing the above expressions of the expected latency it can be derived
that for both the FCFS and PS discipline no replication (full replication) is
better if
$N\mathbb{E}[\min\\{X_{1},\dots,X_{N}\\}]\geq(\leq)\mathbb{E}[X]$aaawith
equality in case of exponentially distributed job sizes.

###### Remark 2

According to Pollaczek-Khinchin we have that

$\displaystyle\mathbb{E}[T_{\mathrm{FCFS}}]\leq(\geq)\mathbb{E}[T_{\mathrm{PS}}],$

if the coefficient of variation
$C_{\mathrm{v}}^{2}:=\frac{\sqrt{\mathbb{E}[X^{2}]-(\mathbb{E}[X])^{2}}}{\mathbb{E}[X]}\leq(\geq)1$††footnotemark:
.

Moreover, a distribution that is NBU (NWU) has
$C_{\mathrm{v}}^{2}\leq(\geq)1$††footnotemark: , see for example [7].

In Figure 1 it can be seen that for $d=2$ we have that
$\mathbb{E}[T_{\mathrm{FCFS}}]<(>)\mathbb{E}[T_{\mathrm{PS}}]$ for NBU (NWU)
distributionsbbbfor exponentially distributed job sizes with $1<d<N$ the
expected latency for the FCFS and PS discipline is not exactly equal, which is
in line with the results for no replication and full replication. For NWU
distributions extensive simulation experiments suggest that full replication
achieves the best performance, in terms of expected latency.

The one-line conclusion of this research abstract, based on the stability, the
tail behavior of the latency and the expected latency, is that for c.o.c.
redundancy the FCFS discipline gives better performance for NBU distributions,
whereas the PS discipline gives better performance for NWU distributions. Now,
as pointed out in [5], the job size distribution in practice is mostly heavy-
tailed with $C_{\mathrm{v}}^{2}>>1$. We observe that, in this scenario,
redundancy scheduling significantly improves the performance. In addition
employing the PS discipline instead of the FCFS discipline enhances this
improvement even more.

## References

  * [1] E. Anton, U. Ayesta, M. Jonckheere, and I.M. Verloop.  On the stability of redundancy models.  Operations Research, in press, 2021.
  * [2] N.H. Bingham, C.M. Goldie, and J.L. Teugels.  Regular Variation. Cambridge University Press, 1987.
  * [3] J. Brutlag.  Speed matters for google weg search.  Technical report, 2009.  https://services.google.com/fh/files/blogs/google_delayexp.pdf.
  * [4] K.S. Gardner, S. Zbarsky, S. Doroudi, M. Harchol-Balter, E. Hyytia, and A. Scheller-Wolf.  Reducing latency via redundant requests: Exact analysis.  ACM SIGMETRICS Performance Evaluation Review, 43(1):347–360, 2015\.
  * [5] M. Harchol-Balter.  Open problems in queueing theory inspired by datacenter computing.  Queueing Systems, 97:3–37, 2021.
  * [6] G. Joshi.  Efficient Redundancy Techniques to Reduce Delay in Cloud Systems. PhD thesis, Massachusetts Institute of Technology, 2016.  https://dspace.mit.edu/handle/1721.1/105944.
  * [7] A.W. Marshall and F. Proschan.  Classes of distributions applicable in replacement with renewal theory implications.  Proceedings of the 6th Berkeley Symposium on Mathematical Statistics and Probability, 1:395–415, 1972.
  * [8] Y. Raaijmakers and S.C. Borst.  Achievable stability in redundancy scheduling.  Proceedings of the ACM on Measurement and Analysis of Computing Systems, 4(3):1–21, 2020.
  * [9] Y. Raaijmakers, S.C. Borst, and O.J. Boxma.  Stability of redundancy systems with processor sharing.  VALUETOOLS ’20: Proceedings of the 13th EAI International Conference on Performance Evaluation Methodologies and Tools, pages 120–127, 2020.
  * [10] Y. Raaijmakers, S.C. Borst, and O.J. Boxma.  Fork-join and redundancy systems with heavy-tailed job sizes.  In preparation, 2021.
  * [11] Y. Raaijmakers, S.C. Borst, and O.J. Boxma.  Stability and tail behavior of redundancy systems with processor sharing.  Performance Evaluation, 147:1–40, 2021.