A computer system includes at least one virtual machine that has a plurality of virtual processors all running on an underlying hardware platform. A software interface layer such as a virtual machine monitor establishes traces on primary structures located in a common memory space as needed for the different virtual processors. Whenever any one of the virtual processors generates a trace event, such as accessing a traced structure, then a notification is sent to at least the other virtual processors that have a trace on the accessed primary structure. In some applications, the VMM derives and maintains secondary structures corresponding to the primary structures, such as where the VMM converts, through binary translation, original code intended to run on a virtual processor into code that can be run on an underlying physical processor of the hardware platform. In these applications, the VMM may rederive or invalidate the secondary structures as needed upon receipt of the notification of the trace event. Different semantics are provided for the notification, providing different choices of performance versus guaranteed consistency between primary and secondary structures. In the preferred embodiment of the invention, a dedicated sub-system is included within the VMM for each virtual processor; each sub-system establishes traces, senses trace events, issues the notification, and performs other operations relating specifically to its respective virtual processor.