Mohamed Alji

Mounir Ait Kerroum
email: maitkerroum@gmail.com

An Improved Region Growing based on Bilateral Symmetry Information for MRI Brain Tumors Segmentation

Keywords: Segmentation, Region growing, MRI, Brain tumors, Symmetry analysis, Three dimensional reconstruction

Both halves of the brain exhibit a high level of bilateral symmetry. A tumor presence destroys this symmetrical property of a healthy brain. Based on this anatomical knowledge and knowing that human intervention in any interactive segmentation method is subject to inter-user and even intrauser differences, we propose an improvement of a seeded region growing method for segmenting tumors in a magnetic resonance imaging scans by transforming it from being interactive to fully automatic. Firstly, we establish a map representing the probabilities of asymmetry occurrences. Secondly, we extract information from the asymmetry map, allowing automatic seeds selection to initialize the seeded region growing method in the region of interest. Thirdly, from the selected seeds we define a suitable homogeneity criteria representing the tumor region. Finally, we apply the modified region growing with the chosen seeds and the predefined criteria on the volumetric magnetic resonance scans in order to extract a pathology mask and reconstruct a 3D representation of the tumor. The segmentation results and the 3D reconstruction are promising.

I. INTRODUCTION

A brain tumor segmentation is an image analysis method that aims to isolate the tumoral cells from the healthy brain in an established scan, which can be an in-vivo magnetic resonance imaging (MRI) scan. Detection of a tumor presence, localization, diagnosis, staging, and monitoring treatment responses are crucial procedures in oncology as stated by N. Gordillo [START_REF] Gordillo | State of the art survey on MRI brain tumor segmentation[END_REF]. An accurate delineation of the tumor structure in medical imaging, such as MRI, helps a neurologist to figure out the right treatment to establish for the patient. In the particular case of brain tumors, segmentation consists of separating the tissues of the tumor from the tissue of the healthy brain. Manually, the neuroradiologists perform an empirical delineation or segmentation of the brain tumor. This task is a time consuming, and operator-dependent. Fortunately, specialized software and hardware technology allow as developing computer-aided diagnosis (CAD) systems. CAD systems can assist in routine clinical practice [START_REF] Liu | Symmetry and asymmetry analysis and its implications to computer-aided diagnosis: A review of the literature[END_REF], but an accurate segmentation of the brain tumor is still a challenging problem because of the complex shape of the tumor, location and the overlap between the tumoral and the healthy tissue of the brain. Even the manual segmentations show inter-rater variations [START_REF] Menze | The Multimodal Brain Tumor Image Segmentation Benchmark (BRATS)[END_REF]. There is plenty of brain tumor segmentation methods. The reader can refer to the state-of-the-art survey on MRI brain tumor segmentation [START_REF] Gordillo | State of the art survey on MRI brain tumor segmentation[END_REF] for further reading. According to the degree of required human interaction, a brain tumor segmentation method can be classified into three categories: manual, semiautomatic, and fully automatic segmentation. The primary task is to establish the most accurate segmentation method and require less human intervention. The seeded region growing [START_REF] Adams | Seeded region growing[END_REF] is a semi-automatic segmentation method that needs the user to localize the initial seeds from which the algorithm will start and grow to extract meaningful regions of the patient brain.

Since it has been proven to be difficult to perform a fully automated segmentation on brain tumors based solely on the information contained in the image, integrating anatomical knowledge will intuitively increase the utility of the computeraided diagnosis systems in helping clinicians to make the right decision [START_REF] Liu | Symmetry and asymmetry analysis and its implications to computer-aided diagnosis: A review of the literature[END_REF]. In our case, the anatomical knowledge is the high level of symmetry between the left and the right halves of the healthy brain. A pathology presence could break this relative symmetry. Such fact can somehow be incorporated into the segmentation method to improve its results. The aim of this article is to transform the region growing method into an automatic segmentation method by exploiting the relative symmetry between the two halves of a healthy brain.

The paper is organized as follows. Section II gives a description of the classical method. Then, we elaborate on the proposed method. Section III discusses the results of our method. Section IV concludes the paper. Fig. 2. Human brain exhibits a high level of symmetry between its two halves (Credit to EUSKALANATO changes were made to the original photo).

II. METHOD DESCRIPTION

Region growing is one of the simplest region-based segmentation methods that mean to segment an image into regions [START_REF] Gonzalez | Digital Image Processing Using Matlab[END_REF]. It allows extracting a group of connected pixels that have a similar criterion from a starting sub-regions or seeds [START_REF] Gordillo | State of the art survey on MRI brain tumor segmentation[END_REF]. As its name implies, the algorithm of the region growing starts at least with one seed that belongs to the element of interest and then "grows". Neighbors of the concerned seed are checked on a predefined criterion of growth. If they satisfy the homogeneity or the similarity criterion, then the pixels are added to the active output region. The algorithm iterates until no more pixels can be added to the region. The similarity criterion can be a range of pixel intensities or any feature from the image such as the average intensity of the original seeds or color. The advantage of the region growing segmentation method is its capability to segment correctly the objects of an image that have similar properties and generate connected regions.

In the region growing segmentation process, there are two factors to be taken into consideration [START_REF] Cui | An Improved Region Growing Algorithm for Image Segmentation[END_REF]. The first one is how to choose the initial seeds in order to get a good segmentation result in dependence on the type of the segmentation problem, and by that avoid an interactive method that is subject to interuser differences in the results. The best solution is to find the initial seeds by an automatic selection process. The second factor is how to choose a suitable similarity criterion to well discriminant the pixels that represent meaningful regions.

The method has some drawbacks. It is sensitive to noisy data and depends on the initial seeds selection. Suppose the case of the original seeds corresponding to outliers. That means Fig. 3. The flow chart of the proposed method the extracted feature from the selected pixels to establish the similarity criterion is not representative of the desired segment being extracted.

It also suffers from the partial volume effect that blurs the intensity distinction between two, or more, tissues because the voxel/pixel may represent more than one kind of tissue types. In the article [START_REF] Sato | A gradient magnitude based region growing algorithm for accurate segmentation[END_REF], M. Sato proposes to incorporate the gradient magnitude to the region growing algorithm to enhance the boundary definition. By applying its simple algorithm, the problem of the partial volume effect on the boundary was solved in the case of colon segmentation.

Morphologically speaking, a normal human head exhibits a high level of bilateral symmetry [START_REF] Liu | Symmetry and asymmetry analysis and its implications to computer-aided diagnosis: A review of the literature[END_REF]. Corresponding regions of two hemispheres have approximately identical anatomical properties. A pathology presence breaks this symmetry. The idea is to exploit this asymmetry to detect, localize and segment a tumor in the brain.

Our segmentation method is represented in the flow chart 3. It consists of five steps.A parallelogram represents each step. In the first step, the preprocessing is skull stripping only. In the second phase, the proposed method computes an asymmetry map based on the detection of the symmetry axis or symmetry plane in case of volumetric approach. The detection of symmetry axis is a challenging task due to the relative symmetry of the brain and the possible misalignment of the patient's head in the MRI scanner. The third step consists of finding the initial seeds based on the asymmetry map. How is that? The asymmetry map shows pixels that are very likely to be asymmetric in both halves of the brain. A presence of connected pixels of this king means a possible presence of the tumor. A threshold of the asymmetry map can be established to allow the extraction of only the highly probable pixels that can be used as initial seeds for the proposed method. The fourth step is to define a suitable homogeneity criteria representing the tumor properties. Based on the sub-region of the initial seeds, the homogeneity criterion can simply be a range of intensities or a more sophisticated set of criteria that take into consideration a possible shape and size of the tumor. The fifth step is to apply the classical region growing method using the previous initial seeds and the defined homogeneity criteria to segment the tumor. This step produces a pathology mask from that a 3D tumor reconstruction can be done.

III. RESULT AND DISCUSSION

To measure the segmentation results of the proposed method, we perform several tests on a well-known dataset of a magnetic resonance scans of low-and high-grade glioma patients with ground truth from manual delineations by several human experts and realistically synthetic brain tumor dataset with its corresponding known golden truth [START_REF] Menze | Proceedings of the MICCAI Challenge on Multimodal Brain Tumor Image Segmentation ( BRATS )[END_REF].

The quantitative comparison between the binary pathology mask and the ground truth shows a promising result and can be measured using the Dice Similarity Coefficient (Dice), Accuracy Coefficient (AC), Sensitivity and Specificity.

The previous similarity coefficients measure pixel-wise (pixel by pixel) the spatial overlap between the segmented regions and the ground truth. Dice [START_REF] Zou | Statistical Validation of Image Segmentation Quality Based on a Spatial Overlap Index[END_REF], for example, varies from 0 to 1. One means a total overlap of the segmented (2)

Sensitivity = T P T P + F N (3)
Specif icity = T N T N + F P

where : TP True Positive, Pixels correctly segmented as a tumor in ground truth and by our method. FP True Positive, Pixels not segmented as a tumor in ground truth, but considered as a tumor by our method. TN True Negative, Pixels not classified as a tumor in ground truth and by our method. FN False Negative, Pixels classified as a tumor in ground truth, but not designated as a tumor by the proposed method. The score of Dice can be evaluated up to 0,89 for some slices corresponding to the segmentation of a simulated tumor Fig. 6. Comparison of a binary segmentation (Seg) with the reference image (Ref) or simply the truth, with the true positive pixels (TP), the true negatives (TN), the false positives (FP) and the false negatives (FN). The figure is adapted from [START_REF] Anbeek | Automatic segmentation of different-sized white matter lesions by voxel probability estimation[END_REF] of high-glioma. As shown in figure 7, the 3D reconstruction of the tumor reveals promising results. We presented a new fully automatic approach for a regionoriented segmentation method of MRI scans by combining the asymmetry map computation and a classical segmentation method. We intend to advance our method and establish full results using all the previous metrics on the datasets of BRATS 2012 http://www2.imm.dtu.dk/projects/BRATS2012/. We will also evaluate the performance of the segmentation using another class of scores that consider the distances between segmentation boundaries. The results are in progress.

Further method improvements are remaining such as: combining the segmentation results of multiple imaging modalities, finding the right set of criteria that may characterize the tumor region, etc.

Fig. 1 .

 1 Fig. 1. Example of a tumor (blue curve) and edema (red curve) segmentation results for T1C, T2, FLAIR and T1 MRI images respectively (the figure is adapted from the article [4]).

Fig. 4 .

 4 Fig. 4. a patient brain with a simulated high-glioma tumor (yellow).

Fig. 5 .

 5 Fig. 5. A computed asymmetry map based on the possible symmetry between both halves of the brain.

Fig. 7 .

 7 Fig. 7. Segmentation result of a simulated pathology reconstructed in 3D

ACKNOWLEDGMENT

I would like to thank M. Youssef FAKHRI and my colleagues of LaRIT Laboratory.


Shishun Tian
email: shishun.tian@insa-rennes.fr

Lu Zhang

Luce Morin

Olivier Déforges

Performance comparison of objective metrics on free-viewpoint videos with different depth coding algorithms

Keywords: free-viewpoint video, DIBR, distortion, depth coding, quality assessment

The popularity of 3D applications has brought out new challenges in the creation, compression and transmission of 3D content due to the large size of 3D data and the limitation of transmission. Several compression standards, such as, Multiview-HEVC and 3D-HEVC have been proposed to compress the 3D content aiding by view synthesis technologies, among which the most commonly used algorithm is Depth-Image-Based-Rendering (DIBR), but the quality assessment of DIBR-synthesized view is very challenging owing to its new types of distortions induced by inaccurate depth map which the conventional 2D quality metrics may fail to assess. In this paper, we test the performance of existing objective metrics on free-viewpoint video with different depth coding algorithms. Results show that all the existing objective metrics perform not well on this database including the full-reference and the no-reference. There is certainly room for further improvement for the algorithms.

INTRODUCTION

Providing more immersive perception of a visual scene, 3D video applications , such as 3D-TV 1 and Freeviewpoint TV (FTV), [START_REF] Tanimoto | Free-viewpoint tv[END_REF] have gained great public interest and curiosity in recent years. In most 3D applications, 3D content is obtained by using multiple cameras to record the same scene at slightly different viewpoints.

The Multiview-Video-Plus-Depth (MVD) [START_REF] Merkle | Multi-view video plus depth representation and coding[END_REF] format is one of the most 3D representations, it consists of multiple texture views and their associated depth maps from different viewpoints. Furthermore, this 3D representation could be exploited by generating virtual viewpoints, thus the virtual view from a viewpoint which has not been recorded can be rendered by using Depth-Image-Based-Rendering (DIBR). MVD and DIBR can be used for many 3D applications, such as, Free-viewpoint TV (FTV) which is able to allow the users to view a 3D scene by freely changing their viewpoints. Efficient compression methods are also needed for 3D applications. Extensions of High-Efficiency-Video-Coding (HEVC): Multiview-HEVC (MV-HEVC) and 3D-HEVC have been developed by the Joint Collaborative Team on 3D Video Coding Extension Development (JCT-3V). 3D-HEVC exploits additional coding tools and achieves the best compression performance for MVD data. [START_REF] Mller | 3d high-efficiency video coding for multi-view video and depth data[END_REF] Benefiting from efficient coding methods and DIBR, only limited number of original views need to be coded and transferred, the additional virtual views on the receiver side can be synthesized from the decoded views. However, this process will lead to some new kinds of distortions, which are very different from the distortions induced by 2D image compression. Since most video coding standards rely on Discrete Cosine Transform, which leads to specific distortions, 5 these distortions are often scattered over the whole image. Whereas the Depth-Image-Based-Rendering (DIBR) synthesized artifacts are mainly caused by depth compression and view synthesis, those usually happen in the dis-occluded areas. Especially, the inaccurate depth map may results in the displacement of the pixels in the synthesized virtual view, which causes geometric distortions. Therefore, the conventional 2D quality metrics, which focus on the common compression artifacts, may not be capable to evaluate DIBR view synthesis artifacts. Especially for free view-point videos, this problem becomes more challenging due to the lack of real reference.

The distortion in DIBR-synthesized views mainly originate from the pristine texture/depth image and the DIBR process as well. Several effort have been made to assess the quality of DIBR-synthesized views, [START_REF] Farid | Perceptual quality assessment of 3d synthesized images[END_REF][START_REF] Farid | Evaluating virtual image quality using the side-views information fusion and depth maps[END_REF][START_REF] Tian | NIQSV: A no reference image quality assessment metric for 3D synthesized views[END_REF][START_REF] Tian | NIQSV+: A No-Reference Synthesized View Quality Assessment Metric[END_REF][START_REF] Tian | A full-reference image quality assessment metric for 3d synthesized views[END_REF] but the influence of imperfect compressed depth map has been less discussed. Since the depth map is used to warp the pixel from the original viewpoint to the target viewpoint, the imperfect depth map may cause various structural geometric distortions in the synthesized views. In this paper, we specially focus on the impact of different compressed depth map on the synthesized view. The the performance of state-of-the-art objective quality metrics has been tested on free-viewpoint videos with different depth coding methods.

TESTED QUALITY METRICS

In this paper, we use 5 2D objective quality assessment metrics and 8 DIBR dedicated quality assessment metrics, including full-reference (FR), reduced-reference (RR) and no-reference (NR). Within which, there are two special metrics, they use the pristine image at the original viewpoint, from which the synthesized image at a new viewpoint is generated, as the reference image. They do not need the original image at the new viewpoint. That is not classical FR metric, so we call is side view based FR metric in this paper.

Tested 2D quality metrics:

• PSNR: the commonly used pixel-based Peak Signal-to-Noise-Ratio;

• SSIM: Structural SIMilarity, a widely used full-reference (FR) objective image quality assessment (IQA) metric proposed by Wang et al. 11

• VIF: Visual Information Fidelity, the objective FR IQA metric proposed by Sheikh et al. [START_REF] Sheikh | Image information and visual quality[END_REF] The image quality is calculated by quantifying the information loss between the reference and the distorted image;

• VIIDEO: Video Intrinsic Integrity and Distortion Evaluation Oracle, a completely blind objective video quality assessment (VQA) metric based on natural video statistics proposed by Mittal et al. [START_REF] Mittal | A completely blind video integrity oracle[END_REF] The visual video quality is obtained by measuring their deviations from these regularities.

• RRED: reduce-reference entropy-difference, a reduced-reference (RR) VQA metric proposed by Soundararajan et al. [START_REF] Soundararajan | Rred indices: Reduced reference entropic differencing for image quality assessment[END_REF] They assume that the wavelet coefficients of natural image follow Gaussian scale mixture (GSM) distribution. The quality is obtained as the distance between the GSM distribution of the reference image and the distorted image.

Tested DIBR dedicated metrics:

• MW-PSNR: Multi-scale Wavelet PSNR, the MW-PSNR was the first FR metric applied on free viewpoint videos porposed by Sandić-Stanković. [START_REF] Sandi-Stankovi | Free viewpoint video quality assessment based on morphological multiscale metrics[END_REF][START_REF] Sandić-Stanković | DIBR synthesized image quality assessment based on morphological wavelets[END_REF] It firstly decomposed the two views (reference and synthesized) using separable morphological wavelet transformation, then calculated the weighted sum of the mean squared errors (MSE) of all sub-bands at all the corresponding scales of the two views.

• MP-PSNR: Morphological pyramid PSNR, proposed by the same author 17 as MW-PSNR, MP-PSNR uses multi-scale decomposition as well. MP-PSNR uses morphological filters instead of morphological wavelet for decomposition. The geometric distortions are maintained by comparing the difference between the reference and synthesized image across different resolution levels.

• MW-PSNRr, MP-PSNRr: the reduced version proposed by the same authors, [START_REF] Sandić-Stanković | Dibr-synthesized image quality assessment based on morphological multi-scale approach[END_REF] which only use the detail images at higher decomposition levels.

• VQA-SIAT: an FR Video Quality Assessment metric proposed by Liu et al. [START_REF] Liu | Subjective and objective video quality assessment of 3d synthesized views with texture/depth compression distortion[END_REF] The quality score is obtained by measuring the temporal flickering and the distortion of spatio-temporal activity.

• NIQSV: No-reference Image Quality assessment of Synthesized-Views, a NR IQA metric proposed by Tian et al. [START_REF] Tian | NIQSV: A no reference image quality assessment metric for 3D synthesized views[END_REF] The distortion at each color component is captured by a pair of morphological erosion and dilation operations, then these distortions are integrated and weighted by an edge image since the DIBR synthesized artifacts mainly happen in around the object edges.

Tested DIBR dedicated side view based FR metrics:

• LOGS: the FR objective IQA metric proposed by Li et al. [START_REF] Li | Quality assessment of dibr-synthesized images by measuring local geometric distortions and global sharpness[END_REF] based on measuring the LOcal Geometric distortions in the disoccluded region and global Sharpness.

• DSQM: DIBR-Synthesized image Quality Metric, proposed by Farid et al. [START_REF] Farid | Perceptual quality assessment of 3d synthesized images[END_REF] A block matching is firstly used to match the content in the reference image and the synthesized image, then the difference of Phase congruency (PC) in these two matched blocks is used to measure the quality of the block in the synthesized image. The final image quality is obtained by averaging the quality score of all the blocks.

EXPERIMENT

In this section, the performances of the above metrics are compared and analyzed. We firstly introduce the used database, and then present the performance comparison of these metrics.

Free-viewpoint Video database

The quality metrics are evaluated on the IRCCyN/IVC Free-viewpoint video (FVV) database [START_REF]IRCCyN/IVC Free-Viewpoint synthesized videos database[END_REF] which is introduced in. The associated depth maps were encoded through the following seven coding algorithms:

• C1: 3D-HEVC test model, 3D-HTM 0.4, [START_REF]3D-HTM[END_REF] inter-view prediction and V iew Synthesis Optimization enabled;

• C2: Multiview Video Coding (MVC), JM 18.4; 25

• C3: HEVC Test model, HM 6.1; 26

• C4: JPEG2000, Kakadu implementation; 27

• C5: based on, 28 a lossless-edge depth map coding based on optimize path and fast homogeneous diffusion;

• C6: based on, [START_REF] Pasteau | Adaptive color decorrelation for predictive image codecs[END_REF] this algorithm exploits the correlation with color frames;

