{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:25:43Z","timestamp":1750220743285,"version":"3.41.0"},"reference-count":34,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2020,9,5]],"date-time":"2020-09-05T00:00:00Z","timestamp":1599264000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"National Research Foundation (NRF), Singapore under the Corp Lab @ University Scheme"},{"name":"NTU Start-up Grant"},{"DOI":"10.13039\/501100021556","name":"Delta-NTU Corporate Laboratory for Cyber-Physical Systems","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100021556","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Delta Electronics Inc."}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Sen. Netw."],"published-print":{"date-parts":[[2020,11,30]]},"abstract":"<jats:p>\n            Naturally occurring disturbances and malicious attacks can lead to faults in synchronizing the clocks of two network nodes. In this article, we investigate the fundamental resilience bounds of network clock synchronization for a system of\n            <jats:italic>N<\/jats:italic>\n            nodes against the peer-to-peer synchronization faults. Our analysis is based on practical synchronization algorithms with time complexity down to\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>N<\/jats:italic>\n            <jats:sup>3<\/jats:sup>\n            ) that attempt to correct the faults by checking the consistency among the following three types of data: (1) the estimated faults, (2) the estimated clock offsets among the nodes, and (3) the measured clock offsets from the potentially faulty peer-to-peer synchronization sessions. Our analysis gives the following three major results. First, the maximum number of faults that can be corrected by the algorithms has a tight bound of \u230a\n            <jats:italic>N<\/jats:italic>\n            \/2 \u230b \u2212 1 when every node pair performs a synchronization session. Second, by converting the fault resilience problem to a graph-theoretic edge connectivity problem and applying Menger\u2019s theorem, we develop an algorithm to compute the tight bound when not every node pair performs a synchronization session. Third, the number of synchronization sessions to achieve the capability of correcting any\n            <jats:italic>K<\/jats:italic>\n            faults has a lower bound of \u2308\n            <jats:italic>N<\/jats:italic>\n            (2\n            <jats:italic>K<\/jats:italic>\n            +1) \/ 2 \u2309 ; we also develop an algorithm to schedule the synchronization sessions to approach the lower bound. The above results provide basic understanding and useful guidelines to the design of resilient clock synchronization systems. For instance, our results suggest that, the four-node network achieves the highest degree of resilience that is defined as the ratio of the maximum number of correctable faults to the number of synchronization sessions. Therefore, by organizing a large-scale clock synchronization system into a hierarchy of multiple tiers with each consisting of four-node synchronization groups, we can achieve satisfactory and understood resilience against faults with reduced synchronization sessions.\n          <\/jats:p>","DOI":"10.1145\/3409804","type":"journal-article","created":{"date-parts":[[2020,9,5]],"date-time":"2020-09-05T10:14:24Z","timestamp":1599300864000},"page":"1-30","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Resilience Bounds of Network Clock Synchronization with Fault Correction"],"prefix":"10.1145","volume":"16","author":[{"given":"Linshan","family":"Jiang","sequence":"first","affiliation":[{"name":"Nanyang Technological University, Singapore"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8441-9973","authenticated-orcid":false,"given":"Rui","family":"Tan","sequence":"additional","affiliation":[{"name":"Nanyang Technological University, Singapore"}]},{"given":"Arvind","family":"Easwaran","sequence":"additional","affiliation":[{"name":"Nanyang Technological University, Singapore"}]}],"member":"320","published-online":{"date-parts":[[2020,9,5]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/1380427.1380429"},{"volume-title":"Proceedings of the 10th ACM\/IEEE International Conference on Information Processing in Sensor Networks (IPSN\u201911)","year":"2011","author":"Chen Yin","key":"e_1_2_1_2_1"},{"volume-title":"Introduction to Algorithms","author":"Cormen Thomas H.","key":"e_1_2_1_3_1"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/9128.9132"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTAS.2017.9"},{"volume-title":"SI","year":"2002","author":"Elson Jeremy","key":"e_1_2_1_6_1"},{"volume-title":"Proceedings of the 1st International Conference on Embedded Networked Sensor Systems (SenSys\u201903)","author":"Ganeriwal Saurabh","key":"e_1_2_1_7_1"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDCS47774.2020.00109"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-00224-3_12"},{"volume-title":"Proceedings of the 32nd IEEE Real-time Systems Symposium (RTSS\u201911)","author":"Hao T.","key":"e_1_2_1_10_1"},{"volume-title":"IEEE standard for a precision clock synchronization protocol for networked measurement and control systems","year":"2008","author":"IEEE.","key":"e_1_2_1_11_1"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-54945-5_78"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2455.2457"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1999995.2000012"},{"volume-title":"Proceedings of the 16th ACM\/IEEE International Conference on Information Processing in Sensor Networks (IPSN). ACM, 55--66","author":"Li Yang","key":"e_1_2_1_15_1"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2348543.2348611"},{"volume-title":"Proceedings of the 8th ACM\/IEEE International Conference on Information Processing in Sensor Networks (IPSN\u201909)","year":"2009","author":"Lukac Martin","key":"e_1_2_1_17_1"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1031495.1031501"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/26.103043"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISPCS.2012.6336612"},{"key":"e_1_2_1_21_1","doi-asserted-by":"crossref","unstructured":"T. Mizrahi. 2014. Security Requirements of Time Protocols in Packet Switched Networks. Retrieved from https:\/\/tools.ietf.org\/html\/rfc7384.  T. Mizrahi. 2014. Security Requirements of Time Protocols in Packet Switched Networks. Retrieved from https:\/\/tools.ietf.org\/html\/rfc7384.","DOI":"10.17487\/rfc7384"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2382196.2382245"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/24.370218"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/322047.322048"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3052973.3053020"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1644038.1644060"},{"volume-title":"Shafarevich and Alexey Remizov","year":"2012","author":"Igor","key":"e_1_2_1_27_1"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/PADSW.2018.8644871"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISPCS.2009.5340224"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3195182"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01294465"},{"volume-title":"Introduction to Graph Theory","author":"\u00a0al Douglas Brent","key":"e_1_2_1_32_1"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.2307\/1968197"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3131672.3131681"}],"container-title":["ACM Transactions on Sensor Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3409804","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3409804","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:38:41Z","timestamp":1750199921000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3409804"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,9,5]]},"references-count":34,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2020,11,30]]}},"alternative-id":["10.1145\/3409804"],"URL":"https:\/\/doi.org\/10.1145\/3409804","relation":{},"ISSN":["1550-4859","1550-4867"],"issn-type":[{"type":"print","value":"1550-4859"},{"type":"electronic","value":"1550-4867"}],"subject":[],"published":{"date-parts":[[2020,9,5]]},"assertion":[{"value":"2019-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-09-05","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}