{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T12:12:17Z","timestamp":1781007137692,"version":"3.54.1"},"reference-count":0,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","license":[{"start":{"date-parts":[[2021,9,17]],"date-time":"2021-09-17T00:00:00Z","timestamp":1631836800000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001665","name":"French National Research Agency","doi-asserted-by":"crossref","award":["ANR-16-CE25-0006"],"award-info":[{"award-number":["ANR-16-CE25-0006"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:p>In distributed computing, multiple processes interact to solve a problem\ntogether. The main model of interaction is the message-passing model, where\nprocesses communicate by exchanging messages. Nevertheless, there are several\nmodels varying along important dimensions: degree of synchrony, kinds of\nfaults, number of faults... This variety is compounded by the lack of a general\nformalism in which to abstract these models. One way to bring order is to\nconstrain these models to communicate in rounds. This is the setting of the\nHeard-Of model, which captures many models through predicates on the messages\nsent in a round and received on time. Yet, it is not easy to define the\npredicate that captures a given operational model. The question is even harder\nfor the asynchronous case, as unbounded message delay means the implementation\nof rounds must depend on details of the model. This paper shows that\ncharacterising asynchronous models by heard-of predicates is indeed meaningful.\nThis characterization relies on delivered predicates, an intermediate\nabstraction between the informal operational model and the heard-of predicates.\nOur approach splits the problem into two steps: first extract the delivered\nmodel capturing the informal model, and then characterize the heard-of\npredicates that are generated by this delivered model. For the first part, we\nprovide examples of delivered predicates, and an approach to derive more. It\nuses the intuition that complex models are a composition of simpler models. We\ndefine operations like union, succession or repetition that make it easier to\nderive complex delivered predicates from simple ones while retaining\nexpressivity. For the second part, we formalize and study strategies for when\nto change rounds. Intuitively, the characterizing predicate of a model is the\none generated by a strategy that waits for as much messages as possible,\nwithout blocking forever.<\/jats:p>","DOI":"10.46298\/lmcs-17(3:26)2021","type":"journal-article","created":{"date-parts":[[2021,9,20]],"date-time":"2021-09-20T13:56:55Z","timestamp":1632146215000},"source":"Crossref","is-referenced-by-count":2,"title":["Characterization and Derivation of Heard-Of Predicates for Asynchronous Message-Passing Models"],"prefix":"10.46298","volume":"Volume 17, Issue 3","author":[{"given":"Adam","family":"Shimi","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Aur\u00e9lie","family":"Hurault","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Philippe","family":"Queinnec","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"25203","published-online":{"date-parts":[[2021,9,17]]},"container-title":["Logical Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/lmcs.episciences.org\/8496\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/lmcs.episciences.org\/8496\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,20]],"date-time":"2023-06-20T20:18:29Z","timestamp":1687292309000},"score":1,"resource":{"primary":{"URL":"https:\/\/lmcs.episciences.org\/6929"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,9,17]]},"references-count":0,"URL":"https:\/\/doi.org\/10.46298\/lmcs-17(3:26)2021","relation":{"has-preprint":[{"id-type":"arxiv","id":"2011.12879v2","asserted-by":"subject"},{"id-type":"arxiv","id":"2011.12879v1","asserted-by":"subject"}],"is-same-as":[{"id-type":"arxiv","id":"2011.12879","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.2011.12879","asserted-by":"subject"}]},"ISSN":["1860-5974"],"issn-type":[{"value":"1860-5974","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,9,17]]},"article-number":"6929"}}