# Time complexity for synchronizer

In the field of Synchronizers on Distributed algorithms exists two type of time complexities of synchronizer $\xi$. Where $\xi$ denotes any synchronizer.

$T_\text{pulse}(\xi) = \max \left \{ t_{\max}(p+1) -t_{\max}(p)\right \}$, where $t_{\max}(p)$ is the time when the slowest of the processors has progressed to pulse $p$.

$T_\text{gap}(\xi) = \max \left \{ t(v,p+1) - t(v,p) \right \}$ among all nodes $v$ and all pulses $p$. $T_\text{gap}$ stands for the longest duration of some pulse among all nodes.

The question is what is relationship between $T_\text{pulse}$ and $T_\text{gap}$. For me it seems intuitive that $T_\text{gap} \geq T_\text{pulse}$, because $T_\text{gap}$ shows the longest duration of the slowest node on the pulse $p$, and $T_\text{pulse}$ shows the duration of the longest pulse among all nodes, which is cannot be longer than the longest duration of the slowest node.

In short, I don't have strong mathematical explanation, will appreciate for one.

-

Honestly I havent met $\xi$ synchronizer, I only know ABD, "Simple", $\alpha$, $\beta$ and $\gamma$. Could you provide some reference to $\xi$ synchronizer? – Bartek Dec 26 '12 at 22:05
Sorry, it's my mistake, $\xi$ denoting every synchronizer, the goal is to show relationship between $T_{gap}$ and $T_{pulse}$ for every synchronizer. – tam Dec 27 '12 at 5:34
Are there any additonal assumtpions about your distributed system model? Eg. how pulse messages are handled, are they prioritezed or handled after computation. Does pulse computation takes fixed time or are allowed to run for any time after pulse message. Because answer may vary depending on model assumptions. – Bartek Dec 28 '12 at 17:10
your question is not clear. I dont understand exactly what you mean by $T _{gap}$ and $T _{pulse}$. But usually, we dont study the time complexity of a "synchrnoizer" beceause there could be some random delays between pulses in asynchronous network. We usually study the message complexity of a synchrnoizer instead. – AJed Dec 28 '12 at 18:38
I don't agree. We can count time complexity for synchronizers. But under few additional assumptions. Like that message transimission time and message handling is bounded by some constant $\mu$ and $\bf pulse$ messages are handled as soon as they arrive to asynchronous process. This would allow us to see what is relation between $T_{\text{gap}}$ and $T_{\text{pulse}}$, relation would still be a little fuzzy but it will give us upper limit of relation. – Bartek Dec 29 '12 at 10:58
show 2 more comments
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 29, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9288378953933716, "perplexity_flag": "middle"}