2 Search Results for "Nataf, Raïssa"

Document
DOI: 10.4230/LIPIcs.DISC.2023.30
Null Messages, Information and Coordination

Authors: Raïssa Nataf, Guy Goren, and Yoram Moses

Published in: LIPIcs, Volume 281, 37th International Symposium on Distributed Computing (DISC 2023)

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.
Cite as

Raïssa Nataf, Guy Goren, and Yoram Moses. Null Messages, Information and Coordination. In 37th International Symposium on Distributed Computing (DISC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 281, pp. 30:1-30:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2023.30},
  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}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2022.49
Brief Announcement: Null Messages, Information and Coordination

Authors: Raïssa Nataf, Guy Goren, and Yoram Moses

Published in: LIPIcs, Volume 246, 36th International Symposium on Distributed Computing (DISC 2022)

Abstract
This paper investigates how null messages can transfer information in fault-prone synchronous systems. The notion of an f-resilient message block is defined and is shown to capture the fundamental communication pattern for knowledge transfer. In general, this pattern combines both null messages and explicit messages. It thus provides a fault-tolerant extension of the classic notion of a message-chain. Based on the above, we provide tight necessary and sufficient characterizations of the generalized communication patterns that can serve to solve the distributed tasks of (nice-run) Signalling and Ordered Response.
Cite as

Raïssa Nataf, Guy Goren, and Yoram Moses. Brief Announcement: Null Messages, Information and Coordination. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 49:1-49:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{nataf_et_al:LIPIcs.DISC.2022.49,
  author =	{Nataf, Ra\"{i}ssa and Goren, Guy and Moses, Yoram},
  title =	{{Brief Announcement: Null Messages, Information and Coordination}},
  booktitle =	{36th International Symposium on Distributed Computing (DISC 2022)},
  pages =	{49:1--49:3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-255-6},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{246},
  editor =	{Scheideler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2022.49},
  URN =		{urn:nbn:de:0030-drops-172409},
  doi =		{10.4230/LIPIcs.DISC.2022.49},
  annote =	{Keywords: null messages, fault tolerance, coordination, information flow}
}
  • Refine by Author
  • 2 Goren, Guy
  • 2 Moses, Yoram
  • 2 Nataf, Raïssa

  • Refine by Classification
  • 2 Computing methodologies → Reasoning about belief and knowledge
  • 2 Theory of computation → Distributed algorithms

  • Refine by Keyword
  • 2 coordination
  • 2 fault tolerance
  • 2 information flow
  • 2 null messages
  • 1 knowledge analysis

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2022
  • 1 2023

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact