{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:23:12Z","timestamp":1750220592558,"version":"3.41.0"},"reference-count":30,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2021,1,4]],"date-time":"2021-01-04T00:00:00Z","timestamp":1609718400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["1991\/19"],"award-info":[{"award-number":["1991\/19"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Parallel Comput."],"published-print":{"date-parts":[[2021,3,31]]},"abstract":"<jats:p>\n            In 1999, Brodal and Fagerberg (BF) gave an algorithm for maintaining a low outdegree orientation of a dynamic uniformly sparse graph. Specifically, for a dynamic graph on\n            <jats:italic>n<\/jats:italic>\n            -vertices, with arboricity bounded by\n            <jats:italic>\u0251<\/jats:italic>\n            at all times, the BF algorithm supports edge updates in\n            <jats:italic>O<\/jats:italic>\n            (log\n            <jats:italic>n<\/jats:italic>\n            ) amortized update time, while keeping the maximum outdegree in the graph bounded by\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>\u0251<\/jats:italic>\n            ). Such an orientation provides a basic data structure for uniformly sparse graphs, which found applications to several dynamic graph algorithms, including adjacency queries and labeling schemes, maximal and approximate matching, approximate vertex cover, forest decomposition, and distance oracles.\n          <\/jats:p>\n          <jats:p>\n            A significant weakness of the BF algorithm is the possible\n            <jats:italic>temporary<\/jats:italic>\n            blowup of the maximum outdegree, following edge insertions. Although BF eventually reduces all outdegrees to\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>\u0251<\/jats:italic>\n            ), some vertices may reach an outdegree of \u03a9(\n            <jats:italic>n<\/jats:italic>\n            ) during the process, and hence local memory usage at the vertices, which is an important quality measure in distributed systems, cannot be bounded. We show how to modify the BF algorithm to guarantee that the outdegrees of all vertices are bounded by\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>\u0251<\/jats:italic>\n            ) at all times, without hurting any of its other properties and present an efficient distributed implementation of the modified algorithm. This provides the\n            <jats:italic>first<\/jats:italic>\n            representation of distributed networks in which the local memory usage at all vertices is bounded by the arboricity (which is essentially the average degree of the densest subgraph) rather than the maximum degree.\n          <\/jats:p>\n          <jats:p>\n            For settings where there is no strict limitation on the local memory, one may take the temporary outdegree blowup to the extreme and allow a permanent outdegree blowup. This allows us to address the second significant weakness of the BF algorithm\u2014its inherently\n            <jats:italic>global<\/jats:italic>\n            nature: An insertion of an edge (\n            <jats:italic>u,v<\/jats:italic>\n            ) may trigger changes in the orientations of edges that are arbitrarily far away from\n            <jats:italic>u<\/jats:italic>\n            and\n            <jats:italic>v<\/jats:italic>\n            . Such a non-local scheme may be prohibitively expensive in various practical applications. We suggest an alternative\n            <jats:italic>local<\/jats:italic>\n            scheme, which does not guarantee any outdegree bound on the vertices, yet is just as efficient as the BF scheme for some of the aforementioned applications. For example, we obtain a local dynamic algorithm for maintaining a maximal matching with sub-logarithmic update time in uniformly sparse networks, providing an exponential improvement over the state of the art in this context. We also present a distributed implementation of this scheme and some of its applications.\n          <\/jats:p>","DOI":"10.1145\/3434395","type":"journal-article","created":{"date-parts":[[2021,1,4]],"date-time":"2021-01-04T14:45:42Z","timestamp":1609771542000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Dynamic Representations of Sparse Distributed Networks"],"prefix":"10.1145","volume":"8","author":[{"given":"Haim","family":"Kaplan","sequence":"first","affiliation":[{"name":"Tel Aviv University, Tel Aviv, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shay","family":"Solomon","sequence":"additional","affiliation":[{"name":"Tel Aviv University, Tel Aviv, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,1,4]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973099.89"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(97)00007-3"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188922"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/323596.323621"},{"volume-title":"Proceedings of the 9th ACM Symposium on Principles of Distributed Computing (PODC\u201990)","author":"Awerbuch B.","key":"e_1_2_1_5_1","unstructured":"B. Awerbuch , A. Baratz , and D. Peleg . 1990. Cost-sensitive analysis of communication protocols . In Proceedings of the 9th ACM Symposium on Principles of Distributed Computing (PODC\u201990) . 177--187. B. Awerbuch, A. Baratz, and D. Peleg. 1990. Cost-sensitive analysis of communication protocols. In Proceedings of the 9th ACM Symposium on Principles of Distributed Computing (PODC\u201990). 177--187."},{"key":"e_1_2_1_6_1","volume-title":"Technical Report CS92-22, Weizmann Institute.","author":"Awerbuch B.","year":"1992","unstructured":"B. Awerbuch , A. Baratz , and D. Peleg . October , 1992 . Efficient broadcast and light-weight spanners. Technical Report CS92-22, Weizmann Institute. B. Awerbuch, A. Baratz, and D. Peleg. October, 1992. Efficient broadcast and light-weight spanners. Technical Report CS92-22, Weizmann Institute."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-009-0088-2"},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","unstructured":"Leonid Barenboim and Michael Elkin. 2013. Distributed Graph Coloring: Fundamentals and Recent Developments. Morgan 8 Claypool Publishers.  Leonid Barenboim and Michael Elkin. 2013. Distributed Graph Coloring: Fundamentals and Recent Developments. Morgan 8 Claypool Publishers.","DOI":"10.1007\/978-3-031-02009-4"},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the 28th International Symposium on Algorithms and Computation (ISAAC\u201917)","author":"Berglin Edvin","year":"2017","unstructured":"Edvin Berglin and Gerth St\u00f8lting Brodal . 2017 . A simple greedy algorithm for dynamic graph orientation . In Proceedings of the 28th International Symposium on Algorithms and Computation (ISAAC\u201917) . 12:1\u201312:12. Edvin Berglin and Gerth St\u00f8lting Brodal. 2017. A simple greedy algorithm for dynamic graph orientation. In Proceedings of the 28th International Symposium on Algorithms and Computation (ISAAC\u201917). 12:1\u201312:12."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-47672-7_14"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974331.ch50"},{"volume-title":"Proceedings of the 6th Algorithms and Data Structures Symposium (WADS\u201999)","author":"Brodal G. S.","key":"e_1_2_1_12_1","unstructured":"G. S. Brodal and R. Fagerberg . 1999. Dynamic representation of sparse graphs . In Proceedings of the 6th Algorithms and Data Structures Symposium (WADS\u201999) . 342--351. G. S. Brodal and R. Fagerberg. 1999. Dynamic representation of sparse graphs. In Proceedings of the 6th Algorithms and Data Structures Symposium (WADS\u201999). 342--351."},{"volume-title":"Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC\u201916)","author":"Censor-Hillel Keren","key":"e_1_2_1_13_1","unstructured":"Keren Censor-Hillel , Elad Haramaty , and Zohar S. Karnin . 2016. Optimal dynamic distributed MIS . In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC\u201916) . 217--226. Keren Censor-Hillel, Elad Haramaty, and Zohar S. Karnin. 2016. Optimal dynamic distributed MIS. In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC\u201916). 217--226."},{"issue":"2018","key":"e_1_2_1_14_1","first-page":"69","article-title":"Best of two local models: Local centralized and local distributed algorithms","volume":"262","author":"Even Guy","year":"2014","unstructured":"Guy Even , Moti Medina , and Dana Ron . 2014 . Best of two local models: Local centralized and local distributed algorithms . Inf. Comput. 262 ( 2018 ), 69 -- 89 . DOI:10.1016\/j.ic.2018.07.001 10.1016\/j.ic.2018.07.001 Guy Even, Moti Medina, and Dana Ron. 2014. Best of two local models: Local centralized and local distributed algorithms. Inf. Comput. 262 (2018), 69--89. DOI:10.1016\/j.ic.2018.07.001","journal-title":"Inf. Comput."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2684464.2684469"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974782.166"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-13075-0_11"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-43951-7_45"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2006.12.006"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780565"},{"volume-title":"Proceedings of the 20th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA\u201908)","author":"Lotker Z.","key":"e_1_2_1_21_1","unstructured":"Z. Lotker , B. Patt-Shamir , and S. Pettie . 2008. Improved distributed approximate matching . In Proceedings of the 20th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA\u201908) . 129--136. Z. Lotker, B. Patt-Shamir, and S. Pettie. 2008. Improved distributed approximate matching. In Proceedings of the 20th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA\u201908). 129--136."},{"volume-title":"Proceedings of the 16th International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX\u201913)","author":"Mansour Y.","key":"e_1_2_1_22_1","unstructured":"Y. Mansour and S. Vardi . 2013. A local computation approximation scheme to maximum matching . In Proceedings of the 16th International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX\u201913) . 260--273. Y. Mansour and S. Vardi. 2013. A local computation approximation scheme to maximum matching. In Proceedings of the 16th International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX\u201913). 260--273."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488703"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974331.ch17"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/355459"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974331.ch51"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/0218050"},{"volume-title":"Proceedings of the 2nd ACM International Conference on Supercomputing (ICS\u201911)","author":"Rubinfeld R.","key":"e_1_2_1_28_1","unstructured":"R. Rubinfeld , G. Tamir , S. Vardi , and N. Xie . 2011. Fast local computation algorithms . In Proceedings of the 2nd ACM International Conference on Supercomputing (ICS\u201911) . 223--238. R. Rubinfeld, G. Tamir, S. Vardi, and N. Xie. 2011. Fast local computation algorithms. In Proceedings of the 2nd ACM International Conference on Supercomputing (ICS\u201911). 223--238."},{"key":"e_1_2_1_29_1","volume-title":"Proceedings of the 9th Innovations in Theoretical Computer Science (ITCS\u201918)","author":"Solomon Shay","year":"2018","unstructured":"Shay Solomon . 2018 . Local algorithms for bounded degree sparsifiers in sparse graphs . In Proceedings of the 9th Innovations in Theoretical Computer Science (ITCS\u201918) . 52:1\u201352:19. Shay Solomon. 2018. Local algorithms for bounded degree sparsifiers in sparse graphs. In Proceedings of the 9th Innovations in Theoretical Computer Science (ITCS\u201918). 52:1\u201352:19."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2431211.2431223"}],"container-title":["ACM Transactions on Parallel Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3434395","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3434395","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:31:48Z","timestamp":1750195908000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3434395"}},"subtitle":["A Locality-sensitive Approach"],"short-title":[],"issued":{"date-parts":[[2021,1,4]]},"references-count":30,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,3,31]]}},"alternative-id":["10.1145\/3434395"],"URL":"https:\/\/doi.org\/10.1145\/3434395","relation":{},"ISSN":["2329-4949","2329-4957"],"issn-type":[{"type":"print","value":"2329-4949"},{"type":"electronic","value":"2329-4957"}],"subject":[],"published":{"date-parts":[[2021,1,4]]},"assertion":[{"value":"2020-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-01-04","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}