[{"language":[{"iso":"eng"}],"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."}],"publication":"Stabilization, Safety, and Security of Distributed Systems","title":"Invited Paper: Distributed Rhombus Formation of Sliding Squares","publisher":"Springer Nature Switzerland","date_created":"2025-11-23T21:07:12Z","year":"2025","_id":"62285","user_id":"15578","department":[{"_id":"79"}],"editor":[{"full_name":"Bonomi, Silvia","last_name":"Bonomi","first_name":"Silvia"},{"last_name":"Mandal","full_name":"Mandal, Partha Sarathi","first_name":"Partha Sarathi"},{"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"}],"status":"public","type":"conference","conference":{"location":"Kathmandu","end_date":"2025-10-11","start_date":"2025-10-09","name":"27th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS)"},"doi":"10.1007/978-3-032-11127-2_26","date_updated":"2026-02-11T08:31:14Z","author":[{"last_name":"Kostitsyna","full_name":"Kostitsyna, Irina","first_name":"Irina"},{"last_name":"Liedtke","id":"55557","full_name":"Liedtke, David Jan","first_name":"David Jan"},{"last_name":"Scheideler","full_name":"Scheideler, Christian","id":"20792","first_name":"Christian"}],"place":"Cham","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>","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>.","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>","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.","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} }"},"page":"325-342","publication_status":"published","publication_identifier":{"isbn":["9783032111265","9783032111272"],"issn":["0302-9743","1611-3349"]}},{"user_id":"88238","_id":"64881","language":[{"iso":"eng"}],"publication":"Lecture Notes in Computer Science","type":"book_chapter","status":"public","date_created":"2026-03-11T07:42:55Z","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"}],"date_updated":"2026-03-11T07:43:49Z","publisher":"Springer Nature Switzerland","doi":"10.1007/978-3-032-11127-2_5","title":"Efficient Distributed Algorithms for Shape Reduction via Reconfigurable Circuits","publication_identifier":{"isbn":["9783032111265","9783032111272"],"issn":["0302-9743","1611-3349"]},"publication_status":"published","citation":{"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>","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.","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>.","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>.","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} }","short":"N. Almalki, S. Gupta, O. Michail, A. Padalkin, in: Lecture Notes in Computer Science, Springer Nature Switzerland, Cham, 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>"},"year":"2025","place":"Cham"}]