{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,28]],"date-time":"2026-02-28T04:23:54Z","timestamp":1772252634443,"version":"3.50.1"},"reference-count":14,"publisher":"MDPI AG","issue":"1","license":[{"start":{"date-parts":[[2017,1,28]],"date-time":"2017-01-28T00:00:00Z","timestamp":1485561600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>Broadcasting a message from one to many processors in a network corresponds to concurrent reading on a random access shared memory parallel machine. Computing the trees of a forest, the level of each node in its tree and the path between two nodes are problems that can easily be solved with concurrent reading in a time logarithmic in the maximum height of a tree. Solving such problems with exclusive reading requires a time logarithmic in the number of nodes, implying message passing between disjoint pairs of processors on a distributed system. Allowing concurrent reading in parallel algorithm design for distributed computing might be advantageous in practice if these problems are faced on shallow trees with some specific constraints. We show an application to LZC (Lempel-Ziv-Compress)-compressed file decoding, whose parallelization employs these computations on such trees for realistic data. On the other hand, zipped files do not have this advantage, since they are compressed by the Lempel\u2013Ziv sliding window technique.<\/jats:p>","DOI":"10.3390\/a10010021","type":"journal-article","created":{"date-parts":[[2017,1,30]],"date-time":"2017-01-30T11:36:30Z","timestamp":1485776190000},"page":"21","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Concurrent vs. Exclusive Reading in Parallel Decoding of LZ-Compressed Files"],"prefix":"10.3390","volume":"10","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1379-8010","authenticated-orcid":false,"given":"Sergio","family":"Agostino","sequence":"first","affiliation":[{"name":"Computer Science Department, Sapienza University of Rome, Rome 00185, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bruno","family":"Carpentieri","sequence":"additional","affiliation":[{"name":"Dipartmento di Informatica, Universit\u00e0 di Salerno, Fisciano (SA) 84084, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Raffaele","family":"Pizzolante","sequence":"additional","affiliation":[{"name":"Dipartmento di Informatica, Universit\u00e0 di Salerno, Fisciano (SA) 84084, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2017,1,28]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1109\/TIT.1976.1055501","article-title":"On the Complexity of Finite Sequences","volume":"22","author":"Lempel","year":"1976","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1109\/TIT.1977.1055714","article-title":"A Universal Algorithm for Sequential Data Compression","volume":"23","author":"Lempel","year":"1977","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"530","DOI":"10.1109\/TIT.1978.1055934","article-title":"Compression of Individual Sequences via Variable-Rate Coding","volume":"24","author":"Ziv","year":"1978","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"862","DOI":"10.1137\/0214061","article-title":"An Efficient Parallel Biconnectivity Algorithm","volume":"14","author":"Tarjan","year":"1985","journal-title":"SIAM J. Comput."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"8","DOI":"10.1109\/MC.1984.1659158","article-title":"A Technique for High-Performance Data Compression","volume":"17","author":"Welch","year":"1984","journal-title":"IEEE Comput."},{"key":"ref_6","unstructured":"Bell, T.C., Cleary, J.G., and Witten, I.H. (1990). Text Compression, Prentice Hall."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1016\/0304-3975(94)90106-6","article-title":"P-complete Problems in Data Compression","volume":"127","year":"1994","journal-title":"Theor. Comput. Sci."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"183","DOI":"10.3390\/a4030183","article-title":"Lempel-Ziv Data Compression on Parallel and Distributed Systems","volume":"4","year":"2011","journal-title":"Algorithms"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"1957","DOI":"10.1016\/0167-8191(95)01030-0","article-title":"A Parallel Decoding Algorithm for LZ2 Data Compression","volume":"21","year":"1995","journal-title":"Parallel Comput."},{"key":"ref_10","unstructured":"De Agostino, S. (2015, January 24\u201329). The Uncompress Application on Distributed Communications Systems. Proceedings of the ICNS2015: The Eleventh International Conference on Networking and Services, Rome, Italy."},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Karloff, H.J., Suri, S., and Vassilvitskii, S. (2010, January 17\u201319). A Model of Computation for MapReduce. Proceedings of the SIAM-ACM Symposium on Discrete Algorithms, Austin, TX, USA.","DOI":"10.1137\/1.9781611973075.76"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"928","DOI":"10.1145\/322344.322346","article-title":"Data Compression via Textual Substitution","volume":"24","author":"Storer","year":"1982","journal-title":"J. ACM"},{"key":"ref_13","unstructured":"Storer, J.A. (1988). Data Compression: Methods and Theory, Computer Science Press."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"351","DOI":"10.1142\/S0129626404001933","article-title":"Almost Work-Optimal PRAM EREW Decoders of LZ-Compressed Text","volume":"14","year":"2004","journal-title":"Parallel Process. Lett."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/10\/1\/21\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T18:27:12Z","timestamp":1760207232000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/10\/1\/21"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,1,28]]},"references-count":14,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2017,3]]}},"alternative-id":["a10010021"],"URL":"https:\/\/doi.org\/10.3390\/a10010021","relation":{"has-preprint":[{"id-type":"doi","id":"10.20944\/preprints201611.0137.v1","asserted-by":"object"}]},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,1,28]]}}}