Browsing by Author "Paz, Ami"

Now showing 1 - 4 of 4
  • Thumbnail Image
    Item
    Brief announcement: Sinkless orientation is hard also in the supported LOCAL model
    (Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2021-10-01) Korhonen, Janne H.; Paz, Ami; Rybicki, Joel; Schmid, Stefan; Suomela, Jukka; Department of Computer Science; Gilbert, Seth; Computer Science Professors; Computer Science - Large-scale Computing and Data Analysis (LSCA); Computer Science - Algorithms and Theoretical Computer Science (TCS); Professorship Suomela J.; University of Vienna; IST Austria
    We show that any algorithm that solves the sinkless orientation problem in the supported LOCAL model requires Ω(log n) rounds, and this is tight. The supported LOCAL is at least as strong as the usual LOCAL model, and as a corollary this also gives a new, short and elementary proof that shows that the round complexity of the sinkless orientation problem in the deterministic LOCAL model is Ω(log n).
  • Thumbnail Image
    Item
    Redundancy in distributed proofs
    (Springer Verlag, 2020-10-07) Feuilloley, Laurent; Fraigniaud, Pierre; Hirvonen, Juho; Paz, Ami; Perry, Mor; Department of Computer Science; Professorship Suomela J.; Universidad de Chile; Institut de Recherche en Informatique Fondamentale; University of Vienna; Weizmann Institute of Science
    Distributed proofs are mechanisms that enable 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 objects 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 a 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.
  • Thumbnail Image
    Item
    Redundancy in Distributed Proofs
    (Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018-10-01) Feuilloley, Laurent; Fraigniaud, Pierre; Hirvonen, Juho; Paz, Ami; Perry, Mor; Department of Computer Science; Schmid, Ulrich; Hirvonen, Juho; Professorship Suomela J.; Institut de Recherche en Informatique Fondamentale; Tel Aviv University
    Distributed 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.
  • Thumbnail Image
    Item
    Sinkless Orientation Made Simple
    (2023-01-12) Balliu, Alkida; Korhonen, Janne H.; Kühn, Fabian; Lievonen, Henrik; Olivetti, Dennis; Pai, Shreyas; Paz, Ami; Rybicki, Joel; Schmid, Stefan; Studený, Jan; Suomela, Jukka; Uitto, Jara; Department of Computer Science; Professorship Suomela J.; Computer Science Professors; Computer Science - Large-scale Computing and Data Analysis (LSCA); Computer Science - Algorithms and Theoretical Computer Science (TCS); Professorship Uitto J.; University of Freiburg; University of Vienna; IST Austria; Aalborg University; Gran Sasso Science Institute
    The sinkless orientation problem plays a key role in understanding the foundations of distributed computing. The problem can be used to separate two fundamental models of distributed graph algorithms, LOCAL and SLOCAL: the locality of sinkless orientation is Ω(log n) in the deterministic LOCAL model and O(log log n) in the deterministic SLOCAL model. Both of these results are known by prior work, but here we give new simple, self-contained proofs for them.