{"entities":{"Q1098276":{"pageid":1109028,"ns":120,"title":"Item:Q1098276","lastrevid":66125898,"modified":"2026-04-12T07:43:24Z","type":"item","id":"Q1098276","labels":{"en":{"language":"en","value":"On the costs of self-stabilization"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4037173"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098276$C14BB10C-D4C0-40A9-9221-7618A46BB3B1","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"dfb6696f027a1d7e10791a64414246566293ad9c","datavalue":{"value":{"text":"On the costs of self-stabilization","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1098276$4D36ECC9-549D-4CCC-9536-59B885015B23","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"b77b639521eae800c915292cc068a92323ee512c","datavalue":{"value":"0636.68020","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1098276$D0C5860D-92EF-409B-BF7B-F1874424D1A8","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"46e127ea5db39fe184149678572cb584b9a74376","datavalue":{"value":"10.1016/0020-0190(87)90155-4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1098276$6C43B4C6-2D46-4CAC-BC97-0CD96DB466D4","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"f2e4a19114a38089dbb669425d70a97055d6bedf","datavalue":{"value":{"entity-type":"item","numeric-id":1098275,"id":"Q1098275"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098276$E81B639C-EB69-4B95-8BAA-668B7EA45ADB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"2e6160b1afa79a7d6f2e719b560caa692a1b0be9","datavalue":{"value":{"entity-type":"item","numeric-id":876701,"id":"Q876701"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098276$9461EC62-66BA-4BCA-9F1B-FCBE73AB28E4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"956f360c7200d34ee35046e3c320bd8b33250e32","datavalue":{"value":{"entity-type":"item","numeric-id":455972,"id":"Q455972"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098276$EA2DE1D1-8CC6-4C79-849F-4D2DCC7B3DDB","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"52fa7d44b58d0511cb8993765bd916aef86052d8","datavalue":{"value":{"entity-type":"item","numeric-id":63092,"id":"Q63092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098276$8C13068D-E33E-43C6-9296-4EFF8BFBA299","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5ae48c61eed19d1e1e1f33f9255d5b329362d064","datavalue":{"value":{"time":"+1987-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1098276$0000D174-779C-46A8-BC7E-9391F80EDEFF","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"4b575e36c0e6f44bde9c6ba8342797843a6f3e2a","datavalue":{"value":"The Dijkstra recovery algorithms for a distributed ring of loosely coupled processors that have entered an illegal state are based on message exchanges that implement the property of self-stabilization. One of these is the k-state algorithm, which depends on one of the processors, called bottom, to be distinct in its behaviour from the others. The processors change their labelling such that regardless of the initial state (labellings) of the processors, they are guaranteed to arrive at a legitimate state. In each round, a central demon chooses a processor which may initiate a message exchange, depending on its labelling relationship to its neighbour.    This paper addresses the analysis of the k-state algorithm with respect to the expected number of message passes and the expected number of rounds, given that some rounds will not cause messages to be exchanged. The analysis uses a sub-problem within the k-state algorithm, that of not permitting the bottom processor to be relabelled. Thus the expected behaviour of the k-state algorithm is bounded by the results given by the analysis of this sub-problem, which is shown to be \\(O(n^{1.5})\\) for the expected number of messages and \\(O(n^ 2)\\) for the expected number of rounds. The conclusion is that this distributed robustness algorithm which continuously monitors stability, is expensive to implement.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1098276$53890D98-44C1-4F41-9EE5-46E7C0BD87EB","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"ec3769495799f08479987ac368adf64f125a2b66","datavalue":{"value":"68N25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1098276$27273308-7079-4CCD-89B1-00CFBC768E72","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1098276$6CFB19E6-7FCC-4066-84BA-83BCE6A68C0A","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b894a24ace90acf6d90978a8583fe22a73b2d849","datavalue":{"value":"4037173","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1098276$1BE75564-605D-400D-9772-373E263F19A4","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e225ac4aec700ae2c67cab0cb7802b0627e7a3da","datavalue":{"value":"distributed system","type":"string"},"datatype":"string"},"type":"statement","id":"Q1098276$B2525431-B52E-4444-8E31-9BD820176AA6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b22f452301296ce1fd570302777b983185c9d12b","datavalue":{"value":"Concurrent programming","type":"string"},"datatype":"string"},"type":"statement","id":"Q1098276$D254BC9D-325F-4DF3-9359-6E1EB33BA13B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"90bc349d6d55eb8026148892e900ce256ffdd986","datavalue":{"value":"analysis of algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1098276$276D6FBA-5791-4BB0-BCB9-CCDB33D50C69","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5cfc79edf190778c24fdbd9385cfe925d57fbdd6","datavalue":{"value":"reliability","type":"string"},"datatype":"string"},"type":"statement","id":"Q1098276$52A3C60A-ADA1-4C68-BAC2-20DDEAE988DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ecbe8e4fe613e941483e8825364cef96a8cb555e","datavalue":{"value":"Dijkstra recovery algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1098276$E81A805B-FD77-47B3-9D3B-47284B9EC7BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e5037dad296a241cfa4d4139d1f63309727fd86f","datavalue":{"value":"self-stabilization","type":"string"},"datatype":"string"},"type":"statement","id":"Q1098276$7F3217FE-2C28-4090-8EFC-06B9ECE6B280","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4a6d5f441d931f6d32660d9ead364de0d8b7b44a","datavalue":{"value":"labellings","type":"string"},"datatype":"string"},"type":"statement","id":"Q1098276$D2666C32-BD93-4BF1-8AE4-6F6DF89FF3A7","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098276$4B9754DC-E2BC-44FB-B442-2DAC50D8BB17","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"4d76d39c60c885fd452026e92ac4025527fb57ed","datavalue":{"value":"https://doi.org/10.1016/0020-0190(87)90155-4","type":"string"},"datatype":"url"},"type":"statement","id":"Q1098276$25645772-B98E-424F-8DFC-7A84762A28A8","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"4e3f5609042f337b8ec4ecfb6d8a39f16c569ec6","datavalue":{"value":"W1993055948","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1098276$F05DC8FC-5B74-4A47-BB0B-C11689353687","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"21a8eb34c519834b5b923e52b9f7343a721bfe4a","datavalue":{"value":{"entity-type":"item","numeric-id":4061976,"id":"Q4061976"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098276$E9A498A8-949C-4075-A9D5-F0C6503123D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c9539532d16bcb82516fae2db58a1eb7e9c6ca7b","datavalue":{"value":{"entity-type":"item","numeric-id":5538132,"id":"Q5538132"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098276$F034E486-68D4-412E-9532-D811CA27CEF4","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"159bc2f3edacf55921cff5859dd8bb8aa9f3890e","datavalue":{"value":{"entity-type":"item","numeric-id":913475,"id":"Q913475"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"02cfc6471e2258912697a6b973fbce5a7dda5dda","datavalue":{"value":{"amount":"+0.864734","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1098276$D0BC6762-32A3-401E-95A0-EEE979BC0E38","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8bd8ce7b7d8bb3df5f66494eb665c3d45500eef6","datavalue":{"value":{"entity-type":"item","numeric-id":2028746,"id":"Q2028746"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e007bce99db29b46895f326ae4184199cbd4b074","datavalue":{"value":{"amount":"+0.83450377","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1098276$39B57A48-893D-4393-B498-177000A0A29C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5ecbb6e3d60ca7c84b5d514503458bb57ab80305","datavalue":{"value":{"entity-type":"item","numeric-id":2782251,"id":"Q2782251"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"05f0a95096098c61b2cad62c52dcc2e94be6b140","datavalue":{"value":{"amount":"+0.83189595","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1098276$173C60B8-314D-4833-A0BA-C5569F578F56","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2a7274f7c3be4948146bea21c6cc6d91934b7377","datavalue":{"value":{"entity-type":"item","numeric-id":1083187,"id":"Q1083187"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"132a5eb186f6debd89acb2a7fe083357d4387fad","datavalue":{"value":{"amount":"+0.8149065","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1098276$D98EE455-F64F-4D1D-932B-5A883C5B1E60","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0403112f4c2c7f8d2bc1943bda78fc99dacd0ef2","datavalue":{"value":{"entity-type":"item","numeric-id":4363321,"id":"Q4363321"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7aa263a052e3a89d64382ee39ea28647d3df2f5c","datavalue":{"value":{"amount":"+0.81109345","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1098276$7B779C75-3BC0-4B73-89CC-CBC3AEDBD9D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2afdcf32015ace4f98c165a31f7b5b208b3197f2","datavalue":{"value":{"entity-type":"item","numeric-id":3691363,"id":"Q3691363"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0bf7feada3243ca186d6176bd012c338b685eaab","datavalue":{"value":{"amount":"+0.80862296","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1098276$2C11FCCC-C3AD-487E-87B3-6AA81396A872","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f86a797e3a71dc891a76645abc2ff0c7632e98d7","datavalue":{"value":{"entity-type":"item","numeric-id":1959435,"id":"Q1959435"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c7d407637909b291bac22269a29f7cb7282f214f","datavalue":{"value":{"amount":"+0.80710167","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1098276$1AB1B7FA-8480-423C-819B-0FA24271A124","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"01b580edd2e2dd4dce281986070e5fca3cce08a7","datavalue":{"value":{"entity-type":"item","numeric-id":701152,"id":"Q701152"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e9cb7222e9842d360475d19dce5457359e61b4e1","datavalue":{"value":{"amount":"+0.80491626","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1098276$1CFCA6F8-7E27-404D-97EE-F81BA431879E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On the costs of self-stabilization","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_the_costs_of_self-stabilization"}}}}}