{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,4]],"date-time":"2022-04-04T22:00:48Z","timestamp":1649109648902},"reference-count":22,"publisher":"Cambridge University Press (CUP)","issue":"4","license":[{"start":{"date-parts":[[2008,9,12]],"date-time":"2008-09-12T00:00:00Z","timestamp":1221177600000},"content-version":"unspecified","delay-in-days":4303,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[1996,12]]},"abstract":"<jats:p>We consider the problem of broadcasting in an<jats:italic>n<\/jats:italic>\u2013node hypercube whose links and nodes fail independently with given probabilities p &lt; 1 and q &lt; 1, respectively. Information held in a fault-free node, called the<jats:italic>source<\/jats:italic>, has to reach all other fault-free nodes. Messages may be directly transmitted to adjacent nodes only, and every node may communicate with at most one neighbour in a unit of time. A message can be transmitted only if both communicating neighbours and the link joining them are fault-free. For parameters<jats:italic>p<\/jats:italic>and<jats:italic>q<\/jats:italic>satisfying (1 \u2013<jats:italic>p<\/jats:italic>)(1 \u2013<jats:italic>q<\/jats:italic>) \u227d 0.99 (e.g.<jats:italic>p<\/jats:italic>=<jats:italic>q<\/jats:italic>= 0.5%), we give an algorithm working in time<jats:italic>O<\/jats:italic>(log<jats:italic>n<\/jats:italic>) and broadcasting source information to all fault-free nodes with probability exceeding 1 \u2013<jats:italic>cn<\/jats:italic><jats:sup>-e<\/jats:sup>for some positive constant<jats:italic>\u03b5, c<\/jats:italic>depending on<jats:italic>p<\/jats:italic>and<jats:italic>q<\/jats:italic>but not depending on<jats:italic>n<\/jats:italic>.<\/jats:p>","DOI":"10.1017\/s0963548300002108","type":"journal-article","created":{"date-parts":[[2008,9,12]],"date-time":"2008-09-12T11:13:14Z","timestamp":1221217994000},"page":"337-350","source":"Crossref","is-referenced-by-count":4,"title":["Reliable Broadcasting in Hypercubes with Random Link and Node Failures"],"prefix":"10.1017","volume":"5","author":[{"given":"Bogdan S.","family":"Chlebus","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Krzysztof","family":"Diks","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andrzej","family":"Pelc","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2008,9,12]]},"reference":[{"key":"S0963548300002108_ref010","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230220505"},{"key":"S0963548300002108_ref016","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230180406"},{"key":"S0963548300002108_ref022","doi-asserted-by":"publisher","DOI":"10.1145\/2465.2467"},{"key":"S0963548300002108_ref015","volume-title":"Hypercube Multiprocessors","author":"Heath","year":"1988"},{"key":"S0963548300002108_ref020","doi-asserted-by":"publisher","DOI":"10.1109\/12.9743"},{"key":"S0963548300002108_ref008","doi-asserted-by":"publisher","DOI":"10.1137\/0405025"},{"key":"S0963548300002108_ref006","first-page":"266","article-title":"Optimal broadcasting in faulty hypercubes","author":"Chlebus","year":"1991","journal-title":"Proc. 21st Int. Symp. on Fault-Tolerant Computing"},{"key":"S0963548300002108_ref021","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(89)90007-3"},{"key":"S0963548300002108_ref019","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(91)90174-G"},{"key":"S0963548300002108_ref009","doi-asserted-by":"publisher","DOI":"10.1214\/aoap\/1177005440"},{"key":"S0963548300002108_ref003","doi-asserted-by":"publisher","DOI":"10.1137\/0607002"},{"key":"S0963548300002108_ref002","doi-asserted-by":"crossref","first-page":"210","DOI":"10.1109\/FTCS.1990.89368","article-title":"Strategies for reconfiguring hypercubes under faults","author":"Banerjee","year":"1990","journal-title":"Proc. 20th Int. Symp. on Fault-Tolerant Computing"},{"key":"S0963548300002108_ref001","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(79)90045-X"},{"key":"S0963548300002108_ref012","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(90)90214-I"},{"key":"S0963548300002108_ref004","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(88)90037-6"},{"key":"S0963548300002108_ref018","doi-asserted-by":"publisher","DOI":"10.1137\/0221010"},{"key":"S0963548300002108_ref013","first-page":"274","article-title":"Reconfiguring a hypercube in the presence of faults","author":"Hastad","year":"1987","journal-title":"Proc. 19th Ann. Symp. on Theory of Computing"},{"key":"S0963548300002108_ref011","doi-asserted-by":"publisher","DOI":"10.1137\/0608036"},{"key":"S0963548300002108_ref014","first-page":"251","article-title":"Fast computation using faulty hypercubes","author":"Hastad","year":"1989","journal-title":"Proc. 21st Ann. Symp. on Theory of Computing"},{"key":"S0963548300002108_ref017","doi-asserted-by":"publisher","DOI":"10.1137\/0221026"},{"key":"S0963548300002108_ref007","first-page":"978","article-title":"Reliable gossip schemes with random link failures","author":"Diks","year":"1990","journal-title":"Proc. 28th Ann. Allerton Conf. on Comm. Control and Comp."},{"key":"S0963548300002108_ref005","first-page":"332","article-title":"Sparse networks supporting efficient reliable broadcasting","volume":"1","author":"Chlebus","year":"1994","journal-title":"Nordic J. on Computing"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548300002108","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,8]],"date-time":"2020-05-08T06:57:09Z","timestamp":1588921029000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548300002108\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996,12]]},"references-count":22,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1996,12]]}},"alternative-id":["S0963548300002108"],"URL":"https:\/\/doi.org\/10.1017\/s0963548300002108","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[1996,12]]}}}