• C7: Z-LAR-RP, 30 a region-based algorithm.

In this database, all coding algorithms were used in intra coding mode. Three quantization parameters were selected for each depth map codec test according to the visual quality of the rendered views. Views synthesized from compressed depth map and uncompressed depth map are used as the distorted and reference videos separately in this database in order to estimate the synthesis distortions produced by depth map compression.

Performance comparison

The reliability of objective metric could be evaluated by their correlation with subjective test scores. Differential Mean Opinion Score (DMOS) is usually used as subjective score. In this paper, the consistency of objective metrics was calculated by using Pearson Linear Correlation Coefficients (PLCC), Spearmans Rank Order Correlation Coefficients (SROCC) and Root-Mean-Square-Error (RMSE). Before measuring the PLCC, RMSE and SROCC values, the objective scores were fitted to the predicted DMOS (DM OS p ). The following nonlinear regression function should be used to map the objective scores to subjective scale, which is recommended by the Video Quality Expert Group (VQEG) Phase I FR-TV. [START_REF] Group | Final report from the video quality experts group on the validation of objective models of multimedia quality assessment[END_REF]

DM OS

p = β 1 ( 1 2 - 1 1 + e β2(score-β3) ) + β 4 score + β 5 ( 1
)
where score is the score obtained by the objective metric and β 1 , β 2 , β 3 , β 4 , β 5 are the parameters of this function.

They are obtained through regression to minimize the difference between DM OS p and DM OS. For the image quality assessment metrics, the video quality scores are calculated by averaging the score of all the frames of each video. The obtained PLCC, RMSE, SROCC values are shown in Table 1. It can be observed that none of the tested quality metrics performs well on this Free Viewpoint Video database, since there is no metric whose PLCC is higher than 0.65. Generally, the DIBR metrics perform much better than conventional 2D metrics except PSNR, which is logical since these metrics are dedicated to handle the DIBR distortions.

The scatter plot of each quality metric is shown in Fig. 2. It seems that these methods have difficulties in predicting the worst or best qualities, which leave large empty regions in on the DM OS p axis compared to the DM OS axis. Which is consistent with the results shown in Table 1 that no metric get a PLCC value bigger than 0.65. The metrics VIF, RRED and LOGS get the largest empty regions, they show lower correlation with the subjective results, which is similar to their correlation coefficients in Table 1. While most metrics succeed in assessing the videos with medium qualities.

The above methods compare the performance of each metric by calculating their correlations with the subjective results, however they just take the mean value of subjective scores into consideration, the uncertainty of the subjective scores has been ignored. In addition, the quality scores need to be regressed by a regression function cf. Eq. 1, that is not the way they are exactly used in real scenarios. Thus, we further conduct a statistical test proposed by Krasula et al., [START_REF] Krasula | On the accuracy of objective image and video quality models: New methodology for performance evaluation[END_REF] which does not suffer from the drawbacks of the above methods. The performance of objective metrics are evaluated by their classification abilities.

Firstly, the tested video pairs in the database are divided into two groups: different and similar. The first performance analysis is conducted by how well the objective metric can distinguish the video pair are significant different or not. If the two videos in the pair are significant different according to the subjective results, in the (c) better / worse (AUC) 12) and NIQSV (13); the white color in the significant plots indicates that the performance in the row is significantly better and the metric in the column, similarly the block mean lower and gray means there is no significant difference between these two metrics.

second analysis, we determine whether the objective metric can correctly recognize the video of higher quality in the pair. The obtained results, the Area Under the Curves (AUC) and the Correct Classification percentage (C 0 ) are given in Fig. 3.

In the first different/similar analysis, the AUC values of most metrics are between 0.55 and 0.65, the VQA-SIAT performs significantly better than the others and the DSQM performs significant worse. In the better/worse analysis, the DIBR FR metrics perform significantly better than the 2D metrics except PSNR, but there is no AUC values bigger than 0.85, which is consistent with the results in Table 1 and Fig. 2 that none of the metrics can achieve a satisfactory correlation with the ground truth. Especially, the better/worse analysis results are consistent with the SROCC values, which give the monotonicity estimation, in Table 1. The metrics which lower SROCC values performs worse in the better/worse analysis according to Fig. 3 (b) and (c).

CONCLUSION

In this paper, we conducted a comparison of the performance of existing quality metrics on free-viewpoint videos with different depth coding algorithms. The results show that the DIBR dedicated metrics performs better than the conventional 2D quality metrics generally, but none of these metrics can achieve a satisfactory correlation with the ground truth since both the PLCC and SROCC values of these metrics are less than 0.65. There is certainly room for the improvement of quality assessment method of free-viewpoint videos with compressed depth maps.

  MW-PSNR (FR)

  MW-PSNRr (RR)

  MP-PSNR (FR)

Figure 2 .

 2 Figure 2. Scatter plots of DMOS versus DMOSp of each quality assessment method, where FR* indicates that the metric is side view based FR metric

Figure 3 .

 3 Figure 3. Results of Krasula's method, the metric numbers from 1 to 13 refer to: PSNR (1), SSIM (2), VIF (3), VIIDEO (4), RRED (5), MW-PSNR (6), MW-PSNRr (7), MP-PSNR (8), MP-PSNRr (9), VQA-SIAT(10), LOGS(11), DSQM(12) and NIQSV(13); the white color in the significant plots indicates that the performance in the row is significantly better and the metric in the column, similarly the block mean lower and gray means there is no significant difference between these two metrics.

  [START_REF] Bosc | A quality assessment protocol for free-viewpoint video sequences synthesized from decompressed depth data[END_REF] This FVV database contains six different multiview sequences: Balloons (1024 × 768), BookArrival (1024 × 768), U ndoDancer (1920 × 1080), GT F ly (1920 × 1080), Kendo (1024 × 768), N ewspaper (1024 × 768). For each MVD sequence, two real views at one time instant t were chosen to generate 49 intermediate synthesized views in-between these two views using the View Synthesis Reference Software 1D Fast (VSRS-1D-Fast).[START_REF] Zhang | 3d-hevc test model 5[END_REF] There are two different synthesis mode to be considered: blended mode and non -blended mode. The blended mode means the combination of the both view using a weighted blending based on the baseline distance, the non-blended mode means using the closer view for rendering and the other one for hole filling. A video sequence of 100 frames (at 10 fps) was built from the 49 intermediate virtual frames and 2 original real views to simulate a smooth camera motion from left to right and from right to left. as shown in Fig.1. Where O1 and O2 denote the real views, S1 • • • S49 denote the synthesized views.

	O1	S1	S2 ... S48	S49	O2	S49 S48 ... S2 S1

Figure 1. Video frame sequence

Table 1 .

 1 Performance of each metrics on IVC Free Viewpoint Video database, where FR* indicates that the metric is side view based FR metric.

		Metric	PLCC RMSE SROCC
		PSNR (FR)	0.6052 0.7888	0.6043
		SSIM (FR)	0.5190 0.8471	0.5161
	2D metrics	VIF (FR)	0.3552 0.9264	0.3545
		VIIDEO (NR)	0.4011 0.9078	0.3631
		RRED (RR)	0.4129 0.9026	0.4035
		MW-PSNR (FR) 0.6273 0.7708	0.6205
		MW-PSNRr (RR) 0.6028 0.7908	0.6066
		MP-PSNR (FR)	0.6466 0.7560	0.6355
		MP-PSNRr (RR) 0.6239 0.7745	0.6192
	DIBR metrics	VQA-SIAT (FR) 0.6287 0.7706	0.6232
		LOGS (FR*)	0.5398 0.8342	0.4292
		DSQM (FR*)	0.5766 0.8097	0.4938
		NIQSV (NR)	0.6192 0.7781	0.5508


Shishun Tian

Lu Zhang

Luce Morin

Olivier Déforges

SC-IQA: Shift compensation based image quality assessment for DIBR-synthesized views

Keywords: Synthesized view, Quality assessment, Shift compensation, Affine transform, Block matching

published or not. The documents may come

I. INTRODUCTION

Enabling users to view a 3D scene from different angles, Free-viewpoint TV (FTV) and Multiview TV have gained great public interest and curiosity in the past decade. Multiview-Video-Plus-Depth (MVD) is the main representation method for 3D applications. It consists of limited number of texture views from different viewpoints and their associated depth maps, which are used to synthesize the virtual views at other viewpoints based on Depth-Image-Based-Rendering (DIBR) [START_REF] Fehn | Depth-image-based rendering (DIBR), compression, and transmission for a new approach on 3d-tv[END_REF]. However, view synthesis can also induce some new types of distortion due to depth errors, dis-occlusions and inpainting methods. The distortions caused by 2D image compression, such as blur, blockiness and ringing, are often scattered over the whole image while the DIBR-synthesized distortions are mostly local. Besides, inaccurate depth maps and imperfect image impainting methods can also introduce object shifting and geometric distortions in the synthesized views. For this reason, the conventional 2D quality metrics do not work well on DIBR-synthesized artifacts. Thus, quality metrics suitable for synthesized views are urgently needed. Such an effective quality metric could be used as a feedback to optimize not only the view synthesis but also the compression.

In order to solve this problem, several full-reference (FR) methods have been proposed to evaluate the quality of DIBRsynthesized views in the past few years. 1) VSQA: View Synthesis Quality Assessment [START_REF] Conze | Objective view synthesis quality assessment[END_REF] was proposed aiming to characterize the image complexity by applying three weighting maps on the SSIM distortion map. The gain of PLCC approached 17.8% over original SSIM in correlation with subjective judgment. 2) 3DSwIM: 3D Synthesized view Image Quality Metric [START_REF] Battisti | Objective image quality assessment of 3d synthesized views[END_REF] is based on a comparison of statistical features of wavelet sub-bands of the original and DIBR-synthesized images. A registration process and a skin detection step are used to make sure that the best matching blocks are always compared, and that the most sensitive distorted blocks are penalized.

3) MW-PSNR, MP-PSNR: Morphological Wavelet Peak

Signal-to-Noise Ratio measure [START_REF] Sandić-Stanković | Dibr synthesized image quality assessment based on morphological wavelets[END_REF] and Morphological Pyramid Peak Signal-to-Noise Ratio [START_REF]Multi-scale synthesized view assessment based on morphological pyramids[END_REF] were proposed by Sandic-Stankovic et al. to handle the geometric distortions in different resolution levels. In addition, their reduced versions, the reduced MW-PSNR (MWPSNRr) and reduced MP-PSNR (MP-PSNRr) in [START_REF] Sandić-Stanković | Dibr-synthesized image quality assessment based on morphological multi-scale approach[END_REF], were also proposed to improve the performance. 4) CT-IQA: a variable-length context tree based image quality assessment [START_REF] Ling | Quality assessment for synthesized view based on variable-length context tree[END_REF] proposed by Ling et al. aims to quantify the overall structure dissimilarity and dissimilarities in various contour characteristics. 5) EM-IQA: In [START_REF] Ling | Image quality assessment for dibr synthesized views using elastic metric[END_REF], Ling et al. also proposed an elastic metric based image quality assessment metric by quantifying the deformation of curves in the local distortion regions.

According to recent research [START_REF] Moorthy | Visual importance pooling for image quality assessment[END_REF], Human Visual System (HVS) is more sensitive to local artifacts compared to the global object shift. However, the global shift in DIBRsynthesized views can be easily penalized by most pixel-wise quality metrics, eg. PSNR, SSIM. In this paper, we propose an FR shift compensation based image quality assessment metric (SC-IQA) for DIBR-synthesized views. Besides, we use a visual saliency map to weight the final quality map. This paper Fig. 1. Block scheme of the proposed method is organized as follows: the proposed method is introduced in Section II, the experimental results on the IRCCyN/IVC DIBR database [START_REF] Bosc | Towards a new quality metric for 3-d synthesized view assessment[END_REF] are presented and discussed in Section III and finally the conclusions are drawn in Section IV.

II. PROPOSED METHOD

In this section, the proposed FR metric is introduced in detail. We assume that the reference views, which is captured at the same viewpoints as the synthesized views, are available; and the FR metrics compute the distortions between the synthesized and the reference views. As mentioned above, the global shift is acceptable to human observer while it can be easily penalized by pixel-wise metrics. Thus, the proposed method concentrates on compensating the global shift between the DIBR-synthesized views and the reference views.

The block diagram is shown in Fig. 1, the proposed shift compensation method consists of two parts: firstly, the global geometric shift is compensated approximately by feature points matching and transform is used to compensate the shift roughly; then, we use block matching to compensate it precisely. Besides, a saliency map is also used as a weighting function to improve the performance. The final overall quality scores are obtain by measuring the γ % worst matched blocks since human observers are more sensitive to poor quality regions rather than the good ones.

A. Feature points matching and transform Fig. 2 (a) gives an example of the SSIM map between the synthesized image and the reference image in the adopted database [START_REF] Bosc | Towards a new quality metric for 3-d synthesized view assessment[END_REF], it could be observed that there exists great global shift between the synthesized image and the reference image. In this part, the global geometric shift is compensated roughly by SURF [START_REF] Bay | Surf: Speeded up robust features[END_REF] + RANSAC [START_REF] Fischler | Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography[END_REF] homography approach.

Firstly, SURF feature points in the reference and synthesized images are detected and matched. Then, to be robust, the RANSAC algorithm is used to refine the matching and estimate the homography matrix H. After that, the pixels of the synthesized image are warped to the corresponding positions in reference image by H. The SSIM map before transform, the matched feature point pairs and the SSIM map after transform are shown in Fig. 2.

We can observe that the global shift between the synthesized and the reference images has been roughly compensated. In the next step, we use block matching to compensate the shift precisely.

B. Block matching

In this part, a multi-resolution block matching algorithm is used to precisely compensate the shift and also to detect the large geometric distortions. In the first step, we use a large block N 1 × N 1 (N1 = 64) for primary matching; then we use a small block N 2 × N 2 (N2 = 8) for final matching. The matching process can be described by the following steps:

1) Divide the synthetized view into a regular grid of N 1 × N 1 blocks; 2) For each N 1 × N 1 block, search for the best matching block in the reference view. The best matching block is the one showing the largest following similarity criterion:

sim(s, r) = con(s, r) + var(s) + var(r) +

where s, r denote the blocks in the synthesized image and the reference image; the operation cov and var denote the co-variance and variance respectively; is a constant value to stabilize the division with weak denominator.

3) Each

N 1 × N 1 block is divided into smaller N 2 × N 2
blocks and the process is repeated with a smaller search window. Since the shift only occurs in the horizontal direction, we only search the blocks in this direction for matching. We assume the biggest shift in the synthesized image to be 30, the search windows of N1 and N2 are restricted to 30 and 5 respectively.

The goal of this multi-resolution block matching algorithm is to compensate the global shift and penalize the local geometric distortions. Now, if we directly use N 2 × N 2 block for matching, and set the search window to 30 (the biggest shift range in the synthesized image), the computational complexity will be much higher. Besides, as shown in Fig. 3, there exists great geometric distortion in the red block (N 1 × N 1) in Fig. 3

(d).

There exists little difference between these two red blocks, so the geometric distortion will not be penalized. On the contrary, if we use the proposed multiresolution block matching method, the matched block is the green one, this geometric distortion will be surely penalized. The multi-resolution approach is thus more robust.

C. Saliency weighting

In addition, a saliency detection [START_REF] Jiang | Salient object detection: A discriminative regional feature integration approach[END_REF] is also used as a weighting map to improve the performance of the proposed metric. The distortion of each N 2 × N 2 block is measured by averaging the weighted mean square errors between the blocks of the synthesized and the reference images, as shown in:

M SE B = (i,j)∈B (syn(i, j) -ref (i, j)) 2 × Salmap(i, j) (i,j)∈B Salmap(i, j) (2

D. Quality pooling

Since the humans tend to perceive poor regions in an image with more severity than the good ones [START_REF] Moorthy | Visual importance pooling for image quality assessment[END_REF], [START_REF] Liu | Subjective and objective video quality assessment of 3D synthesized views with texture/depth compression distortion[END_REF], we only use the blocks with the worst quality to calculate the final quality as shown in Eq. 3.

M SE W = 1 N W i∈W M SE B (i) (3)
where W represents the set of the worst 1% blocks in the image, N W is the number of items in the set W.

The final quality scores are computed as the following equation:

Score SC-IQA = 10 × log 10 (255 × 255/M SE W ) (4)
where a higher quality score indicates a better quality.

III. EXPERIMENTAL RESULTS

This section describes and discusses the experiments of the proposed SC-IQA metric. The performance of SC-IQA is tested on the IRCCyN/IVC DIBR database [START_REF] Bosc | Towards a new quality metric for 3-d synthesized view assessment[END_REF], which consists of 84 synthesized views generated by seven different DIBR view synthesis algorithmsand their associated 12 reference views along with the subjective scores -mean opinion score (MOS). The performance of objective quality metrics can be represented by their correlations with subjective judgements. In this paper, the following 3 widely employed criteria are used:

Pearson Linear Correlation Coefficients (PLCC), Spearmans Rank Order Correlation Coefficients (SROCC) and Root-Mean-Square-Error (RMSE). Before calculating these 3 coefficients, the objective scores need to be regressed to remove the nonlinearities due to the subjective rating process, as recommended by Video Quality Expert Group (VQEG) Phase I FR-TV [START_REF]Final report from the video quality experts group on the validation of objective models of multimedia quality assessment[END_REF]. The scatter plot of the predicted scores versus the subjective scores and the regression function are shown in Fig. 4.

The comparison results of the proposed metric (with γ = 1), the state-of-the-art DIBR dedicated quality metrics and the commonly used 2D quality metrics are concluded in Table I. It shows that the proposed metric significantly outperforms the state-of-the-art DIBR dedicated quality metrics: MW-PSNR, MP-PSNR, MP-PSNRr, MW-PSNRr, 3DSwIM, VSQA, CT-IQA and EM-IQA, and the commonly utilized 2D image quality metrics: PSNR, SSIM. In addition, the performance dependency of the proposed metric on ratio γ% is also discussed as shown in Fig. 5. Especially the ratio 0 is associated with the proposed metric without saliency map. According to Fig. 5, the use of the saliency map improves the proposed metric slightly; the performance of the proposed metric goes down as the ratio increases, however even the lowest scores are still superior to most of the stateof-the-art metrics in Table I. This shows the robustness of the proposed metric. IV. CONCLUSION In this paper, we proposed a novel full-reference shift compensation based image quality assessment metric for DIBRsynthesized views (SC-IQA). An SURF + RANSAC homography approach and a multi-resolution block matching are used to compensate the global shift and to penalize the geometric distortions as well. The experimental results show that it significantly outperforms the state-of-the art 3D synthesized view dedicated metrics: 3DSwIM, MP-PSNR, MW-PSNR, CT-IQA, EM-IQA and the conventional 2D IQA metrics: PSNR, SSIM.

  (a) compared to its matched block in the reference (a) SSIM map before transform (b) optimized matched feature point pairs (c) SSIM map after transform

Fig. 2 .Fig. 3 .

 23 Fig. 2. Example of feature points matching and transform

  ) where B means the matched N 2 × N 2 blocks; (i, j) denotes the pixel in the block; syn and ref represent the blocks in the synthesized image and reference image respectively; Salmap represents the saliency map in this block.

Fig. 4 .

 4 Fig. 4. Scatter plot of SC-IQA quality score versus DMOS

Fig. 5 .

 5 Fig. 5. Performance dependency of the proposed metric with the changing ratios (γ%)

TABLE I PERFORMANCE

 I

	COMPARISON BETWEEN THE PROPOSED METRIC AND THE
	STATE-OF-THE-ART METRICS (WITH γ = 1)
	Metric	PLCC	RMSE	SROCC
	PSNR	0.4557	0.5927	0.4417
	SSIM	0.4348	0.5996	0.4004
	3DSwIMr	0.6864	0.4842	0.6125
	VSQA	0.6122	0.5265	0.6032
	MW-PSNR	0.6200	0.5224	0.5739
	MW-PSNRr	0.6625	0.4987	0.6232
	MP-PSNR	0.6729	0.4925	0.6272
	MP-PSNRr	0.6954	0.4784	0.6606
	CT-IQA	0.6809	0.4877	-
	EM-IQA	0.7430	0.4455	-
	SC-IQA	0.8496	0.3511	0.7640


Chung Shue Chen
email: chungshue.chen@loria.fr

Shing Wing

Wong
email: wswong@ie.cuhk.edu.hk

Ye-Qiong Song
email: song@loria.fr

The Design and Analysis of Protocol Sequences for Robust Wireless Accessing

In this paper, a family of linear congruence sequences with interesting cross-correlation properties is investigated for potential applications in defining new multiple access protocols for distributed wireless systems. One can show that for any finite subset of the sequences with rate sum not exceeding a certain level, there cannot have enough collisions to completely block any particular user no matter how they are shifted with respect to one another. The user un-suppressibility and service guarantee can be exploited in many applications such as wireless sensor or impulse radio systems. To enhance the system's allowable rate sum while possessing the non-blocking property, new protocol sequences are designed. Besides, the throughput shift-invariant property is obtained.

I. INTRODUCTION

In a wireless communication system, the most fundamental question of a multiple access control is how to accommodate users in the shared channel. To avoid transmission conflict, one may employ a rigid protocol such as time division multiple access (TDMA). However, it may not be practical due to the difficulties in synchronizing transmissions from different senders [START_REF] Tinguely | The collision channel with recovery[END_REF]. Contention-based random access protocols such as IEEE 802.11 CSMA/CA can provide a more flexible transmission scheme. However, usually they require some backoff algorithms and a feedback link to ensure successful delivery.

For system simplicity, it is desirable to have a simple multiple access protocol which does not require stringent time synchronization and complicated processing such as backoff algorithm or random number generator. The model of collision channel without feedback [START_REF] Massey | The collision channel without feedback[END_REF] is worth of a revisit. Senders are assumed cannot synchronize transmissions between one another due to a lack of feedback link and their relative time offsets are unknown. Thus, each user will make packet transmissions simply at times governed by its protocol sequence in a distributed way. It can be shown that a simple and reliable multiple access scheme under these constraints is still possible even without a requirement of packet retransmission. The result can provide a helpful alternative for wireless accessing.

Potential applications include wireless sensor networks in which computing power and communication capability are often very limited [START_REF] Akyildiz | A survey on sensor networks[END_REF]. Meanwhile, frequent monitoring of the channel for feedback information and complicated backoff processing can be eliminated. Besides, when considering an This work is also supported by a grant from the Research Grants Council of the Hong Kong Special Administrative Region (Project no. CUHK416906). ad-hoc system with dynamic topology [START_REF] Jurdak | A survey, classification and comparative analysis of medium access control protocols for ad hoc networks[END_REF], sharing a radio channel with the requirement of well-coordinated transmissions and time offsets could be hard for thin devices.

In this paper, a class of periodic binary sequences with interesting properties is investigated for defining new multiple access protocols in a shared radio channel. The idea of using deterministic binary sequences to define medium accessing can be traced back to [START_REF] Massey | The collision channel without feedback[END_REF]- [START_REF] Shaar | A survey of one-coincidence sequences for frequency-hopped spread-spectrum systems[END_REF]. Some related works in the collision channel can be found in [START_REF] Nguyen | Constructions of binary constant-weight cyclic codes and cyclically permutable codes[END_REF]- [START_REF] Chen | A robust access protocol for wireless sensor networks[END_REF]. Besides, packet recovery from collisions with multiuser detectors was discussed in [START_REF] Tinguely | The collision channel with recovery[END_REF]. In protocol sequence designs, major concerns include the number of sequences available, user throughput performance and the length of sequences. Cross-correlation between sequences is one of the important performance indicators.

II. CHANNEL MODEL

Following the model of collision channel without feedback [START_REF] Massey | The collision channel without feedback[END_REF], a communication channel is divided into time slots of equal durations. Each user follows a binary sequence, W = {W (t), t = 0, 1, 2, • • •}, and will transmit a data packet at time slot t if W (t) = 1. Otherwise, it keeps silent. Here, we restrict our attention to the slot-synchronized model in which users transmit packets aligned to the common slot boundaries. However, users do not know the time offsets between one another and cannot synchronize their transmissions. They may have different transmission starting time.

At any time slot, a packet collision occurs if more than one user transmits at the same time. All transmitted packets in this duration are considered lost. Otherwise, the receiver can receive the packet correctly and decode the content. For system simplicity, each packet will include a header which contains sender identity like those commonly defined in conventional MAC protocols [START_REF] Jurdak | A survey, classification and comparative analysis of medium access control protocols for ad hoc networks[END_REF]. If the packet payload is large, the cost of overhead is relatively small. For advanced packet identification or coding schemes, discussions can be found in [START_REF] Massey | The collision channel without feedback[END_REF], [START_REF] Thomas | Capacity of the wireless packet collision channel without feedback[END_REF].

For a periodic binary sequence with period L, its duty factor or proportional transmission rate, r, is defined as

r = 1 L L-1 t=0 W (t). (1)
The effective throughput of a user is defined as the fraction of packets it can send without suffering any collision.

In a random access system, one is usually most interested in the symmetric case in which all users are signaling at the same rate [START_REF] Massey | The collision channel without feedback[END_REF]. Here, we will focus on the design for symmetric users. It is known that in this case the system capacity tends to 1/e as the number of active users, M , tends to infinity. However, in addition to system throughput, it is also important to look at the service reliability for each individual user. Related works in the tradition usually focus on the system throughput. Without loss of generality, it is favorable to have a design which can support both system and individual performance stability. Thus, one can always ensure the availability of a reliable communication channel for any of the active users as long as the allowable rate sum does not exceed a given level.

III. DISTRIBUTED WIRELESS ACCESSING

In the following, an investigation on the class of linear congruence sequence [START_REF] Titlebaum | Time-frequency hop signals, part I: coding based upon the theory of linear congruences[END_REF] and its deployment for robust wireless accessing with user un-suppressibility [START_REF] Wong | New protocol sequences for random access channels without feedback[END_REF] is reported. The result and analysis has also motivated our design for a system enhancement. The details are given below.

A. Linear Congruence Sequence

Let W = {W (t), t = 0, 1, 2, • • •} be a binary sequence. It can also be represented by indexing the positions of '1's. I W (i) is used to denote the position at which the i-th entry of 1's in W appears. Let b and l be two integers such that 0 ≤ b < l. The linear congruence sequence generated by (b, l) is expressible as

I W (i) = il + ib -⌊ib/l⌋ l ( 2
)
where b is known as the key generator. The duty factor of a sequence generated by (b, l) is equal to 1/l. For b > 0, the minimum period is equal to l 2 . For b = 0, I W (i) = il. For example, given b = 1 and l = 3, following (2), I W = {4, 8, 9, • • •}. The core pattern of W is {0, 0, 0, 1, 0, 0, 0, 1, 1}. The sequence has a duty factor r = 1/3 and period of 9.

Note that, for prime l, the set of linear congruence sequences is also known as prime sequences [START_REF] Shaar | A survey of one-coincidence sequences for frequency-hopped spread-spectrum systems[END_REF].

B. Correlation Properties

Let W 1 and W 2 be two binary sequences with common period L. For any relative time shift s, we define the Hamming cross-correlation function between W 1 and W 2 as

H W1,W2 (s) = L-1 t=0 W 1 (t)W 2 (t + s) (3)
while the normalized cross-correlation is given by

HW1,W2 (s) = H W1,W2 (s)/L. (4)
for any 0 ≤ s < l 2 , where r, the duty factor, is equal to 1/l. For b 1 , b 2 > 0, this upper bound is tight [START_REF] Wong | New protocol sequences for random access channels without feedback[END_REF].

If b 1 = 0 or b 2 = 0, HW1,W2 (s) = 1/l 2 = r 2 . (6)
For example, given l = 5, let W i be the set of sequences generated by (i, l), where 0 ≤ i < 5. Following (2),

      W 0 W 1 W 2 W 3 W 4       =       0000100001000010000100001 0000010000010000010000011 0000001000000101000000101 0000000100100000001001001 0000000010001000100010001       . ( 7
)
The number of coincidences, or hits, between two distinct sequences in ( 7) is given by

          H W0,W i =0 (s) H W1,W2 (s) H W1,W3 (s) H W1,W4 (s) H W2,W3 (s) H W2,W4 (s) H W3,W4 (s)           =           1111111111111111111111111 1210110220110121120111021 1210110211111201101211111 1202010202110211111111201 1111111021121101011211201 1121011102120111012111111 1121012002101211120111021           (8)
for the relative time shift 0 ≤ s ≤ 24. It demonstrates that

0 ≤ H Wi,W j =i (s) ≤ 2 (9)
where H Wi,W j =i (s) indicates the number of packets collided between senders by W i and W j with relative time offset s. The number of hits is counted in the common period, l 2 = 25.

C. Protocol Sequences and Un-suppressibility

Following the definition of (2), a family of protocol sequences can be formulated below. To satisfy the condition for the performance of ( 5) and ( 6), and have a greater flexibility of b, here l is restricted to prime number, denoted by p.

A family of periodic binary sequences, F p , is defined as the set of linear congruence sequences generated by (b, p), where 0 ≤ b < p. The sequences in F p have a minimum common period L = p 2 and each has a duty factor 1/p. By ( 5) and [START_REF] Jurdak | A survey, classification and comparative analysis of medium access control protocols for ad hoc networks[END_REF],

max s H Wi,Wj (s) = 2 (10)
for any i = j. A user un-suppressibility [START_REF] Wong | New protocol sequences for random access channels without feedback[END_REF] property of a set of above protocol sequences can be established accordingly. Consider a collision channel without feedback in which multiple active users need to be supported in a distributed manner and, over a long time horizon, occasional data loss is not a serious problem or can be recovered by some channel coding [START_REF] Thomas | Capacity of the wireless packet collision channel without feedback[END_REF], the set F p can be used to define protocol sequences for packet transmissions. Note that a packet retransmission mechanism can be embedded if preferred and feedback channel is available. However, the detail is out of the scope here.

For any finite subset of

