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