License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.DISC.2023.30
URN: urn:nbn:de:0030-drops-191564
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/19156/
Go to the corresponding LIPIcs Volume Portal

Nataf, Raïssa ; Goren, Guy ; Moses, Yoram

Null Messages, Information and Coordination

pdf-format:
LIPIcs-DISC-2023-30.pdf (1 MB)

Abstract

This paper investigates the role that null messages play in synchronous systems with and without failures, and provides necessary and sufficient conditions on the structure of protocols for information transfer and coordination there. We start by introducing a new and more refined definition of null messages. A generalization of message chains that allow these null messages is provided, and is shown to be necessary and sufficient for information transfer in reliable systems. Coping with crash failures requires a much richer structure, since not receiving a message may be the result of the sender’s failure. We introduce a class of communication patterns called resilient message blocks, which impose a stricter condition on protocols than the silent choirs of Goren and Moses (2020). Such blocks are shown to be necessary for information transfer in crash-prone systems. Moreover, they are sufficient in several cases of interest, in which silent choirs are not. Finally, a particular combination of resilient message blocks is shown to be necessary and sufficient for solving the Ordered Response coordination problem.

BibTeX - Entry

@InProceedings{nataf_et_al:LIPIcs.DISC.2023.30,
  author =	{Nataf, Ra\"{i}ssa and Goren, Guy and Moses, Yoram},
  title =	{{Null Messages, Information and Coordination}},
  booktitle =	{37th International Symposium on Distributed Computing (DISC 2023)},
  pages =	{30:1--30:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-301-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{281},
  editor =	{Oshman, Rotem},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/19156},
  URN =		{urn:nbn:de:0030-drops-191564},
  doi =		{10.4230/LIPIcs.DISC.2023.30},
  annote =	{Keywords: null messages, fault tolerance, coordination, information flow, knowledge analysis}
}

Keywords: null messages, fault tolerance, coordination, information flow, knowledge analysis
Collection: 37th International Symposium on Distributed Computing (DISC 2023)
Issue Date: 2023
Date of publication: 05.10.2023

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI