Home | << 1 >> |
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 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 | D'Angelo, G.; Di Stefano, G.; Navarra, A.; Nisse, N.; Suchan, K. | ||||
Title | Computing on Rings by Oblivious Robots: A Unified Approach for Different Tasks | Type | |||
Year | 2015 | Publication | Algorithmica | Abbreviated Journal | Algorithmica |
Volume | 72 | Issue | 4 | Pages | 1055-1096 |
Keywords | Distributed computing; Exploration; Searching; Gathering; Oblivious anonymous robots; Asynchronous anonymous networks; Look-Compute-Move | ||||
Abstract | A set of autonomous robots have to collaborate in order to accomplish a common task in a ring-topology where neither nodes nor edges are labeled (that is, the ring is anonymous). We present a unified approach to solve three important problems: the exclusive perpetual exploration, the exclusive perpetual clearing, and the gathering problems. In the first problem, each robot aims at visiting each node infinitely often while avoiding that two robots occupy a same node (exclusivity property); in exclusive perpetual clearing (also known as graph searching), the team of robots aims at clearing the whole ring infinitely often (an edge is cleared if it is traversed by a robot or if both its endpoints are occupied); and in the gathering problem, all robots must eventually occupy the same node. We investigate these tasks in the Look-Compute-Move model where the robots cannot communicate but can perceive the positions of other robots. Each robot is equipped with visibility sensors and motion actuators, and it operates in asynchronous cycles. In each cycle, a robot takes a snapshot of the current global configuration (Look), then, based on the perceived configuration, takes a decision to stay idle or to move to one of its adjacent nodes (Compute), and in the latter case it eventually moves to this neighbor (Move). Moreover, robots are endowed with very weak capabilities. Namely, they are anonymous, asynchronous, oblivious, uniform (execute the same algorithm) and have no common sense of orientation. In this setting, we devise algorithms that, starting from an exclusive and rigid (i.e. aperiodic and asymmetric) configuration, solve the three above problems in anonymous ring-topologies. | ||||
Address | [D'Angelo, Gianlorenzo] Gran Sasso Sci Inst GSSI, Laquila, Italy, Email: gianlorenzo.dangelo@gssi.infn.it; | ||||
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:000356461400008 | Approved | |||
Call Number | UAI @ eduardo.moreno @ | Serial | 504 | ||
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 |