figure table

# Modeling human observer detection in undersampled magnetic resonance imaging
(MRI) reconstruction with total variation and wavelet sparsity regularization

Alexandra G. O’Neill  Manhattan College, Department of Mathematics, 4513
Manhattan College Pkwy, The Bronx, NY, USA, 10471  Emely L. Valdez  Manhattan
College, Department of Mathematics, 4513 Manhattan College Pkwy, The Bronx,
NY, USA, 10471  Sajan Goud Lingala  University of Iowa, Roy J. Carver
Department of Biomedical Engineering, Iowa City, IA, USA, 52242  Angel R.
Pineda  Manhattan College, Department of Mathematics, 4513 Manhattan College
Pkwy, The Bronx, NY, USA, 10471

###### Abstract

Purpose: Task-based assessment of image quality in undersampled magnetic
resonance imaging (MRI) provides a way of evaluating the impact of
regularization on task performance. In this work, we evaluated the effect of
total variation (TV) and wavelet regularization on human detection of signals
with a varying background and validated a model observer in predicting human
performance.

Approach: Human observer studies used two-alternative forced choice (2-AFC)
trials with a small signal known exactly (SKE) task but with varying
backgrounds for fluid-attenuated inversion recovery (FLAIR) images
reconstructed from undersampled multi-coil data. We used a 3.48 undersampling
factor with TV and a wavelet sparsity constraints. The sparse difference-of-
Gaussians (S-DOG) observer with internal noise was used to model human
observer detection. The internal noise for the S-DOG was chosen to match the
average percent correct (PC) in 2-AFC studies for four observers using no
regularization. That S-DOG model was used to predict the percent correct of
human observers for a range of regularization parameters.

Results: We observed a trend that the human observer detection performance
remained fairly constant for a broad range of values in the regularization
parameter before decreasing at large values. A similar result was found for
the normalized ensemble root mean squared error (ERMSE). Without changing the
internal noise, the model observer tracked the performance of the human
observers as the regularization was increased but over-estimated the PC for
large amounts of regularization for TV and wavelet sparsity, as well as the
combination of both parameters.

Conclusions: For the task we studied, the S-DOG observer was able to
reasonably predict human performance with both total variation and wavelet
sparsity regularizers over a broad range of regularization parameters. We
observed a trend that task performance remained fairly constant for a range of
regularization parameters before decreasing for large amounts of
regularization.

###### keywords:

model observers, magnetic resonance imaging, constrained reconstruction, image
quality assessment

*Angel R. Pineda<EMAIL_ADDRESS>
##  1 Introduction

Task-based assessment of image quality [1, 2] for reconstructed MRI images is
critical to the development and validation of accelerated reconstruction
techniques. This approach has been extensively used in other imaging
modalities [3, 4, 5, 6, 7, 8, 9, 10, 11, 12] There has been research using
task-based techniques in MRI for parallel imaging [13] and compressed sensing
[14] but most methods utilized for assessment of image quality in MRI are
typically root mean square error (RMSE) and structural similarity index
(SSIM). These are measures of pixel value differences between the original and
reconstructed image[15, 16]. While these measures do give an indication of
similarity between images, neither RMSE nor SSIM take into account the
specific task for which the image will be used. As a result, images with the
same RMSE and SSIM could produce different performance in these tasks.
Observer models are an alternative way to assess image quality by taking into
account human visual principles as well as the task for which the image will
be used [17, 18, 19].

Previous results related to evaluating MRI reconstruction of undersampled
images using an approximation to the ideal linear observer [20, 21, 22] showed
that the area under the ROC curve (AUC) for the channelized Hotelling observer
with Laguerre Gauss channels showed only a small improvement with
regularization. However, both SSIM and RMSE showed a large improvement. Our
preliminary results using human observer studies [23, 24] suggest a similar
result in that there was no large improvement with regularization for this
task. The purpose of this work is to evaluate constrained reconstruction of
undersampled MRI data using TV, wavelet, and a combination of these
constraints based on human observer performance in detecting a small signal in
a 2-AFC task. A model observer (S-DOG) is used to model human observer
performance in this detection task. Along with optimizing reconstruction, a
goal of this work is also to reduce the number of future human observer
studies needed in undersampled MRI reconstruction by using model observers to
evaluate image quality.

##  2 Methods

###  2.1 Undersampled acquisition in MRI

For this study we consider 1-D undersampling of FLAIR images (Figure 1) with
an acquisition that samples every fourth phase encoding line plus fully
sampling the middle 16 kspace lines resulting in an effective undersampling
factor of 3.48. Data used in the preparation of this article were obtained
from the NYU fastMRI Initiative database [25]. The average white matter signal
to noise ratio (SNR) for the fully sampled multi-coil SENSE reconstructions
(R=1) was measured by estimating the standard deviation from components of the
image with only noise and assuming a Rayleigh distribution [26] and the mean
signal across a homogeneous region of white matter image in the reconstructed
slices. This led to an average white matter SNR of 83 in the 50 slices used
for the observer studies. The NYU fastMRI investigators provided data but did
not participate in analysis or writing of this report.

---
Figure 1:  (A) Sampling mask for 4x undersampling, (B) Fully sampled image,
(C) Undersampled constrained reconstruction with no TV regularization,
Aliasing in the vertical axis is visible in the undersampled image. The
acquisition had a 2x oversampling in the horizonal direction.

###  2.2 Constrained Reconstruction from multi-coil Data

Constrained reconstruction minimizes a data agreement functional with
additional constraints. For this work we consider a total variation and
wavelet constraint[16] and multi-coil parallel imaging using SENSE[27] with
the coil sensitivities estimated using the sum of squares method which leads
to real estimates of real-valued objects.
The following functional was minimized when reconstructing these images:

$||H(f)-g||^{2}_{2}+\alpha_{\Psi}\,||\Psi(f)||_{1}+\alpha_{TV}\,||\nabla
f||_{1},$ (1)

where $H(f)$ is the undersampled Fourier operator acting on the discretized
object $f$, the Fourier data is ${\bf g}$, $\Psi$ is the Daubechies 4 wavelet
transform, $||\nabla f||_{1}$ is the $L_{1}$ norm of the gradient which is the
total variation operator and $\alpha_{\Psi}$ and $\alpha_{TV}$ are the
regularization parameters for the wavelet and TV constraints respectively
[16]. Sample images with different amounts of TV and wavelet regularization
are shown in Figure 2 and Figure 3 respectively. The reconstruction of the
images was done using the Berkeley Advanced Reconstruction Toolbox (BART)
toolbox [28]. The ensemble root mean squared error for the reconstructed
images (ERMSE) was computed using the fully sampled unregularized
reconstruction normalized to [0,1] as the reference image. The underampled
reconstructions were normalized to [0,1] before computing the RMSE. The ERMSE
was computed from 50 slices from 5 volumes.

---
Figure 2:  Sample undersampled images reconstructed with TV regularization, A)
$\alpha_{TV}=0.01$, B) $\alpha_{TV}=0.02$, C) $\alpha_{TV}=0.05$, D)
$\alpha_{TV}=0.1$. As the regularization increases, there are reduced aliasing
artifacts but also reduced resolution. The arrow in image A shows the location
of one of the undersampling artifacts.
---
Figure 3:  Sample undersampled images reconstructed with wavelet sparsity, A)
$\alpha_{W}=0.01$, B) $\alpha_{W}=0.02$, C) $\alpha_{W}=0.05$, D)
$\alpha_{W}=0.1$. As the regularization increases, there are reduced aliasing
artifacts but also reduced resolution but with different texture than in TV
regularization. The arrow in image A shows the location of one of the
undersampling artifacts.

###  2.3 Two-alternative forced choice experiments

In each individual trial of the 2AFC experiment we presented three 128x128
pixel images: one image of an anatomical background with the signal, the
signal, and one image of an anatomical background without the signal. The
signal image was always in the center, and the location (left or right) of the
anatomical image with the signal was randomly chosen for each trial. All
images are scaled to [0,1] before being displayed using the 8 bit gray scale
colormap in MATLAB. Since the observers were not radiologists, the images were
windowed and leveled for them. Our choice of windowing leads to a different
number of gray scale values representing the signals depending on the
backgrounds and regularization. In all cases, a reasonable number of gray
scale values was used to represent the signal contrast with an average of 32
gray scale values for images with no regularization down to an average of 8
gray scale values for images with the most regularization ($\alpha_{TV}$=0.1,
$\alpha_{W}$=0.1). An example trial is shown in Figure 4. The signal location
is always in the middle of the anatomical image, which makes this task a
signal known exactly (SKE) with varying backgrounds and the human observer
only determines whether or not it is present in the image.

---
Figure 4:  Sample 2AFC trial with signal in the left image. The arrow present
in this image was not used in the observer study and is there to help the
reader identify the signal. In order to see differences in performances due to
regularization, the images used were subtle. These images were generated with
no regularization but the artifacts are more visible in the image to the
right.

###  2.4 Experimental procedure

For each experimental condition, 200 2AFC trials were carried out by four
observers. As training, all observers repeated an initial set of 200 trials
until the performance plateaued. Based on performance in the training trials,
the signal amplitude was chosen so that the mean percent correct for the
observers would be close to 90 percent when no regularization was used.

The observer studies were done using a Barco MDRC 2321 monitor in a dark room.
The resolution of the Barco monitor was 0.294 mm and the observers were
approximately 50 cm from the screen. A marker at 50 cm was provided for
reference.

For each individual trial, a set of images like Figure 4 appeared on the
screen and the observer chose which image they believed contained the signal.
The observers received feedback on whether they had identified the signal
correctly after each trial for possible improvement between trials and took
breaks between sets of 200 trials to avoid fatigue.

For each observer, the images used in each 2-AFC trial were randomly paired
from 200 backgrounds with the signal and 200 background images. For each level
of regularization, the standard deviation was computed using the percent
correct of each of the four observers. There are several sources of
variability in this estimate of the percent correct due to the multiple reader
- multiple case (MRMC) experimental design. Our estimate of the standard
deviation based on the percent correct of the individual observers is a
summary of the variability of the percent correct values from the readers but
not based on an unbiased estimate [29].

###  2.5 Model Observers

The model that we used in our study was the S-DOG channelized Hotelling
Observer [17]. The channel data ${\bf g_{c}}$ is obtained by taking the inner
product of the image with the channels centered at the signal. The elements
$g_{c,j}$ of the vector ${\bf g_{c}}$ are given by:

$g_{c,j}=C_{j}^{t}f,$ (2)

where $C_{j}$ is the $j^{th}$ channel in the spatial domain and $f$ is the
object in the spatial domain. We used the S-DOG channels of the form

$C_{j}(k)=exp[-\frac{1}{2}\left(\frac{k}{Q*\sigma_{j}}\right)^{2}]-exp[-\frac{1}{2}\left(\frac{k}{\sigma_{j}}\right)^{2}]$
(3)

in the frequency domain where $k$ is the distance from the zero frequency, Q
is the multiplicative factor of the bandwidth,
$\sigma_{j}=\sigma_{0}*\alpha^{j}$, where j denotes the jth channel and
$\sigma_{j}$ denotes the standard deviation of each channel. The parameters
that were used for the S-DOG were $Q=2$, $\alpha=2$, and $\sigma_{0}=0.015$
which were used by Abbey[17] (Figure 5).

Figure 5:  (A) The cross section of S-DOG channels matched for human
performance with no TV regularization in the frequency domain and (B) spatial
domain.

The test statistic ($\lambda$) for the S-DOG observer for each image was
computed using:

$\lambda=[(K_{c}+K_{int})^{-1}\bf{s_{c}}]^{t}(\bf{g_{c}}+\bf{n_{int}}),$ (4)

where $K_{c}$ is the sample covariance matrix of the data in the channel
domain, $K_{int}$ is the covariance matrix of the channel internal noise,
$s_{c}$ is the mean signal difference in the channel domain, $g_{c}$ is the
image in the channel domain and $n_{int}$ is a noise vector drawn from the
distribution $N(0,K_{int})$.

The covariance for the internal noise is:

$K_{int}=\epsilon\,diag(K_{c}),$ (5)

where $\epsilon$ is the internal noise constant and $diag(K_{c})$ is a
diagonal matrix with the diagonal elements of $K_{c}$ [17].

The channel covariance matrix $K_{c}$ is computed by taking the average of the
channel covariance matrix with and without the signal. The mean signal
difference ($s_{c}$)is computed by subtracting the sample average of the
channel outputs without the signal from the average channel outputs with the
signal. The internal noise was determined by varying the noise constant
$\epsilon$ values until the performance matched the average human performance
for the unregularized reconstruction. This calibrated model with the images
with no regularization was used to predict all other experimental conditions
with regularization.

We utilized six regularization parameter values for each of the three
regularization conditions that were generated with 4x undersampling. For TV
and wavelet regularization, the parameters used were: 0, 0.001, 0.002,
$2*10^{-1}$, $5*10^{-1}$, and 0.1. These values were also used when both types
of regularization were combined.

##  3 Results and Discussion

The S-DOG overestimated human performance without the addition of internal
noise. However, the pattern of performance as TV increased was the same as
both the human observers. Once the internal noise was added, tracking the
human performance can be seen with the S-DOG in Figure 6. The S-DOG closely
tracks human performance for small amounts of regularization (which would be
used in practice) and over-estimates the human performance for large amounts
of regularization.

Figure 6:  A) S-DOG observer with internal noise matched to average human
observer for images with no TV regularization. The S-DOG observer tracked the
human observer data for the other regularization parameters. The S-DOG
slightly overestimates for the largest regularization parameters. B)
Normalized ERMSE for varying TV regularization. The ERMSE metric leads to
similar conclusions as the 2-AFC detection performance.

Similarly, the S-DOG is also able to track human observer performance for
varying wavelet regularization but again overestimates performance at the
largest values of regularization as seen in Figure 7. Wavelet regularization
was not found to meaningfully improve human performance in this task. Lastly,
the combination of wavelet and TV regularization does not lead to a large
improvement in human performance for this detection task. Figure 8 shows the
prediction for performance based on the S-DOG before doing the observer study
where the two types of regularization were combined. In Figure 9, the
predictions were validated using an observer study. The same S-DOG model was
used in this plot as in Figures 6, 7, 8. The ERMSE showed a similar behavior
for all these types of regularization. In all cases, the internal noise was
chosen so that the model observer matched the average human observer
performance with no regularization.

Figure 7:  A) S-DOG observer with internal noise matched to average human
observer for images with no wavelet sparsity. The S-DOG observer tracked the
human observer data for the other regularization parameters. The S-DOG
slightly overestimates for the largest regularization parameter. B) Normalized
ERMSE for varying wavelet sparsity. The ERMSE metric leads to similar
conclusions as the 2-AFC detection performance. Figure 8:  A) The S-DOG
observer predicts that even with a combination of wavelet and TV
regularization, the average human observer performance remains fairly constant
for this task for a range of regularization parameters and that it degrades at
high levels of regularization. B) The ERMSE behaves leads to similar
conclusions as the S-DOG observer. Figure 9:  A) The S-DOG observer predicts
that even with a combination of wavelet and TV regularization, the average
human observer performance remains fairly constant for this task for a range
of regularization parameters and that it degrades at high levels of
regularization. B) The ERMSE behaves leads to similar conclusions as the S-DOG
observer.

It is difficult to quantify task performance based on subjective evaluation of
image quality by looking at the images. Figure 10 show sample images with a
signal for different levels of regularization. Previous work showed that the
MSE and SSIM may change in a meaningful way with regularization [22] but the
task performance and visual assessment remain similar.

---
Figure 10:  Sample subimages with lesions undersampled images reconstructed
with TV and Wavelet regularization, A) $\alpha_{TV}=0.0,\alpha_{W}=0.0$ B)
$\alpha_{TV}=0.01,\alpha_{W}=0.01$, C) $\alpha_{TV}=0.02,\alpha_{W}=0.02$, D)
$\alpha_{TV}=0.05,\alpha_{W}=0.05$. As the regularization increases, there are
reduced aliasing artifacts but also reduced resolution. Image quality and task
performance (as measured by the average percent correct shown in the images)
is difficult to assess from the sample images.

This study considered undersampling at a high SNR. The effect of
regularization on detection performance for with varying backgrounds could be
different at lower SNR regimes. Some slight improvement was seen in the
context of ramp-spectrum noise for human observers [17] and in ideal observer
performance in undersampled MRI [22]. Recent work studying the effect of
denoising using neural networks on detection performance in SPECT showed that
denoising could decrease detection performance even if it improved RSME and
SSIM [30]. In another study using simulated images showed similar results
[31]. Exploring applications where regularization helps in a detection-based
perspective would be useful to better understand the regimes where metrics
like ERMSE and detection performance agree and disagree.

The visibility of the signal varies depending on the background. Figure 11
shows the variability in the sample images for a single regularization value.

---
Figure 11:  Sample subimages with lesions undersampled images reconstructed
with TV and Wavelet regularization ($\alpha_{TV}$=0.01,$\alpha_{W}$=0.01).
Even though the signals are always present, subjectively we see that the
signal is easier to detect in images A and B but harder to see in images C and
D. This variability in visibility due to background variability for the same
reconstruction is one of the reasons why it is important to average over
multiple backgrounds to estimate performance.

A limitation of this study is the experimental design which paired the images
in the 2-AFC study randomly for each of the observers. This leads to
complicated correlations within the cases and readers since readers may share
the signal image in a 2-AFC trial but with different background images, for
example. To our knowledge, current approaches for unbiased estimates of
variance do not include such an experimental design [32, 33].

##  4 Conclusion

To our knowledge, this is the first application of a model observer for
tracking human observer detection performance in undersampled MRI
reconstruction. The S-DOG model observer was able to track human performance
for TV and wavelet constraints, as well as the combination of both TV and
wavelet. One of the results of this study is that model observers are able to
track human observer performance as the regularization changes. We also
observed a trend that commonly used regularization parameters of TV, wavelet,
and combination TV and wavelet constraints led to a plateau in detection
performance for low levels of regularization before causing a drop in
performance for large levels of regularization. This suggests that within that
plateau, the regularization parameter could be chosen by some other criteria
without affecting task performance.

### Data, Materials and Code Availability

The code used for placing the signals in the raw k-space data, and running the
observer studies and model observers can be found at: https://github.com/MoMI-
Manhattan-College/MRI-Signal-Detection

### Acknowledgements

This work was supported by the National Institute of Biomedical Imaging and
Bioengineering of the National Institutes of Health under award number
R15-EB029172, the Manhattan College Faculty Development Grant and the Kakos
Center for Scientific Computing. The authors thank Dr. Krishna S. Nayak at the
University of Southern California and Dr. Craig K. Abbey at University of
California, Santa Barbara for their time and guidance. The authors would also
like to thank the reviewers for their thoughtful comments which improved the
manuscript and identified areas of future work.

