|   | 
Details
   web
Records
Author (up) 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 (up) Matamala, M.; Moreno, E.
Title Minimum Eulerian circuits and minimum de Bruijn sequences Type
Year 2009 Publication Discrete Mathematics Abbreviated Journal Discret. Math.
Volume 306 Issue 17 Pages 5298-5304
Keywords Eulerian circuits; Labelled digraph; De Bruijn sequences
Abstract Given a digraph (directed graph) with a labeling on its arcs, We Study the problem of finding the Eulerian circuit of lexicographically minimum label. We prove that this problem is NP-complete in general, but if the labelling is locally injective (arcs going out from each vertex have different labels), we prove that it is solvable in linear time by giving an algorithm that Constructs this circuit. When this algorithm is applied to a de Bruijn graph, it obtains the de Bruijn sequences with lexicographically minimum label. (C) 2007 Elsevier B.V. All rights reserved.
Address [Moreno, Eduardo] Univ Adolfo Ibanez, Sch Engn, Santiago, Chile, Email: mmatamal@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 0012-365x ISBN Medium
Area Expedition Conference
Notes WOS:000269600400007 Approved
Call Number UAI @ eduardo.moreno @ Serial 58
Permanent link to this record