Two Column Paper

% Neutral two column research paper, standard packages only.
\documentclass[10pt,twocolumn]{article}
\usepackage[letterpaper,margin=0.8in,top=1in]{geometry}
\usepackage{lmodern}
\usepackage{amsmath}
\usepackage{titlesec}

\setlength{\columnsep}{0.28in}
\pagestyle{plain}

\titleformat{\section}{\large\bfseries}{\thesection}{0.6em}{}
\titleformat{\subsection}{\normalsize\bfseries}{\thesubsection}{0.6em}{}
\titlespacing*{\section}{0pt}{1.4ex plus .4ex}{0.8ex}

\begin{document}

\twocolumn[{
  \centering
  {\LARGE\bfseries An Empirical Study of Tail Latency\\ in Microservice Deployments\par}
  \vskip 14pt
  {\large Henrik Dalgaard \quad Lucia Ferretti \quad Samuel Kiptoo}\\[5pt]
  {\small Department of Computer Science, IT University of Copenhagen}\\[2pt]
  {\small\texttt{\{hend, lufe, samk\}@itu.dk}}
  \vskip 22pt
}]

\begin{center}{\bfseries Abstract}\end{center}
\noindent Tail latency in microservice systems is usually attributed to
stragglers in individual services, yet operators routinely observe p99
spikes with no slow service in sight. We instrument 41 production-derived
service graphs and show that 62\% of tail episodes emerge from benign
per-service variance amplified by fan-out and retry topology. We derive a
closed-form amplification bound, validate it against traces, and use it to
guide three low-cost mitigations: hedged requests on deep paths, retry
budgets scoped per edge, and fan-out-aware timeouts. Applied together, the
mitigations cut p99 latency by 44\% on our benchmark graphs without
raising median load.

\section{Introduction}
A request entering a microservice deployment fans out across dozens of
dependent calls, and the slowest branch sets the response time. Even when
every service meets its own latency objective, the composition may not:
sampling the maximum of many well-behaved distributions shifts mass into
the tail~\cite{holm2023fanout}.

For a request that fans out to $n$ independent branches with latency CDF
$F$, the probability the request exceeds deadline $t$ is
\begin{equation}
  \Pr\bigl[\,T > t\,\bigr] \;=\; 1 - F(t)^{\,n},
  \label{eq:tail}
\end{equation}
so a branch-level p99 becomes roughly a p78 at $n = 25$.
Equation~\eqref{eq:tail} is elementary, but our traces show operators
consistently underestimate effective $n$ because retries and background
refreshes multiply the branch count.

\section{Findings and Mitigations}
Across 41 graphs from three organizations we find that retry storms account
for the worst 5\% of episodes, matching earlier incident
analyses~\cite{vandermeer2024retries}, while pure fan-out amplification
explains the bulk of routine spikes. Edge-scoped retry budgets eliminate
storms at a cost of 0.02\% additional failed requests, and hedging only on
call paths deeper than three hops captures 87\% of hedging's benefit at
11\% of its extra load, consistent with the selective-hedging results
of~\cite{albrecht2022hedging}.

\begin{thebibliography}{9}
\bibitem{holm2023fanout} A. Holm and R. Deshpande.
Fan-out and the physics of tail latency.
In \textit{Proceedings of the ACM Symposium on Cloud Computing}, 2023.
\bibitem{vandermeer2024retries} J. van der Meer, T. Abebe, and C. Lindqvist.
Anatomy of retry storms in production incident reports.
In \textit{Proceedings of the 21st USENIX Symposium on Networked Systems Design and Implementation}, 2024.
\bibitem{albrecht2022hedging} M. Albrecht and S. Rao.
Hedging where it helps: selective request duplication.
In \textit{Proceedings of the 13th ACM SIGOPS Asia-Pacific Workshop on Systems}, 2022.
\end{thebibliography}

\end{document}