caa a22 4500 44535514X CHVBK 20180317142857.0 cr unu---uuuuu 170323e20110401xx s 000 0 eng 10.1007/s00446-010-0124-2 doi (NATIONALLICENCE)springer-10.1007/s00446-010-0124-2 Efficient online algorithm for identifying useless states in distributed systems [Elektronische Daten] [Lung-Pin Chen, Der-Johng Sun, William Chu] In a distributed system, detecting whether a given logical predicate is true on the global states is fundamental for testing and debugging the program. Detecting predicates by examining all global states is intractable due to the combinatorial nature of the problem. This work designs an efficient online algorithm that identifies the consistent and useless states each time a new state is reported. This paper formulates the optimality of detecting algorithms in terms of pseudo states, which are employed to represent unknown states to the monitor process. Based on this technique, memory space of the debugger can be minimized by removing the useless states without affecting the debugging results. While minimizing memory space, the proposed algorithm requires only O(p 2 M) time in total, where p is the number of processes, and M is the number of reported states. Springer-Verlag, 2010 Checkpoint nationallicence Distributed debugging nationallicence Global predicate detection nationallicence Chen Lung-Pin Department of Computer Science and Information Engineering, TungHai University, Taichung, Taiwan aut Sun Der-Johng Department of Computer Science and Information Engineering, National Chiao-Tung University, Hsinchu, Taiwan aut Chu William Department of Computer Science and Information Engineering, TungHai University, Taichung, Taiwan aut Distributed Computing Springer-Verlag 23/5-6(2011-04-01), 359-372 0178-2770 23:5-6<359 2011 23 446 https://doi.org/10.1007/s00446-010-0124-2 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00446-010-0124-2 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Chen Lung-Pin Department of Computer Science and Information Engineering, TungHai University, Taichung, Taiwan aut NATIONALLICENCE 700 1- Sun Der-Johng Department of Computer Science and Information Engineering, National Chiao-Tung University, Hsinchu, Taiwan aut NATIONALLICENCE 700 1- Chu William Department of Computer Science and Information Engineering, TungHai University, Taichung, Taiwan aut NATIONALLICENCE 773 0- Distributed Computing Springer-Verlag 23/5-6(2011-04-01), 359-372 0178-2770 23:5-6<359 2011 23 446 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer