11 Search Results for "Richa, Andréa"

Volume

LIPIcs, Volume 91

31st International Symposium on Distributed Computing (DISC 2017)

DISC 2017, October 16-20, 2017, Vienna, Austria

Editors: Andréa Richa

Document
DOI: 10.4230/LIPIcs.OPODIS.2023.7
Energy-Constrained Programmable Matter Under Unfair Adversaries

Authors: Jamison W. Weber, Tishya Chhabra, Andréa W. Richa, and Joshua J. Daymude

Published in: LIPIcs, Volume 286, 27th International Conference on Principles of Distributed Systems (OPODIS 2023)

Abstract
Individual modules of programmable matter participate in their system’s collective behavior by expending energy to perform actions. However, not all modules may have access to the external energy source powering the system, necessitating a local and distributed strategy for supplying energy to modules. In this work, we present a general energy distribution framework for the canonical amoebot model of programmable matter that transforms energy-agnostic algorithms into energy-constrained ones with equivalent behavior and an 𝒪(n²)-round runtime overhead - even under an unfair adversary - provided the original algorithms satisfy certain conventions. We then prove that existing amoebot algorithms for leader election (ICDCN 2023) and shape formation (Distributed Computing, 2023) are compatible with this framework and show simulations of their energy-constrained counterparts, demonstrating how other unfair algorithms can be generalized to the energy-constrained setting with relatively little effort. Finally, we show that our energy distribution framework can be composed with the concurrency control framework for amoebot algorithms (Distributed Computing, 2023), allowing algorithm designers to focus on the simpler energy-agnostic, sequential setting but gain the general applicability of energy-constrained, asynchronous correctness.
Cite as

