|   | 
Details
   web
Records
Author Becker, F.; Kosowski, A.; Matamala, M.; Nisse, N.; Rapaport, I.; Suchan, K.; Todinca, I.
Title Allowing each node to communicate only once in a distributed system: shared whiteboard models Type
Year 2015 Publication Distributed Computing Abbreviated Journal Distrib. Comput.
Volume 28 Issue 3 Pages 189-200
Keywords Distributed computing; Local computation; Graph properties; Bounded communication
Abstract In this paper we study distributed algorithms on massive graphs where links represent a particular relationship between nodes (for instance, nodes may represent phone numbers and links may indicate telephone calls). Since such graphs are massive they need to be processed in a distributed way. When computing graph-theoretic properties, nodes become natural units for distributed computation. Links do not necessarily represent communication channels between the computing units and therefore do not restrict the communication flow. Our goal is to model and analyze the computational power of such distributed systems where one computing unit is assigned to each node. Communication takes place on a whiteboard where each node is allowed to write at most one message. Every node can read the contents of the whiteboard and, when activated, can write one small message based on its local knowledge. When the protocol terminates its output is computed from the final contents of the whiteboard. We describe four synchronization models for accessing the whiteboard. We show that message size and synchronization power constitute two orthogonal hierarchies for these systems. We exhibit problems that separate these models, i.e., that can be solved in one model but not in a weaker one, even with increased message size. These problems are related to maximal independent set and connectivity. We also exhibit problems that require a given message size independently of the synchronization model.
Address [Becker, Florent; Todinca, Ioan] Univ Orleans, LIFO, Orleans, France, Email: florent.becker@univ-orleans.fr;
Corporate Author Thesis
Publisher Springer Place of Publication Editor
Language English Summary Language Original Title
Series Editor Series Title Abbreviated Series Title
Series Volume Series Issue Edition
ISSN 0178-2770 ISBN Medium
Area Expedition Conference
Notes WOS:000354708400003 Approved
Call Number UAI @ eduardo.moreno @ Serial 492
Permanent link to this record
 

 
Author Becker, F.; Montealecre, P.; Rapaport, I.; Todinca, I.
Title The Impact Of Locality In The Broadcast Congested Clique Model Type
Year 2020 Publication Siam Journal On Discrete Mathematics Abbreviated Journal SIAM Discret. Math.
Volume 34 Issue 1 Pages 682-700
Keywords broadcast congested clique; induced cycles; graph degeneracy
Abstract The broadcast congested clique model (BCLIQUE) is a message-passing model of distributed computation where n nodes communicate with each other in synchronous rounds. First, in this paper we prove that there is a one-round, deterministic algorithm that reconstructs the input graph G if the graph is d-degenerate, and rejects otherwise, using bandwidth b = O(d . log n). Then, we introduce a new parameter to the model. We study the situation where the nodes, initially, instead of knowing their immediate neighbors, know their neighborhood up to a fixed radius r. In this new framework, denoted BCLIQuE[r], we study the problem of detecting, in G, an induced cycle of length at most k (CYCLE <= k) and the problem of detecting an induced cycle of length at least k +1 (CYCLE>k). We give upper and lower bounds. We show that if each node is allowed to see up to distance r = left perpendicular k/2 right perpendicular + 1, then a polylogarithmic bandwidth is sufficient for solving CYCLE>k with only two rounds. Nevertheless, if nodes were allowed to see up to distance r = left perpendicular k/3 right perpendicular, then any one-round algorithm that solves CYCLE>k needs the bandwidth b to be at least Omega(n/ log n). We also show the existence of a one-round, deterministic BCLIQUE algorithm that solves CYCLE <= k with bandwitdh b = O(n(1/left perpendicular k/2 right perpendicular). log n). On the negative side, we prove that, if epsilon <= 1/3 and 0 < r <= k/4, then any epsilon-error, R-round, b-bandwidth algorithm in the BCLIQUE[r] model that solves problem CYCLE(<= k )satisfies R . b = Omega(n(1/left perpendicular k/2 right perpendicular)).
Address [Becker, F.; Todinca, I] Univ Orleans, INSA Ctr Val Loire, LIFO EA 4022, Orleans, France, Email: florent.becker@univ-orleans.fr;
Corporate Author Thesis
Publisher Siam Publications Place of Publication Editor
Language English Summary Language Original Title
Series Editor Series Title Abbreviated Series Title
Series Volume Series Issue Edition
ISSN 0895-4801 ISBN Medium
Area Expedition Conference
Notes WOS:000546886700033 Approved
Call Number UAI @ eduardo.moreno @ Serial 1182
Permanent link to this record
 

 
Author Feuilloley, L.; Fraigniaud, P.; Montealegre, P.; Rapaport, I.; Remila, E.; Todinca, I.
Title Compact Distributed Certification of Planar Graphs Type
Year 2021 Publication Algorithmica Abbreviated Journal Algorithmica
Volume Early Access Issue Pages
Keywords Distributed algorithms; Network algorithms; Graph property certification; Labeling schemes; Planarity
Abstract Naor M., Parter M., Yogev E.: (The power of distributed verifiers in interactive proofs. In: 31st ACM-SIAM symposium on discrete algorithms (SODA), pp 1096-115, 2020. https://doi.org/10.1137/1.9781611975994.67) have recently demonstrated the existence of a distributed interactive proof for planarity (i.e., for certifying that a network is planar), using a sophisticated generic technique for constructing distributed IP protocols based on sequential IP protocols. The interactive proof for planarity is based on a distributed certification of the correct execution of any given sequential linear-time algorithm for planarity testing. It involves three interactions between the prover and the randomized distributed verifier (i.e., it is a dMAM protocol), and uses small certificates, on O(log n) bits in n-node networks. We show that a single interaction with the prover suffices, and randomization is unecessary, by providing an explicit description of a proof-labeling scheme for planarity, still using certificates on just O(log n) bits. We also show that there are no proof-labeling schemes-in fact, even no locally checkable proofs-for planarity using certificates on o(log n) bits.
Address
Corporate Author Thesis
Publisher Place of Publication Editor
Language Summary Language Original Title
Series Editor Series Title Abbreviated Series Title
Series Volume Series Issue Edition
ISSN ISBN Medium
Area Expedition Conference
Notes WOS:000648028200001 Approved
Call Number UAI @ alexi.delcanto @ Serial 1376
Permanent link to this record
 

 
Author Fraigniaud, P.; Montealegre-Barba, P.; Oshman, R.; Rapaport, I.; Todinca, I.
Title On Distributed Merlin-Arthur Decision Protocols Type
Year 2019 Publication Lecture Notes in Computer Sciences Abbreviated Journal Lect. Notes Comput. Sc.
Volume 11639 Issue Pages
Keywords
Abstract
Address
Corporate Author Thesis
Publisher Place of Publication Editor
Language Summary Language Original Title
Series Editor Series Title Abbreviated Series Title
Series Volume Series Issue Edition
ISSN ISBN Medium
Area Expedition Conference
Notes Approved
Call Number UAI @ eduardo.moreno @ Serial 1302
Permanent link to this record
 

 
Author Goles, E.; Guillon, P.; Rapaport, I.
Title Traced communication complexity of cellular automata Type
Year 2011 Publication Theoretical Computer Science Abbreviated Journal Theor. Comput. Sci.
Volume 412 Issue 30 Pages 3906-3916
Keywords Cellular automata; Communication complexity
Abstract We study cellular automata with respect to a new communication complexity problem: each of two players know half of some finite word, and must be able to tell whether the state of the central cell will follow a given evolution, by communicating as little as possible between each other. We present some links with classical dynamical concepts, especially equicontinuity, expansivity, entropy and give the asymptotic communication complexity of most elementary cellular automata. (C) 2011 Elsevier B.V. All rights reserved.
Address [Guillon, P; Rapaport, I] Univ Chile, DIM CMM, CNRS, UMI 2807, Santiago, Chile, Email: eric.chacc@uai.cl
Corporate Author Thesis
Publisher Elsevier Science Bv Place of Publication Editor
Language English Summary Language Original Title
Series Editor Series Title Abbreviated Series Title
Series Volume Series Issue Edition
ISSN 0304-3975 ISBN Medium
Area Expedition Conference
Notes WOS:000292589800009 Approved
Call Number UAI @ eduardo.moreno @ Serial 152
Permanent link to this record
 

 
Author Goles, E.; Meunier, P.E.; Rapaport, I.; Theyssier, G.
Title Communication complexity and intrinsic universality in cellular automata Type
Year 2011 Publication Theoretical Computer Science Abbreviated Journal Theor. Comput. Sci.
Volume 412 Issue 1-2 Pages 2-21
Keywords Cellular automata; Communication complexity; Intrinsic universality
Abstract The notions of universality and completeness are central in the theories of computation and computational complexity. However, proving lower bounds and necessary conditions remains hard in most cases. In this article, we introduce necessary conditions for a cellular automaton to be “universal”, according to a precise notion of simulation, related both to the dynamics of cellular automata and to their computational power. This notion of simulation relies on simple operations of space-time rescaling and it is intrinsic to the model of cellular automata. intrinsic universality, the derived notion, is stronger than Turing universality, but more uniform, and easier to define and study. Our approach builds upon the notion of communication complexity, which was primarily designed to study parallel programs, and thus is, as we show in this article, particulary well suited to the study of cellular automata: it allowed us to show, by studying natural problems on the dynamics of cellular automata, that several classes of cellular automata, as well as many natural (elementary) examples, were not intrinsically universal. (C) 2010 Elsevier B.V. All rights reserved.
Address [Meunier, P. -E.; Theyssier, G.] Univ Savoie, CNRS, LAMA, F-73376 Le Bourget Du Lac, France, Email: guillaume.theyssier@univ-savoie.fr
Corporate Author Thesis
Publisher Elsevier Science Bv Place of Publication Editor
Language English Summary Language Original Title
Series Editor Series Title Abbreviated Series Title
Series Volume Series Issue Edition
ISSN 0304-3975 ISBN Medium
Area Expedition Conference
Notes WOS:000285952400002 Approved
Call Number UAI @ eduardo.moreno @ Serial 118
Permanent link to this record
 

 
Author Goles, E.; Moreira, A.; Rapaport, I.
Title Communication complexity in number-conserving and monotone cellular automata Type
Year 2011 Publication Theoretical Computer Science Abbreviated Journal Theor. Comput. Sci.
Volume 412 Issue 29 Pages 3616-3628
Keywords Cellular automata; Communication complexity; Elementary cellular automata; Number-conserving
Abstract One third of the elementary cellular automata (CAs) are either number-conserving (NCCAs) or monotone (increasing or decreasing). In this paper we prove that, for all of them, we can find linear or constant communication protocols for the prediction problem. In other words, we are able to give a succinct description for their dynamics. This is not necessarily true for general NCCAs. In fact, we also show how to explicitly construct, from any CA, a new NCCA which preserves the original communication complexity. (C) 2011 Elsevier B.V. All rights reserved.
Address [Moreira, A] Univ Tecn Federico Santa Maria, Dept Informat, Valparaiso, Chile, Email: eric.chacc@uai.cl
Corporate Author Thesis
Publisher Elsevier Science Bv Place of Publication Editor
Language English Summary Language Original Title
Series Editor Series Title Abbreviated Series Title
Series Volume Series Issue Edition
ISSN 0304-3975 ISBN Medium
Area Expedition Conference
Notes WOS:000292077200019 Approved
Call Number UAI @ eduardo.moreno @ Serial 153
Permanent link to this record
 

 
Author Kiwi, M.; de Espanes, P.M.; Rapaport, I.; Rica, S.; Theyssier, G.
Title Strict Majority Bootstrap Percolation in the r-wheel Type
Year 2014 Publication Information Processing Letters Abbreviated Journal Inf. Process. Lett.
Volume 114 Issue 6 Pages 277-281
Keywords Bootstrap percolation; Interconnection networks
Abstract In the strict Majority Bootstrap Percolation process each passive vertex v becomes active if at least [deg(v)+1/2] of its neighbors are active (and thereafter never changes its state). We address the problem of finding graphs for which a small proportion of initial active vertices is likely to eventually make all vertices active. We study the problem on a ring of n vertices augmented with a “central” vertex u. Each vertex in the ring, besides being connected to u, is connected to its r closest neighbors to the left and to the right. We prove that if vertices are initially active with probability p > 1/4 then, for large values of r, percolation occurs with probability arbitrarily close to I as n -> infinity. Also, if p < 1/4, then the probability of percolation is bounded away from 1. (c) 2014 Elsevier B.V. All rights reserved.
Address [Kiwi, M.; de Espanes, P. Moisset; Rapaport, I.] Univ Chile, DIM, CMM, UMI 2807 CNRS, Santiago, Chile, Email: rapaport@dim.uchile.cl
Corporate Author Thesis
Publisher Elsevier Science Bv Place of Publication Editor
Language English Summary Language Original Title
Series Editor Series Title Abbreviated Series Title
Series Volume Series Issue Edition
ISSN 0020-0190 ISBN Medium
Area Expedition Conference
Notes WOS:000334485800001 Approved
Call Number UAI @ eduardo.moreno @ Serial 370
Permanent link to this record
 

 
Author Montealegre, R.; Perez-Salazar, S.; Rapaport, I.; Todinca, I.
Title Graph reconstruction in the congested clique Type
Year 2020 Publication Journal Of Computer And System Sciences Abbreviated Journal J. Comput. Syst. Sci.
Volume 113 Issue Pages 1-17
Keywords Distributed computing; Congested clique; Round complexity; Reconstruction problem; Graph classes
Abstract In this paper we study the reconstruction problem in the congested clique model. Given a class of graphs g, the problem is defined as follows: if G is not an element of g, then every node must reject; if G is an element of g, then every node must end up knowing all the edges of G. The cost of an algorithm is the total number of bits received by any node through one link. It is not difficult to see that the cost of any algorithm that solves this problem is Omega(log vertical bar g(n)vertical bar/n), where g(n) is the subclass of all n-node labeled graphs in g. We prove that the lower bound is tight and that it is possible to achieve it with only 2 rounds. (C) 2020 Elsevier Inc. All rights reserved.
Address [Montealegre, R.] Univ Adolfo Ibanez, Fac Ingn & Ciencias, Santiago, Chile, Email: p.montealegre@edu.uai;
Corporate Author Thesis
Publisher Academic Press Inc Elsevier Science Place of Publication Editor
Language English Summary Language Original Title
Series Editor Series Title Abbreviated Series Title
Series Volume Series Issue Edition
ISSN 0022-0000 ISBN Medium
Area Expedition Conference
Notes WOS:000539435200001 Approved
Call Number UAI @ eduardo.moreno @ Serial 1190
Permanent link to this record
 

 
Author Montealegre-Barba, P.; Perez-Salazar, S.; Rapaport, I.; Todinca, I.
Title Two Rounds Are Enough for Reconstructing Any Graph (Class) in the Congested Clique Model Type
Year 2018 Publication Lecture Notes in Computer Sciences Abbreviated Journal Lect. Notes Comput. Sc.
Volume 11085 Issue Pages
Keywords
Abstract
Address
Corporate Author Thesis
Publisher Place of Publication Editor
Language Summary Language Original Title
Series Editor Series Title Abbreviated Series Title
Series Volume Series Issue Edition
ISSN ISBN Medium
Area Expedition Conference
Notes Approved
Call Number UAI @ eduardo.moreno @ Serial 1296
Permanent link to this record
 

 
Author Nisse, N.; Rapaport, I.; Suchan, K.
Title Distributed computing of efficient routing schemes in generalized chordal graphs Type
Year 2012 Publication Theoretical Computer Science Abbreviated Journal Theor. Comput. Sci.
Volume 444 Issue Pages 17-27
Keywords Routing scheme; Stretch; Chordal graph; Distributed algorithm
Abstract Efficient algorithms for computing routing tables should take advantage of particular properties arising in large scale networks. Two of them are of special interest: low (logarithmic) diameter and high clustering coefficient. High clustering coefficient implies the existence of few large induced cycles. Considering this fact, we propose here a routing scheme that computes short routes in the class of k-chordal graphs, i.e., graphs with no induced cycles of length more than k. In the class of k-chordal graphs, our routing scheme achieves an additive stretch of at most k – 1, i.e., for all pairs of nodes, the length of the route never exceeds their distance plus k – 1. In order to compute the routing tables of any n-node graph with diameter D we propose a distributed algorithm which uses O(log n)-bit messages and takes O(D) time. The corresponding routing scheme achieves the stretch of k – 1 on k-chordal graphs. We then propose a routing scheme that achieves a better additive stretch of 1 in chordal graphs (notice that chordal graphs are 3-chordal graphs). In this case, distributed computation of routing tables takes O(min{Delta D, n}) time, where Delta is the maximum degree of the graph. Our routing schemes use addresses of size log n bits and local memory of size 2(d-1) log n bits per node of degree d. (c) 2012 Elsevier B.V. All rights reserved.
Address [Suchan, Karol] Univ Adolfo Ibanez, Fac Ingn & Ciencias, Santiago, Chile, Email: nicolas.nisse@inria.fr;
Corporate Author Thesis
Publisher Elsevier Science Bv Place of Publication Editor
Language English Summary Language Original Title
Series Editor Series Title Abbreviated Series Title
Series Volume Series Issue Edition
ISSN 0304-3975 ISBN Medium
Area Expedition Conference
Notes WOS:000306041700003 Approved
Call Number UAI @ eduardo.moreno @ Serial 222
Permanent link to this record
 

 
Author Rapaport, I.; Suchan, K.; Todinca, I.; Verstraete, J.
Title On Dissemination Thresholds in Regular and Irregular Graph Classes Type
Year 2011 Publication Algorithmica Abbreviated Journal Algorithmica
Volume 59 Issue 1 Pages 16-34
Keywords Bootstrap percolation; Cubic graphs; Information dissemination
Abstract We investigate the natural situation of the dissemination of information on various graph classes starting with a random set of informed vertices called active. Initially active vertices are chosen independently with probability p, and at any stage in the process, a vertex becomes active if the majority of its neighbours are active, and thereafter never changes its state. This process is a particular case of bootstrap percolation. We show that in any cubic graph, with high probability, the information will not spread to all vertices in the graph if p < 1/2. We give families of graphs in which information spreads to all vertices with high probability for relatively small values of p.
Address [Todinca, I.] Univ Orleans, LIFO, Orleans, France, Email: rapaport@dim.uchile.cl
Corporate Author Thesis
Publisher Springer Place of Publication Editor
Language English Summary Language Original Title
Series Editor Series Title Abbreviated Series Title
Series Volume Series Issue Edition
ISSN 0178-4617 ISBN Medium
Area Expedition Conference
Notes WOS:000286525300003 Approved
Call Number UAI @ eduardo.moreno @ Serial 119
Permanent link to this record