Distributed systems frequently exhibit properties of interest which span multiple entities. These properties cannot easily be recognized from any single entity, but can be readily detected by combining the knowledge of multiple entities. Testing for distributed properties is especially important in debugging or verifying software for modular robots. We have developed a technique we call distributed watchpoint triggers which can efficiently recognize distributed conditions. Our watchpoint description language can handle a variety of temporal, spatial and logical properties spanning multiple robots. In this paper we present the specification language, describe the distributed online mechanism for detecting distributed conditions in a running system and evaluate the performance of our implementation.
Bacon, D.F. and Goldstein, S.C. (1991). Hardware-assisted replay of multiprocessor programs . PADD '91: Proceedings of the 1991 ACM/ONR workshop on Parallel and distributed debugging. New York, NY, ACM Press, pp. 194— 206.
2.
Carr, S., Mayo, J. and Shene, C.-K. (2001). Race conditions: a case study. The Journal of Computing in Small Colleges,17(1): 88—102.
3.
Chandy, K.M. and Lamport, L. (1985). Distributed snapshots: determining global states in distributed systems. ACM Transactions on Computer Systems , 3(1): 63—75.
4.
Chase, C.M. and Garg, V.K. (1998). Detection of global predicates: techniques and their limitations. Distributed Computing, 11(4): 191—201.
5.
Chen, I. and Burdick, J.W. (1995). Determining task optimal modular robot assembly configurations. Proceedings of the 1995 IEEE International Conference on Robotics and Automation (ICRA '05).
6.
Collett, T.H., MacDonald, B.A. and Gerkey, B.P. (2005). Player 2.0: toward a practical robot programming framework. Proceedings of the Australasian Conference on Robotics and Automation (ACRA 2005).
7.
De Rosa, M. et al. (2006). Scalable shape sculpting via hole motion: motion planning in lattice constrained modular robots. Proceedings of the IEEE International Conference on Robotics and Automation (ICRA '06).
8.
Fitch, R. and Butler, Z. (2006). Million module march: scalable locomotion planning for large self-reconfiguring robots. Robotics: Science and Systems, Workshop on Self-Reconfigurable Robots.
9.
Fromentin, E. et al. (1994). On the fly testing of regular patterns in distributed computations. Proceedings of the International Conference on Parallel Processing, pp. 73—76.
10.
FSF (2007). GDB: The GNU Project Debugger. Free Software Foundation.
11.
Gerkey, B., Vaughan, R.T. and Howard, A. (2003). The player/stage project: tools for multi-robot and distributed sensor systems. Proceedings of the 11th International Conference on Advanced Robotics (ICAR 2003).
12.
Goldstein, S., Campbell, J. and Mowry, T. (2005). Programmable matter. IEEE Computer , 38(6): 99—101.
13.
Hurfin, M. et al. (1998). Efficient distributed detection of conjunctions of local predicates. Software Engineering, 24(8):664—677.
14.
Jorgensen, M.W., Ostergaard, E.H. and Lund, H. (2003). Modular atron: modules for a self-reconfigurable robot. Proceedings of IEEE/RSJ International Conference on Robots and Systems (IROS).
15.
Kotay, K. et al. (1998). The self-reconfiguring robotic molecule . Proceedings of the IEEE International Conference on Robotics and Automation.
16.
Lamine, K.B. and Kabanza, L. (2002). Reasoning about robot actions: a model checking approach. Advances in Plan-Based Control of Robotic Agents , pp. 123—139.
17.
Loo, B. et al. (2005). Implementing declarative overlays. Proceedings of ACM Symposium on Operating System Principles (SOSP) .
18.
Murata, S. et al. (2002). M-tran: self-reconfigurable modular robotic system. IEEE/ASME Transactions on Mechatronics, 7(4): 431—441.
19.
Nagpal, R. (2001). Programmable self-assembly: constructing global shape using biologically-inspired local interactions and origami mathematics. Ph.D. Thesis, Cambridge, MA, MIT, Department of Electrical Engineering and Computer Science.
20.
Nethercote, N. and Seward, J. (2003). Valgrind: a program supervision framework. Electronic Notes in Theoretical Computer Science, 89(2).
21.
Pamecha, A. et al. (1996). Design and implementation of metamorphic robots. Proceedings of the 1996 ASME Design Engineering Technical Conference and Computers in Engineering Conference.
22.
Pnueli, A. (1977). The temporal logic of programs. Proceedings of the 18th IEEE Symposium on Foundations of Computer Science, pp. 46—67.
23.
Reshko, G. (2004). Localization techniques for synthetic reality. Master's Thesis, Pittsburgh, PA, Carnegie Mellon University.
24.
Savage, S. et al. (1997). Eraser: a dynamic data race detector for multithreaded programs. ACM Transactions on Computer Systems , 15(4): 391—411.
25.
Singh, A. et al. (2006). Using queries for distributed monitoring and forensics. Proceedings of EuroSys2006, pp. 389— 402.
26.
Støy, K. (2004). Controlling self-reconfiguration using cellular automata and gradients. Proceedings of the 8th International Conference on Intelligent Autonomous Systems (IAS-8), pp. 693—702.
27.
Støy, K., Shen, W.-M. and Will, P. (2002). Using role based control to produce locomotion in chain-type self-reconfigurable robots. IEEE Transactions on Mechatronics, 7(4): 410—417.
28.
Tansley, S. (2007). Trends in embedded systems—a Microsoft perspective . Proceedings fo the IEEE International Conference on Microelectronic Systems Education (MSE '07).
29.
Xu, M., Bodik, R. and Hill, M.D. (2003). A “flight data recorder” for enabling full-system multiprocessor deterministic replay. ISCA '03: Proceedings of the 30th Annual International Symposium on Computer Architecture, New York, NY, ACM Press, pp. 122—135.
30.
Yang, Z. and Marsland, T.A. (1992). Global snapshots for distributed debugging. Proceedings of the International Conference on Computing and Information , pp. 436—440.
31.
Yim, M., Homans, S. and Roufas, K. (2001). Climbing with snake-like robots. Proceedings of IFAC Workshop on Mobile Robot Technology.
32.
Yim, M. et al. (1997). Rhombic dodecahedron shape for self-assembling robots. Technical Report P9710777, Xerox PARC SPL.
