The Splendors and Miseries of Rounds
Author: 
Adam ShimiAuthors Info & Claims
Abstract
Take a stroll with me through the distributed computing literature: we could scour the proceedings of PODC, DISC, SIROCCO, OPODIS, and more; we could explore the issues of Distributed Com- puting; or we could skim through the multitude of preprints on arXiv. Yet, I can already predict that with good probability, the paper we choose to read will contain the word \round" or łayer".1 Is it a lower-bound paper? Then round complexity is probably one measure of performance considered. Is it a combinatorial topology paper? Almost all techniques developed from application of combinatorial topology assume layers of communication, such that an execution can be reduced as successive complexes; here again rounds are essential. Is it a paper on fault-tolerance? Then some broadcasting strategy to ensure decent replication probably uses rounds.
References
[1]
Yehuda Afek and Eli Gafni. A simple characterization of asynchronous computations. Theor. Comput. Sci., 561:88{95, January 2015.
[2]
Eshrat Arjomandi, Michael J. Fischer, and Nancy A. Lynch. A di erence in efficiency between synchronous and asynchronous systems. In Proceedings of the Thirteenth An- nual ACM Symposium on Theory of Computing, STOC '81, pages 128{132. ACM, 1981.
[3]
Sanjeev Arora and Boaz Barak. Computational Complexity: A Modern Approach. Cambridge University Press, 1st edition, 2009.
[4]
Michael Ben-Or. Another advantage of free choice (extended abstract): Completely asynchronous agreement protocols. In Proceedings of the Second Annual ACM Symposium on Principles of Distributed Computing, PODC '83, pages 27{30. ACM, 1983. 800221.806707.
[5]
Martin Biely, Peter Robinson, Manfred Schmid, Ulrich Schwarz, and Kyrill Winkler. Gracefully degrading consensus and k-set agreement in directed dynamic networks. Theoretical Computer Science, 726:41{77, 2018.
[6]
Tushar Deepak Chandra, Vassos Hadzilacos, and Sam Toueg. The weakest failure detector for solving consensus. J. ACM, 43(4):685{722, July 1996.
[7]
Tushar Deepak Chandra and Sam Toueg. Unreliable failure detectors for reliable distributed systems. J. ACM, 43(2):225{267, March 1996.
[8]
Mouna Chaouch-Saad, Bernadette Charron-Bost, and Stephan Merz. A reduction theorem for the veri cation of round-based distributed algorithms. In Proceedings of the 3rd International Workshop on Reachability Problems, RP '09, pages 93{106. Springer-Verlag, 2009. 1007/978--3--642-04420--5_10.
[9]
Bernadette Charron-Bost, Henri Debrat, and Stephan Merz. Formal veri cation of consensus algorithms tolerating malicious faults. In Stabilization, Safety, and Security of Distributed Sys- tems, pages 120{134. Springer Berlin Heidelberg, 2011. 11.
[10]
Bernadette Charron-Bost, Matthias Fugger, and Thomas Nowak. Approximate consensus in highly dynamic networks: The role of averaging algorithms. In Automata, Languages, and Programming, pages 528{539, 2015.
[11]
Bernadette Charron-Bost and Andr--e Schiper. The heard-of model: computing in distributed systems with benign faults. Distributed Computing, 22(1):49{71, April 2009. s00446-009-0084--6.
[12]
Imrich Chlamtac and Shay Kutten. On broadcasting in radio networks - problem analysis and protocol design. IEEE Transactions on Communications, 33(12):1240{1246, December 1985.
[13]
Alejandro Cornejo, Anna Dornhaus, Nancy Lynch, and Radhika Nagpal. Task allocation in ant colonies. In Proceedings of the 28th International Conference on Distributed Computing, DISC'14, pages 46{60. Springer-Verlag, 2014.
[14]
Alejandro Cornejo and Fabian Kuhn. Deploying wireless networks with beeps. In Proceed- ings of the 24th International Conference on Distributed Computing, DISC'10, pages 148{162. Springer-Verlag, 2010.
[15]
--Etienne Coulouma, Emmanuel Godard, and Joseph Peters. A characterization of oblivious message adversaries for which consensus is solvable. Theoretical Computer Science, 584:80{ 90, 2015. Special Issue on Structural Information and Communication Complexity.
[16]
Adrien Damien, Cezara Dragoi, Alexandru Militaru, and Josef Widder. Reducing asynchrony to synchronized rounds. CoRR, abs/1804.07078, 2018. URL: http://arxiv.org/abs/1804. 07078, arXiv:1804.07078.
[17]
Atish Das Sarma, Stephan Holzer, Liah Kor, Amos Korman, Danupon Nanongkai, Gopal Pandurangan, David Peleg, and Roger Wattenhofer. Distributed veri cation and hardness of distributed approximation. In Proceedings of the Forty-third Annual ACM Symposium on The- ory of Computing, STOC '11, pages 363{372. ACM, 2011.
[18]
Cezara Dragoi, Thomas A. Henzinger, and Damien Zu erey. Psync: A partially synchronous language for fault-tolerant distributed algorithms. SIGPLAN Not., 51(1):400{415, January 2016.
[19]
Tzilla Elrad and Nissim Francez. Decomposition of distributed programs into communicationclosed layers. Science of Computer Programming, 2(3):155{173, 1982. 0167--6423(83)90013--8.
[20]
Pierre Fraigniaud, Amos Korman, and David Peleg. Towards a complexity theory for local distributed computing. J. ACM, 60(5):35:1{35:26, October 2013.
[21]
Eli Gafni. Round-by-round fault detectors (extended abstract): Unifying synchrony and asynchrony. In Proceedings of the Seventeenth Annual ACM Symposium on Principles of Distributed Computing, PODC '98, pages 143{152. ACM, 1998.
[22]
Mohsen Gha ari, David G. Harris, and Fabian Kuhn. On derandomizing local distributed algorithms. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 662{673, October 2018.
[23]
Seth Gilbert, James Maguire, and Calvin Newport. On bioelectric algorithms: A novel application of theoretical computer science to core problems in developmental biology. CoRR, abs/1809.10046, 2018. URL: http://arxiv.org/abs/1809.10046.
[24]
Klaus V. Gleissenthall, Rami Gokhan Kici, Alexander Bakst, Deian Stefan, and Ranjit Jhala. Pretend synchrony: Synchronous veri cation of asynchronous distributed programs. Proc. ACM Program. Lang., 3(POPL):59:1{59:30, January 2019.
[25]
Emmanuel Godard and Eloi Perdereau. k-set agreement in communication networks with omission faults. In 20th International Conference on Principles of Distributed Systems (OPODIS 2016), volume 70 of Leibniz International Proceedings in Informatics (LIPIcs), pages 8:1{8:17, Dagstuhl, Germany, 2017. Schloss Dagstuhl{Leibniz-Zentrum fuer Informatik.
[26]
Oded Goldreich. Computational Complexity: A Conceptual Perspective. Cambridge University Press, 1st edition, 2008.
[27]
Mika Goos and Jukka Suomela. Locally checkable proofs. In Proceedings of the 30th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, PODC '11, pages 159{168. ACM, 2011.
[28]
Rachid Guerraoui. Indulgent algorithms (preliminary version). In Proceedings of the Nineteenth Annual ACM Symposium on Principles of Distributed Computing, PODC '00, pages 289{297. ACM, 2000.
[29]
Bernhard Haeupler and Fabian Kuhn. Lower bounds on information dissemination in dynamic networks. In Distributed Computing, pages 166{180. Springer Berlin Heidelberg, 2012.
[30]
Lauri Hella, Matti Jarvisalo, Antti Kuusisto, Juhana Laurinharju, Tuomo Lempiainen, Kerkko Luosto, Jukka Suomela, and Jonni Virtema. Weak models of distributed computing, with connections to modal logic. In Proceedings of the 2012 ACM Symposium on Principles of Dis- tributed Computing, PODC '12, pages 185{194. ACM, 2012.
[31]
Maurice Herlihy, Dmitry Kozlov, and Sergio Rajsbaum. Distributed Computing Through Com- binatorial Topology. Morgan Kaufmann Publishers Inc., 1st edition, 2013.
[32]
Maurice Herlihy and Nir Shavit. The topological structure of asynchronous computability. J. ACM, 46(6):858{923, November 1999.
[33]
Denis Jeanneau, Thibault Rieutord, Luciana Arantes, and Pierre Sens. Solving k-set agreement using failure detectors in unknown dynamic networks. IEEE Transactions on Parallel and Distributed Systems, 28(5):1484{1499, 2017.
[34]
Flavio P. Junqueira, Benjamin C. Reed, and Marco Sera ni. Zab: High-performance broadcast for primary-backup systems. In Proceedings of the 2011 IEEE/IFIP 41st International Con- ference on Dependable Systems&Networks, DSN '11, pages 245{256. IEEE Computer Society, 2011.
[35]
Idit Keidar and Alexander Shraer. Timeliness, failure-detectors, and consensus performance. In Proceedings of the Twenty- fth Annual ACM Symposium on Principles of Distributed Com- puting, PODC '06, pages 169{178. ACM, 2006.
[36]
Amos Korman and Shay Kutten. On distributed veri cation. In Proceedings of the 8th In- ternational Conference on Distributed Computing and Networking, ICDCN'06, pages 100{114. Springer-Verlag, 2006.
[37]
Fabian Kuhn, Thomas Locher, and Rotem Oshman. Gradient clock synchronization in dynamic networks. Theory of Computing Systems, 49(4):781{816, Nov 2011. s00224-011--9348--1.
[38]
Fabian Kuhn, Nancy Lynch, and Rotem Oshman. Distributed computation in dynamic networks. In Proceedings of the Forty-second ACM Symposium on Theory of Computing, STOC '10, pages 513{522. ACM, 2010.
[39]
Fabian Kuhn, Yoram Moses, and Rotem Oshman. Coordinated consensus in dynamic networks. In Proceedings of the 30th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, PODC '11, pages 1{10. ACM, 2011.
[40]
Leslie Lamport. The part-time parliament. ACM Trans. Comput. Syst., 16(2):133{169, May 1998.
[41]
Ognjen Mari--c, Christoph Sprenger, and David Basin. Cuto bounds for consensus algorithms. In Computer Aided Veri cation, pages 217{237. Springer International Publishing, 2017.
[42]
Thomas Nowak, Ulrich Schmid, and Kyrill Winkler. Topological characterization of consensus under general message adversaries. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC '19, 2019.
[43]
Brian M. Oki and Barbara H. Liskov. Viewstamped replication: A new primary copy method to support highly-available distributed systems. In Proceedings of the Seventh Annual ACM Symposium on Principles of Distributed Computing, PODC '88, pages 8{17. ACM, 1988.
[44]
David Peleg. Distributed Computing: A Locality-sensitive Approach. Society for Industrial and Applied Mathematics, 2000.
[45]
Michel Raynal and Matthieu Roy. A note on a simple equivalence between round-based synchronous and asynchronous models. In Proceedings of the 11th Paci c Rim International Symposium on Dependable Computing, PRDC '05, pages 387{392. IEEE Computer Society, 2005.
[46]
Michel Raynal and Julien Stainer. Synchrony weakened by message adversaries vs asynchrony restricted by failure detectors. In Proceedings of the 2013 ACM Symposium on Principles of Distributed Computing, PODC '13, pages 166{175. ACM, 2013. 2484249.
[47]
Nicola Santoro and Peter Widmayer. Time is not a healer. In Proceedings of the 6th An- nual Symposium on Theoretical Aspects of Computer Science on STACS 89, pages 304{313. Springer-Verlag New York, Inc., 1989.
[48]
Ulrich Schmid, Manfred Schwarz, and Kyrill Winkler. On the strongest message adversary for consensus in directed dynamic networks. In Structural Information and Commu- nication Complexity, pages 102{120. Springer International Publishing, 2018. 978--3-030-01325--7_13.
[49]
Adam Shimi, Aur--elie Hurault, and Philippe Qu--einnec. Characterizing asynchronous messagepassing models through rounds. In 22nd International Conference on Principles of Distributed Systems (OPODIS 2018), volume 125 of Leibniz International Proceedings in Informatics (LIPIcs), pages 18:1{18:17, 2018.
Recommendations
Differential attack on nine rounds of the SEED block cipher
The SEED block cipher has a 128-bit block length, a 128-bit user key and a total number of 16 rounds. It is an ISO international standard. In this letter, we describe two 7-round differentials with a trivially larger probability than the best previously ...
Improving integral attacks against Rijndael-256 up to 9 rounds
AFRICACRYPT'08: Proceedings of the Cryptology in Africa 1st international conference on Progress in cryptologyRijndael is a block cipher designed by V. Rijmen and J. Daemen and it was chosen in its 128-bit block version as AES by the NIST in October 2000. Three key lengths - 128, 192 or 256 bits - are allowed. In the original contribution describing Rijndael [4]...
Attacking 9 and 10 Rounds of AES-256
ACISP '09: Proceedings of the 14th Australasian Conference on Information Security and PrivacyThe AES-256 has received less attention in cryptanalysis than the 192 or 128-bit versions of the AES. In this paper we propose new attacks on 9 and 10-round AES-256. In particular we present a 9-round attack on AES-256 which has the lowest data ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
September 2019
92 pages
Copyright © 2019 Copyright is held by the owner/author(s).
Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for third-party components of this work must be honored. For all other uses, contact the Owner/Author.
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 24 September 2019
Published in SIGACT Volume 50, Issue 3
Check for updates
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 98Total Downloads
- Downloads (Last 12 months)6
- Downloads (Last 6 weeks)1
Reflects downloads up to 18 Feb 2025
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in