F p , {W i , i = 0, 1, • • • , (M -1)}, provided that M -1 i=0,i =j r i ≡ M -1 i=0 r i -r j < 1 2 (11)
which refers to the sum of duty factors of active users excluding user j, following the definition of (3), by [START_REF] Chen | A robust access protocol for wireless sensor networks[END_REF] and [START_REF] Sarwate | Crosscorrelation properties of pseudorandom and related sequences[END_REF], the total number of collisions to W j is equal to

M -1 i=0,i =j L-1 t=0 W j (t)W i (t + s i,j ) ≡ M -1 i=0,i =j H Wi,Wj (s i,j ) ≤ M -1 i=0,i =j 2 < 1/2 1/p × 2 = p (12)
for any combinations of relative time shifts s i,j in W i with reference to W j . The number of collisions in any period p 2 is strictly less than p. Thus, there cannot have enough collisions to completely block any particular user j in any cycles as long as the sum of other duty factors {r i =j } does not exceed 1/2, even if the relative time shifts between one another may change from time to time due to different reasons. Similarly, as long as

M -1 i=0 r i ≤ 1/2, we have M -1 i=0,i =j L-1 t=0 W j (t)W i (t + s i,j ) ≤ 1/2 -1/p 1/p × 2 = p -2. ( 13
)
That is, for each user in the above set, in any cycle, at least 2 transmitted packets have no collision. User un-suppressibility is ensured such that, even in the worst case, all the users can successfully transmit information to a guaranteed amount in every time period in a distributed multiple access. A reliable communication is possible even without the requirement of user synchronization or a feedback link.

Note that the bound of allowable rate sum in ( 11) is not tight. One can find examples in which the un-suppressibility holds while the inequality is violated. A natural follow-up is to enhance the maximum allowable rate sum and construct a set of corresponding periodic sequences which possess the un-suppressibility guarantee. Designs are presented below.

IV. NEW PROTOCOL SEQUENCES

In this section, new constructions of protocol sequences which have smaller normalized cross-correlations are described. The result can significantly enhance the allowable rate sum of active users in the system.

A. General Idea

Recall ( 5) and ( 6), one can find that

H Wi,Wj (s) = {0, 1, 2} (14)
while HWi,Wj (s) ≤ 2r 2 for i = j. This could be a hint to construct a new set of sequences with HWi,Wj (s) = r 2 based on an observation of the following property [START_REF] Sarwate | Crosscorrelation properties of pseudorandom and related sequences[END_REF] that

λ avg (W i , W j ) ∆ = L-1 s=0 HWi,Wj (s) = r i r j L. (15)
Generally, the average number of coincidences between any two sequences W i and W j , with duty factors r i and r j respectively, over their common period L is equal to r i r j L since each of the r i L 1's in W i will meet r j L 1's in W j when s shifts from 0 to 1, 2, • • •, up to L -1, stepwise. Take (8) as an example, where L = 25 and r = 1/5,

λ avg (W i , W j ) = 1 L L-1 s=0 H Wi,Wj (s) = 25/25 = 1. (16)
That is, the average number of hits between two sequences is in fact equal to 1 after averaging out over all the relative time shifts 0 ≤ s < L. The frequency of "H Wi,Wj (s) = 2" is just the same as that of "H Wi,Wj (s) = 0". There is no bias.

So, one way to obtain a set of periodic binary sequences with HWi,Wj (s) = r i r j can be done by concatenating the original sequences from (2) with their shifted versions so as to combine all the effects due to the time shifts. Thus, in the new sequences, for any relative time shift, one can get the average performance, "H Wi,Wj (s) = 1", i.e. on average one collision with another sequence per p packets transmitted. In other words, HWi,Wj (s) = 1/p 2 . The cross-correlation between two sequences will be shift invariant.

Thus, as long as

M -1 i=0 r i ≤ 1, similarly to (13), M -1 i=0,i =j L-1 t=0 W j (t)W i (t + s i,j ) ≡ M -1 i=0,i =j H Wi,Wj (s i,j ) = M -1 i=0,i =j L p • 1 p ≤ 1 -(1/p) 1/p • L p 2 = L p - L p 2 (17)
which shows that, in any common period L, the number of collisions is strictly less than the number of packets one transmits, L/p. There cannot have enough collisions to completely block any particular user. Even when the system is saturated and rate sum equals to 1, each user has a throughput not less than 1/p 2 . In fact, the actual throughput could be much higher since in general the upper bound on the number of collisions given by (17) is not tight. Section V will show the performance.

B. Construction 1

Let us start with p = 3 to elaborate the details. By [START_REF] Jurdak | A survey, classification and comparative analysis of medium access control protocols for ad hoc networks[END_REF], since HW0,W1 (s) = HW0,W2 (s) = r 2 = 1/9, first we take W 0 and W 2 (otherwise, W 0 and W 1 ) as the basic codewords. By (5), max s HW1,W2 (s) = 2/9. Thus, if one employs W 0 , W 1 and W 2 simultaneously, W 1 (or W 2 ) will be completely blocked by W 2 and W 0 (respectively, W 1 and W 0 ) in worst case.

To make all sequence pairs with H(s) = 1/9, by following the idea of "averaging out", the construction is expressible as

   W (1) 1 W (1) 2 W (1) 0    =   W 1,θ=0 W 1,θ=1 • • • W 1,θ=8 W 2,θ=0 W 2,θ=0 • • • W 2,θ=0 W 0,θ=0 W 0,θ=0 • • • W 0,θ=0   ( 18
)
where W i,θ=n refers to a cyclic shift of W i by n bits toward the left while the superscript on W

(1) i is to label Construction 1. For example, here, W 1,θ=0 ≡ W 1 = {000100011} and W 1,θ=1 = {001000110}. New sequences need to be longer. Following (18), for any relative shift s, the normalized cross-correlation between W

(1) 1

and W

(1) 2

is given by:

HW (1) 1 ,W (1) 2
(s) ≡ 1 p 4 p 4 -1 t=0 W (1) 1 (t)W (1) 2 (t + s) = 1 p 4 p 2 -1 n=0 p 2 -1 t=0 W 1,θ=n (t)W 2,θ=0 (t + s) = 1 p 4 p 2 -1 n=0 p 2 -1 t=0 W 1 (t)W 2 (t + s -n) = 1 p 4 p 2 -1 n=0 p 2 • HW1,W2 (s -n) = p 2 p 4 × 1 = 1 p 2 = 1 9 (19)
since by (15),

p 2 -1 n=0 HW1,W2 (s -n) = 1
, where L = p 2 and r i = r j = 1/p. For W

(1) 0 and the other, since HW0,W1 (s) = HW0,W2 (s) = 1/p 2 , it is straightforward that

HW (1) 0 ,W (1) 1
(s) = HW (1) 0 ,W

(s) = 1/p 2 . ( (1) 2
) 20
Hence, {W

0 , W

1 , W

2 } is a set of sequences with normalized Hamming cross-correlation equal to r 2 . The result is independent of s. Even when all of them are used simultaneously and rate sum equals to 1, the un-suppressibility holds.

For sequences of duty factor equal to 1/5, to make HW (1) i ,W

(1) j =i (s) = 1/25, following the same idea,

       W (1) 1 W (1) 2 W (1) 3 W (1) 4 W (1) 0        =       [W 1,θ=0 • • • W 1,θ=24 ] 25×25 [W 2,θ=0 ] 25 • • • [W 2,θ=24 ] 25 25 [W 3,θ=0 ] 25×25 • • • [W 3,θ=24 ] 25×25 [W 4,θ=0 ] 25×25×25 [W 0,θ=0 ] 25×25×25       (21)
where [W i ] k refers to a concatenation of k copies of W i consecutively. The aim is to extend the original sequences such that for any pair of them all their shifted combinations are contained. Consequently, no matter how they shift, the resultant cross-correlation is always equal to the desired average. That is, HW (1) i ,W

(s) = 1/p 2 . The proof is very similar to that in (19) and because of limited space, it is omitted here.

Similarly, for each p, a set of shift invariant sequences with HWi,W j =i (s) = 1/p 2 can be constructed in an iterative way.

Even when all the protocol sequences are used simultaneously, the un-suppressibility still holds. It is worth pointing out that the idea of "averaging out" with ( 15) is generally applicable to many codewords. Similar results are achievable.

However, the new sequence needs to be much longer than the original one for the allowable rate sum enhancement. Let L (1) p be the sequence length of Construction 1 for the set of p. Since W (1) 0 requires only a simple concatenation, we have L (1) p = p 2 p-1 = p 2(p-1) . (

) 22
For example, L = 7 12 . In a channel of 1 Mb/s, it takes about 13.84 × 10 3 seconds to complete one sequence cycle. This could be a problem for some applications. It is desirable to have a shorter required sequence length.

C. Construction 2

In Construction 1, we may have excessively collected too many copies of the variants or shifted versions of the original sequences to average out all the cross-correlation combinations. However, some concatenations may not be necessary.

By an investigation of the cross-correlations between linear congruence sequences, it is found [START_REF] Wong | New protocol sequences for random access channels without feedback[END_REF] that, for i = j,

p-1 n=0 HWi,Wj (n • p + t) = 1/p (23)
for any integer 0 ≤ t < p. Thus, a design that contains concatenations with cyclic shifts over {0, p, 2p, • • • , p(p -1)} suffices to characterize the average performance and represent all the combinations. For p = 3, (18) can be simplified as

   W (2) 1 W (2) 2 W (2) 0    =   W 1,θ=0 W 1,θ=3 W 1,θ=6 W 2,θ=0 W 2,θ=0 W 2,θ=0 W 0,θ=0 W 0,θ=0 W 0,θ=0   . ( 24
)
Similar to (19), the normalized cross-correlation is equal to

HW (2) 1 ,W (2) 2
(s)

≡ 1 p 3 p-1 n=0 p 2 -1 t=0 W 1,θ=np (t)W 2,θ=0 (t + s) = 1 p 3 p-1 n=0 p 2 -1 t=0 W 1 (t)W 2 (t + s -np) = 1 p 3 p-1 n=0 p 2 HW1,W2 (s -np) = p 2 p 3 × 1 p = 1 p 2 (25)
while HW (2) 0 ,W

(s) = HW (2) 0 ,W

(s) = 1/p 2 . Thus, even when W

(2) 0 , W

and W

(2) 2

are used simultaneously and the rate sum is equal to 1, the un-suppressibility holds.

