Redundancy in Distributed Proofs

Simple item page
dc.contributorAalto-yliopistofi
dc.contributorAalto Universityen
dc.contributor.authorFeuilloley, Laurenten_US
dc.contributor.authorFraigniaud, Pierreen_US
dc.contributor.authorHirvonen, Juhoen_US
dc.contributor.authorPaz, Amien_US
dc.contributor.authorPerry, Moren_US
dc.contributor.departmentDepartment of Computer Scienceen
dc.contributor.editorSchmid, Ulrichen_US
dc.contributor.editorHirvonen, Juhoen_US
dc.contributor.groupauthorProfessorship Suomela J.en
dc.contributor.organizationInstitut de Recherche en Informatique Fondamentaleen_US
dc.contributor.organizationTel Aviv Universityen_US
dc.date.accessioned2019-01-30T15:11:46Z
dc.date.available2019-01-30T15:11:46Z
dc.date.issued2018-10-01en_US
dc.description.abstractDistributed proofs are mechanisms enabling the nodes of a network to collectively and efficiently check the correctness of Boolean predicates on the structure of the network (e.g. having a specific diameter), or on data structures distributed over the nodes (e.g. a spanning tree). We consider well known mechanisms consisting of two components: a prover that assigns a certificate to each node, and a distributed algorithm called verifier that is in charge of verifying the distributed proof formed by the collection of all certificates. We show that many network predicates have distributed proofs offering a high level of redundancy, explicitly or implicitly. We use this remarkable property of distributed proofs to establish perfect tradeoffs between the size of the certificate stored at every node, and the number of rounds of the verification protocol.en
dc.description.versionPeer revieweden
dc.format.extent18
dc.format.extent1-18
dc.format.mimetypeapplication/pdfen_US
dc.identifier.citationFeuilloley, L, Fraigniaud, P, Hirvonen, J, Paz, A & Perry, M 2018, Redundancy in Distributed Proofs . in U Schmid & J Hirvonen (eds), 32nd International Symposium on Distributed Computing (DISC 2018) . Leibniz International Proceedings in Informatics (LIPIcs), vol. 121, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Dagstuhl, Germany, pp. 1-18, International Symposium on Distributed Computing, New Orleans, Louisiana, United States, 15/10/2018 . https://doi.org/10.4230/LIPIcs.DISC.2018.24en
dc.identifier.doi10.4230/LIPIcs.DISC.2018.24en_US
dc.identifier.isbn978-3-95977-092-7
dc.identifier.issn1868-8969
dc.identifier.otherPURE UUID: eed22597-91a8-45dd-ad85-f208b102da09en_US
dc.identifier.otherPURE ITEMURL: https://research.aalto.fi/en/publications/eed22597-91a8-45dd-ad85-f208b102da09en_US
dc.identifier.otherPURE FILEURL: https://research.aalto.fi/files/31172878/LIPIcs_DISC_2018_24.pdfen_US
dc.identifier.urihttps://aaltodoc.aalto.fi/handle/123456789/36316
dc.identifier.urnURN:NBN:fi:aalto-201901301486
dc.language.isoenen
dc.publisherSchloss Dagstuhl-Leibniz-Zentrum fuer Informatik
dc.relation.ispartofInternational Symposium on Distributed Computingen
dc.relation.ispartofseries32nd International Symposium on Distributed Computing (DISC 2018)en
dc.relation.ispartofseriesLeibniz International Proceedings in Informatics (LIPIcs)en
dc.relation.ispartofseriesVolume 121en
dc.rightsopenAccessen
dc.subject.keyworddistributed verificationen_US
dc.subject.keyworddistributed graph algorithmsen_US
dc.subject.keywordproof-labeling schemesen_US
dc.subject.keywordspace-time tradeoffsen_US
dc.subject.keywordnon-determinismen_US
dc.titleRedundancy in Distributed Proofsen
dc.typeConference article in proceedingsfi
dc.type.versionpublishedVersion
Files
Collections
[article-cris] Perustieteiden korkeakoulu / SCI