[{"publication_identifier":{"issn":["0178-2770","1432-0452"]},"author":[{"id":"88238","last_name":"Padalkin","first_name":"Andreas","full_name":"Padalkin, Andreas"},{"full_name":"Scheideler, Christian","last_name":"Scheideler","first_name":"Christian","id":"20792"}],"year":"2026","title":"Polylogarithmic time algorithms for shortest path forests in programmable matter","intvolume":"        39","date_updated":"2026-05-29T12:13:09Z","publication_status":"published","language":[{"iso":"eng"}],"article_number":"15","doi":"10.1007/s00446-026-00505-2","publication":"Distributed Computing","issue":"2","abstract":[{"text":"<jats:title>Abstract</jats:title>\r\n                  <jats:p>\r\n                    In this paper, we study the computation of shortest paths within the\r\n                    <jats:italic>geometric amoebot model</jats:italic>\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                    <jats:italic>reconfigurable circuit extension</jats:italic>\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                    <jats:italic>shortest path forest problem</jats:italic>\r\n                    where, given a set of\r\n                    <jats:italic>k</jats:italic>\r\n                    sources and a set of\r\n                    <jats:inline-formula>\r\n                      <jats:alternatives>\r\n                        <jats:tex-math>$$\\ell $$</jats:tex-math>\r\n                        <mml:math xmlns:mml=\"http://www.w3.org/1998/Math/MathML\">\r\n                          <mml:mi>ℓ</mml:mi>\r\n                        </mml:math>\r\n                      </jats:alternatives>\r\n                    </jats:inline-formula>\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                    <jats:inline-formula>\r\n                      <jats:alternatives>\r\n                        <jats:tex-math>$$O(\\log \\ell )$$</jats:tex-math>\r\n                        <mml:math xmlns:mml=\"http://www.w3.org/1998/Math/MathML\">\r\n                          <mml:mrow>\r\n                            <mml:mi>O</mml:mi>\r\n                            <mml:mo>(</mml:mo>\r\n                            <mml:mo>log</mml:mo>\r\n                            <mml:mi>ℓ</mml:mi>\r\n                            <mml:mo>)</mml:mo>\r\n                          </mml:mrow>\r\n                        </mml:math>\r\n                      </jats:alternatives>\r\n                    </jats:inline-formula>\r\n                    rounds, and the second algorithm a shortest path forest for an arbitrary number of sources within\r\n                    <jats:inline-formula>\r\n                      <jats:alternatives>\r\n                        <jats:tex-math>$$O(\\log n \\log ^2 k)$$</jats:tex-math>\r\n                        <mml:math xmlns:mml=\"http://www.w3.org/1998/Math/MathML\">\r\n                          <mml:mrow>\r\n                            <mml:mi>O</mml:mi>\r\n                            <mml:mo>(</mml:mo>\r\n                            <mml:mo>log</mml:mo>\r\n                            <mml:mi>n</mml:mi>\r\n                            <mml:msup>\r\n                              <mml:mo>log</mml:mo>\r\n                              <mml:mn>2</mml:mn>\r\n                            </mml:msup>\r\n                            <mml:mi>k</mml:mi>\r\n                            <mml:mo>)</mml:mo>\r\n                          </mml:mrow>\r\n                        </mml:math>\r\n                      </jats:alternatives>\r\n                    </jats:inline-formula>\r\n                    rounds. The former algorithm also provides an\r\n                    <jats:italic>O</jats:italic>\r\n                    (1) rounds solution for the\r\n                    <jats:italic>single pair shortest path problem</jats:italic>\r\n                    (SPSP) and an\r\n                    <jats:inline-formula>\r\n                      <jats:alternatives>\r\n                        <jats:tex-math>$$O(\\log n)$$</jats:tex-math>\r\n                        <mml:math xmlns:mml=\"http://www.w3.org/1998/Math/MathML\">\r\n                          <mml:mrow>\r\n                            <mml:mi>O</mml:mi>\r\n                            <mml:mo>(</mml:mo>\r\n                            <mml:mo>log</mml:mo>\r\n                            <mml:mi>n</mml:mi>\r\n                            <mml:mo>)</mml:mo>\r\n                          </mml:mrow>\r\n                        </mml:math>\r\n                      </jats:alternatives>\r\n                    </jats:inline-formula>\r\n                    rounds solution for the\r\n                    <jats:italic>single source shortest path problem</jats:italic>\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                    <jats:inline-formula>\r\n                      <jats:alternatives>\r\n                        <jats:tex-math>$$O(h \\log ^3 n)$$</jats:tex-math>\r\n                        <mml:math xmlns:mml=\"http://www.w3.org/1998/Math/MathML\">\r\n                          <mml:mrow>\r\n                            <mml:mi>O</mml:mi>\r\n                            <mml:mo>(</mml:mo>\r\n                            <mml:mi>h</mml:mi>\r\n                            <mml:msup>\r\n                              <mml:mo>log</mml:mo>\r\n                              <mml:mn>3</mml:mn>\r\n                            </mml:msup>\r\n                            <mml:mi>n</mml:mi>\r\n                            <mml:mo>)</mml:mo>\r\n                          </mml:mrow>\r\n                        </mml:math>\r\n                      </jats:alternatives>\r\n                    </jats:inline-formula>\r\n                    rounds w.h.p. where\r\n                    <jats:italic>h</jats:italic>\r\n                    denotes the number of holes.\r\n                  </jats:p>","lang":"eng"}],"date_created":"2026-05-29T12:11:32Z","department":[{"_id":"34"},{"_id":"7"},{"_id":"79"}],"type":"journal_article","status":"public","publisher":"Springer Science and Business Media LLC","_id":"65733","volume":39,"user_id":"15578","citation":{"bibtex":"@article{Padalkin_Scheideler_2026, title={Polylogarithmic time algorithms for shortest path forests in programmable matter}, volume={39}, DOI={<a href=\"https://doi.org/10.1007/s00446-026-00505-2\">10.1007/s00446-026-00505-2</a>}, number={215}, journal={Distributed Computing}, publisher={Springer Science and Business Media LLC}, author={Padalkin, Andreas and Scheideler, Christian}, year={2026} }","ama":"Padalkin A, Scheideler C. Polylogarithmic time algorithms for shortest path forests in programmable matter. <i>Distributed Computing</i>. 2026;39(2). doi:<a href=\"https://doi.org/10.1007/s00446-026-00505-2\">10.1007/s00446-026-00505-2</a>","mla":"Padalkin, Andreas, and Christian Scheideler. “Polylogarithmic Time Algorithms for Shortest Path Forests in Programmable Matter.” <i>Distributed Computing</i>, vol. 39, no. 2, 15, Springer Science and Business Media LLC, 2026, doi:<a href=\"https://doi.org/10.1007/s00446-026-00505-2\">10.1007/s00446-026-00505-2</a>.","short":"A. Padalkin, C. Scheideler, Distributed Computing 39 (2026).","chicago":"Padalkin, Andreas, and Christian Scheideler. “Polylogarithmic Time Algorithms for Shortest Path Forests in Programmable Matter.” <i>Distributed Computing</i> 39, no. 2 (2026). <a href=\"https://doi.org/10.1007/s00446-026-00505-2\">https://doi.org/10.1007/s00446-026-00505-2</a>.","ieee":"A. Padalkin and C. Scheideler, “Polylogarithmic time algorithms for shortest path forests in programmable matter,” <i>Distributed Computing</i>, vol. 39, no. 2, Art. no. 15, 2026, doi: <a href=\"https://doi.org/10.1007/s00446-026-00505-2\">10.1007/s00446-026-00505-2</a>.","apa":"Padalkin, A., &#38; Scheideler, C. (2026). Polylogarithmic time algorithms for shortest path forests in programmable matter. <i>Distributed Computing</i>, <i>39</i>(2), Article 15. <a href=\"https://doi.org/10.1007/s00446-026-00505-2\">https://doi.org/10.1007/s00446-026-00505-2</a>"}},{"page":"241-254","_id":"3872","publisher":"Springer Nature","user_id":"15504","volume":31,"status":"public","citation":{"mla":"Ogierman, Adrian, et al. “Sade: Competitive MAC under Adversarial SINR.” <i>Distributed Computing</i>, vol. 31, no. 3, Springer Nature, 2017, pp. 241–54, doi:<a href=\"https://doi.org/10.1007/s00446-017-0307-1\">10.1007/s00446-017-0307-1</a>.","ama":"Ogierman A, Richa A, Scheideler C, Schmid S, Zhang J. Sade: competitive MAC under adversarial SINR. <i>Distributed Computing</i>. 2017;31(3):241-254. doi:<a href=\"https://doi.org/10.1007/s00446-017-0307-1\">10.1007/s00446-017-0307-1</a>","bibtex":"@article{Ogierman_Richa_Scheideler_Schmid_Zhang_2017, title={Sade: competitive MAC under adversarial SINR}, volume={31}, DOI={<a href=\"https://doi.org/10.1007/s00446-017-0307-1\">10.1007/s00446-017-0307-1</a>}, 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} }","apa":"Ogierman, A., Richa, A., Scheideler, C., Schmid, S., &#38; Zhang, J. (2017). Sade: competitive MAC under adversarial SINR. <i>Distributed Computing</i>, <i>31</i>(3), 241–254. <a href=\"https://doi.org/10.1007/s00446-017-0307-1\">https://doi.org/10.1007/s00446-017-0307-1</a>","ieee":"A. Ogierman, A. Richa, C. Scheideler, S. Schmid, and J. Zhang, “Sade: competitive MAC under adversarial SINR,” <i>Distributed Computing</i>, vol. 31, no. 3, pp. 241–254, 2017.","chicago":"Ogierman, Adrian, Andrea Richa, Christian Scheideler, Stefan Schmid, and Jin Zhang. “Sade: Competitive MAC under Adversarial SINR.” <i>Distributed Computing</i> 31, no. 3 (2017): 241–54. <a href=\"https://doi.org/10.1007/s00446-017-0307-1\">https://doi.org/10.1007/s00446-017-0307-1</a>.","short":"A. Ogierman, A. Richa, C. Scheideler, S. Schmid, J. Zhang, Distributed Computing 31 (2017) 241–254."},"doi":"10.1007/s00446-017-0307-1","title":"Sade: competitive MAC under adversarial SINR","year":"2017","publication_identifier":{"issn":["0178-2770","1432-0452"]},"author":[{"full_name":"Ogierman, Adrian","last_name":"Ogierman","first_name":"Adrian"},{"last_name":"Richa","first_name":"Andrea","full_name":"Richa, Andrea"},{"id":"20792","full_name":"Scheideler, Christian","first_name":"Christian","last_name":"Scheideler"},{"full_name":"Schmid, Stefan","first_name":"Stefan","last_name":"Schmid"},{"full_name":"Zhang, Jin","first_name":"Jin","last_name":"Zhang"}],"date_updated":"2022-01-06T06:59:47Z","publication_status":"published","intvolume":"        31","date_created":"2018-08-10T07:05:12Z","type":"journal_article","department":[{"_id":"79"}],"issue":"3","publication":"Distributed Computing","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."}]}]