## References

  * [1] H. H. Barrett, “Objective assessment of image quality: effects of quantum noise and object variability,” J. Opt. Soc. Am. A 7, 1266–1278 (1990).
  * [2] H. H. Barrett and K. J. Myers, Foundations of Image Science, John Wiley and Sons, Hoboken, NJ (2004).
  * [3] L. Yu, B. Chen, J. M. Kofler, et al., “Correlation between a 2d channelized hotelling observer and human observers in a low-contrast detection task with multislice reading in ct,” Medical Physics 44(8), 3990–3999 (2017).
  * [4] C. P. Favazza, A. Ferrero, L. Yu, et al., “Use of a channelized Hotelling observer to assess CT image quality and optimize dose reduction for iteratively reconstructed images,” Journal of Medical Imaging 4(3), 1 – 8 (2017).
  * [5] H.-W. Tseng, J. Fan, and M. A. Kupinski, “Design of a practical model-observer-based image quality assessment method for x-ray computed tomography imaging systems,” Journal of Medical Imaging 3(3), 1 – 10 (2016).
  * [6] G. J. Gang, J. Lee, J. W. Stayman, et al., “Analysis of fourier-domain task-based detectability index in tomosynthesis and cone-beam ct in relation to human observer performance,” Medical Physics 38(4), 1754–1768 (2011).
  * [7] H. C. Gifford, P. E. Kinahan, C. Lartizien, et al., “Evaluation of multiclass model observers in pet lroc studies,” IEEE Transactions on Nuclear Science 54(1), 116–123 (2007).
  * [8] J. G. Brankov, “Evaluation of the channelized hotelling observer with an internal-noise model in a train-test paradigm for cardiac SPECT defect detection,” Physics in Medicine and Biology 58, 7159–7182 (2013).
  * [9] J. Baek, A. R. Pineda, and N. J. Pelc, “To bin or not to bin? the effect of ct system limiting resolution on noise and detectability,” Phys. Med. Biol. 58, 1433 (2013).
  * [10] A. K. Jha, E. Clarkson, and M. A. Kupinski, “An ideal-observer framework to investigate signal detectability in diffuse optical imaging,” Biomed. Opt. Express 4, 2107–2123 (2013).
  * [11] A. R. Pineda, M. Schweiger, S. R. Arridge, et al., “Information content of data types in time-domain optical tomography,” J. Opt. Soc. Am. A 23, 2989–2996 (2006).
  * [12] A. Pineda, S. Yoon, D. S. Paik, et al., “Optimization of a tomosynthesis system for the detection of lung nodules,” Medical Physics 33, 1372–1379 (2006).
  * [13] Y. Jiang, D. Huo, and D. L. Wilson, “Methods for quantitative image quality evaluation of mri parallel reconstructions: detection and perceptual difference model,” Magnetic Resonance Imaging 25(5), 712–721 (2007).
  * [14] C. G. Graff and E. Y. Sidky, “Compressive sensing in medical imaging,” Appl. Opt. 54, C23–C44 (2015).
  * [15] Z. Wang, A. Bovik, H. Sheikh, et al., “Image quality assessment: From error visibility to structural similarity,” IEEE Trans. Image Process. 13, 600–612 (2004).
  * [16] M. Lustig, D. Donoho, and J. M. Pauly, “Sparse mri: The application of compressed sensing for rapid mr imaging,” Magn. Reson. Med. 58, 1182–1195 (2007).
  * [17] C. K. Abbey and H. H. Barrett, “Human-and model-observer performance in ramp-spectrum noise: effects of regularization and object variability,” J. Opt. Soc. Am. A 18, 473–488 (2001).
  * [18] A. E. Burgess, “Statistically defined backgrounds: performance of a modified nonprewhitening observer model,” Journal of the Optical Society of America A 11(4), 1237–1242 (1994).
  * [19] K. J. Myers and H. H. Barrett, “Addition of a channel mechanism to the ideal-observer model,” J. Opt. Soc. Am. A 4, 2447–2457 (1987).
  * [20] Y. Chen, Y. Lou, M. A. Kupinski, et al., “Task-based data-acquisition optimization for sparse image reconstruction systems,” Proc. SPIE. 10136, 264 – 269 (2017).
  * [21] A. R. Pineda, “Laguerre-Gauss and sparse difference-of-Gaussians observer models for signal detection using constrained reconstruction in magnetic resonance imaging,” in Medical Imaging 2019: Image Perception, Observer Performance, and Technology Assessment, R. M. Nishikawa and F. W. Samuelson, Eds., 10952, 53 – 58, International Society for Optics and Photonics, SPIE (2019).
  * [22] A. Pineda, H. Miedema, S. Lingala, et al., “Optimizing constrained reconstruction in magnetic resonance imaging for signal detection,” Phys Med Biol. 66, 145014 (2021).  [doi:10.1117/1.2338565].
  * [23] A. G. O’Neill, E. L. Valdez, S. G. Lingala, et al., “Modeling human observer detection in undersampled magnetic resonance imaging (MRI),” in Medical Imaging 2021: Image Perception, Observer Performance, and Technology Assessment, F. W. Samuelson and S. Taylor-Phillips, Eds., 11599, 85 – 90, International Society for Optics and Photonics, SPIE (2021).
  * [24] A. G. O’Neill, S. G. Lingala, and A. R. Pineda, “Predicting human detection performance in magnetic resonance imaging (MRI) with total variation and wavelet sparsity regularizers,” in Medical Imaging 2022: Image Perception, Observer Performance, and Technology Assessment, C. R. Mello-Thoms and S. Taylor-Phillips, Eds., 12035, 256 – 261, International Society for Optics and Photonics, SPIE (2022).
  * [25] F. Knoll and J. Zbontar, “fastmri: A publicly available raw k-space and dicom dataset of knee images for accelerated mr image reconstruction using machine learning,” Radiology: Artificial Intelligence 2(1) (2020).
  * [26] O. Dietrich, J. G. Raya, S. B. Reeder, et al., “Measurement of signal-to-noise ratios in mr images: Influence of multichannel coils, parallel imaging, and reconstruction filters,” Journal of Magnetic Resonance Imaging 26(2), 375–385 (2007).
  * [27] K. P. Pruessmann, M. Weiger, M. B. Scheidegger, et al., “Sense: Sensitivity encoding for fast mri,” Magnetic Resonance in Medicine 42(5), 952–962 (1999).
  * [28] M. Uecker, F. Ong, J. I. Tamir, et al., “Berkeley advanced reconstruction toolbox,” Proc. Intl. Soc. Mag. Reson. Med 23, 2486 (2015).
  * [29] B. D. Gallas, G. A. Pennello, and K. J. Myers, “Multireader multicase variance analysis for binary data,” J. Opt. Soc. Am. A 24(12), B70–B80 (2007).
  * [30] Z. Yu, M. A. Rahman, and A. K. Jha, “Investigating the limited performance of a deep-learning-based SPECT denoising approach: an observer-study-based characterization,” in Medical Imaging 2022: Image Perception, Observer Performance, and Technology Assessment, C. R. Mello-Thoms and S. Taylor-Phillips, Eds., 12035, 120350D, International Society for Optics and Photonics, SPIE (2022).
  * [31] K. Li, W. Zhou, H. Li, et al., “Assessing the impact of deep neural network-based image denoising on binary signal detection tasks,” IEEE Transactions on Medical Imaging 40(9), 2295–2305 (2021).
  * [32] B. D. Gallas, A. Bandos, F. W. Samuelson, et al., “A framework for random-effects roc analysis: Biases with the bootstrap and other variance estimators,” Communications in Statistics - Theory and Methods 38(15), 2586–2603 (2009).
  * [33] B. J. Smith and S. L. Hillis, “Multi-reader multi-case analysis of variance software for diagnostic performance comparison of imaging modalities,” in Medical Imaging 2020: Image Perception, Observer Performance, and Technology Assessment, F. W. Samuelson and S. Taylor-Phillips, Eds., 11316, 113160K, International Society for Optics and Photonics, SPIE (2020).

Alexandra G. O’Neill is a clinical research coordinator in the Division of
Neuropsychiatry and Neuromodulation at Massachusetts General Hospital. She
received her BS in mathematics and psychology from Manhattan College in 2022.
Her research interests include modeling of human observer performance and
statistical analysis in psychology.

Emely L. Valdez is a mathematics teacher at DreamYard Preparatory High School.
She received her BS in mathematics from Manhattan College. Her research
interests include modeling of human observer performance.

Sajan Goud Lingala, PhD is an Assistant Professor of Biomedical Engineering
and Radiology at the University of Iowa. He received his Bachelors, Masters,
PhD all in Biomedical Engineering respectively from the Osmania University
(2002-06), Indian Institute of Technology (2006-08), University of Iowa
(2008-14). Between 2014-2017, he completed a postdoctoral fellowship at the
University of Southern California. His current research interests include
rapid MRI sequence design, dynamic MRI, model based reconstruction using
adaptive priors (eg. learning based).

Angel R. Pineda is a professor of mathematics at Manhattan College. He
completed his BS in chemical engineering from Lafayette College, his PhD in
applied mathematics from the University of Arizona and his postdoctoral
fellowship in the Radiology Department of Stanford University. His research
quantifies the information content of medical images from a task-based
perspective.


