Reliable hashing without collision detection

Autor:	Denis Leroy, Pierre Wolper
Rok vydání:	1993
Předmět:	Reduction (complexity) Computer science Distributed computing Hash function State space Effective method Temporal logic Collision detection Hash table Variety (cybernetics)
Zdroj:	Computer Aided Verification ISBN: 9783540569220 CAV
DOI:	10.1007/3-540-56922-7_6
Popis:	Thanks to a variety of new techniques, state-space exploration is becoming an increasingly effective method for the verification of concurrent programs. One of these techniques, hashing without collision detection, was proposed by Holzmann as a way to vastly reduce the amount of memory needed to store the explored state space. Unfortunately, this reduction in memory use comes at the price of a high probability of ignoring part of the state space and hence of missing existing errors. In this paper, we carefully analyze this method and show that, by using a modified strategy, it is possible to reduce the risk of error to a negligible amount while maintaining the memory use advantage of Holzmann's technique. Our proposed strategy has been implemented and we describe experiments that confirm the excellent expected results.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::0cb2ae7f7017917661ebb419f79d5691 https://doi.org/10.1007/3-540-56922-7_6 Zobrazit plný text záznamu