{"entities":{"Q1103403":{"pageid":1114155,"ns":120,"title":"Item:Q1103403","lastrevid":69648909,"modified":"2026-04-13T08:27:03Z","type":"item","id":"Q1103403","labels":{"en":{"language":"en","value":"Limits on the power of concurrent-write parallel machines"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4053025"}},"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":"Q1103403$FD1770FA-A643-49B1-81A0-211C42D93153","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"0c101dd50edaa4d9ce7d9cd9af1b78f271ca344f","datavalue":{"value":{"text":"Limits on the power of concurrent-write parallel machines","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1103403$63F6C00B-A99D-40F8-8A38-62C8D2019308","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"ec8759759dda565925b3bdada2899d5eee11ea7d","datavalue":{"value":"0645.68060","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1103403$EF29565A-239A-4F91-B43B-5DCB2EEB39AA","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"77c8bd77eac753ef28544ef81dd4bdb523432233","datavalue":{"value":"10.1016/0890-5401(88)90040-5","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1103403$EE4FEC30-42E1-4D4C-BD48-2249095A3DF1","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"fa2d1ad91af9619c8dd37ab889fe279a84c4057e","datavalue":{"value":{"entity-type":"item","numeric-id":259032,"id":"Q259032"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1103403$7476B36D-BDCE-4FBB-9DBD-D66A1F323B7E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"31a1937240ca4a323604b4728c31d242b5596d7c","datavalue":{"value":{"time":"+1988-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":"Q1103403$AE1B8EDB-2AAC-4773-9C3D-1B2000DF9715","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"c2463a01ff9391ce357fce162862238c786de8db","datavalue":{"value":"The computation of specific functions using the most general form of concurrent-read-concurrent-write parallel RAM is considered. It is shown that such a machine can compute any function of Boolean inputs in time log n-\\(\\log \\log n+O(1)\\) given a polynomial number of processors and memory cells and that this bound is tight for integer addition. Despite this evidence of the power of the model we show that a very simple function, namely parity, requires time \\(\\Omega\\) (\\(\\sqrt{\\log n})\\) to compute given a polynomial bound on the number of processors, independent of the number of memory cells.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1103403$BC4DF088-3124-4815-A860-6E5FE4F9BDB2","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1103403$96F22230-17E4-4E9A-BCED-CFCDA1BA6C3B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"ec3769495799f08479987ac368adf64f125a2b66","datavalue":{"value":"68N25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1103403$C154AA11-5040-4032-B361-C01B1B257688","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"7164d6da3434ebac885850c6f78e01aabd154c3a","datavalue":{"value":"4053025","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1103403$948EFA7C-17FE-4B43-B1EF-D332101B6EBA","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"aaef260348ec35b09bd9f0cb7977667f5c107fd6","datavalue":{"value":"concurrent-read-concurrent-write parallel RAM","type":"string"},"datatype":"string"},"type":"statement","id":"Q1103403$B8AC69AB-8CAF-4F4A-BF8A-D98ECF2BE91F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"234b3509715ae13f43a779222a986d4e35f52b73","datavalue":{"value":"function of Boolean inputs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1103403$E1B84E1D-99F0-48BD-9152-128691B8F745","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fc68e48ba3c8d693c7ec3942cf84a34a20017dfc","datavalue":{"value":"polynomial number of processors","type":"string"},"datatype":"string"},"type":"statement","id":"Q1103403$CC254A6C-FA16-44C4-912A-45DEF0B71D0C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9f3c3681a6a16edf0d14c77c88d6e0f2b1888b27","datavalue":{"value":"integer addition","type":"string"},"datatype":"string"},"type":"statement","id":"Q1103403$9C275539-BA35-49F0-91DC-40794875528E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0d146385bd214c988dc91b3c0cc2011de48b86fe","datavalue":{"value":"parity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1103403$08007531-1470-4B17-B653-2061B3F9747F","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"bdeac5e928e087a649bdeced20db2b34fab0678f","datavalue":{"value":{"entity-type":"item","numeric-id":1822913,"id":"Q1822913"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1103403$0F09F6D6-F6BA-435D-BB32-9F062A765CC3","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":"Q1103403$48361037-0F6F-4336-A59F-71754D474F6E","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"9e47802d4e2726797a7f454f03895f639e969da7","datavalue":{"value":"https://doi.org/10.1016/0890-5401(88)90040-5","type":"string"},"datatype":"url"},"type":"statement","id":"Q1103403$F2EAD1BD-FC8A-4A9E-9D12-7889ACE2772F","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"a361a78f93c3e19a87478ec1b93316ddc1415f23","datavalue":{"value":"W2061503133","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1103403$23D2350A-EEED-4235-86E6-C22F20AC8C90","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"957892286a77298fd7faca30f1f60dbb53f94696","datavalue":{"value":{"entity-type":"item","numeric-id":1054720,"id":"Q1054720"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1103403$29B1D792-7078-45DB-BD9C-3E59FBA4496F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d3aa57810f0528ce2438cd0f484c242c53bb4e54","datavalue":{"value":{"entity-type":"item","numeric-id":3325043,"id":"Q3325043"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1103403$18FDBE25-D6B3-4031-9F17-0C5E0FE4C3CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bc7e469a8fa14b237d73aa7dbd98d094baae506d","datavalue":{"value":{"entity-type":"item","numeric-id":3719831,"id":"Q3719831"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1103403$F8A0305E-FD9B-460F-BE7E-503A7480B9F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"50e39951d487d3bf563c62341ed381ea5be4f484","datavalue":{"value":{"entity-type":"item","numeric-id":3318683,"id":"Q3318683"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1103403$D693D0A8-127D-4308-9E22-89C90679B4CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"769cf6c7ee115ce4ebdbc44071512764e92350d4","datavalue":{"value":{"entity-type":"item","numeric-id":1171382,"id":"Q1171382"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1103403$46ECF1BE-95A1-4274-A853-1EC20CEBF00C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"37ef69a646e2fd966c83a602fd12d448a0773473","datavalue":{"value":{"entity-type":"item","numeric-id":3746884,"id":"Q3746884"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1103403$811C2B3C-62C5-4276-9E5E-25493ED3327F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b4ab13142076117cc14856c9cfe9c081eaaa2f9d","datavalue":{"value":{"entity-type":"item","numeric-id":4172915,"id":"Q4172915"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1103403$365557CA-118D-4A7E-9D6A-7B21D9DD9313","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6c21977b84ef0771cf411ee2a4f304fab4e90c8e","datavalue":{"value":{"entity-type":"item","numeric-id":3746899,"id":"Q3746899"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1103403$04F29B8F-CE9F-43CF-B913-904A9D0A7EA3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f450486e6dd81b9bc183a0057d83ff04fd2d4632","datavalue":{"value":{"entity-type":"item","numeric-id":3316595,"id":"Q3316595"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1103403$1894968D-FC7F-4AB3-AE4A-D1B49FCAE967","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"43a25f91f1879c40c0b3374c776578fa61b362f0","datavalue":{"value":{"entity-type":"item","numeric-id":3691060,"id":"Q3691060"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1103403$813377AD-58B7-4CE2-9FC0-C7B4C090F8E4","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f64be5d32daf6b6f82af29b49dbde89ec5247e3c","datavalue":{"value":{"entity-type":"item","numeric-id":3204042,"id":"Q3204042"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d1d8aa1e6289eefc7d8f8f630b3f1a4776ae3079","datavalue":{"value":{"amount":"+0.8708999156951904","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":"Q1103403$EA2A9290-67E8-44EB-9F1A-67C4D14F48D5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b3a89f10872a56916c7ef1cf8dadbe0ad564739e","datavalue":{"value":{"entity-type":"item","numeric-id":4710687,"id":"Q4710687"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1c8f0a116b88dd9723cd81a1c472aa1bc0631ad8","datavalue":{"value":{"amount":"+0.8704346418380737","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":"Q1103403$B5DC64D4-9B84-4052-A2F7-778DDAFDCC84","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"87b10d3aa6ad33d92782d6035cfcd30d2f26ed77","datavalue":{"value":{"entity-type":"item","numeric-id":3719831,"id":"Q3719831"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d1bb8e2770464b899497d767a821a04f9315b84a","datavalue":{"value":{"amount":"+0.8602591753005981","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":"Q1103403$40933181-0DBB-410B-B3A4-4082764A7C9C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"45af66cd1af2363f262863204b148cadbaae256c","datavalue":{"value":{"entity-type":"item","numeric-id":807013,"id":"Q807013"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c5816818ea83e2c49b2375339a571ad6030ab8f2","datavalue":{"value":{"amount":"+0.8444019556045532","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":"Q1103403$33F59226-8151-4A81-A6C4-F2A080BEF70C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4f250817672c0ee83e3761812a7226eb584e914e","datavalue":{"value":{"entity-type":"item","numeric-id":1816745,"id":"Q1816745"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f2433dede39d7d7a0bf4bbc354df693318e43b39","datavalue":{"value":{"amount":"+0.8418757319450378","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":"Q1103403$424EED83-1BA0-4628-9C1D-1766787DC89B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Limits on the power of concurrent-write parallel machines","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Limits_on_the_power_of_concurrent-write_parallel_machines"}}}}}