---
_id: '62285'
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.'
author:
- first_name: Irina
full_name: Kostitsyna, Irina
last_name: Kostitsyna
- first_name: David Jan
full_name: Liedtke, David Jan
id: '55557'
last_name: Liedtke
- first_name: Christian
full_name: Scheideler, Christian
id: '20792'
last_name: Scheideler
citation:
ama: 'Kostitsyna I, Liedtke DJ, Scheideler C. Invited Paper: Distributed Rhombus
Formation of Sliding Squares. In: Bonomi S, Mandal PS, Robinson P, Sharma G, Tixeuil
S, eds. Stabilization, Safety, and Security of Distributed Systems. Springer
Nature Switzerland; 2025:325-342. doi:10.1007/978-3-032-11127-2_26'
apa: 'Kostitsyna, I., Liedtke, D. J., & Scheideler, C. (2025). Invited Paper:
Distributed Rhombus Formation of Sliding Squares. In S. Bonomi, P. S. Mandal,
P. Robinson, G. Sharma, & S. Tixeuil (Eds.), Stabilization, Safety, and
Security of Distributed Systems (pp. 325–342). Springer Nature Switzerland.
https://doi.org/10.1007/978-3-032-11127-2_26'
bibtex: '@inproceedings{Kostitsyna_Liedtke_Scheideler_2025, place={Cham}, title={Invited
Paper: Distributed Rhombus Formation of Sliding Squares}, DOI={10.1007/978-3-032-11127-2_26},
booktitle={Stabilization, Safety, and Security of Distributed Systems}, publisher={Springer
Nature Switzerland}, author={Kostitsyna, Irina and Liedtke, David Jan and Scheideler,
Christian}, editor={Bonomi, Silvia and Mandal, Partha Sarathi and Robinson, Peter
and Sharma, Gokarna and Tixeuil, Sebastien}, year={2025}, pages={325–342} }'
chicago: 'Kostitsyna, Irina, David Jan Liedtke, and Christian Scheideler. “Invited
Paper: Distributed Rhombus Formation of Sliding Squares.” In Stabilization,
Safety, and Security of Distributed Systems, edited by Silvia Bonomi, Partha
Sarathi Mandal, Peter Robinson, Gokarna Sharma, and Sebastien Tixeuil, 325–42.
Cham: Springer Nature Switzerland, 2025. https://doi.org/10.1007/978-3-032-11127-2_26.'
ieee: 'I. Kostitsyna, D. J. Liedtke, and C. Scheideler, “Invited Paper: Distributed
Rhombus Formation of Sliding Squares,” in Stabilization, Safety, and Security
of Distributed Systems, Kathmandu, 2025, pp. 325–342, doi: 10.1007/978-3-032-11127-2_26.'
mla: 'Kostitsyna, Irina, et al. “Invited Paper: Distributed Rhombus Formation of Sliding
Squares.” Stabilization, Safety, and Security of Distributed Systems, edited
by Silvia Bonomi et al., Springer Nature Switzerland, 2025, pp. 325–42, doi:10.1007/978-3-032-11127-2_26.'
short: 'I. Kostitsyna, D.J. Liedtke, C. Scheideler, in: S. Bonomi, P.S. Mandal,
P. Robinson, G. Sharma, S. Tixeuil (Eds.), Stabilization, Safety, and Security
of Distributed Systems, Springer Nature Switzerland, Cham, 2025, pp. 325–342.'
conference:
end_date: 2025-10-11
location: Kathmandu
name: 27th International Symposium on Stabilization, Safety, and Security of Distributed
Systems (SSS)
start_date: 2025-10-09
date_created: 2025-11-23T21:07:12Z
date_updated: 2026-02-11T08:31:14Z
department:
- _id: '79'
doi: 10.1007/978-3-032-11127-2_26
editor:
- first_name: Silvia
full_name: Bonomi, Silvia
last_name: Bonomi
- first_name: Partha Sarathi
full_name: Mandal, Partha Sarathi
last_name: Mandal
- first_name: Peter
full_name: Robinson, Peter
last_name: Robinson
- first_name: Gokarna
full_name: Sharma, Gokarna
last_name: Sharma
- first_name: Sebastien
full_name: Tixeuil, Sebastien
last_name: Tixeuil
language:
- iso: eng
page: 325-342
place: Cham
publication: Stabilization, Safety, and Security of Distributed Systems
publication_identifier:
isbn:
- '9783032111265'
- '9783032111272'
issn:
- 0302-9743
- 1611-3349
publication_status: published
publisher: Springer Nature Switzerland
status: public
title: 'Invited Paper: Distributed Rhombus Formation of Sliding Squares'
type: conference
user_id: '15578'
year: '2025'
...
---
_id: '64881'
author:
- first_name: Nada
full_name: Almalki, Nada
last_name: Almalki
- first_name: Siddharth
full_name: Gupta, Siddharth
last_name: Gupta
- first_name: Othon
full_name: Michail, Othon
last_name: Michail
- first_name: Andreas
full_name: Padalkin, Andreas
last_name: Padalkin
citation:
ama: 'Almalki N, Gupta S, Michail O, Padalkin A. Efficient Distributed Algorithms
for Shape Reduction via Reconfigurable Circuits. In: Lecture Notes in Computer
Science. Springer Nature Switzerland; 2025. doi:10.1007/978-3-032-11127-2_5'
apa: Almalki, N., Gupta, S., Michail, O., & Padalkin, A. (2025). Efficient Distributed
Algorithms for Shape Reduction via Reconfigurable Circuits. In Lecture Notes
in Computer Science. Springer Nature Switzerland. https://doi.org/10.1007/978-3-032-11127-2_5
bibtex: '@inbook{Almalki_Gupta_Michail_Padalkin_2025, place={Cham}, title={Efficient
Distributed Algorithms for Shape Reduction via Reconfigurable Circuits}, DOI={10.1007/978-3-032-11127-2_5},
booktitle={Lecture Notes in Computer Science}, publisher={Springer Nature Switzerland},
author={Almalki, Nada and Gupta, Siddharth and Michail, Othon and Padalkin, Andreas},
year={2025} }'
chicago: 'Almalki, Nada, Siddharth Gupta, Othon Michail, and Andreas Padalkin. “Efficient
Distributed Algorithms for Shape Reduction via Reconfigurable Circuits.” In Lecture
Notes in Computer Science. Cham: Springer Nature Switzerland, 2025. https://doi.org/10.1007/978-3-032-11127-2_5.'
ieee: 'N. Almalki, S. Gupta, O. Michail, and A. Padalkin, “Efficient Distributed
Algorithms for Shape Reduction via Reconfigurable Circuits,” in Lecture Notes
in Computer Science, Cham: Springer Nature Switzerland, 2025.'
mla: Almalki, Nada, et al. “Efficient Distributed Algorithms for Shape Reduction
via Reconfigurable Circuits.” Lecture Notes in Computer Science, Springer
Nature Switzerland, 2025, doi:10.1007/978-3-032-11127-2_5.
short: 'N. Almalki, S. Gupta, O. Michail, A. Padalkin, in: Lecture Notes in Computer
Science, Springer Nature Switzerland, Cham, 2025.'
date_created: 2026-03-11T07:42:55Z
date_updated: 2026-03-11T07:43:49Z
doi: 10.1007/978-3-032-11127-2_5
language:
- iso: eng
place: Cham
publication: Lecture Notes in Computer Science
publication_identifier:
isbn:
- '9783032111265'
- '9783032111272'
issn:
- 0302-9743
- 1611-3349
publication_status: published
publisher: Springer Nature Switzerland
status: public
title: Efficient Distributed Algorithms for Shape Reduction via Reconfigurable Circuits
type: book_chapter
user_id: '88238'
year: '2025'
...