---
_id: '65733'
abstract:
- lang: eng
text: "Abstract\r\n \r\n In
this paper, we study the computation of shortest paths within the\r\n geometric
amoebot model\r\n , a commonly used model for
programmable matter. Shortest paths are essential for various tasks and therefore
have been heavily investigated in many different contexts. We consider the\r\n
\ reconfigurable circuit extension\r\n
\ of the model where the amoebot structure is able to interconnect
amoebots by so-called circuits. These circuits permit the instantaneous transmission
of simple signals between connected amoebots. We propose distributed algorithms
for the\r\n shortest path forest problem\r\n
\ where, given a set of\r\n k\r\n
\ sources and a set of\r\n \r\n
\ \r\n $$\\ell
$$\r\n \r\n
\ ℓ\r\n \r\n
\ \r\n \r\n
\ destinations, the amoebot structure has to compute a forest
that connects each destination to its closest source on a shortest path. Our main
results are two algorithms for hole-free structures. The first algorithm constructs
a shortest path tree for a single source within\r\n \r\n
\ \r\n $$O(\\log
\\ell )$$\r\n \r\n
\ \r\n O\r\n
\ (\r\n log\r\n
\ ℓ\r\n )\r\n
\ \r\n \r\n
\ \r\n \r\n
\ rounds, and the second algorithm a shortest path forest for
an arbitrary number of sources within\r\n \r\n
\ \r\n $$O(\\log
n \\log ^2 k)$$\r\n \r\n
\ \r\n O\r\n
\ (\r\n log\r\n
\ n\r\n \r\n
\ log\r\n 2\r\n
\ \r\n k\r\n
\ )\r\n \r\n
\ \r\n \r\n
\ \r\n rounds. The
former algorithm also provides an\r\n O\r\n
\ (1) rounds solution for the\r\n single
pair shortest path problem\r\n (SPSP) and an\r\n
\ \r\n \r\n
\ $$O(\\log n)$$\r\n \r\n \r\n
\ O\r\n (\r\n
\ log\r\n n\r\n
\ )\r\n \r\n
\ \r\n \r\n
\ \r\n rounds solution
for the\r\n single source shortest path problem\r\n
\ (SSSP) since these problems are special cases of the considered
problem. Then, we adapt the latter algorithm to an offset version of the problem.
This allows us to solve the problem for amoebot structures with holes within\r\n
\ \r\n \r\n
\ $$O(h \\log ^3 n)$$\r\n
\ \r\n
\ \r\n O\r\n
\ (\r\n h\r\n
\ \r\n log\r\n
\ 3\r\n \r\n
\ n\r\n )\r\n
\ \r\n \r\n
\ \r\n \r\n
\ rounds w.h.p. where\r\n h\r\n
\ denotes the number of holes.\r\n "
article_number: '15'
author:
- first_name: Andreas
full_name: Padalkin, Andreas
id: '88238'
last_name: Padalkin
- first_name: Christian
full_name: Scheideler, Christian
id: '20792'
last_name: Scheideler
citation:
ama: Padalkin A, Scheideler C. Polylogarithmic time algorithms for shortest path
forests in programmable matter. Distributed Computing. 2026;39(2). doi:10.1007/s00446-026-00505-2
apa: Padalkin, A., & Scheideler, C. (2026). Polylogarithmic time algorithms
for shortest path forests in programmable matter. Distributed Computing,
39(2), Article 15. https://doi.org/10.1007/s00446-026-00505-2
bibtex: '@article{Padalkin_Scheideler_2026, title={Polylogarithmic time algorithms
for shortest path forests in programmable matter}, volume={39}, DOI={10.1007/s00446-026-00505-2},
number={215}, journal={Distributed Computing}, publisher={Springer Science and
Business Media LLC}, author={Padalkin, Andreas and Scheideler, Christian}, year={2026}
}'
chicago: Padalkin, Andreas, and Christian Scheideler. “Polylogarithmic Time Algorithms
for Shortest Path Forests in Programmable Matter.” Distributed Computing
39, no. 2 (2026). https://doi.org/10.1007/s00446-026-00505-2.
ieee: 'A. Padalkin and C. Scheideler, “Polylogarithmic time algorithms for shortest
path forests in programmable matter,” Distributed Computing, vol. 39, no.
2, Art. no. 15, 2026, doi: 10.1007/s00446-026-00505-2.'
mla: Padalkin, Andreas, and Christian Scheideler. “Polylogarithmic Time Algorithms
for Shortest Path Forests in Programmable Matter.” Distributed Computing,
vol. 39, no. 2, 15, Springer Science and Business Media LLC, 2026, doi:10.1007/s00446-026-00505-2.
short: A. Padalkin, C. Scheideler, Distributed Computing 39 (2026).
date_created: 2026-05-29T12:11:32Z
date_updated: 2026-05-29T12:13:09Z
department:
- _id: '34'
- _id: '7'
- _id: '79'
doi: 10.1007/s00446-026-00505-2
intvolume: ' 39'
issue: '2'
language:
- iso: eng
publication: Distributed Computing
publication_identifier:
issn:
- 0178-2770
- 1432-0452
publication_status: published
publisher: Springer Science and Business Media LLC
status: public
title: Polylogarithmic time algorithms for shortest path forests in programmable matter
type: journal_article
user_id: '15578'
volume: 39
year: '2026'
...
---
_id: '3872'
abstract:
- lang: eng
text: 'This paper considers the problem of how to efficiently share a wireless medium
which is subject to harsh external interference or even jamming. So far, this
problem is understood only in simplistic single-hop or unit disk graph models.
We in this paper initiate the study of MAC protocols for the SINR interference
model (a.k.a. physical model). This paper makes two contributions. First, we introduce
a new adversarial SINR model which captures a wide range of interference phenomena.
Concretely, we consider a powerful, adaptive adversary which can jam nodes at
arbitrary times and which is only limited by some energy budget. Our second contribution
is a distributed MAC protocol called Sade which provably achieves a constant competitive
throughput in this environment: we show that, with high probability, the protocol
ensures that a constant fraction of the non-blocked time periods is used for successful
transmissions.'
author:
- first_name: Adrian
full_name: Ogierman, Adrian
last_name: Ogierman
- first_name: Andrea
full_name: Richa, Andrea
last_name: Richa
- first_name: Christian
full_name: Scheideler, Christian
id: '20792'
last_name: Scheideler
- first_name: Stefan
full_name: Schmid, Stefan
last_name: Schmid
- first_name: Jin
full_name: Zhang, Jin
last_name: Zhang
citation:
ama: 'Ogierman A, Richa A, Scheideler C, Schmid S, Zhang J. Sade: competitive MAC
under adversarial SINR. Distributed Computing. 2017;31(3):241-254. doi:10.1007/s00446-017-0307-1'
apa: 'Ogierman, A., Richa, A., Scheideler, C., Schmid, S., & Zhang, J. (2017).
Sade: competitive MAC under adversarial SINR. Distributed Computing, 31(3),
241–254. https://doi.org/10.1007/s00446-017-0307-1'
bibtex: '@article{Ogierman_Richa_Scheideler_Schmid_Zhang_2017, title={Sade: competitive
MAC under adversarial SINR}, volume={31}, DOI={10.1007/s00446-017-0307-1},
number={3}, journal={Distributed Computing}, publisher={Springer Nature}, author={Ogierman,
Adrian and Richa, Andrea and Scheideler, Christian and Schmid, Stefan and Zhang,
Jin}, year={2017}, pages={241–254} }'
chicago: 'Ogierman, Adrian, Andrea Richa, Christian Scheideler, Stefan Schmid, and
Jin Zhang. “Sade: Competitive MAC under Adversarial SINR.” Distributed Computing
31, no. 3 (2017): 241–54. https://doi.org/10.1007/s00446-017-0307-1.'
ieee: 'A. Ogierman, A. Richa, C. Scheideler, S. Schmid, and J. Zhang, “Sade: competitive
MAC under adversarial SINR,” Distributed Computing, vol. 31, no. 3, pp.
241–254, 2017.'
mla: 'Ogierman, Adrian, et al. “Sade: Competitive MAC under Adversarial SINR.” Distributed
Computing, vol. 31, no. 3, Springer Nature, 2017, pp. 241–54, doi:10.1007/s00446-017-0307-1.'
short: A. Ogierman, A. Richa, C. Scheideler, S. Schmid, J. Zhang, Distributed Computing
31 (2017) 241–254.
date_created: 2018-08-10T07:05:12Z
date_updated: 2022-01-06T06:59:47Z
department:
- _id: '79'
doi: 10.1007/s00446-017-0307-1
intvolume: ' 31'
issue: '3'
page: 241-254
publication: Distributed Computing
publication_identifier:
issn:
- 0178-2770
- 1432-0452
publication_status: published
publisher: Springer Nature
status: public
title: 'Sade: competitive MAC under adversarial SINR'
type: journal_article
user_id: '15504'
volume: 31
year: '2017'
...