Upper and Lower Bounds for the Synchronizer Performance in Systems with Probabilistic Message Loss

In this paper, we revisit the performance of the α-synchronizer in distributed systems with probabilistic message loss as introduced in Függer et al. [Perf. Eval. 93(2015)]. In sharp contrast to the infinite-state Markov chain resp. the exponential-size finite-state upper bound presented in the original paper, we introduce a polynomial-size finite-state Markov chain for a new synchronizer variant α′\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\alpha ^{\prime }$\end{document}, which provides a new upper bound on the performance of the α-synchronizer. Both analytic and simulation results show that our new upper bound is strictly better than the existing one. Moreover, we show that a modified version of the α′\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\alpha ^{\prime }$\end{document}-synchronizer provides a lower bound on the performance of the α-synchronizer. By means of elaborate simulation results, we show that our new lower bound is also strictly better than the lower bound presented in the original paper.