{"entities":{"Q1104074":{"pageid":1114826,"ns":120,"title":"Item:Q1104074","lastrevid":42879261,"modified":"2025-07-15T16:05:52Z","type":"item","id":"Q1104074","labels":{"en":{"language":"en","value":"Programming simultaneous actions using common knowledge"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4055017"}},"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":"Q1104074$A3410181-8612-4B30-B4E6-6617946578C0","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"5ee5fb26071f0671afcee7bcc4167149c92ce17e","datavalue":{"value":{"text":"Programming simultaneous actions using common knowledge","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1104074$5AD3F9A1-7CCE-41A3-9219-4CFAA7DFC10B","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"7d416562f8eb3e3ffd82443247b134a9a9c856e3","datavalue":{"value":"0646.68031","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1104074$0314D86E-CDF1-43B3-A10C-003B83CD7E36","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"f75b3fdf4b6f0ccd490d42ccc210c6ab39ebd790","datavalue":{"value":"10.1007/BF01762112","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1104074$B4821E36-2CFD-4743-B3AC-EA069B90C843","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c68860c93d38aebefcf7361375813f3be0d0b4d2","datavalue":{"value":{"entity-type":"item","numeric-id":418186,"id":"Q418186"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104074$352EC61A-F578-423A-A975-D9443E9C3B03","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"10be6f06ce033e746bf091af8d150d8542a9026e","datavalue":{"value":{"entity-type":"item","numeric-id":1104073,"id":"Q1104073"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104074$39273AFC-F2FB-41E8-AA3B-ADF9AA6F9613","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"65c8fa095fb5e7de7a6818fd747ab8b39647de93","datavalue":{"value":{"entity-type":"item","numeric-id":96582,"id":"Q96582"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104074$55E850F4-4F56-41C2-91B3-2832951C14F7","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":"Q1104074$C0626368-7468-4272-B6C0-7D5F83EC571C","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"5d612e123b9c322697c9d901bc91459ad9003182","datavalue":{"value":"This work applies the theory of knowledge in distributed systems to the design of efficient fault-tolerant protocols. We define a large class of problems requiring coordinated, simultaneous action in synchronous systems, and give a method of transforming specifications of such problems into protocols that are optimal in all runs: these protocols are guaranteed to perform the simultaneous actions as soon as any other protocol could possibly perform them, given the input to the system and faulty processor behavior.    This transformation is performed in two steps. In the first step we extract, directly from the problem specification, a high-level protocol programmed using explicit tests for common knowledge. In the second step we carefully analyze when facts become common knowledge, thereby providing a method of efficiently implementing these protocols in many variants of the omissions failure model.    In the generalized omissions model, however, our analysis shows that testing for common knowledge is NP-hard. Given the close correspondence between common knowledge and simultaneous actions, we are able to show that no optimal protocol for any such problem can be computationally efficient in this model.    The analysis in this paper exposes many subtle differences between the failure models, including the precise point at which this gap in complexity occurs.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1104074$B381194D-D31A-4147-B98B-1B37CF1F11BE","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"ec3769495799f08479987ac368adf64f125a2b66","datavalue":{"value":"68N25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1104074$2E5B2058-CEC4-4581-AD40-2E01F29089F6","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c975dc62df036ebbcfde512cf7024ad9fd0c6c41","datavalue":{"value":"4055017","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1104074$A06571E9-C58A-4F8B-BE07-0B743BFD4225","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"63b5614ed2c634bb51d0fa52f9e3c5031ce47bd9","datavalue":{"value":"Byzantine agreement","type":"string"},"datatype":"string"},"type":"statement","id":"Q1104074$87480566-67C5-489E-9E8E-A07A315A86EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"877546e531c7f05a2905e7c8c83073042780b25f","datavalue":{"value":"distributed firing squad","type":"string"},"datatype":"string"},"type":"statement","id":"Q1104074$6079DA38-829C-4F97-B4D3-7C8C381BF016","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2865ef5b3c291be2d587ccc9261845131b738990","datavalue":{"value":"omissions failure model","type":"string"},"datatype":"string"},"type":"statement","id":"Q1104074$3C15BE19-639E-4A1E-8648-6956EB95DCE7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"19d23abfe23eb7daff912c364d5089f518a2d323","datavalue":{"value":"knowledge in distributed systems","type":"string"},"datatype":"string"},"type":"statement","id":"Q1104074$50B6CC19-A1C9-4137-993F-9EBC542A8541","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b54c310b508e9d37e60524df2234687c068f4424","datavalue":{"value":"efficient fault-tolerant protocols","type":"string"},"datatype":"string"},"type":"statement","id":"Q1104074$30F2B5F7-F373-4AC9-8550-27E98DCCC961","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"02cb3566ea02cb85eece3497f637c2d8c3c14171","datavalue":{"value":"simultaneous action","type":"string"},"datatype":"string"},"type":"statement","id":"Q1104074$B080A6A6-8C9C-4EC6-B98B-A6B0070B0F2C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ae6eaceb3c3d9dd3c15bb339405c9c9aed38e70a","datavalue":{"value":"common knowledge","type":"string"},"datatype":"string"},"type":"statement","id":"Q1104074$F9560310-18BA-4D7C-B4B7-7C277D1D351E","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":"Q1104074$B1CA4FDB-B11F-4D9D-A6BA-FE27FE3F52D8","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"6d2d1adfae1b81eef721cda5469b95a291ba93d8","datavalue":{"value":{"entity-type":"item","numeric-id":1082071,"id":"Q1082071"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104074$59A49301-73DE-49B3-A46B-861A52DB43D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"047c0d51e930a122f92d1a5717bed3a7c11d4fb8","datavalue":{"value":{"entity-type":"item","numeric-id":4729333,"id":"Q4729333"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104074$F70DBC8D-7140-4966-8A65-52BB3829D8F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4aa92b022719f1daaa867865bc99f59182885305","datavalue":{"value":{"entity-type":"item","numeric-id":1168726,"id":"Q1168726"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104074$177F53B0-B07A-4C7C-B44C-26D4A74E7942","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104074$E3EF0825-6CA0-491D-BC4A-E97CD4A0E701","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b1758902a66e2332f9d1d0268ecf38eeeb4d377f","datavalue":{"value":{"entity-type":"item","numeric-id":3862379,"id":"Q3862379"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104074$25BFFE0F-F4B0-495A-B863-7C0012D236DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4a125502fa850f6a5ab3619570f7db924c393b3b","datavalue":{"value":{"entity-type":"item","numeric-id":3680260,"id":"Q3680260"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104074$C444F822-961F-4713-B0EC-F9B8ECA6B177","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e9155b2a89151bd7c3b2b0d60a86b5cb673950cd","datavalue":{"value":{"entity-type":"item","numeric-id":3873545,"id":"Q3873545"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104074$F382F160-0878-4683-9DD1-1A7583D19793","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ca10171208f8927b741ad8265c2e3cdfa92efecd","datavalue":{"value":{"entity-type":"item","numeric-id":3713588,"id":"Q3713588"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104074$0C96BDAC-2243-45DB-9427-437C78F969E7","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"2a2a96fab0145e6e5e949e95d2070f61eb5e5bea","datavalue":{"value":"https://doi.org/10.1007/bf01762112","type":"string"},"datatype":"url"},"type":"statement","id":"Q1104074$928615B1-7526-488C-A4D2-78E2215659D3","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"98e040b0a475c3a52bdb7f1425c43b7eee6a5ed1","datavalue":{"value":"W2092431596","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1104074$7F175300-6CE0-47CC-85CA-E90A3189C408","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f2781668466089c1c5c24ec4293cdafca277fe19","datavalue":{"value":{"entity-type":"item","numeric-id":2365570,"id":"Q2365570"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cd8f4e740519407c2aa6a152847190e8ab90107d","datavalue":{"value":{"amount":"+0.83901167","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1104074$43A2CEA7-DE5E-4ED7-AD8D-63B5EC907635","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ac407869d5efce6d8939591414c516cbee136cb9","datavalue":{"value":{"entity-type":"item","numeric-id":4934809,"id":"Q4934809"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b7bf24f58aca01c694faf16d59d261c6197a368f","datavalue":{"value":{"amount":"+0.8320446","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1104074$7176EA5F-13E7-4203-83B4-9EED5244FC29","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2f32467229f73b758b6bda77dda6eb5f2b0eddbc","datavalue":{"value":{"entity-type":"item","numeric-id":4352530,"id":"Q4352530"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8aec77e1636c932421e19a0eae60edee4b6d8791","datavalue":{"value":{"amount":"+0.82066965","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1104074$32DB0CAC-282C-4C2F-8605-AE08DD744C94","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f9949da4755046b3ebce4fc2aa33edd98a46c9c8","datavalue":{"value":{"entity-type":"item","numeric-id":1127518,"id":"Q1127518"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"252f6b88b01e79b2685528af6bebd5d51fe6015f","datavalue":{"value":{"amount":"+0.81897056","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1104074$AFBAAC7D-C953-434B-8B3E-48B794DCD8A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6d64f7cf5a4a8bef95f15d019d7e2ebc07da1af6","datavalue":{"value":{"entity-type":"item","numeric-id":1207436,"id":"Q1207436"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"87ffcb5a755519eea6c8e5317eac868e5350f33e","datavalue":{"value":{"amount":"+0.81530964","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1104074$4BAA8D3E-F1C7-415B-A8E0-85C9675E2798","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"97be68198be1b161b120408426db4621e236ff3c","datavalue":{"value":{"entity-type":"item","numeric-id":4681376,"id":"Q4681376"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e7601a7d393f7e3605ddf7cd7ecb2c5fa8808be6","datavalue":{"value":{"amount":"+0.81437147","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1104074$95FE26AB-3D4C-4325-A874-5CAB54F22BC5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ae1baa51f964472a83ddc375a07c99ce7123c25d","datavalue":{"value":{"entity-type":"item","numeric-id":1376091,"id":"Q1376091"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7d2e27eff252ede7d024819b377c11fb2c61e6ee","datavalue":{"value":{"amount":"+0.8108981","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1104074$5607EFA8-1640-4571-9D2C-A0EA6ACCDEA1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c6b5916de0a7c3b2bb1d374286abafa92b637c0e","datavalue":{"value":{"entity-type":"item","numeric-id":2344356,"id":"Q2344356"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"03a2dfc20a54a127ea820575629828cef77ff121","datavalue":{"value":{"amount":"+0.80902284","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1104074$5894FAAD-BE81-48A6-9570-6E9F588063C6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0c66f40f7c731dfb8d81d4e48833779f77226ba9","datavalue":{"value":{"entity-type":"item","numeric-id":4893671,"id":"Q4893671"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a479515c6dffda4fc5b31036b97ec79f300eaee6","datavalue":{"value":{"amount":"+0.8089192","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1104074$491F66B8-6E18-4590-BB02-7FCBC70884F5","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1104074","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1104074"}}}}}