{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T05:03:59Z","timestamp":1750309439144,"version":"3.41.0"},"reference-count":23,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2024,12,5]],"date-time":"2024-12-05T00:00:00Z","timestamp":1733356800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"French Agence Nationale de la Recherche","award":["ANR-20-CE25-0017 (SeMaFoR project) and ANR-22-CE25-0008-01 (SkyData project)"],"award-info":[{"award-number":["ANR-20-CE25-0017 (SeMaFoR project) and ANR-22-CE25-0008-01 (SkyData project)"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Form. Asp. Comput."],"published-print":{"date-parts":[[2024,12,31]]},"abstract":"<jats:p>\n            In the cloud computing context, several applications run concurrently over the same underlying physical infrastructure. Phase-based algorithms are key building blocks for many distributed applications such as DBMS or transaction validation services. Indeed, these applications rely on consensus or atomic validation solved by phase-based algorithms (Paxos, ZAB, two-phase commit, etc.). In each phase, at least one participant broadcasts a message and waits for the responses from a subset of the recipients before starting the next phase. For a given phase-based algorithm, it is then possible to predict future communications for each node. Based on this observation, we propose a generic and low-intrusive solution to save network bandwidth in a cloud context by aggregating messages sent by several applications in an opportunistic way. We propose a new API to easily apply our mechanism with applications using phase-based algorithms. The core of this API is the overloading of the\n            <jats:italic>send<\/jats:italic>\n            primitive, where the users can define a tradeoff between message saving and latency degradation. We evaluate our mechanisms using multiple instances of the same algorithm (three variants of the Paxos consensus and the Zookeeper Atomic Broadcast algorithm) running concurrently. Our results show that a good tuning of the new\n            <jats:italic>send<\/jats:italic>\n            primitive saves up to 30% of bandwidth with only a 5% degradation in latency.\n          <\/jats:p>","DOI":"10.1145\/3698593","type":"journal-article","created":{"date-parts":[[2024,10,19]],"date-time":"2024-10-19T11:10:06Z","timestamp":1729336206000},"page":"1-23","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["OMAHA: Opportunistic Message Aggregation for pHase-based Algorithms"],"prefix":"10.1145","volume":"36","author":[{"ORCID":"https:\/\/orcid.org\/0009-0001-0014-4026","authenticated-orcid":false,"given":"Celia","family":"Mahamdi","sequence":"first","affiliation":[{"name":"CNRS, LIP6, DELYS, Sorbonne Universit\u00e9, Paris, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6922-2451","authenticated-orcid":false,"given":"Jonathan","family":"Lejeune","sequence":"additional","affiliation":[{"name":"CNRS, LIP6, DELYS, Sorbonne Universit\u00e9, Paris, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0006-6597-0704","authenticated-orcid":false,"given":"Julien","family":"Sopena","sequence":"additional","affiliation":[{"name":"CNRS, LIP6, DELYS, Sorbonne Universit\u00e9, Paris, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5156-7715","authenticated-orcid":false,"given":"Pierre","family":"Sens","sequence":"additional","affiliation":[{"name":"CNRS, LIP6, DELYS, Sorbonne Universit\u00e9, Paris, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0000-6135-4695","authenticated-orcid":false,"given":"Mesaac","family":"Makpangou","sequence":"additional","affiliation":[{"name":"CNRS, LIP6, Inria, Sorbonne Universit\u00e9, Paris, France"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,12,5]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"crossref","unstructured":"Daniel Balouek Alexandra Carpen Amarie Ghislain Charrier Fr\u00e9d\u00e9ric Desprez Emmanuel Jeannot Emmanuel Jeanvoine Adrien L\u00e8bre David Margery Nicolas Niclausse Lucas Nussbaum Olivier Richard Christian Perez Flavien Quesnel Cyril Rohr and Luc Sarzyniec. 2013. Adding virtualization capabilities to the Grid\u20195000 testbed. In Cloud Computing and Services Science volume 367 of Communications in Computer and Information Science. Springer International Publishing 3\u201320.","DOI":"10.1007\/978-3-319-04519-1_1"},{"key":"e_1_3_3_3_2","doi-asserted-by":"crossref","first-page":"2106","DOI":"10.1109\/IWCMC48107.2020.9148470","volume-title":"2020 International Wireless Communications and Mobile Computing (IWCMC\u201920)","author":"Alqahtani Jarallah","year":"2020","unstructured":"Jarallah Alqahtani, Sultan Alanazi, and Bechir Hamdaoui. 2020. Traffic behavior in cloud data centers: A survey. In 2020 International Wireless Communications and Mobile Computing (IWCMC\u201920). IEEE, 2106\u20132111."},{"key":"e_1_3_3_4_2","doi-asserted-by":"crossref","unstructured":"B. R. Badrinath and Pradeep Sudame. 2000. Gathercast: the design and implementation of a programmable aggregation mechanism for the internet. In 9th International Conference on Computer Communications and Networks. Las Vegas NV 206\u2013213.","DOI":"10.1109\/ICCCN.2000.885492"},{"key":"e_1_3_3_5_2","doi-asserted-by":"publisher","DOI":"10.1145\/1879141.1879175"},{"key":"e_1_3_3_6_2","unstructured":"Mike Burrows. 2006. The Chubby lock service for loosely-coupled distributed systems. In Proceedings of the 7th Symposium on Operating Systems Design and Implementation (OSDI\u201906). USENIX Association USA 335\u2013350."},{"key":"e_1_3_3_7_2","doi-asserted-by":"crossref","unstructured":"Saksham Chand Yanhong A. Liu and Scott D. Stoller. 2016. Formal Verification of Multi-Paxos for Distributed Consensus. 119\u2013136. https:\/\/arxiv.org\/pdf\/1606.01387.pdf","DOI":"10.1007\/978-3-319-48989-6_8"},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2020.3008512"},{"key":"e_1_3_3_9_2","doi-asserted-by":"publisher","unstructured":"James C. Corbett Jeffrey Dean Michael Epstein Andrew Fikes Christopher Frost J. J. Furman Sanjay Ghemawat Andrey Gubarev Christopher Heiser Peter Hochschild Wilson Hsieh Sebastian Kanthak Eugene Kogan Hongyi Li Alexander Lloyd Sergey Melnik David Mwaura David Nagle Sean Quinlan Rajesh Rao Lindsay Rolig Yasushi Saito Michal Szymaniak Christopher Taylor Ruth Wang and Dale Woodford. 2013. Spanner: Google\u2019s globally distributed database. ACM Trans. Comput. Syst. 31 3 Article 8 (August 2013) 22 pages. 10.1145\/2491245","DOI":"10.1145\/2491245"},{"key":"e_1_3_3_10_2","article-title":"Multi-Paxos: An Implementation and Evaluation","author":"Du Hao","year":"2009","unstructured":"Hao Du and David J. St Hilaire. 2009. Multi-Paxos: An Implementation and Evaluation. Department of Computer Science and Engineering, University of Washington, Tech. Rep. UW-CSE-09-09-02 (2009). https:\/\/dada.cs.washington.edu\/research\/tr\/2009\/09\/UW-CSE-09-09-02.PDF","journal-title":"Department of Computer Science and Engineering, University of Washington, Tech. Rep. UW-CSE-09-09-02"},{"key":"e_1_3_3_11_2","doi-asserted-by":"crossref","unstructured":"\u00c1lvaro Garc\u00eda-P\u00e9rez Alexey Gotsman Yuri Meshman and Ilya Sergey. 2018. Paxos Consensus Deconstructed and Abstracted. 912\u2013939. https:\/\/software.imdea.org\/gotsman\/papers\/paxos-esop18.pdf","DOI":"10.1007\/978-3-319-89884-1_32"},{"key":"e_1_3_3_12_2","doi-asserted-by":"publisher","DOI":"10.1109\/MEDITCOM58224.2023.10266597"},{"key":"e_1_3_3_13_2","doi-asserted-by":"crossref","unstructured":"Flavio P. Junqueira Benjamin C. Reed and Marco Serafini. 2011. Zab: High-performance broadcast for primary-backup systems. In 2011 IEEE\/IFIP 41st International Conference on Dependable Systems & Networks (DSN\u201911). 245\u2013256.","DOI":"10.1109\/DSN.2011.5958223"},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/1644893.1644918"},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/3552326.3587450"},{"key":"e_1_3_3_16_2","doi-asserted-by":"crossref","unstructured":"Sanjeev Khanna Joseph Naor and Danny Raz. 2002. Control message aggregation in group communication protocols. In Proceedings of the 29th International Colloquium on Automata Languages and Programming (ICALP\u201902). 135\u2013146.","DOI":"10.1007\/3-540-45465-9_13"},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","unstructured":"Leslie Lamport. 2019. The part-time parliament. Concurrency: The Works of Leslie Lamport. Association for Computing Machinery New York NY USA 277\u2013317. 10.1145\/3335772.3335939","DOI":"10.1145\/3335772.3335939"},{"key":"e_1_3_3_18_2","doi-asserted-by":"crossref","DOI":"10.1007\/s00446-006-0005-x","article-title":"Fast Paxos","author":"Lamport Leslie","year":"2006","unstructured":"Leslie Lamport. 2006. Fast Paxos. Distributed Computing 19 (2006), 79\u2013103. https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2016\/02\/tr-2005-112.pdf","journal-title":"Distributed Computing"},{"key":"e_1_3_3_19_2","doi-asserted-by":"publisher","DOI":"10.14778\/2536360.2536366"},{"key":"e_1_3_3_20_2","doi-asserted-by":"publisher","DOI":"10.1109\/tdsc.2006.35"},{"key":"e_1_3_3_21_2","doi-asserted-by":"crossref","unstructured":"Alberto Montresor and M\u00e1rk Jelasity. 2009. PeerSim: A scalable P2P simulator. IEEE Ninth International Conference on Peer-to-Peer Computing. IEEE.","DOI":"10.1109\/P2P.2009.5284506"},{"key":"e_1_3_3_22_2","doi-asserted-by":"publisher","DOI":"10.17487\/RFC0896"},{"key":"e_1_3_3_23_2","first-page":"314","volume-title":"Proceedings of the 18th European Conference on Computer Systems","author":"Ng Harald","year":"2023","unstructured":"Harald Ng, Seif Haridi, and Paris Carbone. 2023. Omni-Paxos: Breaking the barriers of partial connectivity. In Proceedings of the 18th European Conference on Computer Systems. 314\u2013330."},{"key":"e_1_3_3_24_2","doi-asserted-by":"publisher","unstructured":"Maofan Yin Dahlia Malkhi Michael K. Reiter Guy Golan Gueta and Ittai Abraham. 2019. HotStuff: BFT consensus with linearity and responsiveness. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing (PODC\u201919). Association for Computing Machinery New York NY USA 347\u2013356. 10.1145\/3293611.3331591","DOI":"10.1145\/3293611.3331591"}],"container-title":["Formal Aspects of Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3698593","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3698593","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:09:44Z","timestamp":1750295384000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3698593"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,12,5]]},"references-count":23,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2024,12,31]]}},"alternative-id":["10.1145\/3698593"],"URL":"https:\/\/doi.org\/10.1145\/3698593","relation":{},"ISSN":["0934-5043","1433-299X"],"issn-type":[{"type":"print","value":"0934-5043"},{"type":"electronic","value":"1433-299X"}],"subject":[],"published":{"date-parts":[[2024,12,5]]},"assertion":[{"value":"2024-01-15","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-09-24","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-12-05","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}