On the Power of Graphical Reconfigurable Circuits
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909291729911808 |
|---|---|
| author | Emek, Yuval Gil, Yuval Harlev, Noga |
| author_facet | Emek, Yuval Gil, Yuval Harlev, Noga |
| contents | We introduce the \emph{graphical reconfigurable circuits (GRC)} model as an abstraction for distributed graph algorithms whose communication scheme is based on local mechanisms that collectively construct long-range reconfigurable channels (this is an extension to general graphs of a distributed computational model recently introduced by Feldmann et al.\ (JCB 2022) for hexagonal grids). The crux of the GRC model lies in its modest assumptions: (1) the individual nodes are computationally weak, with state space bounded independently of any global graph parameter; and (2) the reconfigurable communication channels are highly restrictive, only carrying information-less signals (a.k.a.\ \emph{beeps}). Despite these modest assumptions, we prove that GRC algorithms can solve many important distributed tasks efficiently, i.e., in polylogarithmic time. On the negative side, we establish various runtime lower bounds, proving that for other tasks, GRC algorithms (if they exist) are doomed to be slow. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_10761 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On the Power of Graphical Reconfigurable Circuits Emek, Yuval Gil, Yuval Harlev, Noga Distributed, Parallel, and Cluster Computing We introduce the \emph{graphical reconfigurable circuits (GRC)} model as an abstraction for distributed graph algorithms whose communication scheme is based on local mechanisms that collectively construct long-range reconfigurable channels (this is an extension to general graphs of a distributed computational model recently introduced by Feldmann et al.\ (JCB 2022) for hexagonal grids). The crux of the GRC model lies in its modest assumptions: (1) the individual nodes are computationally weak, with state space bounded independently of any global graph parameter; and (2) the reconfigurable communication channels are highly restrictive, only carrying information-less signals (a.k.a.\ \emph{beeps}). Despite these modest assumptions, we prove that GRC algorithms can solve many important distributed tasks efficiently, i.e., in polylogarithmic time. On the negative side, we establish various runtime lower bounds, proving that for other tasks, GRC algorithms (if they exist) are doomed to be slow. |
| title | On the Power of Graphical Reconfigurable Circuits |
| topic | Distributed, Parallel, and Cluster Computing |
| url | https://arxiv.org/abs/2408.10761 |