{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,11]],"date-time":"2026-09-11T04:28:13Z","timestamp":1789100893774,"version":"build-2803163510"},"reference-count":16,"publisher":"Wiley","license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/3.0\/"}],"funder":[{"DOI":"10.13039\/501100003725","name":"National Research Foundation of Korea","doi-asserted-by":"publisher","award":["NRF-2014R1A1A2060082"],"award-info":[{"award-number":["NRF-2014R1A1A2060082"]}],"id":[{"id":"10.13039\/501100003725","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Scientific Programming"],"published-print":{"date-parts":[[2015]]},"abstract":"<jats:p>Data races represent the most notorious class of concurrency bugs in multithreaded programs. To detect data races precisely and efficiently during the execution of multithreaded programs, the epoch-based F<jats:sc>ast<\/jats:sc>T<jats:sc>rack<\/jats:sc>technique has been employed. However, F<jats:sc>ast<\/jats:sc>T<jats:sc>rack<\/jats:sc>has time and space complexities that depend on the maximum parallelism of the program to partially maintain expensive data structures, such as vector clocks. This paper presents an efficient algorithm, called<jats:italic>i<\/jats:italic>FT, that uses only the epochs of the access histories. Unlike F<jats:sc>ast<\/jats:sc>T<jats:sc>rack<\/jats:sc>, our algorithm requires<mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" id=\"M1\"><mml:mi>O<\/mml:mi><mml:mo stretchy=\"false\">(<\/mml:mo><mml:mn>1<\/mml:mn><mml:mo stretchy=\"false\">)<\/mml:mo><\/mml:math>operations to maintain an access history and locate data races, without any switching between epochs and vector clocks. We implement this algorithm on top of the Pin binary instrumentation framework and compare it with other on-the-fly detection algorithms, including F<jats:sc>ast<\/jats:sc>T<jats:sc>rack<\/jats:sc>, which uses a state-of-the-art happens-before analysis algorithm. Empirical results using the PARSEC benchmark show that<jats:italic>i<\/jats:italic>FT reduces the average runtime and memory overhead to 84% and 37%, respectively, of those of F<jats:sc>ast<\/jats:sc>T<jats:sc>rack<\/jats:sc>.<\/jats:p>","DOI":"10.1155\/2015\/205827","type":"journal-article","created":{"date-parts":[[2015,7,16]],"date-time":"2015-07-16T17:01:35Z","timestamp":1437066095000},"page":"1-14","source":"Crossref","is-referenced-by-count":7,"title":["An Efficient Algorithm for On-the-Fly Data Race Detection Using an Epoch-Based Technique"],"prefix":"10.1155","volume":"2015","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6512-8502","authenticated-orcid":true,"given":"Ok-Kyoon","family":"Ha","sequence":"first","affiliation":[{"name":"Engineering Research Institute, Gyeongsang National University, 501 Jinju-daero, Jinju, Gyeongsangnam-do 660-701, Republic of Korea"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yong-Kee","family":"Jun","sequence":"additional","affiliation":[{"name":"Department of Informatics, Gyeongsang National University, 501 Jinju-daero, Jinju, Gyeongsangnam-do 660-701, Republic of Korea"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"311","reference":[{"key":"20","doi-asserted-by":"publisher","DOI":"10.1145\/130616.130623"},{"key":"33","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2012.02.008"},{"key":"27","doi-asserted-by":"publisher","DOI":"10.1145\/312203.312214"},{"issue":"3","key":"18","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1145\/1555815.1555797","volume":"37","year":"2009","journal-title":"SIGARCH's Computer Architecture News"},{"key":"7","doi-asserted-by":"publisher","DOI":"10.1016\/s0167-8191(02)00134-5"},{"key":"23","doi-asserted-by":"publisher","DOI":"10.1109\/71.888645"},{"key":"26","doi-asserted-by":"publisher","DOI":"10.1007\/s10703-012-0143-7"},{"key":"28","doi-asserted-by":"publisher","DOI":"10.1145\/265924.265927"},{"key":"11","doi-asserted-by":"publisher","DOI":"10.1007\/10722468_20"},{"key":"25","doi-asserted-by":"publisher","DOI":"10.1002\/cpe.1064"},{"key":"6","doi-asserted-by":"publisher","DOI":"10.1145\/1809028.1806626"},{"key":"16","doi-asserted-by":"publisher","DOI":"10.1145\/1543135.1542491"},{"issue":"2","key":"2","volume":"3","year":"2002","journal-title":"IEEE Distributed Systems Online"},{"key":"15","doi-asserted-by":"publisher","DOI":"10.1145\/359545.359563"},{"key":"1","doi-asserted-by":"publisher","DOI":"10.1109\/mc.2010.60"},{"issue":"1","key":"22","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1145\/2189750.2150995","volume":"40","year":"2012","journal-title":"ACM SIGARCH Computer Architecture News"}],"container-title":["Scientific Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/downloads.hindawi.com\/journals\/sp\/2015\/205827.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/downloads.hindawi.com\/journals\/sp\/2015\/205827.xml","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/downloads.hindawi.com\/journals\/sp\/2015\/205827.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,6,23]],"date-time":"2017-06-23T11:50:11Z","timestamp":1498218611000},"score":1,"resource":{"primary":{"URL":"http:\/\/www.hindawi.com\/journals\/sp\/2015\/205827\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"references-count":16,"alternative-id":["205827","205827"],"URL":"https:\/\/doi.org\/10.1155\/2015\/205827","relation":{},"ISSN":["1058-9244","1875-919X"],"issn-type":[{"value":"1058-9244","type":"print"},{"value":"1875-919X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015]]}}}