Small Logs for Transactional Services: Distinction is much more accurate than (Positive) Discrimination
For complex services, logging is an integral part of many middleware aspects, especially, transactions and monitoring. In the event of a failure, the log allows us to deduce the cause of failure (diagnosis), recover by compensating the logged actions (atomicity), etc. However, for heterogeneous services, logging all the actions is often impracticable due to privacy/security constraints. Also, logging is expensive in terms of both time and space. Thus, we are interested in determining a small number of actions that needs to be logged, to know with certainty the actual sequence of executed actions from any given partial log. We propose two heuristics to determine such a small set of transitions, with services modeled as Finite State Machines. The first one is based on (Positive) Discrimination of transitions, using every observation to know (discriminate) that a maximal number of transitions occurred. We characterize it algebraically, giving a very fast algorithm. The second algorithm, the distinguishing algorithm, uses every observation to maximize the number of transitions which are ensured not to have occurred. We show experimentally that the second algorithm gives much more accurate results than the first one, although it is also slower (but still fast enough).
Debmalya Biswas Blaise Genest Thomas Gazagnaire
IRISA/INRIA & CNRS Campus Universitaire de Beaulieu 35042 Rennes Cedex, France Citrix Systems R&D Ltd.Black Horse House, Castle Park Cambridge, CB3 0FL, United Kingdom
国际会议
11th IEEE High Assurance Systems Engineering Symposium(HASE 2008)(第十一届IEEE高可信系统工程国际研讨会)
南京
英文
97-106
2008-12-03（万方平台首次上网日期，不代表论文的发表时间）