8 Search Results for "Richa, Andréa W."

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.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.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.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.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.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

Andréa W. Richa. LIPIcs, Volume 91, DISC'17, Complete Volume. In 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.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

Andréa Richa. Front Matter, Table of Contents, Preface, Symposium Organization, Awards. In 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.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
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.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
  • 7 Richa, Andréa W.
  • 3 Daymude, Joshua J.
  • 3 Randall, Dana
  • 3 Scheideler, Christian
  • 2 Oh, Shunhao
  • Show More...

  • Refine by Classification
  • 4 Theory of computation → Self-organization
  • 3 Theory of computation → Random walks and Markov chains
  • 2 Theory of computation → Concurrency
  • 1 Mathematics of computing → Stochastic processes
  • 1 Software and its engineering → Mutual exclusion
  • Show More...

  • Refine by Keyword
  • 2 Programmable matter
  • 2 concurrency
  • 2 distributed algorithms
  • 2 programmable matter
  • 2 self-organization
  • Show More...

  • Refine by Type
  • 8 document

  • Refine by Publication Year
  • 2 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 Schloss Dagstuhl - LZI GmbH Imprint Privacy Contact