{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,2]],"date-time":"2025-05-02T04:05:16Z","timestamp":1746158716158,"version":"3.40.4"},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2013,12,20]],"date-time":"2013-12-20T00:00:00Z","timestamp":1387497600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/2.0"},{"start":{"date-parts":[[2013,12,20]],"date-time":"2013-12-20T00:00:00Z","timestamp":1387497600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/2.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Distrib. Comput."],"published-print":{"date-parts":[[2014,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We present generic transformations, which allow to translate classic fault-tolerant distributed algorithms and their correctness proofs into a real-time distributed computing model (and vice versa). Owing to the non-zero-time, non-preemptible state transitions employed in our real-time model, scheduling and queuing effects (which are inherently abstracted away in classic zero step-time models, sometimes leading to overly optimistic time complexity results) can be accurately modeled. Our results thus make fault-tolerant distributed algorithms amenable to a sound real-time analysis, without sacrificing the wealth of algorithms and correctness proofs established in classic distributed computing research. By means of an example, we demonstrate that real-time algorithms generated by transforming classic algorithms can be competitive even w.r.t. optimal real-time algorithms, despite their comparatively simple real-time analysis.<\/jats:p>","DOI":"10.1007\/s00446-013-0204-1","type":"journal-article","created":{"date-parts":[[2013,12,19]],"date-time":"2013-12-19T15:55:42Z","timestamp":1387468542000},"page":"203-230","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Reconciling fault-tolerant distributed algorithms and real-time computing"],"prefix":"10.1007","volume":"27","author":[{"given":"Heinrich","family":"Moser","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ulrich","family":"Schmid","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2013,12,20]]},"reference":[{"issue":"1","key":"204_CR1","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1006\/inco.1996.0006","volume":"124","author":"JH Anderson","year":"1996","unstructured":"Anderson, J.H., Yang, J.-H.: Time\/contention tradeoffs for multiprocessor synchronization. Inf. Comput. 124(1), 68\u201384 (1996)","journal-title":"Inf. Comput."},{"key":"204_CR2","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1007\/s00446-003-0088-6","volume":"16","author":"JH Anderson","year":"2003","unstructured":"Anderson, J.H., Kim, Y.-J., Herman, T.: Shared-memory mutual exclusion: major research trends since 1986. Distrib. Comput. 16, 75\u2013110 (2003)","journal-title":"Distrib. Comput."},{"key":"204_CR3","doi-asserted-by":"publisher","first-page":"284","DOI":"10.1049\/sej.1993.0034","volume":"8","author":"N Audsley","year":"1993","unstructured":"Audsley, N., Burns, A., Richardson, M., Tindell, K., Wellings, A.J.: Applying new scheduling theory to static priority pre-emptive scheduling. Softw. Eng. J. 8, 284\u2013292 (1993)","journal-title":"Softw. Eng. J."},{"key":"204_CR4","doi-asserted-by":"crossref","unstructured":"Aziz, A., Diffie, W.: Privacy and authentication for wireless local area networks. IEEE Pers. Commun. First Quarter:25\u201331 (1994)","DOI":"10.1109\/98.295357"},{"issue":"40","key":"204_CR5","doi-asserted-by":"publisher","first-page":"5602","DOI":"10.1016\/j.tcs.2010.09.032","volume":"412","author":"M Biely","year":"2011","unstructured":"Biely, M., Schmid, U., Weiss, B.: Synchronous consensus under hybrid process and link failures. Theor. Comput. Sci. 412(40), 5602\u20135630 (2011). doi:10.1016\/j.tcs.2010.09.032","journal-title":"Theor. Comput. Sci."},{"key":"204_CR6","doi-asserted-by":"crossref","unstructured":"Bozga, M., Daws, C., Maler, O., Olivero, A., Tripakis, S., Yovine, S.: Kronos: a model-checking tool for real-time systems. In: Proceedings 10th International Conference on Computer Aided Verification (CAV\u201998), Springer LNCS 1427, pp. 546\u2013550 (1998)","DOI":"10.1007\/BFb0028779"},{"issue":"2","key":"204_CR7","doi-asserted-by":"publisher","first-page":"288","DOI":"10.1145\/42282.42283","volume":"35","author":"C Dwork","year":"1988","unstructured":"Dwork, C., Lynch, N., Stockmeyer, L.: Consensus in the presence of partial synchrony. J. ACM 35(2), 288\u2013323 (1988)","journal-title":"J. ACM"},{"issue":"8","key":"204_CR8","doi-asserted-by":"crossref","first-page":"931","DOI":"10.1109\/TC.2002.1024740","volume":"51","author":"J-F Hermant","year":"2002","unstructured":"Hermant, J.-F., Le Lann, G.: Fast asynchronous uniform consensus in real-time distributed systems. IEEE Trans. Comput. 51(8), 931\u2013944 (2002)","journal-title":"IEEE Trans. Comput."},{"key":"204_CR9","doi-asserted-by":"crossref","unstructured":"Kaynar, D.K., Lynch, N., Segala, R., Vaandrager, F.: Timed I\/O automata: a mathematical framework for modeling and analyzing real-time systems. In: Proceedings 24th IEEE International Real-Time Systems Symposium (RTSS\u201903), 00:166\u2013177 (2003)","DOI":"10.1109\/REAL.2003.1253264"},{"issue":"7","key":"204_CR10","doi-asserted-by":"publisher","first-page":"558","DOI":"10.1145\/359545.359563","volume":"21","author":"L Lamport","year":"1978","unstructured":"Lamport, L.: Time, clocks, and the ordering of events in a distributed system. Commun. ACM 21(7), 558\u2013565 (1978)","journal-title":"Commun. ACM"},{"issue":"3","key":"204_CR11","doi-asserted-by":"publisher","first-page":"382","DOI":"10.1145\/357172.357176","volume":"4","author":"L Lamport","year":"1982","unstructured":"Lamport, L., Shostak, R., Pease, M.: The Byzantine generals problem. ACM Trans. Program. Lang. Syst. 4(3), 382\u2013401 (1982)","journal-title":"ACM Trans. Program. Lang. Syst."},{"issue":"1\u20132","key":"204_CR12","doi-asserted-by":"publisher","first-page":"134","DOI":"10.1007\/s100090050010","volume":"1","author":"KG Larsen","year":"1997","unstructured":"Larsen, K.G., Pettersson, P., Yi, W.: Uppaal in a nutshell. Softw. Tools Technol. Transf. 1(1\u20132), 134\u2013152 (1997)","journal-title":"Softw. Tools Technol. Transf."},{"key":"204_CR13","doi-asserted-by":"publisher","first-page":"190","DOI":"10.1016\/S0019-9958(84)80033-9","volume":"62","author":"J Lundelius","year":"1984","unstructured":"Lundelius, J., Lynch, N.A.: An upper and lower bound for clock synchronization. Inf. Control 62, 190\u2013204 (1984)","journal-title":"Inf. Control"},{"issue":"2","key":"204_CR14","doi-asserted-by":"publisher","first-page":"214","DOI":"10.1006\/inco.1995.1134","volume":"121","author":"N Lynch","year":"1995","unstructured":"Lynch, N., Vaandrager, F.W.: Forward and backward simulations, I: untimed systems. Inf. Comput. 121(2), 214\u2013233 (1995)","journal-title":"Inf. Comput."},{"key":"204_CR15","volume-title":"Distributed Algorithms","author":"N Lynch","year":"1996","unstructured":"Lynch, N.: Distributed Algorithms. Morgan Kaufman, Los Altos (1996)"},{"issue":"1","key":"204_CR16","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1006\/inco.1996.0060","volume":"128","author":"N Lynch","year":"1996","unstructured":"Lynch, N., Vaandrager, F.W.: Forward and backward simulations, II: timing-based systems. Inf. Comput. 128(1), 1\u201325 (1996)","journal-title":"Inf. Comput."},{"key":"204_CR17","doi-asserted-by":"crossref","unstructured":"Martin, S., Minet, P., George, L.: The trajectory approach for the end-to-end response times with non-preemptive fp\/edf. In: Dosch, W., Lee, R.Y., Wu, C. (eds), SERA, Volume 3647 of Lecture Notes in Computer Science, pp. 229\u2013247. Springer, Berlin (2004)","DOI":"10.1007\/11668855_17"},{"key":"204_CR18","doi-asserted-by":"crossref","unstructured":"Merritt, M., Modugno, F., Tuttle, M.R.: Time-constrained automata (extended abstract). In: Proceedings of the 2nd International Conference on Concurrency Theory (CONCUR\u201991), pp. 408\u2013423. Springer, London (1991)","DOI":"10.1007\/3-540-54430-5_103"},{"key":"204_CR19","unstructured":"Meyer, F.J., Pradhan, D.K.: Consensus with dual failure modes. In: In Digest of Papers of the 17th International Symposium on Fault-Tolerant Computing, pp. 48\u201354. Pittsburgh (1987)"},{"key":"204_CR20","doi-asserted-by":"crossref","unstructured":"Moser, H., Schmid, U.: Optimal clock synchronization revisited: upper and lower bounds in real-time systems. In: Proceedings of the International Conference on Principles of Distributed Systems (OPODIS), LNCS 4305, pp. 95\u2013109, Bordeaux & Saint-Emilion, France, Springer (2006)","DOI":"10.1007\/11945529_8"},{"key":"204_CR21","doi-asserted-by":"crossref","unstructured":"Moser, H., Schmid, U.: Optimal deterministic remote clock estimation in real-time systems. In: Proceedings of the International Conference on Principles of Distributed Systems (OPODIS), pp. 363\u2013387, Luxor, Egypt (2008)","DOI":"10.1007\/978-3-540-92221-6_24"},{"key":"204_CR22","unstructured":"Moser, H., Schmid, U.: Reconciling distributed computing models and real-time systems. In: Proceedings Work in Progress Session of the 27th IEEE Real-Time Systems Symposium (RTSS\u201906), pp. 73\u201376. Rio de Janeiro, Brazil (2006)"},{"key":"204_CR23","doi-asserted-by":"crossref","unstructured":"Moser, H., Schmid, U.: Reconciling fault-tolerant distributed algorithms and real-time computing. In: 18th International Colloquium on Structural Information and Communication Complexity (SIROCCO), LNCS 6796, pp. 42\u201353. Springer, Berlin (2011)","DOI":"10.1007\/978-3-642-22212-2_5"},{"key":"204_CR24","unstructured":"Moser, H.: A model for distributed computing in real-time systems. PhD thesis, Technische Universit\u00e4t Wien, Fakult\u00e4t f\u00fcr Informatik, May 2009. (Promotion sub auspiciis)"},{"key":"204_CR25","unstructured":"Moser, H.: The byzantine generals\u2019 round duration. Research Report 9\/2010, Technische Universit\u00e4t Wien, Institut f\u00fcr Technische Informatik, Treitlstr. 1\u20133\/182-2, 1040 Vienna, Austria (2010)"},{"issue":"6\u20137","key":"204_CR26","doi-asserted-by":"publisher","first-page":"629","DOI":"10.1016\/j.tcs.2008.10.012","volume":"410","author":"H Moser","year":"2009","unstructured":"Moser, H.: Towards a real-time distributed computing model. Theor. Comput. Sci. 410(6\u20137), 629\u2013659 (2009)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"204_CR27","doi-asserted-by":"publisher","first-page":"334","DOI":"10.1145\/151261.151267","volume":"40","author":"G Neiger","year":"1993","unstructured":"Neiger, G., Toueg, S.: Simulating synchronized clocks and common knowledge in distributed systems. J. ACM 40(2), 334\u2013367 (1993)","journal-title":"J. ACM"},{"key":"204_CR28","doi-asserted-by":"crossref","unstructured":"Palencia Guti\u00e9rrez, J.C., Guti\u00e9rrez Garc\u00eda, J J., Gonz\u00e1lez Harbour, M.: Best-case analysis for improving the worst-case schedulability test for distributed hard real-time systems. In: Proceedings of the 10th EuroMicro Conference on Real-Time Systems, pp. 35\u201344 (1998)","DOI":"10.1109\/EMWRTS.1998.684945"},{"key":"204_CR29","doi-asserted-by":"crossref","unstructured":"Schmid, U., Fetzer, C.: Randomized asynchronous consensus with imperfect communications. In: 22nd Symposium on Reliable Distributed Systems (SRDS\u201903), pp. 361\u2013370. Florence, Italy (2003)","DOI":"10.1109\/RELDIS.2003.1238089"},{"key":"204_CR30","unstructured":"Schmid, U., Fetzer, C.: Randomized asynchronous consensus with imperfect communications. Technical Report 183\/1-120, Department of Automation, Technische Universit\u00e4t Wien, January 2002. (Extended version of [30])"},{"issue":"2","key":"204_CR31","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1006\/inco.1997.2671","volume":"141","author":"R Segala","year":"1998","unstructured":"Segala, R., Gawlick, R., Sogaard-Andersen, J.F., Lynch, N.: Liveness in timed and untimed systems. Inf. Comput. 141(2), 119\u2013171 (1998)","journal-title":"Inf. Comput."},{"issue":"2\/3","key":"204_CR32","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1023\/B:TIME.0000045315.61234.1e","volume":"28","author":"L Sha","year":"2004","unstructured":"Sha, L., Abdelzaher, T., Arzen, K.-E., Cervin, A., Baker, T., Burns, A., Buttazzo, G., Caccamo, M., Lehoczky, J., Mok, A.K.: Real time scheduling theory: a historical perspective. Real-Time Syst. J. 28(2\/3), 101\u2013155 (2004)","journal-title":"Real-Time Syst. J."},{"key":"204_CR33","unstructured":"Spuri, M.: Holistic analysis for deadline scheduled real-time distributed system. Technical Report 2873, INRIA Rocquencourt (1996)"},{"issue":"2\u20133","key":"204_CR34","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1016\/0165-6074(94)90080-9","volume":"40","author":"K Tindell","year":"1994","unstructured":"Tindell, K., Clark, J.: Holistic schedulability analysis for distributed hard real-time systems. Microprocess. Microprogram. 40(2\u20133), 117\u2013134 (1994)","journal-title":"Microprocess. Microprogram."},{"issue":"2","key":"204_CR35","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1007\/s00446-007-0026-0","volume":"20","author":"J Widder","year":"2007","unstructured":"Widder, J., Schmid, U.: Booting clock synchronization in partially synchronous systems with hybrid process and link failures. Distrib. Comput. 20(2), 115\u2013140 (2007)","journal-title":"Distrib. Comput."}],"container-title":["Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-013-0204-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00446-013-0204-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-013-0204-1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-013-0204-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,1]],"date-time":"2025-05-01T08:02:59Z","timestamp":1746086579000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00446-013-0204-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,12,20]]},"references-count":35,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2014,6]]}},"alternative-id":["204"],"URL":"https:\/\/doi.org\/10.1007\/s00446-013-0204-1","relation":{},"ISSN":["0178-2770","1432-0452"],"issn-type":[{"type":"print","value":"0178-2770"},{"type":"electronic","value":"1432-0452"}],"subject":[],"published":{"date-parts":[[2013,12,20]]},"assertion":[{"value":"24 January 2012","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 December 2013","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 December 2013","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}