{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:35:13Z","timestamp":1750307713136,"version":"3.41.0"},"reference-count":30,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100004956","name":"Bundesministerium f\u00fcr Verkehr, Innovation und Technologie","doi-asserted-by":"publisher","award":["812205"],"award-info":[{"award-number":["812205"]}],"id":[{"id":"10.13039\/501100004956","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002428","name":"Austrian Science Fund","doi-asserted-by":"publisher","award":["P17757"],"award-info":[{"award-number":["P17757"]}],"id":[{"id":"10.13039\/501100002428","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Auton. Adapt. Syst."],"published-print":{"date-parts":[[2009,1]]},"abstract":"<jats:p>\n            We investigate the complexity of algorithms in message-driven models. In such models, events in the computation can only be caused by message receptions, but not by the passage of time. Hutle and Widder [2005a] have shown that there is no deterministic message-driven self-stabilizing implementation of the eventually strong failure detector and thus \u03a9 in systems with uncertainty in message delays and channels of unknown capacity using only bounded space. Under stronger assumptions it was shown that even the eventually perfect failure detector can be implemented in message-driven systems consisting of at least\n            <jats:italic>f<\/jats:italic>\n            + 2 processes (\n            <jats:italic>f<\/jats:italic>\n            being the upper bound on the number of processes that crash during an execution).\n          <\/jats:p>\n          <jats:p>\n            In this article we show that\n            <jats:italic>f<\/jats:italic>\n            + 2 is in fact a lower bound in message-driven systems, even if nonstabilizing algorithms are considered. This contrasts time-driven models where\n            <jats:italic>f<\/jats:italic>\n            + 1 is sufficient for failure detector implementations.\n          <\/jats:p>\n          <jats:p>\n            Moreover, we investigate algorithms where not all processes send message, that is, are active, but some (in a predetermined set) remain passive. Here, we show that the\n            <jats:italic>f<\/jats:italic>\n            + 2 processes required for message-driven systems must be active, while in time-driven systems it suffices that\n            <jats:italic>f<\/jats:italic>\n            processes are active.\n          <\/jats:p>\n          <jats:p>We also provide message-driven implementations of \u03a9. Our algorithms are efficient in the sense that not all processes have to send messages forever, which is an improvement to previous message-driven failure detector implementations.<\/jats:p>","DOI":"10.1145\/1462187.1462191","type":"journal-article","created":{"date-parts":[[2009,2,10]],"date-time":"2009-02-10T16:42:19Z","timestamp":1234284139000},"page":"1-22","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["Optimal message-driven implementations of omega with mute processes"],"prefix":"10.1145","volume":"4","author":[{"given":"Martin","family":"Biely","sequence":"first","affiliation":[{"name":"Technische Universit\u00e4t Wien, Austria"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Josef","family":"Widder","sequence":"additional","affiliation":[{"name":"Ecole Polytechnique Technische, Universit\u00e4t Wien, Austria"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2009,2,9]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/872035.872081"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1011767.1011816"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1080\/00207729708929476"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/234533.234549"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/226643.226647"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/7531.7533"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/42282.42283"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02252954"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1002\/andp.19053221004"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDCS.2005.57"},{"key":"e_1_2_1_11_1","unstructured":"Fischer M. and Lamport L. 1982. Byzantine generals and transaction commit protocols. Tech. rep. 62 SRI International.  Fischer M. and Lamport L. 1982. Byzantine generals and transaction commit protocols. Tech. rep. 62 SRI International."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3149.214121"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/EDCC.2006.11"},{"key":"e_1_2_1_14_1","unstructured":"G\u00e4rtner F. C. and Pleisch S. 2001. (Im)possibilities of predicate detection in crash-affected systems using interrupt-style failure detectors. In Brief Announcements\u201415th International Symposium on DIStributed Computing (DISC'01) J. Welch Ed. Tech. rep. TR-01-7. Departamento de Inform\u00e1tica Faculdade de Ci\u00eancias da Universidade de Lisboa Lisboa Portugal. 7--12. http:\/\/www.di.fc.ul.pt\/publications\/di-fcul-tr-01-7_document.pdf.  G\u00e4rtner F. C. and Pleisch S. 2001. (Im)possibilities of predicate detection in crash-affected systems using interrupt-style failure detectors. In Brief Announcements\u201415th International Symposium on DIStributed Computing (DISC'01) J. Welch Ed. Tech. rep. TR-01-7. Departamento de Inform\u00e1tica Faculdade de Ci\u00eancias da Universidade de Lisboa Lisboa Portugal. 7--12. http:\/\/www.di.fc.ul.pt\/publications\/di-fcul-tr-01-7_document.pdf."},{"volume":"1151","volume-title":"Proceedings of the 10th International Workshop on Distributed Algorithms (WDAG'96)","author":"Guerraoui R.","key":"e_1_2_1_15_1"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/11795490_26"},{"volume":"9280","volume-title":"Proceedings of the 8th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS'06)","author":"Hutle M.","key":"e_1_2_1_17_1"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/TDSC.2008.24"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1073814.1073852"},{"volume-title":"Proceedings of the IASTED International Conference on Parallel and Distributed Computing and Networks (PDCN'05)","author":"Hutle M.","key":"e_1_2_1_20_1"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/359545.359563"},{"key":"e_1_2_1_22_1","unstructured":"Le Lann G. and Schmid U. 2003. How to implement a timer-free perfect failure detector in partially synchronous systems. Tech. rep. 183\/1-127 Department of Automation Technische Universit\u00e4t Wien.  Le Lann G. and Schmid U. 2003. How to implement a timer-free perfect failure detector in partially synchronous systems. Tech. rep. 183\/1-127 Department of Automation Technische Universit\u00e4t Wien."},{"volume-title":"Distributed Algorithms","author":"Lynch N.","key":"e_1_2_1_23_1"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/11561927_16"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/322186.322188"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1400751.1400815"},{"volume":"349","volume-title":"Proceedings of the 6th Annual Symposium on Theor. Aspects of Computer Science (STACS'89)","author":"Santoro N.","key":"e_1_2_1_27_1"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/28869.28876"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-39989-6_9"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/11408901_3"}],"container-title":["ACM Transactions on Autonomous and Adaptive Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1462187.1462191","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1462187.1462191","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:30:15Z","timestamp":1750253415000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1462187.1462191"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,1]]},"references-count":30,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2009,1]]}},"alternative-id":["10.1145\/1462187.1462191"],"URL":"https:\/\/doi.org\/10.1145\/1462187.1462191","relation":{},"ISSN":["1556-4665","1556-4703"],"issn-type":[{"type":"print","value":"1556-4665"},{"type":"electronic","value":"1556-4703"}],"subject":[],"published":{"date-parts":[[2009,1]]},"assertion":[{"value":"2007-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-02-09","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}