{"entities":{"Q1901690":{"pageid":1912432,"ns":120,"title":"Item:Q1901690","lastrevid":71746728,"modified":"2026-04-14T00:16:34Z","type":"item","id":"Q1901690","labels":{"en":{"language":"en","value":"Bounded delay for a free address"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 814145"}},"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":"Q1901690$BD7CA15F-F073-48CE-9240-B25E9FD9945A","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"a5437641878a752da8c5abf74050f3d190063558","datavalue":{"value":{"text":"Bounded delay for a free address","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1901690$14008DB2-B5A8-4414-8834-0D7E61865BB2","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"7346669e265ea930183c2634fe4fd2af977b00bb","datavalue":{"value":"0849.68031","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1901690$3FA239E7-F659-478E-A8F4-1D20D49844E1","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"d19214d6ab96c1b95faaaf223b83bab4e859315a","datavalue":{"value":{"entity-type":"item","numeric-id":216155,"id":"Q216155"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1901690$3C2F5E78-1480-4509-A1A1-1FEA7D260D7E","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"7d0f02e85530cd06ceb2c58a40dc9c2e0258e194","datavalue":{"value":{"entity-type":"item","numeric-id":161641,"id":"Q161641"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1901690$8E64B55A-1647-4A4B-8816-400E2A4A29EF","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"d00fe8bfda3ed2cfe20a514de7a7e433b0f6c2b5","datavalue":{"value":{"time":"+1995-11-19T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1901690$5EAA3B00-86C6-4900-8E43-7777E467EDD2","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"5d527007e9c1a91686875654f61877646a629489","datavalue":{"value":"https://pure.rug.nl/ws/files/3243828/1996ActaInfHesselink.pdf","type":"string"},"datatype":"url"},"type":"statement","id":"Q1901690$BCA3CC64-B747-4737-BD9F-C217A5240A2F","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"56205bc8c9d47b3cda454217eae408736a285ea2","datavalue":{"value":"The paper treats a problem of concurrent processes that communicate by means of shared variables. The problem is to let \\(n\\) processes concurrently and repeatedly search for free addresses in a range of \\(m\\) addresses. The search must be wait-free: a searching process finds an address in a bounded number of steps. Three solutions are presented. The first one has large atomic actions. The second one is only correct if \\(m \\geq (r + 1) \\cdot n\\) where \\(r\\) is the maximum number of used addresses. The third solution is always partially correct. It is wait-free if \\(m > r + 2 \\cdot n\\). This solution has a worst-case waiting time quadratic in \\(n\\) and an amortized waiting time linear in \\(n\\), even linear in the number of active processes. Invariants are used to prove the correctness of the algorithms.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1901690$6BA1F05A-F029-4A61-BDE2-CA1392AFE8EA","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"35bbdcbda53152c249a7f99650e19b5ef62999f2","datavalue":{"value":"68Q10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1901690$548CAC29-B031-4783-A2B7-72EC65648DE8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1de3565cfd3393000dd87ca545f95ff84d4c1446","datavalue":{"value":"68W10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1901690$2E9CDCA3-82A3-4E4E-9350-6A8F0689452E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1901690$9FD5317F-348D-4B7B-959C-448AB4FBE15D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"3f97694d44af155a68434cb72eabc6a4d5dd5227","datavalue":{"value":"68P10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1901690$81266690-1637-4128-AFA6-6E198073B6C4","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"9d76ff14fbb891c96aa71871e5c18c33815e316c","datavalue":{"value":"814145","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1901690$A47346B4-D7CD-4414-928C-5B39DBBCECE7","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7ec1cd30b157f29f21fa9c7f32f0ba7ee7f6d481","datavalue":{"value":"address searching","type":"string"},"datatype":"string"},"type":"statement","id":"Q1901690$C8934C05-E7C5-485B-8341-E6F06B9E3D74","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"85c99e8a47e8715cd49e1b1de604869efca49ca5","datavalue":{"value":"correctness of algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1901690$753968C3-635D-4122-B2FD-F99A1881B2C6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"09b99ae733070d3d1855ae2b169bdb873a71f7e3","datavalue":{"value":"concurrent processes","type":"string"},"datatype":"string"},"type":"statement","id":"Q1901690$0F305822-9486-4027-AF20-A4CA3F3FB19F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3a16276a11ee5058dcf653a3c32fc3450286c039","datavalue":{"value":"atomic actions","type":"string"},"datatype":"string"},"type":"statement","id":"Q1901690$D17F77D3-A754-465F-8DEB-F21752759093","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"2e07b63a7544a6d7c83390f82ddae368b77e124c","datavalue":{"value":{"entity-type":"item","numeric-id":19570,"id":"Q19570"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1901690$A5AE5CD1-8761-4C50-8A8D-A26896E7232A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1463","hash":"17cfe6afe68a54e81dc559ef2cd5a702765207b0","datavalue":{"value":{"entity-type":"item","numeric-id":25375,"id":"Q25375"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1901690$456FA816-1361-43F4-931F-BA28CB27DE6C","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":"Q1901690$3A104A67-D2BC-4162-B964-E8896B90195C","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"1b0b84eb985dfc201d60514ac8b2bc1413155ef7","datavalue":{"value":"W2109580929","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1901690$1E3888D8-2D88-4FB5-9FC3-7FC87275C1FE","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"71372fdcb48501c76512b55e87a54968a7919d1f","datavalue":{"value":{"entity-type":"item","numeric-id":3999717,"id":"Q3999717"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1901690$22DD8567-AE4F-4AA3-B893-686033741D8C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8dc130e60aed51c89205a9df57c6cb8c74befd93","datavalue":{"value":{"entity-type":"item","numeric-id":3477940,"id":"Q3477940"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1901690$5FD5C64B-D8CC-4FB0-A184-F9126AD2DD63","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4245ea564cd3b6c0d0e92107206c02dccb350ad8","datavalue":{"value":{"entity-type":"item","numeric-id":5365157,"id":"Q5365157"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1901690$EE4A3390-C2B9-417C-AE61-9D28241021B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0aad2711eb9c64a58dada485191047b8af29959d","datavalue":{"value":{"entity-type":"item","numeric-id":4040283,"id":"Q4040283"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1901690$8EC824C2-C976-4D65-9893-565541435688","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"090e4b104dd3f76f7e7cbd674cb41b2227a87ff1","datavalue":{"value":{"entity-type":"item","numeric-id":4692502,"id":"Q4692502"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1901690$BBB68AA0-05BA-418D-9A75-6003F09B621D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"382097be7fd0fb9d3af9de751d9a984d2d930bc1","datavalue":{"value":{"entity-type":"item","numeric-id":5136979,"id":"Q5136979"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1901690$B2666D92-83FC-43BB-A6B4-42B6AFB30C61","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"796364eeefb9789a01eab3a144d0337d6c23ee01","datavalue":{"value":{"entity-type":"item","numeric-id":1219675,"id":"Q1219675"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1901690$C0983867-EEB1-4681-8003-2581409C450D","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"593f249a908bf3b72feca1ce25c664062e0f9b80","datavalue":{"value":"10.1007/S002360050042","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1901690$00D4684E-752B-42A1-A79B-A13F5C48B67E","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2d27e67aa91987e741d605f0ed24d8d7298fa5aa","datavalue":{"value":{"entity-type":"item","numeric-id":2218425,"id":"Q2218425"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cfddbd62868a4168f6efdaacec6b875dad500e90","datavalue":{"value":{"amount":"+0.7532260417938232","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":"Q1901690$199A6D07-3AC8-4A4C-9E34-E33A5AC02F85","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d072ba1ea9b998944bc29a4eba7b87a9f2baff29","datavalue":{"value":{"entity-type":"item","numeric-id":4310843,"id":"Q4310843"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"13cdec300d3fce3b0e8436a6085bea240b12558f","datavalue":{"value":{"amount":"+0.7476682066917419","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":"Q1901690$3567BE2E-DAC2-44A5-9AB2-32E2141782F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1f0fde6c6b4396008f4f9986382ad10e7b9f47ee","datavalue":{"value":{"entity-type":"item","numeric-id":4234103,"id":"Q4234103"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c913bc28b91d10a803e423234cc8712dfbc6a5a1","datavalue":{"value":{"amount":"+0.7419503927230835","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":"Q1901690$E5714162-858E-47E2-B2EE-BB7E6BD20AD2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f07278f8262fa6ac0f547d23cd0df38390356791","datavalue":{"value":{"entity-type":"item","numeric-id":5903449,"id":"Q5903449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"47cead2bd19f79907794e89ad6455c6402617a67","datavalue":{"value":{"amount":"+0.7357572913169861","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":"Q1901690$42D6F3AA-34E5-472D-857F-6DE0C9E1B02E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Bounded delay for a free address","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Bounded_delay_for_a_free_address"}}}}}