{"entities":{"Q2055693":{"pageid":2066435,"ns":120,"title":"Item:Q2055693","lastrevid":54163934,"modified":"2026-01-26T09:24:05Z","type":"item","id":"Q2055693","labels":{"en":{"language":"en","value":"Sublinear-round Byzantine agreement under corrupt majority"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7436974"}},"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":"Q2055693$41CD3E9A-BCED-44B5-99A1-5C13AF8B1A90","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"88e21ff0f87ea44bfa7c54e50d4eb55e087ae67c","datavalue":{"value":{"text":"Sublinear-round Byzantine agreement under corrupt majority","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2055693$4C192F0A-BACF-4637-A4E2-5A06192A6437","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"689ac0d1402ed2f20af5ef9c028017e83471acba","datavalue":{"value":"1482.94044","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2055693$64851782-776A-4DC3-99C6-F7BE78A7A0A8","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"b4d48128de3e3529418d10b58f014b283d8f02a2","datavalue":{"value":"10.1007/978-3-030-45388-6_9","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2055693$BCBD3B83-D81D-4951-A92F-142178E2462D","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"e717f23d81eebaf1511ea14feaf1d4b351946585","datavalue":{"value":{"entity-type":"item","numeric-id":650108,"id":"Q650108"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2055693$2F367E26-C0C0-49C9-BAE6-4FE2EA2675B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"8fb4d7c30f1ec1e2805a68412329b686fb2c16d4","datavalue":{"value":{"entity-type":"item","numeric-id":332269,"id":"Q332269"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2055693$96CDC790-24AD-4709-847F-F2D6585C36D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"adb48c97a327d58f861efcdc36645ec8f0edf9af","datavalue":{"value":{"entity-type":"item","numeric-id":1629436,"id":"Q1629436"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2055693$5B42B39C-A336-430C-B63B-5E098DC4ADBD","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"083b9dcd5269b8796cca7eb2ababa434dff5de3a","datavalue":{"value":{"time":"+2021-12-01T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2055693$A3D42045-C7B6-404F-AC26-C4FF34913F30","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"5237518cbc0fadf6765542377218329a8b92f6a2","datavalue":{"value":"Byzantine agreement (BA) deals with the problem of reaching consensus in a network in the presence of faulty (and malicious) nodes. In particular, the system reaches a BA when the following conditions are satisfied:  \\par 1.) all honest nodes agree on the same outcome, \\par 2.) all honest nodes agree on the sender's output if the sender is honest.  It is known that when the number \\(t\\) of faulty nodes is larger than one third of the total number of nodes the BA is not possible. Nonetheless, it is possible to have an arbitrary number of faulty nodes \\(t < n\\), provided that an additional setup is considered and that the protocol features \\(t+1\\) rounds. It is also known that, although \\(t+1\\) is the optimal bound in the deterministic setting, randomized protocols can run in expected constant rounds when the majority of the nodes is honest, i.e.\\ when \\(t< n/2\\). The present paper deals with the corresponding problem in the absence of an honest majority. Precisely, the authors wonder if ``randomized protocols [can] help to overcome the \\((t+1)\\)-round complexity lower bound when the majority of nodes can be corrupt''. The only previous results in the sense of sub-linear round complexity are related to the case when \\(t=n/2+o(n)\\). The authors prove here (see Theorem 1) that, under some cryptographic assumptions in the setting of a public-key infrastructure, \\(t\\) can be of the form \\(t= (1-\\varepsilon)n\\) for some \\(\\varepsilon > 0\\), provided that a specified number of rounds is considered.  For the entire collection see [Zbl 1481.94004].","type":"string"},"datatype":"string"},"type":"statement","id":"Q2055693$EE79F23D-B7B9-4BAC-81E2-D60A45C4743F","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"5557559bcd525cbbd41c4ac78ed41bd7ddae47cc","datavalue":{"value":{"entity-type":"item","numeric-id":1726009,"id":"Q1726009"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2055693$A8194521-CAA7-4EFE-922B-F7ACFAB08B55","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b3f5570531d36cdad95fcc8cba24a2dabc5fbbbf","datavalue":{"value":"94A60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2055693$611E3F70-7FC5-4FC1-A590-5EE8CF4F9AD5","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"f918dcd9db391a59eb4e8d8b2feb98a2413ab2ec","datavalue":{"value":"7436974","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2055693$74B83329-C3AB-4A5F-8479-C1E124B30438","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"63b5614ed2c634bb51d0fa52f9e3c5031ce47bd9","datavalue":{"value":"Byzantine agreement","type":"string"},"datatype":"string"},"type":"statement","id":"Q2055693$63256D58-B485-41E2-A666-E678B30F6610","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"04ec984f32ef24ae5264467caa8aa91610c7f5b4","datavalue":{"value":"sub-linear round complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q2055693$C30F8066-87EC-481C-8CC8-260863478160","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"420863519b013e0f157865df533bb1aa5ac1e4e2","datavalue":{"value":"corrupt majority","type":"string"},"datatype":"string"},"type":"statement","id":"Q2055693$4C145BB4-7332-482A-9C84-39CD9EAD8A00","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":"Q2055693$363064A2-631E-4866-84F5-B3F0B4D4B6D6","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"b060b5583ad2d5918801ee4610792ab93ff02380","datavalue":{"value":"https://doi.org/10.1007/978-3-030-45388-6_9","type":"string"},"datatype":"url"},"type":"statement","id":"Q2055693$BC371D84-402D-484C-BBC2-3E48F17ACC37","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"00c471cf4c7d730238ea5dc845bf94cabed381b3","datavalue":{"value":"W3022867264","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2055693$FACE411E-9A8D-4DB7-99B6-CA393CD1CF1F","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"fb1429af9ebd5987d195d0b5771fbbed4a6164ed","datavalue":{"value":{"entity-type":"item","numeric-id":5145228,"id":"Q5145228"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2055693$73F2CBFB-6954-418A-B309-6D5768BF1BBB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f4a897117017322f09d5c56e5ff3cd32916a7247","datavalue":{"value":{"entity-type":"item","numeric-id":2656912,"id":"Q2656912"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2055693$8130F36A-B81A-4F1B-A248-E80F869528A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0a44204fb3a6a556685e3af485c5b8f69f5854dd","datavalue":{"value":{"entity-type":"item","numeric-id":3457093,"id":"Q3457093"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2055693$49831F95-9DE3-47B5-9A54-08B00BD117BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"68822df6b76e0008ab4836049ac1154e61940401","datavalue":{"value":{"entity-type":"item","numeric-id":5176082,"id":"Q5176082"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2055693$3FD8AD7F-FB7D-415D-851A-AF299F78B0C5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c16720967df62c90a19f2fcb5e8ff7937ec2b84a","datavalue":{"value":{"entity-type":"item","numeric-id":2055693,"id":"Q2055693"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2055693$88945EB9-2ED5-4714-9F9B-1F1FDECA7377","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c84b7127659298204650cd8ef2874743b0d442ec","datavalue":{"value":{"entity-type":"item","numeric-id":2422025,"id":"Q2422025"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2055693$A724A46B-1861-478F-9575-6432C9B537F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"feb2d4e8709be752059bfdacc652b022be607b6c","datavalue":{"value":{"entity-type":"item","numeric-id":3830798,"id":"Q3830798"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2055693$1F4D0C77-C04E-43F6-8EB4-FAB5BF3DAC1E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"387b9b12cc18520ae469ceca2df7fe7529ab3b6d","datavalue":{"value":{"entity-type":"item","numeric-id":2829949,"id":"Q2829949"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2055693$9DF31FC1-D9C2-4AFE-8490-55208E18ABE4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dd82301c7ea43d8a1f8d34f6a69fee173ff82d65","datavalue":{"value":{"entity-type":"item","numeric-id":3036697,"id":"Q3036697"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2055693$91FCF72D-9358-4CCF-8CCA-A1831A5567B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b3e5dac1a70f96f48e919047d34f8d5f422025cb","datavalue":{"value":{"entity-type":"item","numeric-id":4376159,"id":"Q4376159"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2055693$904A4F79-4695-4047-818E-7738CD427D38","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dda302eb9d54973d1cdca56019624d2a12c13f59","datavalue":{"value":{"entity-type":"item","numeric-id":3646243,"id":"Q3646243"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2055693$032AE818-CF29-4100-B099-3160C2D32680","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f3b5e77687981a252bcfb2087f1cbb5515fa22a6","datavalue":{"value":{"entity-type":"item","numeric-id":2943395,"id":"Q2943395"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2055693$A0E40F3B-9F01-4219-99A9-B0CB210D1194","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"10d49566a7875570e5dc7d5c2951179db8582988","datavalue":{"value":{"entity-type":"item","numeric-id":5395682,"id":"Q5395682"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2055693$FD1BF3C7-426D-421F-8157-C4396446BA38","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d0dbd5eab9d91951334ede3cb47649173adf8a4c","datavalue":{"value":{"entity-type":"item","numeric-id":3563851,"id":"Q3563851"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2055693$34CEC912-A69C-4D18-91AB-1E5AD312E89C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f692848967e7e4874d558465b7d1b496c096a975","datavalue":{"value":{"entity-type":"item","numeric-id":2930350,"id":"Q2930350"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2055693$F487848E-DF15-4A9E-BACB-6CB3F00F34EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"75e8adc2e3736dd7e8fa39d055ff32c7228b1b06","datavalue":{"value":{"entity-type":"item","numeric-id":1004599,"id":"Q1004599"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2055693$429C511D-59B2-47FD-A4F0-B01E41E2DA29","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"38d54e7d47020450b52bad41c6d3aa305d1a792a","datavalue":{"value":{"entity-type":"item","numeric-id":1675731,"id":"Q1675731"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2055693$32BFDDEE-7094-425E-8456-3DCDBEA9102D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f8c1d7230a7db490201ae3fad4d264e54f00c92c","datavalue":{"value":{"entity-type":"item","numeric-id":5395663,"id":"Q5395663"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2055693$5D4471C6-AD23-4914-853B-8AFA57311386","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f81cdab46998167a8194a19f7c9ae056fd8d6d99","datavalue":{"value":{"entity-type":"item","numeric-id":3581515,"id":"Q3581515"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2055693$3334F908-E8DA-4B2A-BD5A-FFC9853D2F13","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c8c60cd2a547f5bc571d8b2f3dd4c64ca607fbca","datavalue":{"value":{"entity-type":"item","numeric-id":3942378,"id":"Q3942378"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2055693$AE457FBD-261C-4CD9-837B-B9E2EEA26C7B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"551a10660249ef9962039673d02f600d19ffbfbc","datavalue":{"value":{"entity-type":"item","numeric-id":6487529,"id":"Q6487529"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2055693$B8FD119A-D0FC-48FB-A27F-557E169A972C","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"97422b5ac4249588332caaade40b0f1bec06fb46","datavalue":{"value":{"entity-type":"item","numeric-id":2121502,"id":"Q2121502"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1377b31da8234045709d3aa9a5cae26d0c00d6c1","datavalue":{"value":{"amount":"+0.8706666231155396","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":"Q2055693$E6D37036-E93D-4B2E-8AB0-9B28311C2F8F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3c390c4707056d4a1d31b4f39d5e1007fc35b2b1","datavalue":{"value":{"entity-type":"item","numeric-id":6487529,"id":"Q6487529"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0b3e00c72734e61e9557ed385cc418207838c857","datavalue":{"value":{"amount":"+0.8625772595405579","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":"Q2055693$B13B3B60-4E5E-4CD2-8BF6-6C047868B886","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"821b6d9970c518ca5e64a0ecae45bc7b9814ccea","datavalue":{"value":{"entity-type":"item","numeric-id":2169994,"id":"Q2169994"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"35baa71c8f9c7a2f9100e6255df5d3707227d3c0","datavalue":{"value":{"amount":"+0.8436903953552246","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":"Q2055693$8BEFDB68-FF3E-4807-8BF5-8C330AFB8248","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"78ce4099815718cedaafff43bd44d93d82c317a7","datavalue":{"value":{"entity-type":"item","numeric-id":2931382,"id":"Q2931382"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1e589aac73229973ff3ed02b74326b32d8d9ca10","datavalue":{"value":{"amount":"+0.8395705223083496","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":"Q2055693$646737EE-0F88-4EF3-8167-518A162CB929","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e97c127f1f4b27d08bd92e9e1afe01fe2dd4586a","datavalue":{"value":{"entity-type":"item","numeric-id":4035678,"id":"Q4035678"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7d476e0d76f5e2a5b76c28f89c1646888ead923f","datavalue":{"value":{"amount":"+0.8379712700843811","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":"Q2055693$CFF77412-0D01-44DA-BE40-8317DC29D78D","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2055693","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2055693"}}}}}