11institutetext: Department of Computer Science, Kent State University, Kent,
OH 44242, USA
11email: {joglio@,khood5@,sharma@cs.,mikhail<EMAIL_ADDRESS>
# Consensus on an Unknown Torus with
Dense Byzantine Faults

Joseph Oglio  Kendric Hood  Gokarna Sharma  Mikhail Nesterenko

###### Abstract

We present a solution to consensus on a torus with Byzantine faults. Any
solution to classic consensus that is tolerant to $f$ Byzantine faults
requires $2f+1$ node-disjoint paths. Due to limited torus connectivity, this
bound necessitates spatial separation between faults. Our solution does not
require this many disjoint paths and tolerates dense faults.

Specifically, we consider the case where all faults are in one column. We
address the version of consensus where only processes in fault-free columns
must agree. We prove that even this weaker version is not solvable if the
column may be completely faulty. We then present a solution for the case where
at least one row is fault-free. The correct processes share orientation but do
not know the identities of other processes or the torus dimensions. The
communication is synchronous.

To achieve our solution, we build and prove correct an all-to-all broadcast
algorithm $\mathcal{BAT}$ that guarantees delivery to all processes in fault-
free columns. We use this algorithm to solve our weak consensus problem. Our
solution, $\mathcal{CBAT}$, runs in $O(H+W)$ rounds, where $H$ and $W$ are
torus height and width respectively. We extend our consensus solution to the
fixed message size model where it runs in $O(H^{3}W^{2})$ rounds. Our results
are immediately applicable if the faults are located in a single row, rather
than a column.

##  1 Introduction

A Byzantine process [16, 20] may arbitrarily deviate from the prescribed
algorithm. This is the strongest fault that can affect a process in a
distributed system. The fault is powerful enough to straddle the realm of
fault tolerance and security as it may model either a device failure or a
malicious intruder.

In the presence of Byzantine faults, the common task for correct processes is
to come to an agreement or consensus. The power of the faults may be abridged
with cryptography [1, 9, 14] or randomization [4, 10, 23]. If neither
primitive is available, the solutions require that the number of correct
processes is large enough to overwhelm the faulty ones.

If the topology of a network is considered, the consensus problem is further
complicated as faulty processes, even small in absolute number may isolate
some correct processes and prevent them from achieving consensus. In a general
topology, it is known that consensus is solvable only if the network is at
least $2f+1$-connected [8, 11, 16]. However, such connectivity demands a dense
network with large node degree which limits the scalability of a solution
achieved this way.

In this paper, we study Byzantine-robust consensus on a torus. Its fixed
degree and small diameter makes torus an attractive architecture for
distributed computing and storage tasks [3, 12]. Torus connectivity is $4$.
Hence, according to classic connectivity bounds, it may not tolerate more than
$1$ fault. To increase tolerance, the fault locations must be restricted. One
approach is to make the faults sparse. That is, the faulty processes need to
be positioned far enough apart so that $2f+1$ connectivity is preserved [17].
Such a solution fails if the faults are located close to each other. In this
paper, we address dense Byzantine faults on a torus of unknown dimensions.
However, to achieve tolerance, we restrict fault location to a single column.

Related work. There are a number of solutions optimizing consensus in
incomplete topologies [2, 7, 18, 24, 25]. Chlebus et al. [7] optimize the
speed of achieving Byzantine consensus in arbitrary topologies. The
connectivity is subject to $2f+1$ bound. Alchieri et al. [2] study synchronous
Byzantine consensus with unknown participants. They use participant detectors
to establish network membership. Tseng and Vaidya [24] explore consensus in
directed graphs. Winkler et al. [25] study consensus in directed dynamic
networks. Oglio et al. [19] solve Byzantine consensus in Euclidean space.

Potentially, network topology may be discovered despite Byzantine faults. This
simplifies consensus solution. Nesterenko and Tixeuil present two generic
Byzantine-tolerant topology discovery algorithms [18]. However, neither
algorithm is suitable for our task: their first algorithm raises an alarm once
an inconsistency is discovered without completing the task. Their second
algorithm requires $2f+1$ connectivity.

Let us discuss consensus on toruses and related topologies. Several papers [5,
15, 21] consider the problem of Byzantine-tolerant reliable broadcast on an
infinite grid or a torus in radio networks. In such a network, all processes
within a particular distance from the sender receive the message
simultaneously. Due to this limitation, their results are not immediately
applicable to our model.

Kandlur and Shin [13] consider a synchronous Byzantine-tolerant broadcast on a
torus. In their approach, each message is delivered over a fixed number of
node-disjoint paths. The correct message is recovered so long as the majority
of paths bypass faulty nodes. Since torus connectivity is $4$, this approach
may tolerate at most one fault. Maurer and Tixeuil [17] study a Byzantine-
tolerant broadcast on a torus. In their model, the byzantine torus dimensions
are not known. Their solution assumes that the faulty nodes are sparse, i.e.
they are located far enough apart such that there is sufficiently many node
disjoint paths between the sender and any of the receivers to ensure that the
influence of the faulty nodes is countered.

Thus, to the best of our knowledge, previous work has not addressed dense
Byzantine faults on a torus.

Paper contribution and approach. We consider the synchronous model,
bidirectional communication, no cryptographic primitives or randomization. The
topology we study is a torus whose dimensions: height $H$ and width $W$ are
unknown to the processes. All processes share orientation. We assume that all
faults are located in a single column.

We consider the weaker consensus where only processes in fault-free columns
must agree on a value. We prove that even this version is not solvable if a
single column is completely faulty.

We examine the case where at least one row is fault-free. To counter faulty
column influence, we assume that $W\geq 5$. To solve this weak consensus
problem, we first present an all-to-all broadcast algorithm $\mathcal{BAT}$
that guarantees delivery to fault-free columns. We prove it correct and show
that it runs in $O(H+W)$ rounds in the LOCAL model [20] where messages are of
arbitrary size. We then use $\mathcal{BAT}$ to build the consensus algorithm
$\mathcal{CBAT}$. We prove it correct and show that it runs in $O(H+W)$ rounds
in LOCAL.

We then extend $\mathcal{BAT}$ and $\mathcal{CBAT}$ to use fixed-size messages
and estimate their running time in the CONGEST model [22]. We determine that
the fixed-size message $\mathcal{BAT}$ runs in $O(H^{2}W)$ rounds and
$\mathcal{CBAT}$ runs in $O(H^{3}W^{2})$ rounds. Our results are immediately
applicable to the case of faults located in a single row rather than column.

Let us now introduce our solution approach. To counter the faults, we leverage
the processes’ shared knowledge of the network topology. The data is first
propagated along the column and the influence of possibly densely packed
column of faults is neutralized. The single correct process is guaranteed to
relay data across the faulty column. This horizontally propagated data is then
disseminated through the fault-free columns to reach all correct processes
there.

Paper organization. In Section 2, we introduce our notation, state the problem
and prove the necessity of a fault-free row. In Section 3, we present and
prove correct our all-to-all broadcast algorithm $\mathcal{BAT}$. In Section
4, we use $\mathcal{BAT}$ to construct and prove correct our consensus
algorithm $\mathcal{CBAT}$. In Section 5, we describe how the algorithms can
be modified for fixed message size and estimate their run time. We conclude
the paper by describing further research directions in Section 6.

##  2 Notation, Problem Statement, Fault Constraints

Computation model. A process $p$ contains variables and actions. We denote
variable $var$ of process $p$ as $var.p$. If process $p$ maintains variable
$var$ about process $q$, we denote it as $var.q.p$. A rectangular grid graph
of processes is a Cartesian product of two chain graphs. Such a grid graph is
embedded on a plane as a matrix of rows and columns. A _torus grid graph_ , or
_torus_ for short, is formed by starting with a grid graph and connecting
corresponding leftmost/rightmost and top/bottom processes with edges.

Every process in the torus has a unique identifier. An adjacent process is a
_neighbor_. In a torus, every process has exactly four neighbors. Each process
knows the identifiers of its neighbors: $\mathit{left}$, $right$, $up$ and
$down$. All processes share the orientation. That is, for any two processes
$p$ and $q$ if $up.p=q$ then $down.q=p$ and if $\mathit{left}.p=q$ then
$right.q=p$. We refer to the shared orientation as North, East, West and
South. The torus dimensions are unknown to the processes. That is, they do not
know the height $H$ or the width $W$ of the torus.

The system is completely synchronous. The operation proceeds in rounds. In
every round, each process receives all pending messages sent to it, does local
calculations and sends messages to its neighbors to be received in the next
round. In one round, a process may thus receive multiple messages from the
same or from different neighbors and then send multiple messages to neighbors.
A _computation_ is an infinite sequence of such rounds.

For most of the paper, we assume that size of the message is arbitrary. We
lift this assumption later in the paper.

Process faults. Processes are either correct or faulty. A _correct_ process
follows the algorithm while a _faulty_ process behaves arbitrarily. A faulty
process is always _black_. A correct process is _grey_ if it has at most one
black process in its column, it is _white_ otherwise. The colors of individual
processes are applied to the rows and columns of the torus: grey-white, black-
white, etc. Refer to Figure 1 for torus depiction and fault location.

Broadcast. Consider the problem where each process $p$ is input an arbitrary
initial value $\mathit{initVal}.p$, and $p$ must share this value with every
other process $q$ so that $val.q.p=\mathit{initVal}.p$

###### Definition 1

In the _Weak Synchronous All-to-All Broadcast Problem_ every white process $p$
must stop and for each white process $q$, $p$ must output $val.q.p$ such that
$val.q.p=\mathit{initVal}.q$.

Consensus. In _Binary Consensus_ , the input value $\mathit{initVal}.p$ is
restricted to either $0$ or $1$. Each process must output an irrevocable
decision $v$ with the following three properties:

  * •

_agreement_ – no two correct processes decide differently;

  * •

_validity_ – if there are no faults and for every process $p$,
$\mathit{initVal}.p=v$, then $p$ decides $v$;

  * •

_termination_ – every correct process eventually decides.

###### Definition 2

In _strong consensus_ , the above properties apply to every grey and white
process, i.e. to each correct process. In _weak consensus_ , the properties
apply only to white processes.

Impossibility. Let us outline the area of the possible. Strong consensus
requires $2f+1$ connectivity [8]. The connectivity of torus is $4$, so there
is no algorithm that solves strong consensus on a torus with $f>1$ and
arbitrary fault location.

If faults are restricted to a single column but may occupy the complete
column, consensus is still impossible. This holds true even if the processes
know the torus dimensions. Intuitively, even if correct processes are
connected, they may not be able to distinguish their faulty and non-faulty
neighbors and agree on a value. The below theorem formalizes this observation.

###### Theorem 2.1

There is no algorithm that solves consensus, weak or strong, on a torus with a
faulty column.

###### Proof

Assume the opposite: there is such an algorithm $\mathcal{A}$ hat solves weak
consensus on a torus with a completely faulty column. Since there are no grey
processes, the requirements of weak and strong consensuses are identical.
Consider a torus $T$ of height $1$ and some width $W$. Since the algorithm
$\mathcal{A}$ is a solution the consensus problem on a torus, it should be
able to solve it on $T$. However, this topology is a ring. Its connectivity is
$2$. According to Dolev et al. [8], the consensus is solvable only if the
connectivity of the network is at least $2f+1=3$. That is, contrary to our
initial assumption, $\mathcal{A}$ may not solve consensus on $T$. Hence the
theorem. ∎

##  3 $\mathcal{BAT}$: Byzantine-Tolerant Broadcast to All-to-All on a Torus

Figure 1: Torus orientation, fault location, message types and message
propagation direction in $\mathcal{BAT}$.

1

2

3

Input: $\mathit{initVal}$

4

5Constants:

6 $p$ // process identifier

7 $up,down,\mathit{left},right$ // neighbor identifiers

8 Variables:

9 $northDone$, initially false

10 $column$, initially $\langle\rangle$ // seq. of value-id pairs received
from down neighbor

11 $\mathit{rowLeft},rowRight$, initially $\langle\rangle$ // columns from
resp. left and right neighbors

12 $matrix$, initially $\langle\rangle$ // results matrix to output

13 $eastWestDone$, initially false // one of horizontal neighbors decided

14 Phases:

15 North  __:

16 Initial action:

17 add $\langle\mathit{initVal},p\rangle$ to $column$ // initiate North Phase

18 send $goNorth(\mathit{initVal},p)$ to $up$

19 Receive action:

20

21 receive  _$goNorth(v,id)$ from $down$_ $\longrightarrow$

22 if  _$\emph{not}\ northDone$_ then // has not started East-West Phase

23 if  _ $id\neq p$ _ then

24 add $\langle v,id\rangle$ to $column$

25 send $goNorth(v,id)$ to $up$

26 else // $p$ receives its own value back

27

28 $northDone\leftarrow\textbf{true}$

29 send $goEast(column,\mathit{left},p,right)$ to $right$

30 send $goWest(column,\mathit{left},p,right)$ to $\mathit{left}$

31

32

33

34

35

36 East-West, Receive actions  __:

37 receive  _$goEast(c,l,id,r)$ from $\mathit{left}$_ $\longrightarrow$

38 if  _$id\neq p$_ then

39 add $\langle c,l,id,r\rangle$ to head of $\mathit{rowLeft}$

40 send $goEast(c,l,id,r)$ to $right$

41

42 else

43 $m\leftarrow\textbf{match}(\langle
column,\mathit{left},p,right\rangle+\mathit{rowLeft},$

44 $\langle column,\mathit{left},p,right\rangle+rowRight$)

45 if  _$matrix=\langle\rangle$ _and_ $m\neq\langle\rangle$_ then

46 $matrix\leftarrow m$

47 Output: $matrix$

48 send $goSouth(matrix,p)$ to $down$ // start South Phase

49 send $done$ to $right$ and $\mathit{left}$ // start Decision Phase

50 if  _ $eastWestDone$_ then stop

51

52

53

54 receive  _$goWest(c,l,id,r)$ from $right$_ $\longrightarrow$

// handle similar to $goEast$, add $\langle c,l,id,r\rangle$ to tail of
$rowRight$

55

56

57

58 South, Receive action  __:

59 receive  _$goSouth(m,id)$ from $up$_ $\longrightarrow$

60 if  _$id\neq p$_ then

61 send $goSouth(m,id)$ to $down$

62 if  _ $matrix=\langle\rangle$_ then // South Phase did not reach $p$ yet

63 $matrix\leftarrow m$

64 Output: $matrix$

65 send $done$ to $right$ and $\mathit{left}$ // start Decision Phase

66 if  _ $eastWestDone$_ then stop

67

68

69

70

71

72 Decision, Receive action  __:

73 receive  _$done$ from $direction$_ $\longrightarrow$

74 if  _ $\emph{not}\ eastWestDone$ _ then

75 $eastWestDone\leftarrow\textbf{true}$

76 if  _ $matrix\neq\langle\rangle$_ then stop

77

78

79

Algorithm 1 $\mathcal{BAT}$: Byzantine All-to-All broadcast on a Torus

54 Functions:

55

56match($\mathit{rleft},rright$)  __:

57 $\mathit{cleft}\leftarrow\textbf{consistent}(\mathit{rleft})$

58 $cright\leftarrow\textbf{consistent}(rright)$

59 if  _ $\mathit{cleft}\neq\langle\rangle$ and $cright\neq\langle\rangle$_
then

// $\mathit{cleft}=cright$

_60_ _ _ if  _$|\mathit{cleft}|=|cright|$ and _

_61_ __ $(\forall i:1\leq i<|\mathit{cleft}|:$

_62_ __ $s(i)\equiv\langle lci,lli,lidi,lri\rangle\in\mathit{cleft}$

_63_ __ $s(i)\equiv\langle rci,rli,ridi,rri\rangle\in cright$ :

64  __ $lci=rci$ and $lli=rli$ and $lidi=ridi$ and $lri=rri$) then

// return columns of $\mathit{cleft}$

65 return $\langle\forall i:1<i\leq|\mathit{cleft}|:s(i)\equiv\langle
ci,li,idi,ri\rangle\in\mathit{cleft}:ci\rangle$

66

67 return $\langle\rangle$

68

69

70consistent($clmn$)  __:

71

_72_ _ _if  _$s\equiv\langle\cdot,\cdot,id,\cdot\rangle$ is unique in $clmn$
and _

_73_ __ exists at most one $i$ : $1\leq i<|clmn|:cminus=clmn\setminus s(i)$
and

_74_ __ exists at most one $j$ : $1\leq j\leq|clmn|:$

_75_ __ $cplus=cminus$ insert $\langle\bot,l,id,r\rangle$ at position $j$ in
$cminus$

_76_ __ $\forall i:1\leq i<|cplus|,j=(i+1$ mod $|cplus|):$

_77_ __ $s(i)\equiv\langle ci,li,idi,ri\rangle\in cplus$

_78_ __ $s(j)\equiv\langle cj,lj,idj,rj\rangle\in cplus:$

79  __ $idi=lj$ and $ri=idj$ then

80 return $cplus$

81 else

82 return $\langle\rangle$

83

Algorithm 2 $\mathcal{BAT}$ functions

Overview. We present algorithm, we call $\mathcal{BAT}$, that solves the Weak
Synchronous All-to-All Broadcast Problem. The code for $\mathcal{BAT}$ is
shown in Algorithm 1. The functions used in $\mathcal{BAT}$ are in Algorithm
2. Our notation is loosely based on UNITY programming language [6]. Each
process starts $\mathcal{BAT}$ by sending initial messages in Line 1. The
execution of the rest of the actions are _receive actions_. Such an action is
guarded by the corresponding message receipt. It is executed only when this
message is sent to the receive process. The actions of the algorithm are
grouped into phases: North, East-West, South and Decision. The algorithm is
designed such that white processes synchronize their transitions through these
phases.

Once done, each process sends the collected column data to its $\mathit{left}$
and $right$ neighbors in the East-West Phase. The data is sent in both
directions for verification to counteract the actions of the grey and black
processes in the row. If the data received from both directions match, each
process starts the South Phase where the confirmed data is sent to $down$
neighbor. This data is a matrix of values from all processes in the torus.

Due to the actions of the black processes in the black-white rows, the white
processes may receive corrupted values and fail to complete the South Phase on
time. Once the data starts propagating down the column in the South Phase, the
white processes synchronize, receive correct matrix and output it. After
output, processes enter the Decision Phase. This phase ensures termination of
white processes.

$\mathcal{BAT}$ details. The input for each process in the algorithm is an
arbitrary value $\mathit{initVal}$. Each process $p$ in $\mathcal{BAT}$ has
its own identifier as well as the ids of its up, down, left and right
neighbors.

Each process $p$ maintains the following variables. The process has $column$,
where it gathers pairs $\langle v,id\rangle$ of values and identifiers of its
column in the North Phase. Boolean $doneNorth$ signifies whethe $p$ completed
its North Phase. After it is done, the column values are exchanged across the
row in two directions: left and right in the East-West Phase. These column
values are collected in $\mathit{rowLeft}$ and $rowRight$. Once the values are
matched across the row, they are propagated through the column in the South
Phase and collected in $matrix$. Variable $doneNeighbor$ records the neighbor
identifiers that made the decision to ensure proper termination.

Let us discuss $\mathcal{BAT}$ operation during each phase in detail. Refer to
Figure 1 for the messages that processes send and their propagation
directions. All non-black processes simultaneously initiate the North Phase by
sending their input values to the $up$ neighbors in a $goNorth$ message (see
Line 1). Then, each process $p$ starts collecting the values of its column
processes by receiving $goNorth$ from the $down$ neighbor and propagating it
upward. This continues until $p$ receives its own message back. Once received,
$p$ initiates the East-West Phase (Line 1).

For that, $p$ sends the collected column to its $\mathit{left}$ and $right$
neighbor in messages $\mathit{goWest}$ and $goEast$, respectively. Together
with the column, $p$ sends its own identifier and the identifiers of
$\mathit{left}$ and $right$. This allows the recipients to reconstruct the
sequence of the processes in the row if one of the entries is missing. Flag
$northDone$ ensures that each process sends $\mathit{goWest}$ and $goEast$ at
most once.

Due to the actions of the black processes in its column, even if some grey
process completes its own North Phase, it may do so out of sync with the White
processes. However, the receipt of $goEast$ or $\mathit{goWest}$ from its
neighbor, enables $g$’s corresponding receive action of the East-West phase.
Thus, even though $g$ itself is out of sync, it relays these messages to the
white processes in its row allowing them to proceed with the execution the
East-West Phase.

Figure 2: Matrix accumulation during the East-West Phase of $\mathcal{BAT}$.
The matrix is accumulated at process $d$ as it collects messages
$\mathit{goEast}$ and $\mathit{goWest}$ from its left and right neighbors
respectively. In case (i), the grey process $b$ starts East West Phase
together with white processes. In case (ii), $b$ starts it one round earlier.

The East-West Phase is the most complicated part of the algorithm. Let us
illustrate its operation with an example. Please see Figure 2. Assume a torus
row contains processes $a$, $b$, $c$, $d$ and $e$. All of them are white,
except for $b$ which is grey. Each white process completes the North Phase in
the same round and starts the East-West Phase by sending the collected column
to its right neighbor in a $\mathit{goEast}$ message and to its left neighbor
in $\mathit{goWest}$ message. The grey process may (i) complete its North
Phase together with the white processes or (ii) miss it and either complete it
in a different round or not at all.

Let us first describe case (i). Once a process receives either
$\mathit{goEast}$ or $\mathit{goWest}$, the process records what the message
carries and sends it further in the same direction. Thus, in the first round
of the East-West Phase, $d$ receives messages from $c$ and $e$, in the second
$b$ and $a$ and so on. As $\mathit{goEast}$ message arrives to $d$ from its
left neighbor, $d$ inserts its contents to the head of $\mathit{rowLeft}.d$.

When $\mathit{goWest}$ message arrives to $d$ from the right, $d$ adds its
contents to the tail of $\mathit{rowRight}.d$. Figure 2 shows the contents
$\mathit{rowLeft}.d$ and $\mathit{rowRight}.d$ after three rounds of the East-
West Phase when $d$ received messages from $c$, $b,$ and $a$ from the left and
$e$, $a$, and $b$ from the right. The East-West Phase proceeds until the
process receives a message from itself. In the example in Figure 2, this
happens in two more rounds, after $d$ receives messages from $e$ then $d$ from
the left and $c$ then, possibly, $d$ from the right.

In case (ii), the grey process $b$ completes the North Phase in a round
different from the white processes. In Figure 2, $b$ completes its North Phase
one round earlier. Therefore, this message reaches $d$ together with a message
from $a$ from the right, and together with message from $c$ from the left.

After the process receives the message from itself, either from the right or
the left, it compares the contents of $\mathit{rowLeft}$ and
$\mathit{rowRight}$ by invoking function match() (Line 1). The operation of
this function is somewhat complex since grey process may be out of synchrony
with the rest of its row. If the contents of the two variables do not match,
Function match() returns the data stripped of a mismatched column of the grey
process. The resultant list of columns: $matrix$ is the output of
$\mathcal{BAT}$. This $matrix$ is sent to the $down$ process in a $goSouth$
message. This begins the South Phase (Line 1).

$\mathcal{BAT}$ operation is such that all white processes either initiate the
South Phase in the same round or do not initiate the South Phase at all.
Indeed, due to the actions of the black processes in the black-white rows, the
white processes may not get the matching data and fail to start their own
South Phase. However, the white processes in the grey-white row are guaranteed
to start the South Phase. The South Phase started by these processes, re-
synchronizes white processes and propagates the correct $matrix$ information
in $goSouth$ message. Once a process receives the missing information, it
outputs it (Line 1).

Yet, the processes should not terminate. Indeed, black processes may force a
grey process in the black-grey column to receive a $goSouth$ message at any
time. The grey processes may output the result and consider its mission
accomplished. If a grey process terminates, its halting prevents it from
forwarding messages from white processes in the East-West Phase.

To ensure proper termination, processes execute the Decision Phase. After
outputting the decision matrix, each process sends $done$ message to its
horizontal, i.e. left and right, immediate neighbors. The process stops if it
receives at least one of them (Line 1) and it has the decision matrix. One of
the horizontal neighbors is guaranteed to be white. Thus, if a process obtains
the decision matrix and gets one $done$, then its white neighbors may not be
in the middle of the East-West Phase and this process may safely stop.

Discussion on $\mathcal{BAT}$ functions. Let us now discuss the functions used
in $\mathcal{BAT}$. They are shown in Algorithm 2. Function match() accepts
the input received from the West – $\mathit{left}$, and East – $right$ during
the East-West Phase. The entries of $\mathit{left}$ and $right$ are of the
following format: the column $c$ received by the original sender, its left
neighbor identifier $l$, its own identifier $id$ and its right neighbor id
$r$.

First, $\mathit{left}$ and $right$ are individually checked for internal
consistency in function consistent(). As process $p$ receives data from either
East or West, the left and right neighbors of the subsequent entries should
match. In grey-white row, this is true for all entries except for possibly the
grey process that may start its East-West phase earlier or later than the
white ones. In this case, the grey process entry may arrive out of order. That
is, it may arrive together with another white process entry while its own spot
in the sequence remains empty.

Function consistent() finds a potential single entry that is out of sequence
as well as a single process gap (Line 2). Specifically, consistent() checks
whether there exists at most one element in its parameter $clmn$ such that if
it is removed, $cminus$ is produced, and then another element is possibly
added to $cminus$ producing $cplus$. This added entry contains $\bot$ for the
column values and the $l,id,r$ tuple are such that the left and right
neighbors in the consequent entries in resultant $cplus$ match. In this case
consistent() returns $cplus$. Consider case (ii) shown in Figure 2. Observe
what $\mathit{rowLeft}$ and parameter $\mathit{left}$ contain:

$(1)\langle\cdot,c,d,e\rangle,(2)\langle\cdot,d,e,a\rangle,(3)\langle\cdot,e,a,b\rangle,(4)\bot,(5)\langle\cdot,b,c,d\rangle/\langle\cdot,a,b,c\rangle$

That is, the third round entry is empty and the fifth round entry contains the
data originated by process $c$ and the grey process $b$. Process $b$ sends its
data out of sync with the white processes. Function consistent(), on the basis
of the adjacent entries, reconstructs the fourth entry and drops the extra
fifth entry sent by $b$:

$(1)\langle\cdot,c,d,e\rangle,(2)\langle\cdot,d,e,a\rangle,(3)\langle\cdot,e,a,b\rangle,(4)\langle\bot,a,b,c\rangle,(5)\langle\cdot,b,c,d\rangle$

The corrected entry is stored in $\mathit{cleft}$ by match(). Similar
manipulation by consistent() yields $\mathit{cright}$. Function match()
determines that $\mathit{cleft}$ is equal to $\mathit{cright}$. That is, the
process $p$ gets the same data from both East and West. In this case match()
returns the matrix of columns stored by $\mathit{cleft}$ and
$\mathit{cright}$.

###### Theorem 3.1

Algorithm $\mathcal{BAT}$ solves the _Weak Synchronous All-to-All Broadcast
Problem_ on an unknown torus with Byzantine faults in at most one column with
at least one correct row in at most $2H+2+W$ rounds.

The above theorem states the correctness and efficiency of $\mathcal{BAT}$.
See the Appendix for proof details. Let us discuss the intuition for the
correctness proof. It is relatively straightforward to show that all white
processes complete the first, North, Phase in $H+1$ round and collect the true
contents of their respective columns. By induction on the number of rounds, we
show that each process $p$ collects a column of true data about any process
$q$ in the same row, so long as the processes between $p$ and $q$, in the
direction of information propagation are non-black. Indeed, the non-black
processes do not impede data propagation.

We then separately consider white processes in (a) grey-white rows and (b)
black-white rows. In the East-West Phase, the information propagates in two
directions. We show that during this phase, in a grey-white row, in round
$H+1+W$, the information spreading in two directions matches. The match is up
to the potentially misplaced data from the single grey process. We prove that
this information is true to the original white process data throughout the
matrix. In the black-white row, we show that a white process either completes
the phase in $H+1+W$ round with correct white process data or not at all.

That is, we show that each white process, regardless of the row location, that
complete the East-West Phase, holds correct information about all the white
processes in the matrix. Moreover, each white process in the grey-white row is
guaranteed to complete this phase.

We then consider the South Phase. There, we show that it is completed in an
additional $H$ rounds, and all the white processes are updated with the
correct matrix information before termination. This completes the proof of
Theorem 3.1.

The computation model that we consider $\mathcal{BAT}$ is called LOCAL. It
assumes unlimited size messages. Theorem 3.1 shows that $\mathcal{BAT}$
completes in $O(H+W)$ rounds in LOCAL.

##  4 $\mathcal{CBAT}$: Consensus Using $\mathcal{BAT}$

Description. Observe that $\mathcal{BAT}$ cannot immediately be used to solve
consensus since, after its completion, the outputs of each process differ by
the values of black and grey processes. An individual white process is not
able to determine the color of the senders. Therefore, if the white process
makes the consensus decision on the basis of the single execution of
$\mathcal{BAT}$, the Byzantine senders may cause white processes to disagree
on their outputs.

Instead we use $\mathcal{BAT}$ to select a leader process and agree on the
input value of this leader. A particular difficulty is presented if the
selected leader process is faulty. In this case, the leader may send different
values to different processes. To prevent that, the processes use
$\mathcal{BAT}$ again to exchange received values, determine whether the
leader is consistent in its transmission of its initial value, and, if not,
replace the leader . This determination has to proceed despite the
inconsistent information provided by the faulty processes in this second
exchange.

78

79Input: $v$ boolean // consensus input value

80

81Variables:

82

83$M_{B}\equiv\\{v_{ij}:1\leq i\leq H,1\leq j\leq W\\}$ // matrix of votes
received by each process

84 $M_{C}\equiv\\{M_{ij}:1\leq i\leq H,1\leq j\leq W\\}$ // votes reported as
received by each process

85 $M_{B}$ and $M_{C}$ are initially $\bot$

86 Stages:

87 Broadcast  __:

88 $M_{B}\leftarrow{\cal BAT}(v)$

89

90 Confirm  __:

91 $M_{C}\leftarrow{\cal BAT}(M_{B})$

92

93 Decide  __:

// deterministically select leader

94 $ldr\leftarrow highestID(M_{B})$

95 let $v_{mn}\in M_{B}$ be the input value of $ldr$

96 let $C_{L}\in M_{B}$ // leader’s column in $M_{B}$

97 let $M_{L}=\\{v_{ij}:v_{mn}\in M_{ij}\in M_{C}\\}$ // $v$ sent by $ldr$,
received by every process

98

// two columns with $\bot$ elements or

// two columns with 1/0 elements or

// two columns whose values differ from rest

_99_ _ _ if  _ $\exists$ $q\neq r$ and $\exists$ $e,f$ : _

_100_ __ $v_{qe},v_{rf}\in M_{L}\setminus C_{L}:$

_101_ __ $v_{qe}=v_{rf}=\bot$

_102_ __ or

_103_ __ $\exists$ $w\neq x$, $y\neq z$ and $\exists$ $a,b,c,d$ :

_104_ __ $v_{wa},v_{xb},v_{yc},v_{zd}\in M_{L}\setminus C_{L}$ :

105  __ $v_{wa}=v_{xb}=0$ and $v_{yc}=v_{zd}=1$ then

// select a new leader from a different column

106 $ldr\leftarrow highestID(M_{B}\setminus C_{L})$

// recompute $M_{L}$ and $C_{L}$

107

108 Output: $majority(M_{L}\setminus C_{L})$

109

Algorithm 3 $\mathcal{CBAT}$

Let us describe the algorithm $\mathcal{CBAT}$ that achieves consensus. It is
shown in Algorithm 3. We assume that the number of columns $W\geq 5$. The
algorithm has three sequentially executing stages: Broadcast, Confirm and
Decide. In the first two stages $\mathcal{CBAT}$ executes $\mathcal{BAT}$.

In the Broadcast Stage, the processes exchange the initial input values. In
the Confirm Stage, they transmit the complete matrix they received during
Broadcast. At the end of Confirm, each white process receives $H\times W$
matrices of such values. In the Decide Stage, every white process
independently arrives at the consensus decision.

Let us describe how this decision is computed. Each process $p$
deterministically selects a leader process $ldr$. In the algorithm, it is the
process with the highest identifier. Then, out $H\times W$ matrices that
process $p$ receives in the second stage, $p$ composes the matrix $M_{L}$ of
values sent to all other processes by the leader as these processes report to
$p$. Process $p$ examines these values for inconsistencies. The
inconsistencies are as follows: either the values differ in more than one
column; or the values contain $\bot$, a sign that $\mathcal{BAT}$ detected
faulty values, in more than one column; or the values in at least two columns
differ from the rest. In the latter case, since the total number of columns is
at least $5$, and the leader column is not considered, there are at least two
columns that are different from at least two other columns. In all cases,
these inconsistencies can be determined by all correct processes. Once the
faulty process is detected, the whole column where all the faulty processes
may be located is also discovered. Therefore, $p$ selects a new leader from a
different column. Once each process selects the leader, that leader may still
be faulty and send arbitrary values to other processes. However, these values
are consistently stored in the $M_{L}$ matrix. Each process decides on the
majority of values in this matrix.

Correctness proof. Note that the below discussion relies on correctness of
$\mathcal{BAT}$ proved in Theorem 3.1. Denote $val.a$ the input value
$\mathit{initVal}$ of some fixed process that is reported by process $a$ after
the Broadcast Stage of $\mathcal{CBAT}$. Denote $val.a.b$ the same fixed
process value received by process $b$ from process $a$ after the Confirm
Stage.

###### Lemma 1

Let $v$, $w$, $x$ be white processes executing $\mathcal{CBAT}$ and
distributing the value input to some process $u$. Then, after the Confirm
Stage of $\mathcal{CBAT}$, if $u$ is white then $val.v.x=val.w.x$; and
$val.v.x=val.v.y$ regardless of the color of $u$.

###### Proof

Let us address the first claim of the lemma where $u$ is white. In the
Broadcast Stage, processes are sending their individual input values using
$\mathcal{BAT}$. This includes $initVal$ of process $u$. If the sender $u$ is
white and the recipients $v$ and $w$ are white, then, according to Theorem
3.1, $initVal=val.v=val.w$. During the Confirm Stage, each process, including
$v$ and $w$, sends the complete matrix of received values, including $val.v$
and $val.w$ to all processes, including $x$ using $\mathcal{BAT}$. Since $v$,
$w$, and $x$ are white, according to Theorem 3.1, $val.v=val.v.x$ and
$val.w=val.w.x$. That is, $val.v.x=val.w.x$. This proves the first claim of
the lemma.

Let us consider the second claim that should hold regardless of the color of
$u$. Consider the value $val.v$ stored at $v$ after the Broadcast Stage.
During Confirm, this value is sent to all processes including $x$ and $y$. If
$v,x$ and $y$ are white, according to Theorem 3.1 $val.v=val.v.x=val.v.y$.
Hence the second claim of the lemma also holds.∎

###### Lemma 2

Every white process selects the same leader in the Decide Stage of
$\mathcal{CBAT}$.

###### Proof

For each white process $p$, algorithm $\mathcal{BAT}$ is guaranteed to produce
a matrix that has the same identifiers, configuration and size. This means
that all processes select the same $ldr$ in Line 3 of $\mathcal{CBAT}$.

Let us consider whether each process changes its leader in Line 3. This
happens if process $p$ detects inconsistencies in at least two columns
excluding the leader column. Process $ldr$ is either correct or faulty.

If $ldr$ is correct, then according to the first claim of Lemma 1, the entries
for $ldr$ in $M_{L}$ at $p$ are the same, except for possibly a single column
of faulty processes. This means that if $ldr$ is correct, none of the white
processes changes its leader after initial selection.

If $ldr$ is faulty, then according to the second claim of Lemma 1, the
corresponding entries for $ldr$ in $M_{L}$ for all white processes are equal.
That is, if processes $p$ and $q$ are white, then if entry $m_{ij}\in M_{L}$
in $p$ is equal to $m_{ij}\in M_{L}$ in $q$.

That is, if two non-leader columns are inconsistent, then all white processes
detect that. That is, if one white process changes leader, all white processes
change leaders also. If the processes change leaders, by the operation of the
algorithm, they select the same leader. Hence the lemma.∎

###### Lemma 3

All white processes in $\mathcal{CBAT}$ output the same value. If the selected
leader $ldr$ is correct, they input $\mathit{initVal}.ldr$.

###### Proof

Every white process $p$ outputs the majority of values in $M_{L}\setminus
C_{L}$. Due to Lemma 2, white processes in $\mathcal{CBAT}$ select the same
leader. The leader may be either correct or faulty.

If the leader is correct, then, According to Lemma 1, all white entries in
$M_{L}\setminus C_{L}$ are equal to $\mathit{initVal}.ldr$. Only one column in
$M_{L}\setminus C_{L}$ may be non-white with potentially arbitrary values.
Since we assume that the torus contains at least $5$ columns, the majority of
$M_{L}\setminus C_{L}$ is equal to $\mathit{initVal}.ldr$ and that is what the
white process $p$ outputs.

Let us consider the case of faulty leader. White processes change the leader
only when they detect that the original leader is faulty. They select it from
a different column, therefore, the new leader is correct and the previous
reasoning to the output value applies.

The remaining case is that of a faulty leader and no leader change. According
to the operation of the algorithm, after leader selection at most one column
in $M_{L}\setminus C_{L}$ has inconsistencies. The rest of the entries hold
the same value $x\in{0,1}$. According to the second claim of Lemma 1, the
inconsistencies are in the same column of $M_{L}\setminus C_{L}$ for each
white process. This means that the rest of the values in the matrix are $x$.
Since white processes output the majority value and the number of columns is
at least $5$, all white processes output the same value $x$. ∎

###### Theorem 4.1

$\mathcal{CBAT}$ solves weak consensus on an unknown torus whose width is at
least $5$ with Byzantine faults in at most one column and with at least one
correct row.

###### Proof

We prove the theorem by showing that $\mathcal{CBAT}$ satisfies all three
properties of consensus. The agreement property of the consensus requires that
all white processes output the same value. Lemma 3 indicates that
$\mathcal{CBAT}$ satisfies that property. The validity property states that in
case there are no faults and all processes are input the same value, they
should all output the same value. According to Lemma 3, if the leader is
correct, all correct processes output its input value. Hence, if all processes
are correct, and they are all input the same value, they select one process as
the leader and output this value. Therefore, $\mathcal{CBAT}$ satisfies
validity.

Let us address termination. The consensus requires that each correct process
terminates. $\mathcal{CBAT}$ sequentially executes three stages. The first two
stages are executions of $\mathcal{BAT}$ and the last one is a finite
computation. According to Theorem 3.1, $\mathcal{BAT}$ terminates. Hence, all
three stages of $\mathcal{CBAT}$ terminate and this algorithm satisfies the
termination property of the consensus.∎

Algorithm $\mathcal{CBAT}$ sequentially executes $\mathcal{BAT}$. Each
$\mathcal{BAT}$ completes in $O(H+W)$ rounds in LOCAL. This means that
$\mathcal{CBAT}$ also completes in $O(H+W)$ rounds.

##  5 Extension to Fixed Message Size

As presented, $\mathcal{BAT}$ is assumed to operate with unlimited size
messages. However, it can be modified to operate with fixed size messages as
follows. Observe that the messages get progressively larger as they accumulate
the data about the torus. In the first phase, the North Phase, the messages
are fixed size since each process only transmits its identifier and its input
value. At most one message is sent per link per round. After the completion of
this phase, the white processes discover the height $H$ of the torus. In the
next phase, the East-West Phase, the processes exchange messages whose size is
proportional to the height of the torus. Since white processes know the torus
size, this message may be replaced by $H$ fixed size messages transmitted over
$H$ rounds. Due to the operation of the algorithm, at most $2$ messages are
transmitted per round in the East-West Phase. In the fixed size
implementation, each process waits for $2H$ rounds to receive appropriate
messages. The black processes may deceive the grey process and assume the
larger torus height. This would make the grey process transmit a message
larger than $H$ rounds during the East-West Phase. This, in turn, may prevent
the correct message from being transmitted in the same round. To eliminate
that, the blocks of the two messages need to be transmitted in the round-robin
manner. The South Phase message transmits the complete matrix. So the fixed
size implementation has to wait for $H\cdot W$ rounds to receive a single
matrix.

The fixed message size model is called CONGEST. Let us estimate the running
time of the modified algorithm in CONGEST. The four phases of the original
$\mathcal{BAT}$ take $O(H)$, $O(W)$, $O(H)$ and $O(1)$ rounds, respectively.
The above argument shows that in each respective phase, the modified
$\mathcal{BAT}$ needs to send $O(1)$, $O(H)$, $O(HW)$ and $O(1)$ sequential
fixed-size messages per round. Hence, the number of rounds in fixed-size
message $\mathcal{BAT}$ is dominated by the third phase and is in $O(H^{2}W)$.

Let us now discuss the fixed message size modification of $\mathcal{CBAT}$. In
the first stage, $\mathcal{CBAT}$ uses $\mathcal{BAT}$ to broadcast constant-
size decision values. Hence, its run time is in $O(H^{2}W)$. In the second
stage, each process sends a complete $H\cdot W$ matrix. Hence, the run time of
this stage, and of the whole algorithm is in $O(H^{3}W^{2})$.

##  6 Conclusion and Future Work

Algorithm $\mathcal{BAT}$ assumes that all the faults are in the same column.
In future research, the following conjectures are worth investigating. We
believe that solving the problem with faulty processes spread across multiple
columns, one fault per row, is possible but requires substantial modification
of the algorithm. We suspect that solving the problem for the case of more
than one fault per row is not possible.

To achieve the solution presented in this paper, we assumed shared process
orientation. It is interesting to explore how important this assumption is to
the solution. That is, whether it is possible to solve the problem without
shared orientation.

In this paper we presented a Byzantine-tolerant consensus algorithm that
exploits the knowledge of the network type – torus, to exceed the tolerance
bound presented by the general consensus algorithm. Our study then opens the
following question: what network types have similar properties? To put another
way, what specifically makes torus Byzantine-fault resistant and can this
property be generalized? We believe that this is a fruitful avenue of future
research.

## References

  * [1] I. Abraham, S. Devadas, K. Nayak, and L. Ren.  Brief announcement: Practical synchronous byzantine consensus.  In 31st International Symposium on Distributed Computing (DISC 2017). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2017.
  * [2] E. A. Alchieri, A. N. Bessani, J. d. Silva Fraga, and F. Greve.  Byzantine consensus with unknown participants.  In International Conference On Principles Of Distributed Systems, pages 22–40. Springer, 2008.
  * [3] P. W. Beame and H. L. Bodlaender.  Distributed computing on transitive networks: the torus.  In Annual Symposium on Theoretical Aspects of Computer Science, pages 294–303. Springer, 1989.
  * [4] M. Ben-Or.  Another advantage of free choice (extended abstract) completely asynchronous agreement protocols.  In Proceedings of the second annual ACM symposium on Principles of distributed computing, pages 27–30, 1983.
  * [5] V. Bhandari and N. H. Vaidya.  On reliable broadcast in a radio network.  In Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, pages 138–147, 2005.
  * [6] K. Chandy and J. Misra.  Parallel program design: A foundation.  Addison Wesley Publishing Co., 1988.
  * [7] B. S. Chlebus, D. R. Kowalski, and J. Olkowski.  Fast agreement in networks with byzantine nodes.  In 34th International Symposium on Distributed Computing (DISC 2020), 2020.
  * [8] D. Dolev.  The byzantine generals strike again.  Journal of algorithms, 3(1):14–30, 1982.
  * [9] D. Dolev and H. R. Strong.  Authenticated algorithms for byzantine agreement.  SIAM Journal on Computing, 12(4):656–666, 1983.
  * [10] P. Feldman and S. Micali.  An optimal probabilistic protocol for synchronous byzantine agreement.  SIAM Journal on Computing, 26(4):873–933, 1997.
  * [11] M. J. Fischer, N. A. Lynch, and M. Merritt.  Easy impossibility proofs for distributed consensus problems.  Distributed Computing, 1:26–39, 1986.
  * [12] P. Ganesan, B. Yang, and H. Garcia-Molina.  One torus to rule them all: multi-dimensional queries in p2p systems.  In Proceedings of the 7th International Workshop on the Web and Databases: colocated with ACM SIGMOD/PODS 2004, pages 19–24, 2004.
  * [13] D. D. Kandlur and K. G. Shin.  Reliable broadcast algorithms for harts.  ACM Transactions on Computer Systems (TOCS), 9(4):374–398, 1991\.
  * [14] J. Katz and C.-Y. Koo.  On expected constant-round protocols for byzantine agreement.  Journal of Computer and System Sciences, 75(2):91–112, 2009.
  * [15] C.-Y. Koo.  Broadcast in radio networks tolerating byzantine adversarial behavior.  In Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, pages 275–282, 2004.
  * [16] L. LAMPORT, R. SHOSTAK, and M. PEASE.  The byzantine generals problem.  ACM Transactions on Programming Languages and Systems, 4(3):382–401, 1982.
  * [17] A. Maurer and S. Tixeuil.  Byzantine broadcast with fixed disjoint paths.  Journal of Parallel and Distributed Computing, 74(11):3153–3160, 2014.
  * [18] M. Nesterenko and S. Tixeuil.  Discovering network topology in the presence of byzantine faults.  In International Colloquium on Structural Information and Communication Complexity, pages 212–226. Springer, 2006.
  * [19] J. Oglio, K. Hood, G. Sharma, and M. Nesterenko.  Byzantine geoconsensus.  In International Conference on Networked Systems, pages 19–35. Springer, 2021.
  * [20] M. Pease, R. Shostak, and L. Lamport.  Reaching agreement in the presence of faults.  Journal of the ACM (JACM), 27(2):228–234, 1980.
  * [21] A. Pelc and D. Peleg.  Broadcasting with locally bounded byzantine faults.  Information Processing Letters, 93(3):109–115, 2005.
  * [22] D. Peleg.  Distributed computing: a locality-sensitive approach.  SIAM, 2000.
  * [23] M. O. Rabin.  Randomized byzantine generals.  In 24th annual symposium on foundations of computer science (sfcs 1983), pages 403–409. IEEE, 1983.
  * [24] L. Tseng and N. H. Vaidya.  Fault-tolerant consensus in directed graphs.  In Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, pages 451–460, 2015.
  * [25] K. Winkler, M. Schwarz, and U. Schmid.  Consensus in rooted dynamic networks with short-lived stability.  Distributed Computing, 32(5):443–458, 2019.

## Appendix

$\mathcal{BAT}$ correctness proof. We assume that in each computation, the
rounds are numbered from $1$ onward. We say that a process _completes_ one of
the first three phases (North, East-West, and South) when it starts the next
phase by sending the appropriate messages (see Lines 1, 1, 1). A process
completes the Decision Phase when it executes stop (Line 1).

During the computation, each process $p$ records input values of the processes
in a column. We say that this column is _size and id matching to origin_ if
the column size, order and ids match the actual origin processes. The column
is _value matching to origin_ if it is size, id and matching to origin and the
values of the corresponding entries in the column match the input value of the
origin processes. The column is _white value matching to origin_ if it is
size, order and id matching and the values of all white processes match the
input values of the origin processes. The definitions of a row is stated
similarly.

###### Lemma 4

In $\mathcal{BAT}$, every white process $p$ completes the North Phase in round
$H+1$. After completion, $column.p$ is size, id and value matching to origin.

Observe that, depending on the messages of the faulty neighbors, a grey
process may complete the North Phase in the same round with the white process,
earlier, later or never. It, however, completes it at most once.

Let $eastRange(p,i)$ be the sequence of $i$ processes in $p$’s row to the
East, i.e. right, of $p$. Process $p$ itself is not included. The tail of
$eastRange$ is the process furthest away from $p$ going East. Let
$westRange(p,i)$ be the similarly defined sequence to the West of $p$.

Denote $\mathit{rowLeft}(i)$ the entry in _rowLeft_ that was added to it in
round $i$. Similarly, $rowRight(i)$ is the entry added to _rowRight_ at round
$i$. Note that since grey or black process may send horizontal messages out of
synch, other processes may send multiple messages in a single round. Thus,
multiple entries may potentially be added to _rowLeft_ in the same round.
Also, if a process does not send a message in a particular round, no entry is
added then.

###### Lemma 5

Let $p$ be a non-black process that completed the North Phase in round $rnd$.
Consider $eastRange(p,i)$ in round $rnd+i$ where $0\leq i<W$. If
$eastRange(p,i)$ is non-black then (a) for every process $q\in eastRange(p,i)$
it follows that $\langle
column.p,\mathit{left}.p,p,right.p\rangle=\mathit{rowLeft}(i).q$ and (b)
message
$\mathit{goEast}(\langle column.p,\mathit{left}.p,p,right.p\rangle)$ is in the
outgoing right channel of the tail process of $eastRange(p,i)$.

Similarly, if all processes in $westRange(p,i)$ are non-black, then for every
process $q\in westRange(p,i)$, $\langle
column.p,\mathit{left}.p,p,right.p\rangle=\mathit{rowRight}(i).q$ and the
message $goWest(\langle column.p,\mathit{left}.p,p,right.p\rangle)$ is in the
outgoing left channel of the tail process of $westRange(p,i)$.

###### Proof

Let us examine the process actions at the completion of the North Phase. When
a process $p$ receives a $goNorth$ message with its own identifier, $p$ sends
a message $goEast$ carrying $\langle
column.p,\mathit{left}.p,p,right.p\rangle$. If $\langle
column.p,\mathit{left}.p,p,right.p\rangle$ is present in $\mathit{rowLeft}.p$,
then $\mathit{rowLeft}$ is never updated. Each non-black process $q$ forwards
$goEast$ sent by $p$, adding the information it carries to
$\mathit{rowLeft}.q$. Note that, by the condition of the lemma, all processes
in $eastRange$ are non-black. The rest of the lemma for $eastRange$ is proven
by induction on $i$. The proof for $westRange$ is similar.∎

A matrix of values, maintained by a process, is _size and id matching to
origin_ if the identifiers, configuration and size of the processes in the
matrix, regardless of process color, matches the torus. A matrix is also
_white-value matching_ if it is size and id matching and the values of all
white processes in the matrix match those of the corresponding input values of
the origins.

Let us discuss the relationship between matching to origin of the matrix and
its columns. If all the columns of a matrix match to origin, the matrix itself
may not necessary do: the order of the columns may be altered or some of the
columns may be missing. Hence the following observation. If every white column
in the matrix is size, id and value matching to origin and at least one column
is size, id and white-value matching to origin, then the matrix itself is
size, id and white-value matching to origin.

###### Lemma 6

Every white process $p$ in a grey-white row completes the East-West Phase in
round $H+1+W$. After completion, for every white process $p$, $matrix.p$ is
size, id and white-value matching to origin.

###### Proof

We prove the lemma by showing that every white column in $matrix.p$ is value
matching to origin and the grey-white row itself is white-value matching to
origin.

According to the operation of the algorithm, each non-black process originates
at most one $goEast$. Other processes always forward it further and it is
never forwarded by the originator. That is, in a grey-white row for each
process $p$, the number of entries in $\mathit{eastRange}$ is at most one for
each process. In the rest of the proof we discuss the order of these entries.

Let us consider a white process $p$ in a grey-white row in round
$rnd=H+1+W-1$. Let $q$ be another white process that shares a row with $p$. In
the round $rnd$, $p\in eastRange(q,W-1)$. Since $p$’s row is grey-white,
$eastRange(q,W-1)$ is grey-white also. Then, according to Lemma 5, $\langle
column.q,\mathit{left}.q,q,right.q\rangle$ is in $\mathit{rowLeft}.p$.
According to Lemma 4, the $column.q$ is size, id and value matching to origin.
Put another way, the columns in $\mathit{rowLeft}.p$ for white processes in
the grey-white row are value matching to origin. Similar discussion applies to
$rowRight.p$.

Let us now discuss the formation of the resultant grey-white row. Since $p$’s
row is grey-white, $eastRange(p,W-1)$ and $westRange(p,W-1)$ are grey-white.
According to Lemma 5, there is a $goEast(\langle
column.p,\mathit{left}.p,p,right.p\rangle)$ message in the outgoing right
channel of the tail process of $eastRange(p,W-1)$. However, the width of the
torus is $W$. That is, the tail process of $eastRange(p,W-1)$ is the West
(left) neighbor of $p$ itself. This means that this message is in the incoming
left channel of $p$. Similarly, there is a _goWest_ message carrying the same
information in the incoming right channel of $p$.

Let us consider the actions of $p$ when it receives either such $goEast$ or
$\mathit{goWest}$. Since the original sender of this message is $p$ itself,
$p$ invokes match() with $\mathit{rleft}=\langle
column.p,\mathit{left}.p,p,right.p\rangle+\mathit{rowLeft}.p$ and
$rright=\langle
column.p,\mathit{left}.p,p,right.p\rangle+\mathit{rowRight}.p$. Function
match(), in turn, invokes consistent() separately on $\mathit{rleft}$ and
$rright$.

Function consistent() processes input and then returns $\mathit{cleft}$ and
$cright$ respectively. Its operation depends on when the grey process, let us
denote it $g$, completes the North Phase. There are two cases to consider: (1)
$g$ completes the North Phase in round $H+1$, (2) $g$ does not complete the
North Phase in this round i.e. it either completes it in a different round or
not at all. Let us address the two cases individually.

  1. 1.

According to Lemma 4, all white processes in $p$’s row complete their North
face in round $H+1$. That is, all processes, including $g$ complete it in this
round.

Let us consider any two neighbor processes $u$ and $v$ that belong to this
row. Suppose $v$ is the right neighbor of $u$. That is: $right.u=v$. This
means that $\mathit{left}.v=u$. Let $rd(p,u)=i$. In this case $rd(p,v)=i+1$.

According to Lemma 5, $\langle
column.u,\mathit{left}.u,u,right.u\rangle=\mathit{rowLeft}(i).p$ and $\langle
column.v,\mathit{left}.v,v,right.v\rangle=\mathit{rowLeft}(i+1).p$. That is,
the entries for $u$ and $v$ are consequent in $\mathit{rowLeft}$. This means
that for every $i$ : $s(i)\equiv\langle
ci,li,idi,ri\rangle\in\mathit{rowLeft}$ and $s(j)\equiv\langle
cj,lj,idj,rj\rangle\in\mathit{rowLeft}$ it follows that $idi=lj$ and $ri=idj$.
To put another way, the left and right entries of $\mathit{rowLeft}$ match and
consistent() returns the rows of these entries for further analysis by
match(). Similar discussion applies to $rowRight$.

  2. 2.

Let us assume that the grey process $g$ completes its North Phase in a round
$H+1+j$ other than $H+1$. Note that, depending on whether $g$ completes it
earlier or later, $j$ may be either positive or negative. The argument for $g$
not completing its North Phase at all is similar. Let $rd(p,i)=i\neq j$.

According to Lemma 5, $s(j)\equiv\langle
c_{j},l_{j},id_{j},r_{j}\rangle\in\mathit{rowLeft}(j).p$.

Each process, including $g$, completes the North Phase at most once. According
to Lemma 5, all other processes complete this phase in round $H+1$. This means
that $\mathit{rowLeft}(i).p$ is empty and it is a single empty spot in
$\mathit{rowLeft}$. In this case, consistent() removes $s(j)\equiv\langle
c_{j},l_{j},id_{j},r_{j}\rangle$ and inserts
$s(i)\equiv\langle\bot,l_{i}=id_{i-1},id_{i}=l_{i-1}=r_{i+1},r_{i}=id_{i+1}\rangle$.
That is, consistent() inserts the entry with an empty column in the same
position in both $\mathit{cleft}$ and $cright$.

To summarize, in both cases, consistent() returns entries of $\mathit{goEast}$
and $\mathit{goWest}$, except for possibly, the second case where the out-of-
place entry of $g$ is replaced by a properly placed entry. The entries are
stored in $\mathit{cleft}$ and $cright$.

Let us discuss the order of these entries. Again, according to Lemma 5, the
entries are in the order of the processes in this grey-white row. In round
$H+1+W-1$, every white process is entered in $\mathit{cleft}$. That is,
$\mathit{cleft}$ is size and id matching to origin.

Let us discuss further operation of match(). It compares corresponding entries
$\mathit{cleft}$ and $cright$ for equality. However, according to Lemma 5,
these entries match for white processes and, by operation of consistent for
the $g$, they also match for the grey process.

In this case match() returns the columns of $\mathit{cleft}$. The columns are
assigned to $matrix.p$ which ends the East-West phase. This means that this
matrix is white-value matching to origin.∎

###### Lemma 7

A white process $p$ in a black-white row completes the East-West Phase only in
the round $H+1+W$. If $p$ completes this phase, $matrix.p$ is size, id and
white-value matching to origin.

###### Proof

Assume $p$ completes the East-West Phase. Let the topology of the row of $p$
be as follows: $\cdots u,x,v\cdots$ where $x$ the black process and $u$ and
$v$ are its respective left and right neighbors.

Let us consider the subsequence $\mathit{cleft}.p$ selected by consistent()
for $\mathit{left}/goEast$. This subsequence starts with $p$ and contains all
the white processes in the longest white $westRange$ of $p$. This means that
it contains $v$. Similarly, the subsequence $cright.p$ selected by
consistent() for $right/goWest$ also contains $p$ and the longest white
$eastRange$ of $p$, meaning that it contains $u^{\prime}s$.

According to Lemma 5, all the white processes entries in $eastRange$ of
$\mathit{cleft}.p$ are matching to origin and all the white process entries in
$westRange$ of $cright.p$ are also matching to origin.

Entry for $v$ contains $x$ as its right neighbor. Since consistent() selected
$\mathit{cleft}.p$, it contains the entry for $x$ where $v$ is its left
neighbor. $\mathit{left}.p$ may contain only a single entry for a process
identifier. This means that there is only one entry for $x$ in
$\mathit{cleft}.p$. Similarly, there is only one entry for $x$ in
$\mathit{cright}.p$.

Function $match()$ checks if $\mathit{cleft}.p$ is identical to $cright.p$.
Since the two are identical, the processes of $eastRange$ of
$\mathit{cleft}.p$ have the corresponding entries in $cright$ and match them.
The last entry in $eastRange$ of $\mathit{cleft}.p$ is $v$ whose left neighbor
is $x$. Since $\mathit{cleft}.p$ matched $cright.p$ the entry for $x$ must
exist in $cright.p$ and match the entry in $\mathit{cleft}.p$. There is only
one entry per identifier. Therefore, this entry in $cright.p$ should have the
right neighbor of $u$. This and remaining entries in $cright.p$ belong to
$westRange$ of $p$. They must match the corresponding entries in
$\mathit{cleft}.p$. However, this means that white process entries in
$cright.p$ and $\mathit{cleft}.p$ match origin and the entry of $x$ matches
the identifier of $origin$. ∎

###### Lemma 8

Every white process $p$ completes the South Phase on or before round
$H+1+W+H$. After completion, $matrix.p$ is size, id and white-value matching
to origin.

###### Proof

Each process $p$ maintains the input values in $matrix.p$. The matrix is
initially empty and the values are recorded there in one of two ways: (a) by
storing the values returned by match() at the completion of the East-West
Phase or (b) by receiving the matrix in $gonorth$ message during the South
Phase.

Let us discuss case (a). Due to Lemmas 6 and 7, each white process $p$
completes the East-West Phase in the same round $H+1+W$ and with $matrix.p$
that is size, id, and white-value matching origin. That is, the matrices
recorded after the completion of the East-West Phase satisfy the lemma.

Let us consider case (b). After the completion of the East-West Phase, each
process $p$ sends the contents of $matrix.p$ down in the $goSouth$ message. In
the torus, the columns are either black-grey or white. After round $H+1+W$,
the only matrices that circulate in white columns in $goSouth$ messages are
size, id, and white-value matching to origin. Moreover, according to Lemma 6,
such message is guaranteed to be sent by every white process in the grey-white
row. This means that every process in the white column receives such message
in $H$ rounds after it was sent by a process in the grey-white row. That is,
every process receives it in $H+1+W+H$ rounds.

Once a process $p$ receives a $goSouth$ message, records the value in the
$matrix.p$, forwards the message further down, starts the Decision Phase by
sending $done$ messages to left and right neighbors and then, possibly, halts.
Thus, the only reason for a process in a white column not to receive the
matrix is if it halts. However, by the design of the algorithm, a process may
not halt only when the $matrix.p$ is not empty, that is, the process receives
the $goSouth$ message. That is, in case (b) each white process eventually
stores a matrix of size, id and white-value matching to origin.∎

###### Lemma 9

Every white process completes the Decision Phase on or before round
$H+1+W+H+1$.

###### Proof

After the completion of the South Phase, each white process ends a $goSouth$
message South and $done$ messages to East and West. The process completes the
Decision Phase when it receives a $goSouth$ phase from its North neighbor and
at least one $done$ message from its horizontal neighbors.

A white process has a white North neighbor and at least one white horizontal
neighbor. According to Lemma 8, every white process completes the South Phase.
This means that each white process receives a $goSouth$ message and at least
one $done$ message. This allows each white process to complete the Decision
Phase and halt. According to Lemma 8, it takes $H+1+W+H$ rounds to complete
the South Phase. ∎

To recap, Lemma 8 states that the output matrix for each white process $p$ is
size, id and white-value matching to origin. That is, for every pair of white
processes $p$ and $q$, $val.q.p=initVal.q$. Lemma 9 that every white process
eventually halts. These are the properties of the _Weak Synchronous All-to-All
Broadcast Problem_. Moreover, according to Lemma 9, this is accomplished in at
most $2H+2+W$ rounds. We summarize the results in Theorem 3.1.