Jamison W. Weber, Tishya Chhabra, Andréa W. Richa, and Joshua J. Daymude. Energy-Constrained Programmable Matter Under Unfair Adversaries. In 27th International Conference on Principles of Distributed Systems (OPODIS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 286, pp. 7:1-7:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{weber_et_al:LIPIcs.OPODIS.2023.7,
  author =	{Weber, Jamison W. and Chhabra, Tishya and Richa, Andr\'{e}a W. and Daymude, Joshua J.},
  title =	{{Energy-Constrained Programmable Matter Under Unfair Adversaries}},
  booktitle =	{27th International Conference on Principles of Distributed Systems (OPODIS 2023)},
  pages =	{7:1--7:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-308-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{286},
  editor =	{Bessani, Alysson and D\'{e}fago, Xavier and Nakamura, Junya and Wada, Koichi and Yamauchi, Yukiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2023.7},
  URN =		{urn:nbn:de:0030-drops-194971},
  doi =		{10.4230/LIPIcs.OPODIS.2023.7},
  annote =	{Keywords: Programmable matter, amoebot model, energy distribution, concurrency}
}
Document
DOI: 10.4230/LIPIcs.SAND.2023.6
Adaptive Collective Responses to Local Stimuli in Anonymous Dynamic Networks

Authors: Shunhao Oh, Dana Randall, and Andréa W. Richa

Published in: LIPIcs, Volume 257, 2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023)

Abstract
We develop a framework for self-induced phase changes in programmable matter in which a collection of agents with limited computational and communication capabilities can collectively perform appropriate global tasks in response to local stimuli that dynamically appear and disappear. Agents reside on graph vertices, where each stimulus is only recognized locally, and agents communicate via token passing along edges to alert other agents to transition to an Aware state when stimuli are present and an Unaware state when the stimuli disappear. We present an Adaptive Stimuli Algorithm that is robust to competing waves of messages as multiple stimuli change, possibly adversarially. Moreover, in addition to handling arbitrary stimulus dynamics, the algorithm can handle agents reconfiguring the connections (edges) of the graph over time in a controlled way. As an application, we show how this Adaptive Stimuli Algorithm on reconfigurable graphs can be used to solve the foraging problem, where food sources may be discovered, removed, or shifted at arbitrary times. We would like the agents to consistently self-organize, using only local interactions, such that if the food remains in a position long enough, the agents transition to a gather phase in which many collectively form a single large component with small perimeter around the food. Alternatively, if no food source has existed recently, the agents should undergo a self-induced phase change and switch to a search phase in which they distribute themselves randomly throughout the lattice region to search for food. Unlike previous approaches to foraging, this process is indefinitely repeatable, withstanding competing waves of messages that may interfere with each other. Like a physical phase change, microscopic changes such as the deletion or addition of a single food source trigger these macroscopic, system-wide transitions as agents share information about the environment and respond locally to get the desired collective response.
Cite as

Shunhao Oh, Dana Randall, and Andréa W. Richa. Adaptive Collective Responses to Local Stimuli in Anonymous Dynamic Networks. In 2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 257, pp. 6:1-6:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{oh_et_al:LIPIcs.SAND.2023.6,
  author =	{Oh, Shunhao and Randall, Dana and Richa, Andr\'{e}a W.},
  title =	{{Adaptive Collective Responses to Local Stimuli in Anonymous Dynamic Networks}},
  booktitle =	{2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023)},
  pages =	{6:1--6:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-275-4},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{257},
  editor =	{Doty, David and Spirakis, Paul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2023.6},
  URN =		{urn:nbn:de:0030-drops-179424},
  doi =		{10.4230/LIPIcs.SAND.2023.6},
  annote =	{Keywords: Dynamic networks, adaptive stimuli, foraging, self-organizing particle systems, programmable matter}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2022.51
Brief Announcement: Foraging in Particle Systems via Self-Induced Phase Changes

Authors: Shunhao Oh, Dana Randall, and Andréa W. Richa

Published in: LIPIcs, Volume 246, 36th International Symposium on Distributed Computing (DISC 2022)

Abstract
The foraging problem asks how a collective of particles with limited computational, communication and movement capabilities can autonomously compress around a food source and disperse when the food is depleted or shifted, which may occur at arbitrary times. We would like the particles to iteratively self-organize, using only local interactions, to correctly gather whenever a food particle remains in a position long enough and search if no food particle has existed recently. Unlike previous approaches, these search and gather phases should be self-induced so as to be indefinitely repeatable as the food evolves, with microscopic changes to the food triggering macroscopic, system-wide phase transitions. We present a stochastic foraging algorithm based on a phase change in the fixed magnetization Ising model from statistical physics: Our algorithm is the first to leverage self-induced phase changes as an algorithmic tool. A key component of our algorithm is a careful token passing mechanism ensuring a dispersion broadcast wave will always outpace a compression wave.
Cite as

Shunhao Oh, Dana Randall, and Andréa W. Richa. Brief Announcement: Foraging in Particle Systems via Self-Induced Phase Changes. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 51:1-51:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{oh_et_al:LIPIcs.DISC.2022.51,
  author =	{Oh, Shunhao and Randall, Dana and Richa, Andr\'{e}a W.},
  title =	{{Brief Announcement: Foraging in Particle Systems via Self-Induced Phase Changes}},
  booktitle =	{36th International Symposium on Distributed Computing (DISC 2022)},
  pages =	{51:1--51:3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-255-6},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{246},
  editor =	{Scheideler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2022.51},
  URN =		{urn:nbn:de:0030-drops-172423},
  doi =		{10.4230/LIPIcs.DISC.2022.51},
  annote =	{Keywords: Foraging, self-organized particle systems, compression, phase changes}
}
Document
DOI: 10.4230/LIPIcs.SAND.2022.12
Local Mutual Exclusion for Dynamic, Anonymous, Bounded Memory Message Passing Systems

Authors: Joshua J. Daymude, Andréa W. Richa, and Christian Scheideler

Published in: LIPIcs, Volume 221, 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)

Abstract
Mutual exclusion is a classical problem in distributed computing that provides isolation among concurrent action executions that may require access to the same shared resources. Inspired by algorithmic research on distributed systems of weakly capable entities whose connections change over time, we address the local mutual exclusion problem that tasks each node with acquiring exclusive locks for itself and the maximal subset of its "persistent" neighbors that remain connected to it over the time interval of the lock request. Using the established time-varying graphs model to capture adversarial topological changes, we propose and rigorously analyze a local mutual exclusion algorithm for nodes that are anonymous and communicate via asynchronous message passing. The algorithm satisfies mutual exclusion (non-intersecting lock sets) and lockout freedom (eventual success with probability 1) under both semi-synchronous and asynchronous concurrency. It requires 𝒪(Δ) memory per node and messages of size Θ(1), where Δ is the maximum number of connections per node. We conclude by describing how our algorithm can implement the pairwise interactions assumed by population protocols and the concurrency control operations assumed by the canonical amoebot model, demonstrating its utility in both passively and actively dynamic distributed systems.
Cite as

Joshua J. Daymude, Andréa W. Richa, and Christian Scheideler. Local Mutual Exclusion for Dynamic, Anonymous, Bounded Memory Message Passing Systems. In 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 221, pp. 12:1-12:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{daymude_et_al:LIPIcs.SAND.2022.12,
  author =	{Daymude, Joshua J. and Richa, Andr\'{e}a W. and Scheideler, Christian},
  title =	{{Local Mutual Exclusion for Dynamic, Anonymous, Bounded Memory Message Passing Systems}},
  booktitle =	{1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)},
  pages =	{12:1--12:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-224-2},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{221},
  editor =	{Aspnes, James and Michail, Othon},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2022.12},
  URN =		{urn:nbn:de:0030-drops-159545},
  doi =		{10.4230/LIPIcs.SAND.2022.12},
  annote =	{Keywords: Mutual exclusion, dynamic networks, message passing, concurrency}
}
Document
DOI: 10.4230/LIPIcs.DISC.2021.20
The Canonical Amoebot Model: Algorithms and Concurrency Control

Authors: Joshua J. Daymude, Andréa W. Richa, and Christian Scheideler

Published in: LIPIcs, Volume 209, 35th International Symposium on Distributed Computing (DISC 2021)

Abstract
The amoebot model abstracts active programmable matter as a collection of simple computational elements called amoebots that interact locally to collectively achieve tasks of coordination and movement. Since its introduction (SPAA 2014), a growing body of literature has adapted its assumptions for a variety of problems; however, without a standardized hierarchy of assumptions, precise systematic comparison of results under the amoebot model is difficult. We propose the canonical amoebot model, an updated formalization that distinguishes between core model features and families of assumption variants. A key improvement addressed by the canonical amoebot model is concurrency. Much of the existing literature implicitly assumes amoebot actions are isolated and reliable, reducing analysis to the sequential setting where at most one amoebot is active at a time. However, real programmable matter systems are concurrent. The canonical amoebot model formalizes all amoebot communication as message passing, leveraging adversarial activation models of concurrent executions. Under this granular treatment of time, we take two complementary approaches to concurrent algorithm design. Using hexagon formation as a case study, we first establish a set of sufficient conditions for algorithm correctness under any concurrent execution, embedding concurrency control directly in algorithm design. We then present a concurrency control framework that uses locks to convert amoebot algorithms that terminate in the sequential setting and satisfy certain conventions into algorithms that exhibit equivalent behavior in the concurrent setting. Together, the canonical amoebot model and these complementary approaches to concurrent algorithm design open new directions for distributed computing research on programmable matter.
Cite as

Joshua J. Daymude, Andréa W. Richa, and Christian Scheideler. The Canonical Amoebot Model: Algorithms and Concurrency Control. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 20:1-20:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{daymude_et_al:LIPIcs.DISC.2021.20,
  author =	{Daymude, Joshua J. and Richa, Andr\'{e}a W. and Scheideler, Christian},
  title =	{{The Canonical Amoebot Model: Algorithms and Concurrency Control}},
  booktitle =	{35th International Symposium on Distributed Computing (DISC 2021)},
  pages =	{20:1--20:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-210-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{209},
  editor =	{Gilbert, Seth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2021.20},
  URN =		{urn:nbn:de:0030-drops-148227},
  doi =		{10.4230/LIPIcs.DISC.2021.20},
  annote =	{Keywords: Programmable matter, self-organization, distributed algorithms, concurrency}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2019.54
A Local Stochastic Algorithm for Separation in Heterogeneous Self-Organizing Particle Systems

Authors: Sarah Cannon, Joshua J. Daymude, Cem Gökmen, Dana Randall, and Andréa W. Richa

Published in: LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)

Abstract
We present and rigorously analyze the behavior of a distributed, stochastic algorithm for separation and integration in self-organizing particle systems, an abstraction of programmable matter. Such systems are composed of individual computational particles with limited memory, strictly local communication abilities, and modest computational power. We consider heterogeneous particle systems of two different colors and prove that these systems can collectively separate into different color classes or integrate, indifferent to color. We accomplish both behaviors with the same fully distributed, local, stochastic algorithm. Achieving separation or integration depends only on a single global parameter determining whether particles prefer to be next to other particles of the same color or not; this parameter is meant to represent external, environmental influences on the particle system. The algorithm is a generalization of a previous distributed, stochastic algorithm for compression (PODC '16) that can be viewed as a special case of separation where all particles have the same color. It is significantly more challenging to prove that the desired behavior is achieved in the heterogeneous setting, however, even in the bichromatic case we focus on. This requires combining several new techniques, including the cluster expansion from statistical physics, a new variant of the bridging argument of Miracle, Pascoe and Randall (RANDOM '11), the high-temperature expansion of the Ising model, and careful probabilistic arguments.
Cite as

Sarah Cannon, Joshua J. Daymude, Cem Gökmen, Dana Randall, and Andréa W. Richa. A Local Stochastic Algorithm for Separation in Heterogeneous Self-Organizing Particle Systems. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 54:1-54:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{cannon_et_al:LIPIcs.APPROX-RANDOM.2019.54,
  author =	{Cannon, Sarah and Daymude, Joshua J. and G\"{o}kmen, Cem and Randall, Dana and Richa, Andr\'{e}a W.},
  title =	{{A Local Stochastic Algorithm for Separation in Heterogeneous Self-Organizing Particle Systems}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
  pages =	{54:1--54:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-125-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{145},
  editor =	{Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2019.54},
  URN =		{urn:nbn:de:0030-drops-112696},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2019.54},
  annote =	{Keywords: Markov chains, Programmable matter, Cluster expansion}
}
Document
Complete Volume
DOI: 10.4230/LIPIcs.DISC.2017
LIPIcs, Volume 91, DISC'17, Complete Volume

Authors: Andréa W. Richa

Published in: LIPIcs, Volume 91, 31st International Symposium on Distributed Computing (DISC 2017)

Abstract
LIPIcs, Volume 91, DISC'17, Complete Volume
Cite as

31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@Proceedings{richa:LIPIcs.DISC.2017,
  title =	{{LIPIcs, Volume 91, DISC'17, Complete Volume}},
  booktitle =	{31st International Symposium on Distributed Computing (DISC 2017)},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-053-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{91},
  editor =	{Richa, Andr\'{e}a},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017},
  URN =		{urn:nbn:de:0030-drops-80247},
  doi =		{10.4230/LIPIcs.DISC.2017},
  annote =	{Keywords: Computer-Communication Networks, Distributed Systems, Concurrent Programming, Data Structures, Theory of Computation, Models of Computation, Modes of Computation}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.DISC.2017.0
Front Matter, Table of Contents, Preface, Symposium Organization, Awards

Authors: Andréa Richa

Published in: LIPIcs, Volume 91, 31st International Symposium on Distributed Computing (DISC 2017)

Abstract
Front Matter, Table of Contents, Preface, Symposium Organization, 2017 Edsger W. Dijkstra Prize in Distributed Computing, and 2017 Principles of Distributed Computing Doctoral Dissertation Award.
Cite as

31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 0:i-0:xviii, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{richa:LIPIcs.DISC.2017.0,
  author =	{Richa, Andr\'{e}a},
  title =	{{Front Matter, Table of Contents, Preface, Symposium Organization, Awards}},
  booktitle =	{31st International Symposium on Distributed Computing (DISC 2017)},
  pages =	{0:i--0:xviii},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-053-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{91},
  editor =	{Richa, Andr\'{e}a},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.0},
  URN =		{urn:nbn:de:0030-drops-79629},
  doi =		{10.4230/LIPIcs.DISC.2017.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Symposium Organization, Edsger W. Dijkstra Prize in Distributed Computing, Principles of Distributed Computi}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2017.47
Brief Announcement: On the Parallel Undecided-State Dynamics with Two Colors

Authors: Andrea Clementi, Luciano Gualà, Francesco Pasquale, and Giacomo Scornavacca

Published in: LIPIcs, Volume 91, 31st International Symposium on Distributed Computing (DISC 2017)

Abstract
The Undecided-State Dynamics is a well-known protocol that achieves Consensus in distributed systems formed by a set of n anonymous nodes interacting via a communication network. We consider this dynamics in the parallel PULL communication model on the complete graph for the binary case, i.e., when every node can either support one of two possible colors or stay in the undecided state. Previous work in this setting only considers initial color configurations with no undecided nodes and a large bias (i.e., Theta(n)) towards the majority color. A interesting open question here is whether this dynamics reaches consensus quickly, i.e. within a polylogarithmic number of rounds. In this paper we present an unconditional analysis of the Undecided-State Dynamics which answers to the above question in the affirmative. Our analysis shows that, starting from any initial configuration, the Undecided-State Dynamics reaches a monochromatic configuration within O(log^2 n) rounds, with high probability (w.h.p.). Moreover, we prove that if the initial configuration has bias Omega(sqrt(n log n)), then the dynamics converges toward the initial majority color within O(log n) round, w.h.p. At the heart of our approach there is a new analysis of the symmetry-breaking phase that the process must perform in order to escape from (almost-)unbiased configurations. Previous symmetry-breaking analysis of consensus dynamics essentially concern sequential communication models (such as Population Protocols) and/or symmetric updated rules (such as majority rules).
Cite as

Andrea Clementi, Luciano Gualà, Francesco Pasquale, and Giacomo Scornavacca. Brief Announcement: On the Parallel Undecided-State Dynamics with Two Colors. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 47:1-47:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{clementi_et_al:LIPIcs.DISC.2017.47,
  author =	{Clementi, Andrea and Gual\`{a}, Luciano and Pasquale, Francesco and Scornavacca, Giacomo},
  title =	{{Brief Announcement: On the Parallel Undecided-State Dynamics with Two Colors}},
  booktitle =	{31st International Symposium on Distributed Computing (DISC 2017)},
  pages =	{47:1--47:4},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-053-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{91},
  editor =	{Richa, Andr\'{e}a},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.47},
  URN =		{urn:nbn:de:0030-drops-79724},
  doi =		{10.4230/LIPIcs.DISC.2017.47},
  annote =	{Keywords: Distributed Consensus, Dynamics, Gossip model, Markov chains}
}
Document
DOI: 10.4230/DagRep.6.7.1
Algorithmic Foundations of Programmable Matter (Dagstuhl Seminar 16271)

Authors: Sándor Fekete, Andréa W. Richa, Kay Römer, and Christian Scheideler

Published in: Dagstuhl Reports, Volume 6, Issue 7 (2016)

Abstract
his report documents the program and the outcomes of Dagstuhl Seminar 16271 "Algorithmic Foundations of Programmable Matter", a new and emerging field that combines theoretical work on algorithms with a wide spectrum of practical applications that reach all the way from small-scale embedded systems to cyber-physical structures at nano-scale. The aim of the Dagstuhl seminar was to bring together researchers from the algorithms community with selected experts from robotics and distributed systems in order to set a solid base for the development of models, technical solutions, and algorithms that can control programmable matter. Both communities benefited from such a meeting for the following reasons: - Meeting experts from other fields provided additional insights, challenges and focus when considering work on programmable matter. - Interacting with colleagues in a close and social manner gave many starting points for continuing collaboration. - Getting together in a strong, large and enthusiastic group provided the opportunity to plan a number of followup activities. In the following, we provide details and activities of this successful week.
Cite as

Sándor Fekete, Andréa W. Richa, Kay Römer, and Christian Scheideler. Algorithmic Foundations of Programmable Matter (Dagstuhl Seminar 16271). In Dagstuhl Reports, Volume 6, Issue 7, pp. 1-14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@Article{fekete_et_al:DagRep.6.7.1,
  author =	{Fekete, S\'{a}ndor and Richa, Andr\'{e}a W. and R\"{o}mer, Kay and Scheideler, Christian},
  title =	{{Algorithmic Foundations of Programmable Matter (Dagstuhl Seminar 16271)}},
  pages =	{1--14},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2016},
  volume =	{6},
  number =	{7},
  editor =	{Fekete, S\'{a}ndor and Richa, Andr\'{e}a W. and R\"{o}mer, Kay and Scheideler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.6.7.1},
  URN =		{urn:nbn:de:0030-drops-67599},
  doi =		{10.4230/DagRep.6.7.1},
  annote =	{Keywords: distributed algorithms, distributed systems, programmable matter, robotics, self-organization}
}
  • Refine by Author
  • 8 Richa, Andréa W.
  • 4 Daymude, Joshua J.
  • 3 Randall, Dana
  • 3 Scheideler, Christian
  • 2 Oh, Shunhao
  • Show More...

  • Refine by Classification
  • 5 Theory of computation → Self-organization
  • 3 Theory of computation → Random walks and Markov chains
  • 2 Theory of computation → Concurrency
  • 2 Theory of computation → Distributed algorithms
  • 1 Mathematics of computing → Stochastic processes
  • Show More...

  • Refine by Keyword
  • 3 Programmable matter
  • 3 concurrency
  • 2 Markov chains
  • 2 distributed algorithms
  • 2 programmable matter
  • Show More...

  • Refine by Type
  • 10 document
  • 1 volume

  • Refine by Publication Year
  • 4 2017
  • 2 2022
  • 1 2016
  • 1 2019
  • 1 2021
  • Show More...

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact