Home << 1 >>
List View
 | 
Citations
 | 
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.; Montealegre, 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 Becker, F.; Montealegre, P.; Rapaport, I.; Todinca, I.
Title The role of randomness in the broadcast congested clique model Type
Year 2021 Publication Information and Computation Abbreviated Journal Inf. Comput.
Volume 281 Issue Pages 104669
Keywords Distributed computing; Broadcast congested clique; Message size complexity; Private and public coins; Simultaneous multi-party communication
Abstract We study the role of randomness in the broadcast congested clique model. This is a message-passing model of distributed computation where the nodes of a network know their local neighborhoods and they broadcast, in synchronous rounds, messages that are visible to every other node.

This works aims to separate three different settings: deterministic protocols, randomized protocols with private coins, and randomized protocols with public coins. We obtain the following results:

If more than one round is allowed, public randomness is as powerful as private ran-domness.

One-round public-coin algorithms can be exponentially more powerful than determin-istic algorithms running in several rounds.

One-round public-coin algorithms can be exponentially more powerful than one-round private-coin algorithms.

One-round private-coin algorithms can be exponentially more powerful than one-round deterministic algorithms.
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 0890-5401 ISBN Medium
Area Expedition Conference
Notes WOS:000721215200042 Approved
Call Number UAI @ alexi.delcanto @ Serial 1491
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 83 Issue 7 Pages 2215-2244
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 0178-4617 ISBN Medium
Area Expedition Conference
Notes WOS:000648028200001 Approved
Call Number UAI @ alexi.delcanto @ Serial 1376
Permanent link to this record
 
 
Author Feuilloley, L.; Fraigniaud, P.; Montealegre, P.; Rapaport, I.; Remila, E.; Todinca, I.
Title Local certification of graphs with bounded genus Type
Year 2023 Publication Discrete Applied Mathematics Abbreviated Journal Discret Appl. Math.
Volume 325 Issue Pages 9-36
Keywords Distributed graph algorithms; Local certification; Proof-labeling scheme; Locally checkable proofs
Abstract Naor, Parter, and Yogev [SODA 2020] recently designed a compiler for automatically translating standard centralized interactive protocols to distributed interactive protocols, as introduced by Kol, Oshman, and Saxena [PODC 2018]. In particular, by using this compiler, every linear-time algorithm for deciding the membership to some fixed graph class can be translated into a dMAM(O(log n)) protocol for this class, that is, a distributed interactive protocol with O(log n)-bit proof size in n-node graphs, and three interactions between the (centralized) computationally-unbounded but non-trustable prover Merlin, and the (decentralized) randomized computationally-limited verifier Arthur. As a corol-lary, there is a dMAM(O(log n)) protocol for recognizing the class of planar graphs, as well as for recognizing the class of graphs with bounded genus.We show that there exists a distributed interactive protocol for recognizing the class of graphs with bounded genus performing just a single interaction, from the prover to the verifier, yet preserving proof size of O(log n) bits. This result also holds for the class of graphs with bounded non-orientable genus, that is, graphs that can be embedded on a non-orientable surface of bounded genus. The interactive protocols described in this paper are actually proof-labeling schemes, i.e., a subclass of interactive protocols, previously introduced by Korman, Kutten, and Peleg [PODC 2005]. In particular, these schn be computed a priori, at low cost, by the nodes themselves. Our results thus extend the recent proof-labeling scheme for planar graphs by Feuilloley et al. [PODC 2020], to graphs of bounded genus, and to graphs of bounded non-orientable genus.
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 0166-218X ISBN Medium
Area Expedition Conference
Notes WOS:000884423700002 Approved
Call Number UAI @ alexi.delcanto @ Serial 1661
Permanent link to this record
 
 
Author Fraigniaud, P.; Montealegre, P.; Rapaport, I.; Todinca, I.
Title Alert Results A Meta-Theorem for Distributed Certification 5 of 28 A Meta-Theorem for Distributed Certification Type
Year 2023 Publication Algorithmica Abbreviated Journal Algorithmica
Volume Early Access Issue Pages
Keywords Proof-labeling scheme; Locally checkable proof; Fault-tolerance; Distributed decision
Abstract Distributed certification, whether it be proof-labeling schemes, locally checkable proofs, etc., deals with the issue of certifying the legality of a distributed system with respect to a given boolean predicate. A certificate is assigned to each process in the system by a non-trustable oracle, and the processes are in charge of verifying these certificates, so that two properties are satisfied: completeness, i.e., for every legal instance, there is a certificate assignment leading all processes to accept, and soundness, i.e., for every illegal instance, and for every certificate assignment, at least one process rejects. The verification of the certificates must be fast, and the certificates themselves must be small. A large quantity of results have been produced in this framework, each aiming at designing a distributed certification mechanism for specific boolean predicates. This paper presents a “meta-theorem”, applying to many boolean predicates at once. Specifically, we prove that, for every boolean predicate on graphs definable in the monadic second-order (MSO) logic of graphs, there exists a distributed certification mechanism using certificates on O(log(2) n) bits in n-node graphs of bounded treewidth, with a verification protocol involving a single round of communication between neighbors
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 0178-4617 ISBN Medium
Area Expedition Conference
Notes WOS:001087304600001 Approved
Call Number UAI @ alexi.delcanto @ Serial 1901
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 1611-3349 ISBN Medium
Area Expedition Conference
Notes Approved
Call Number UAI @ eduardo.moreno @ Serial 1302
Permanent link to this record
 
 
Author Goles, E.; Montealegre-Barba, P.; Todinca, I.
Title The complexity of the bootstraping percolation and other problems Type
Year 2013 Publication Theoretical Computer Science Abbreviated Journal Theor. Comput. Sci.
Volume 504 Issue Pages 73-82
Keywords
Abstract We study the problem of predicting the state of a vertex in automata networks, where the state at each site is given by the majority function over its neighborhood. We show that for networks with maximum degree greater than 5 the problem is P-Complete, simulating a monotone Boolean circuit. Then, we show that the problem for networks with no vertex with degree greater than 4 is in NC, giving a fast parallel algorithm. Finally, we apply the result to the study of related problems. (C) 2012 Elsevier B.V. All rights reserved.
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 0304-3975 ISBN Medium
Area Expedition Conference
Notes WOS:000325905100008 Approved
Call Number UAI @ eduardo.moreno @ Serial 320
Permanent link to this record
 
 
Author Liedloff, M.; Montealegre, P.; Todinca, I.
Title Beyond Classes of Graphs with “Few” Minimal Separators: FPT Results Through Potential Maximal Cliques Type
Year 2019 Publication Algorithmica Abbreviated Journal Algorithmica
Volume 81 Issue 3 Pages 986-1005
Keywords FPT algorithms; Treewidth; Potential maximal cliques
Abstract Let P(G,X) be a property associating a boolean value to each pair (G,X) where G is a graph and X is a vertex subset. Assume that P is expressible in counting monadic second order logic (CMSO) and let t be an integer constant. We consider the following optimization problem: given an input graph G=(V,E), find subsets XFV such that the treewidth of G[F] is at most t, property P(G[F],X) is true and X is of maximum size under these conditions. The problem generalizes many classical algorithmic questions, e.g., Longest Induced Path, Maximum Induced Forest, IndependentH-Packing, etc. Fomin et al. (SIAM J Comput 44(1):54-87, 2015) proved that the problem is polynomial on the class of graph Gpoly, i.e. the graphs having at most poly(n) minimal separators for some polynomial poly. Here we consider the class Gpoly+kv, formed by graphs of Gpoly to which we add a set of at most k vertices with arbitrary adjacencies, called modulator. We prove that the generic optimization problem is fixed parameter tractable on Gpoly+kv, with parameter k, if the modulator is also part of the input.
Address [Liedloff, Mathieu; Todinca, Ioan] Univ Orleans, INSA Ctr Val Loire, LIFO, EA 4022, Orleans, France, Email: mathieu.liedloff@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-4617 ISBN Medium
Area Expedition Conference
Notes WOS:000460105700003 Approved
Call Number UAI @ eduardo.moreno @ Serial 989
Permanent link to this record
 
 
Author Montealegre, P.; 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 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