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