---
_id: '66838'
abstract:
- lang: eng
  text: 'The sliding square model is a widely used abstraction for studying self-reconfigurable
    robotic systems, where modules are square-shaped robots that move by sliding or
    rotating over one another. In this paper, we propose a novel distributed algorithm
    that enables a group of modules to reconfigure into a rhombus shape, starting
    from an arbitrary side-connected configuration. It is connectivity-preserving
    and operates under minimal assumptions: one leader module, common chirality, constant
    memory per module, and visibility and communication restricted to immediate neighbors.
    Unlike prior work, which relaxes the original sliding square move-set, our approach
    uses the unmodified move-set, addressing the additional challenge of handling
    locked configurations. Our algorithm is sequential in nature and operates with
    a worst-case time complexity of O(n^2) rounds, which is optimal for sequential
    algorithms. To improve runtime, we introduce two parallel variants of the algorithm.
    Both rely on a spanning tree data structure, allowing modules to make decisions
    based on local connectivity. Our experimental results show a significant speedup
    for the first variant, and a linear average runtime for the second variant, which
    is worst-case optimal for parallel algorithms.'
article_number: '116196'
article_type: original
author:
- first_name: Irina
  full_name: Kostitsyna, Irina
  last_name: Kostitsyna
- first_name: David
  full_name: Liedtke, David
  id: '55557'
  last_name: Liedtke
- first_name: Christian
  full_name: Scheideler, Christian
  id: '20792'
  last_name: Scheideler
citation:
  ama: Kostitsyna I, Liedtke D, Scheideler C. Distributed rhombus formation of sliding
    squares. <i>Theoretical Computer Science</i>. 2026;1085. doi:<a href="https://doi.org/10.1016/j.tcs.2026.116196">10.1016/j.tcs.2026.116196</a>
  apa: Kostitsyna, I., Liedtke, D., &#38; Scheideler, C. (2026). Distributed rhombus
    formation of sliding squares. <i>Theoretical Computer Science</i>, <i>1085</i>,
    Article 116196. <a href="https://doi.org/10.1016/j.tcs.2026.116196">https://doi.org/10.1016/j.tcs.2026.116196</a>
  bibtex: '@article{Kostitsyna_Liedtke_Scheideler_2026, title={Distributed rhombus
    formation of sliding squares}, volume={1085}, DOI={<a href="https://doi.org/10.1016/j.tcs.2026.116196">10.1016/j.tcs.2026.116196</a>},
    number={116196}, journal={Theoretical Computer Science}, publisher={Elsevier BV},
    author={Kostitsyna, Irina and Liedtke, David and Scheideler, Christian}, year={2026}
    }'
  chicago: Kostitsyna, Irina, David Liedtke, and Christian Scheideler. “Distributed
    Rhombus Formation of Sliding Squares.” <i>Theoretical Computer Science</i> 1085
    (2026). <a href="https://doi.org/10.1016/j.tcs.2026.116196">https://doi.org/10.1016/j.tcs.2026.116196</a>.
  ieee: 'I. Kostitsyna, D. Liedtke, and C. Scheideler, “Distributed rhombus formation
    of sliding squares,” <i>Theoretical Computer Science</i>, vol. 1085, Art. no.
    116196, 2026, doi: <a href="https://doi.org/10.1016/j.tcs.2026.116196">10.1016/j.tcs.2026.116196</a>.'
  mla: Kostitsyna, Irina, et al. “Distributed Rhombus Formation of Sliding Squares.”
    <i>Theoretical Computer Science</i>, vol. 1085, 116196, Elsevier BV, 2026, doi:<a
    href="https://doi.org/10.1016/j.tcs.2026.116196">10.1016/j.tcs.2026.116196</a>.
  short: I. Kostitsyna, D. Liedtke, C. Scheideler, Theoretical Computer Science 1085
    (2026).
date_created: 2026-08-25T05:30:39Z
date_updated: 2026-08-25T05:37:47Z
department:
- _id: '34'
- _id: '7'
- _id: '79'
doi: 10.1016/j.tcs.2026.116196
intvolume: '      1085'
keyword:
- modular robots
- distributed algorithms
- sliding squares
language:
- iso: eng
publication: Theoretical Computer Science
publication_identifier:
  issn:
  - 0304-3975
publication_status: published
publisher: Elsevier BV
status: public
title: Distributed rhombus formation of sliding squares
type: journal_article
user_id: '55557'
volume: 1085
year: '2026'
...