Generally, the construction can be formulated iteratively as:

               W (2) 1 W (2) 2 W (2) 3
. . .

W (2) p-2 W (2) p-1 W (2) 0                =                W 1,θ=0 W 1,θ=p • • • W 1,θ=(p-1)p p (p-3) [ [W 2,θ=0 ] p [W 2,θ=p ] p • • • W 2,θ=(p-1)p p ] p (p-4) [ [W 3,θ=0 ] p 2 • • • W 3,θ=(p-1)p p 2 ] p (p-5) . . . [ [W p-2,θ=0 ] p (p-3) [W p-2,θ=p ] p (p-3) • • • • • • W p-2,θ=(p-1)p p (p-3) ] p 0 [W p-1,θ=0 ] p (p-2) [W 0,θ=0 ] p (p-2)                . (26) Let L (2) p
be the sequence length by Construction 2. From (26), we have

L (2) p = p 2 × p p-2 = p p . (27)
For example, L

= 3 3 = 27, while L

= 7 7 . In a channel of 1 Mb/s, it takes about 0.82s to complete one cycle. This is much smaller than that of 13.84 × 10 3 seconds in Construction 1 and could be acceptable.

However, note that L

(2) p is still exponentially increasing, although it is much smaller than L (1) p . As a result, the number of active users to be supported simultaneously will be limited if long protocol sequences are not allowed. A further improvement is favorable and left open. There is a tradeoff between the sequence length and throughput variance.

V. PERFORMANCE EVALUATION

Investigations on the effective throughput of users with the protocol sequences from Construction 1 and 2 in slotsynchronized collision channel are conducted. Since users are unsynchronized to each other, we assume the time offset between two users is uniformly distributed in their encountered minimum period. In the simulation, we consider there are p active users with symmetric duty factor 1/p. Both individual and system throughputs are measured when the system is saturated, i.e., i r i = 1. Data are obtained after 10 5 runs with random time offsets. Since simulation results of Construction 1 and 2 are exactly the same, only one set of the data are plotted and labeled by "New". However, the plots can represent both.

Fig. 1 shows the individual throughput of users taken over sequence periods. The minimum, mean and maximum throughputs obtained from the new protocol sequences are compared with those obtained from prime sequences of (2) and a random access scheme. In the random access scheme, it is assumed that at each time slot a user will transmit a packet randomly by a probability of its duty factor 1/p. The throughput of a user in the random access scheme is taken over periods same as that of prime sequences for reference.

Comparing the performance of the new construction, prime sequences and random access, the means of their individual throughputs are the same. This is natural and expected since the mean is taken by averaging throughputs of users with uniformly distributed time offsets. One can find from Fig. 2 that the means of their system throughputs are the same as well. However, the observed ranges of throughputs as indicated by [Min, Max] are very different.

As shown in Fig. 1, a user with prime sequence can be completely blocked by other users and the minimum individual throughput is equal to zero. The random access has the same problem. On the other hand, the new protocol sequences have shown its robustness and user un-suppressibility. There cannot have enough collisions to completely block any particular user. It has completely eliminated this risk. Furthermore, as shown in Fig. 1 and2, the new protocol sequences have zero variance in both individual and system throughputs. Fig. 3 shows standard deviations in comparison. The new protocol sequences provide an extremely stable and shift invariant throughput performance in contrast to the highly fluctuated performance in the prime sequence and random access schemes. Deterministic performance guarantees are supported. The minimum, mean and maximum system throughputs from simulation in which duty factor of users = 1/p and system rate sum = 1.

It should be noted that in general the new construction has a longer sequence length, p p , than that of prime sequence, p 2 . The probability of zero individual throughput in the prime sequence and random access schemes could be smaller when measured over a longer period. Besides, the random access scheme will obtain a smaller variance in user throughputs [START_REF] Chen | A robust access protocol for wireless sensor networks[END_REF], while the difference to prime sequences is negligible. However, without loss of generality, a user in these two schemes always has a non-zero probability of being completely blocked. Moreover, although the average throughputs are the same in these three schemes, the new protocol supports a service of higher minimum throughputs generally as shown in Fig. 1 and2.

Furthermore, we compare the throughput performance between the protocol sequences of Construction 2 and that by Massey and Mathys [START_REF] Massey | The collision channel without feedback[END_REF] under this model. Both of them have the same sequence length. Numerical results show that they have the same average individual and system throughputs when measured over complete cycles of their minimum sequence periods. It is observed that the construction in [START_REF] Massey | The collision channel without feedback[END_REF] also yields zero variance in individual and system throughputs. However, when effective throughputs are considered in partial periods for practical considerations as the sequence length is exponentially increasing, there is a significant difference between the two designs. Fig. 4 shows the standard deviations of individual throughputs measured over 1/8, 1/4, 1/2 and one complete sequence periods respectively. The new construction outperforms and has a much smaller throughput fluctuation in partial periods generally. However, it should be noted that the work in [START_REF] Massey | The collision channel without feedback[END_REF] is more focus on the studies of the capacity regions, sender identification techniques and packet recovery.

It is worth pointing out that the achieved throughputs in the new design can be expressed in closed form. For a system of p symmetric users with duty factors 1/p, the individual throughput for any user j is expressible as: rj = p i=1 (1/p) i (-1) i-1 p -1 i -1 (28)

while the system throughput equals to (1 -1/p) p-1 . Due to a lack of space, the detail will be addressed elsewhere.

VI. CONCLUDING REMARKS In this paper, a class of linear congruence sequences with interesting cross-correlation properties is investigated for defining robust wireless access protocols. The analysis has also led to new designs with the following major advantages. While holding the feature of user un-suppressibility, the enhancement allows a higher rate sum equal to 1. Meanwhile, no matter how the sequences are shifted relative to one another, no one will be completely blocked. This ensures a reliable communication channel for each user even without backoff mechanisms and a feedback link for user synchronization. It does not require a centralized scheduling. Moreover, it is found that the new design has shift invariant individual and system throughputs. The "zero variance" service is capable of providing deterministic guarantees. When comparing partial period performance with [START_REF] Massey | The collision channel without feedback[END_REF], the new design has a much smaller fluctuation.

On the other hand, since the protocol sequences are deterministic, generally a receiver can explicitly address the following packets after a successfully received packet as sender's transmission time can be determined by (b, p) in the header. This is more energy efficient since continuous channel listening for packet reception can be eliminated. Besides, by the sequence periodicity, some collisions can be avoided in a predictive way to have throughput enhancement when concerned [START_REF] Chen | A robust access protocol for wireless sensor networks[END_REF]. There is also a potential of other interesting designs and applications of the resource sharing.

Let l, b 1

 1 and b 2 be integers satisfying 0 ≤ b 1 , b 2 < l, b 1 = b 2 and gcd (|b 2 -b 1 |, l) = 1, where gcd denotes the greatest common divisor. For linear congruence sequences W 1 and W 2 generated by (b 1 , l) and (b 2 , l) respectively, HW1,W2 (s) ≤ 2/l 2 = 2r 2

) 3 = 3 4

 33 = 81, while L (1) 5 = 25 4 . It should be noted that L (1) p could be very large. As a demonstration, when p = 7, L (1) 7

5 = 5 5

 55 = 3125. Comparing (27) with (22), L (2) p /L (1) p = p p /p 2(p-1) = 1/p p-2 , which indicates a big reduction in the sequence length by Construction 2. For demonstration, when p = 7, L

Fig. 1 .

 1 Fig.1. The minimum, mean and maximum individual throughputs from simulations in which duty factor of users = 1/p and system rate sum = 1.

  Fig. 2.The minimum, mean and maximum system throughputs from simulation in which duty factor of users = 1/p and system rate sum = 1.

Fig. 3 .

 3 Fig. 3. The standard deviations of individual and system throughputs are shown for comparison. "New" has zero variance for all the cases.

Fig. 4 .

 4 Fig. 4. The standard deviations of individual throughputs measured over 1/8, 1/4, 1/2 and one sequence periods are plotted respectively.


Igor Konnov

Jure Kukovec
email: jkukovec@forsyte.at

Thanh Hai Tran
email: tran@forsyte.at

BmcMT: Bounded Model Checking of TLA + Specifications with SMT

We present the development version of BmcMT-a symbolic model checker for TLA + . It finds, whether a TLA + specification satisfies an invariant candidate by checking satisfiability of an SMT formula that encodes: (1) an execution of bounded length, and (2) preservation of the invariant candidate in every state of the execution. Our tool is still in the experimental phase, due to a number of challenges posed by TLA + semantics to SMT solvers. We will discuss these challenges and our current approach to them in the talk. Our preliminary experiments show that BmcMT scales better than the standard TLA + model checker TLC for large parameter values, e.g., when a TLA + specification models a system of 10 processes, though TLC is more efficient for tiny parameters, e.g., when the system has 3 processes.

We believe that early feedback from the TLA + community will help us to focus on the most important language features and improve our tool.

Overview

Our work is motivated by the success story of software model checkers that use SAT and SMT solvers in the back-end, as well as by the work of Stephan Merz and Hernán Vanzetto on automating TLA + proofs with SMT [START_REF] Merz | Encoding TLA + into many-sorted first-order logic[END_REF]. In contrast to automated theorem provers, our goal is to develop a tool that, in principle, should work on all TLA + specifications that are accepted by TLC. Hence, to avoid quantifiers in SMT formulas, we use the following pragmatic assumptions, similar to the assumptions of TLC:

• Finite states. As in TLC, all sets, function domains, and function co-domains constructed during an execution of a TLA + specification should be finite.

• Fixed and finite constants. The user initializes all the specification parameters. Again, the parameter values should be finite.

• Restrictions on the formula structure. Under certain circumstances, we interpret an equality x = e as an assignment of the e's value to the variable x. Likewise, a membership test x ∈ S is sometimes interpreted as a non-deterministic assignment of values from the set S to the variable x. Finding such assignments symbolically, that is, without evaluating the specification, happened to be a non-trivial problem. We reported on a solution to this problem in [START_REF] Kukovec | Extracting symbolic transitions from TLA + specifications[END_REF].

In order to encode TLA + values in SMT, we are using a type system similar to [START_REF] Merz | Encoding TLA + into many-sorted first-order logic[END_REF]. However, our tool is running type inference on-the-fly: It finds the types for the initial states based on the user input; then, given the types of the values at the ith state, it finds the types of the values computed at the (i + 1)th state. Due to this approach, type inference BmcMT is fairly simple.

To translate action-level TLA + expressions to SMT, we define operational semantics over finite TLA + values. To this end, our tool computes a static layout of the data structures that may be created during an execution of a TLA + specification. This static layout overapproximates the data structures that are computed in an actual execution, whereas the precise shape of the data structures is defined by constraints within the SMT solver. We use the static layout to define operations such as set equality, which otherwise would require us to write axioms similar to [START_REF] Merz | Encoding TLA + into many-sorted first-order logic[END_REF] and thus introduce quantified formulas. Similarly, quantified TLA + expressions ∀x ∈ S. P and ∃x ∈ S. P are expanded to finite disjunctions and conjunctions over potential elements of S. By doing so, we manage to stay within the theory of QF-UFLIA, that is, quantifier-free linear integer arithmetics with uninterpreted functions.

So far, we have defined and implemented semantics of the following TLA + features:

• Logical operators, except choose and unbounded quantifiers ∀x. e and ∃x. e;

• Integer operators, including the range operator a..b for constant a and b;

• Set operators over finite sets: {e 1 , . . . , e k }, {x ∈ S : P }, {e : • Operators over tuples and records with constant domains, as well as if-then-else.

x ∈ S}, x ∈ S, X ⊂ Y , X = Y , X ∪ Y , X ∩ Y ,
We believe that most of the other TLA + operators can be encoded in SMT using our approach. However, the following operators are particularly challenging: set cardinality and sequence operators with non-constant arguments like x..y. Interestingly, these operators are not a problem for TLC, as it computes the exact variable values by state enumeration.

The development version of the tool is available at [START_REF] Konnov | APALACHE BmcMT (development version)[END_REF].

•

  subset S, and union S. Function operators over functions with finite domains and co-domains: [x ∈ S → e], f [e], [f except ![e 1 ] = e 2 ], [S → T ], domain f , and equality.

* This research supported in part by the Vienna Science and Technology Fund (WWTF) through project APALACHE (ICT15-103).


Igor Konnov
email: igor.konnov@inria.fr

Stephan Merz
email: stephan.merz@loria.fr

Model Checking of Fault-Tolerant Distributed Algorithms: from Classics towards Contemporary

Fault-tolerant distributed algorithms-such as agreement, reliable broadcast, and consensus-lie at the heart of distributed systems. Although these algorithms are tiny in comparison to the rest of the system code, they are hard to design and verify. In this short research statement, we discuss the Byzantine model checker, which was developed for automatic verification of asynchronous fault-tolerant distributed algorithms. Further, we discuss the challenges that are posed by contemporary protocols for Blockchain consensus.

Introduction

Fault-tolerant distributed algorithms are difficult to design right. Not surprisingly, they are even harder to verify. In [START_REF] Konnov | Who is afraid of Model Checking Distributed Algorithms?[END_REF], we noticed that there was a significant gap even between the textbook fault-tolerant distributed algorithms and the capabilities of the actual verification and bug finding tools, e.g., model checkers. The main challenges for model checking are as follows:

i. Lack of formal specifications: algorithms usually come in pseudo-code, and their formalization is tricky; ii. Parameterization: one has to prove an algorithm being correct for all possible system sizes, e.g., independently of how many processes are in the distributed system; iii. Faults: Since faults perturb the distributed system, they significantly increase the degree of non-determinism in the system and the global state space. In Section 2, we give a short overview of the techniques that address the agenda of [START_REF] Konnov | Who is afraid of Model Checking Distributed Algorithms?[END_REF]. In Section 3, we discuss the new challenges posed by new distributed protocols such as Blockchain consensus.

Classics: Byzantine Model Checker

The Byzantine model checker (ByMC [START_REF]ByMC: Byzantine model checker[END_REF]) verifies faulttolerant algorithms that work under the assumptions of asynchronous reliable communication: (a) a fraction of processes may fail-crash or exhibit Byzantine behavior, (b) the This research supported in part by the Vienna Science and Technology Fund (WWTF) through project APALACHE (ICT15-103).

correct processes make infinitely many steps, and (c) a message sent by a correct process is eventually received by every correct process. The examples of such algorithms are: reliable broadcast [START_REF] Srikanth | Simulating authenticated broadcasts to derive simple fault-tolerant algorithms[END_REF], consensus in one communication step [START_REF] Song | Bosco: One-step Byzantine asynchronous consensus[END_REF], atomic commitment with failure detectors [START_REF] Guerraoui | Non-blocking atomic commit in asynchronous distributed systems with failure detectors[END_REF], [START_REF]A case study of agreement problems in distributed systems: Non-blocking atomic commitment[END_REF]. Importantly, these algorithms are parameterized with: the number of processes n, the upper bound on the number of faulty processes t, the number of actual faults f ≤ t. The algorithms are resilient to faults, when the parameters satisfy the resilience condition, typically, n > 3t or n > 2t.

In ByMC, each correct process is modelled as a threshold automaton. For example, the threshold automaton in Figure 1 models the algorithm for Asynchronous Byzantine Agreement [START_REF] Bracha | Asynchronous consensus and broadcast protocols[END_REF]. The effect of sending a message to all processes is expressed by an increment of a shared variable, which stores the number of messages sent by the correct processes, such as x++ and y++ in our example. Thus, when y ≥ t + 1 holds true, a correct process could have received t + 1 messages from the correct processes. (To enforce that every correct process eventually receives at least y messages, we write fairness constraints in linear temporal logic). Byzantine processes may add-but do not have to-up to f messages, and thus the above expression becomes y ≥ t + 1 -f . The distributed system is thus modelled as a composition of threshold automata. Depending on the type of faults, we run either n -f instances (Byzantine faults), or n instances (crashes). Details on our modeling decisions and threshold automata can be found in [START_REF] Konnov | A short counterexample property for safety and liveness verification of fault-tolerant distributed algorithms[END_REF], [START_REF]What you always wanted to know about model checking of fault-tolerant distributed algorithms[END_REF].

INIT0 INIT1 ECHO READY ACCEPT x ≥ (n + t)/2 -f → x++ y ≥ t + 1 -f → x + + true → x++ x ≥ (n + t)/2 -f → y++ y ≥ t + 1 -f → y++ y ≥ 2t + 1 -f Figure 1.
A threshold automaton for Byzantine agreement [START_REF] Bracha | Asynchronous consensus and broadcast protocols[END_REF] ByMC verifies, whether safety and liveness properties hold for the systems of threshold automata, for all the combinations of parameters that satisfy the resilience condition, e.g., n > 3t. This is done by encoding the bounded model checking problem with an SMT solver. Although bounded model checking is incomplete in general, ByMC relies on the short counterexample property for threshold automata [START_REF] Konnov | A short counterexample property for safety and liveness verification of fault-tolerant distributed algorithms[END_REF], which states that it is sufficient to explore the executions of certain shapes within the precomputed bounds.

Importantly, ByMC provides the user with a counterexample, if there is an instance of the system that violates one of the properties. A counterexample is a sequence of steps by threshold automata for fixed parameters (e.g., for n = 4, t = 1, and f = 1).

Recently, the verification technique of ByMC was applied in a synthesis loop [START_REF] Lazic | Synthesis of distributed algorithms with parameterized threshold guards[END_REF], in order to automatically find the thresholds, such as t + 1 -f and 2t + 1 -f in Figure 1.

Contemporary: Challenges and Approaches

The approach of ByMC has been successful, due to good understanding of the computation model of reliable communication, which is a standard textbook material. The situation is different with the new protocols such as Blockchain consensus. In this note, we follow the layered view of Blockchain by Abraham & Malkhi [START_REF] Abraham | The blockchain consensus layer and BFT[END_REF].

Needless to say, when one considers Blockchain protocols instead of the textbook algorithms, the problems emphasized in [START_REF] Konnov | Who is afraid of Model Checking Distributed Algorithms?[END_REF] do not disappear. Most importantly, one needs a formal specification of the protocol just to start the verification efforts. Pseudo-code alone does not help when the underlying computational model is not well-understood. On top of that, Blockchain adds more challenges:

• Computational and resource thresholds. The textbook algorithms assume that the parameters n, t, and f are fixed for each run and use thresholds such as t + 1.

Blockchain protocols use other kinds of thresholds such as the amount of computational power or the amount of resources. • Hashing. Related to the thresholds, hash functions play a central role in Blockchain. • Multiple transactions. In contrast to reliable broadcast [START_REF] Srikanth | Simulating authenticated broadcasts to derive simple fault-tolerant algorithms[END_REF], one cannot reason about one Blockchain transaction in isolation, but reasons about the longest chains. • Synchrony assumptions. As the Byzantine processes may counterbalance their low computational power by incurring long delays, Blockchain assumes limits on the asynchrony in the system. In view of all these challenges combined, one would probably need years of research to invent new parameterized model checking techniques similar to [START_REF] Konnov | A short counterexample property for safety and liveness verification of fault-tolerant distributed algorithms[END_REF]. We believe that a more pragmatic approach would be to let the users specify the emerging protocols in a language that does not restrict the computational model at all. As a concrete example, we are assuming that fault-tolerant protocols are specified in TLA + [START_REF] Lamport | Specifying systems: the TLA + language and tools for hardware and software engineers[END_REF], which recently received attention of distributed system designers [START_REF] Newcombe | How Amazon web services uses formal methods[END_REF].

Having specified a protocol in TLA + , the users have two choices: write mechanical proofs with the TLA + proof system [START_REF] Cousineau | TLA + proofs[END_REF], or use a model checker such as TLC [START_REF] Yu | Model checking TLA + specifications[END_REF]. While TLC does not require much effort from the user, it is challenging for TLC to scale to complex protocols. We are currently developing the new APALACHE model checker [START_REF]APALACHE TLA + model checker (development version)[END_REF], which is using bounded model checking techniques and SMT solvers as reasoning back-ends.

Conclusions

We hope that this note will raise awareness among the research community on the need for formal specification of the emerging protocols. Such specifications are of ultimate importance for development of new verification tools.