Efficient parallel derivation of short distinguishing sequences for nondeterministic finite state machines using MapReduce
Abstract Distinguishing sequences are widely used in finite state machine-based conformance testing to solve the state identification problem. In this paper, we address the scalability issue encountered while deriving distinguishing sequences from complete observable nondeterministic finite state ma...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
SpringerOpen
2021-11-01
|
| Series: | Journal of Big Data |
| Subjects: | |
| Online Access: | https://doi.org/10.1186/s40537-021-00535-6 |
| _version_ | 1819006375796146176 |
|---|---|
| author | Bilal Elghadyry Faissal Ouardi Zineb Lotfi Sébastien Verel |
| author_facet | Bilal Elghadyry Faissal Ouardi Zineb Lotfi Sébastien Verel |
| author_sort | Bilal Elghadyry |
| collection | DOAJ |
| description | Abstract Distinguishing sequences are widely used in finite state machine-based conformance testing to solve the state identification problem. In this paper, we address the scalability issue encountered while deriving distinguishing sequences from complete observable nondeterministic finite state machines by introducing a massively parallel MapReduce version of the well-known Exact Algorithm. To the best of our knowledge, this is the first study to tackle this task using the MapReduce approach. First, we give a concise overview of the well-known Exact Algorithm for deriving distinguishing sequences from nondeterministic finite state machines. Second, we propose a parallel algorithm for this problem using the MapReduce approach and analyze its communication cost using Afrati et al. model. Furthermore, we conduct a variety of intensive and comparative experiments on a wide range of finite state machine classes to demonstrate that our proposed solution is efficient and scalable. |
| first_indexed | 2024-12-21T00:07:41Z |
| format | Article |
| id | doaj.art-73a721a384aa4cce84bde04ca5e307a5 |
| institution | Directory Open Access Journal |
| issn | 2196-1115 |
| language | English |
| last_indexed | 2024-12-21T00:07:41Z |
| publishDate | 2021-11-01 |
| publisher | SpringerOpen |
| record_format | Article |
| series | Journal of Big Data |
| spelling | doaj.art-73a721a384aa4cce84bde04ca5e307a52022-12-21T19:22:26ZengSpringerOpenJournal of Big Data2196-11152021-11-018112710.1186/s40537-021-00535-6Efficient parallel derivation of short distinguishing sequences for nondeterministic finite state machines using MapReduceBilal Elghadyry0Faissal Ouardi1Zineb Lotfi2Sébastien Verel3Univ. Littoral Côte d’Opale, UR 4491, LISIC, Laboratoire d’Informatique Signal et Image de la Côte d’OpaleANISSE research Team, Department of Computer Science, Faculty of Sciences, Mohammed V University in RabatANISSE research Team, Department of Computer Science, Faculty of Sciences, Mohammed V University in RabatUniv. Littoral Côte d’Opale, UR 4491, LISIC, Laboratoire d’Informatique Signal et Image de la Côte d’OpaleAbstract Distinguishing sequences are widely used in finite state machine-based conformance testing to solve the state identification problem. In this paper, we address the scalability issue encountered while deriving distinguishing sequences from complete observable nondeterministic finite state machines by introducing a massively parallel MapReduce version of the well-known Exact Algorithm. To the best of our knowledge, this is the first study to tackle this task using the MapReduce approach. First, we give a concise overview of the well-known Exact Algorithm for deriving distinguishing sequences from nondeterministic finite state machines. Second, we propose a parallel algorithm for this problem using the MapReduce approach and analyze its communication cost using Afrati et al. model. Furthermore, we conduct a variety of intensive and comparative experiments on a wide range of finite state machine classes to demonstrate that our proposed solution is efficient and scalable.https://doi.org/10.1186/s40537-021-00535-6Conformance testFinite state machinesParallel algorithmMapReduce framework |
| spellingShingle | Bilal Elghadyry Faissal Ouardi Zineb Lotfi Sébastien Verel Efficient parallel derivation of short distinguishing sequences for nondeterministic finite state machines using MapReduce Journal of Big Data Conformance test Finite state machines Parallel algorithm MapReduce framework |
| title | Efficient parallel derivation of short distinguishing sequences for nondeterministic finite state machines using MapReduce |
| title_full | Efficient parallel derivation of short distinguishing sequences for nondeterministic finite state machines using MapReduce |
| title_fullStr | Efficient parallel derivation of short distinguishing sequences for nondeterministic finite state machines using MapReduce |
| title_full_unstemmed | Efficient parallel derivation of short distinguishing sequences for nondeterministic finite state machines using MapReduce |
| title_short | Efficient parallel derivation of short distinguishing sequences for nondeterministic finite state machines using MapReduce |
| title_sort | efficient parallel derivation of short distinguishing sequences for nondeterministic finite state machines using mapreduce |
| topic | Conformance test Finite state machines Parallel algorithm MapReduce framework |
| url | https://doi.org/10.1186/s40537-021-00535-6 |
| work_keys_str_mv | AT bilalelghadyry efficientparallelderivationofshortdistinguishingsequencesfornondeterministicfinitestatemachinesusingmapreduce AT faissalouardi efficientparallelderivationofshortdistinguishingsequencesfornondeterministicfinitestatemachinesusingmapreduce AT zineblotfi efficientparallelderivationofshortdistinguishingsequencesfornondeterministicfinitestatemachinesusingmapreduce AT sebastienverel efficientparallelderivationofshortdistinguishingsequencesfornondeterministicfinitestatemachinesusingmapreduce |