{"entities":{"Q692907":{"pageid":694756,"ns":120,"title":"Item:Q692907","lastrevid":63546207,"modified":"2026-04-11T13:54:01Z","type":"item","id":"Q692907","labels":{"en":{"language":"en","value":"How to prove impossibility under global fairness: on space complexity of self-stabilizing leader election on a population protocol model"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6113532"}},"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":"Q692907$58F53B0F-B550-4595-94B5-F5099E29A82D","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"917517c6fa0318e276d514731dd502239a78051e","datavalue":{"value":{"text":"How to prove impossibility under global fairness: on space complexity of self-stabilizing leader election on a population protocol model","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q692907$E146D555-DAF6-47CA-85FF-04152A4B1599","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"ed6071a985b12f0544d533f1179f37c4cbf2e119","datavalue":{"value":"1281.68049","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q692907$DC7EE563-9280-4DF1-8B00-167D0E496A72","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"011ca6dce312d685188f08c79b1e4649c399e6a7","datavalue":{"value":{"entity-type":"item","numeric-id":692906,"id":"Q692906"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q692907$52AEF3B0-D4D6-42CC-800F-E367FF67DBD2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"926abee696426210c8ab1cac519cb69075f183cf","datavalue":{"value":{"entity-type":"item","numeric-id":313807,"id":"Q313807"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q692907$B9DFB6FE-992E-4232-94EC-E630D39C087A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"c9bab2f6789e7cf606a7ed6fe41b1d79e4c3b9a9","datavalue":{"value":{"entity-type":"item","numeric-id":418775,"id":"Q418775"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q692907$649FC513-55E8-4E5B-8807-D0134690AB8B","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"b559743f011d61696dff04b2ecd3408df2541e49","datavalue":{"value":{"entity-type":"item","numeric-id":169698,"id":"Q169698"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q692907$B5259524-FD2A-49E4-B859-CA231A9DDA48","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"dff58ac691764932e2d1883ecce372141126289a","datavalue":{"value":{"time":"+2012-12-06T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q692907$BB7F6CDC-C41C-40CA-8FA7-4F04EDE287EC","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"10424acb6c3dbc6cb0cff9421639639a70896a40","datavalue":{"value":"Population protocols is one of the distributed computing models where a number of mobile agents change their states by pairwise interactions. A self-stabilizing protocol ensures that the system converges to the desired behavior regardless its initial configuration. A leader election allows to distinguish a single agent with the final state ELECTED, the state of the other agents is NON-ELECTED. Global fairness guarantees the occurrence of any possible transition.  This paper proves that under the assumption of global fairness, no protocol using only \\(n-1\\) states (where \\(n\\) is the number of agents) can solve the self-stabilizing leader election in complete interaction graphs.","type":"string"},"datatype":"string"},"type":"statement","id":"Q692907$A27D782C-0011-4BD0-B3CB-5C16E45138B3","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"e58c6dffa2cb5b51020de9c6757ee2fa56512d39","datavalue":{"value":{"entity-type":"item","numeric-id":690236,"id":"Q690236"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q692907$568AC3BA-A3CA-4811-952E-D15ABD24928C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"62ff42057022552eaa82447a5a1563ef3bf93acd","datavalue":{"value":"68M14","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q692907$9EA0470F-C06B-4E6F-9E38-3BFB184745DC","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"1d3340ea3ee5fc0d631b580698cebb68aa4ee627","datavalue":{"value":"6113532","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q692907$682D9FCD-003F-4525-ACB0-92F6346104F6","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"30e18b5f74879d022f2f865fc8c3928cd3c59ce0","datavalue":{"value":"distributed algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q692907$147D70E0-C602-4AA1-9FD1-329D0DBDFC9B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e4b342bface8af7dbc6ff44690c7a82174759179","datavalue":{"value":"leader election","type":"string"},"datatype":"string"},"type":"statement","id":"Q692907$50868044-72FE-4D86-9040-362A197DEA27","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e3b804050ba9014ee47183028d56a24833d5a3bb","datavalue":{"value":"population protocol","type":"string"},"datatype":"string"},"type":"statement","id":"Q692907$0A06F872-A28D-43DF-BF6E-D012E50DE866","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e5037dad296a241cfa4d4139d1f63309727fd86f","datavalue":{"value":"self-stabilization","type":"string"},"datatype":"string"},"type":"statement","id":"Q692907$5A65CD5D-3F1C-4D7F-8975-09BCA936A1D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3f60ae39507c560d09ff93d4d0dd252e904da670","datavalue":{"value":"global fairness","type":"string"},"datatype":"string"},"type":"statement","id":"Q692907$0E4C2C49-E637-42F9-9133-50F9B4EF9A42","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":"Q692907$93354F82-E58E-4765-AEBB-2BE77658E096","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"b1450c2863da168159dfca20f02e49e0fc2c356a","datavalue":{"value":"https://doi.org/10.1007/s00224-011-9313-z","type":"string"},"datatype":"url"},"type":"statement","id":"Q692907$60524889-92AD-4D61-BBB9-9A73F560F454","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"0310405f1f2c95de0958c29c50a8ab9766224797","datavalue":{"value":"W2092232879","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q692907$CCAD9540-B056-41F4-B910-9DC0CD7A1A3B","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"0371d3c582f0c784ecc91a277cc4c5ff16fb0fa4","datavalue":{"value":{"entity-type":"item","numeric-id":2375293,"id":"Q2375293"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q692907$16E38009-C330-412E-8E5E-8F331A625668","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e51eb9aaaf072720781654561733f0774148451e","datavalue":{"value":{"entity-type":"item","numeric-id":5177291,"id":"Q5177291"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q692907$9020ECC0-CD06-4624-A664-E8B97F595515","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"82ad3d2532c8ad09aa5d9d41b66a341a80e60642","datavalue":{"value":{"entity-type":"item","numeric-id":3523196,"id":"Q3523196"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q692907$59C207EB-D9AD-4520-B062-12A518BB3D49","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"94a34ef9306bdded0ee4f49da10d7542d8abbde8","datavalue":{"value":{"entity-type":"item","numeric-id":1954251,"id":"Q1954251"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q692907$C7122C5F-3CBB-4C26-B1A1-7096ECBEAF42","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3a21c3a25a483b0dac91ed31f35b71d371e25b3c","datavalue":{"value":{"entity-type":"item","numeric-id":3396623,"id":"Q3396623"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q692907$B942D6AF-C6BC-4D6A-875C-3EA7C389EC19","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0705531fdb61b6e3f34fc69ed410a55e12d5af65","datavalue":{"value":{"entity-type":"item","numeric-id":3523199,"id":"Q3523199"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q692907$9E5CED2B-C392-4ACD-B219-B3686E5D1987","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"958444e33af654c6df7820011a79a34e32b4a3a9","datavalue":{"value":"10.1007/S00224-011-9313-Z","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q692907$4461490F-E478-4792-9476-CEE5B8154B46","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"56a53ad590a532c988ebb8cfc5ecb60b6c4de995","datavalue":{"value":{"entity-type":"item","numeric-id":3408164,"id":"Q3408164"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"de89906eda49af1c7b2c2d05636cf8fd3604ab36","datavalue":{"value":{"amount":"+0.9001430869102478","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q692907$11A2ACE7-439B-4EFD-A3EB-70D2B76CD24B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a65ac75cd60ef834efa174c8d30cb2d772d23fe6","datavalue":{"value":{"entity-type":"item","numeric-id":6487917,"id":"Q6487917"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c354c9587fe25298e73b61bf67fbc824ea05d167","datavalue":{"value":{"amount":"+0.8043585419654846","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q692907$3A55889B-37BB-4CDB-A19B-77CE6404A45F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8a87d2c35158df15f4270e054c2b774edf5d480f","datavalue":{"value":{"entity-type":"item","numeric-id":3408179,"id":"Q3408179"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"270ad2850e6e41b7e84ad93e276a4e59961a6ab1","datavalue":{"value":{"amount":"+0.7975971698760986","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q692907$AB8828E5-11EB-4311-BA16-5CFE5C223531","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"How to prove impossibility under global fairness: on space complexity of self-stabilizing leader election on a population protocol model","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/How_to_prove_impossibility_under_global_fairness:_on_space_complexity_of_self-stabilizing_leader_election_on_a_population_protocol_model"}}}}}