Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Reports, Documentation, and Standards
  4. DPOR-DS: Dynamic Partial Order Reduction in Distributed Systems
 
Loading...
Thumbnail Image
report

DPOR-DS: Dynamic Partial Order Reduction in Distributed Systems

Yabandeh, Maysam  
•
Kostic, Dejan  
2009

In this paper, we present DPOR-DS, an algorithm for dynamic partial order reduction in model checking of distributed systems. This work is inspired by the techniques introduced in the seminal work of DPOR which is designed for multi-threaded systems. Different characteristics between distributed systems and multi-threaded systems raises new challenges for implementing the idea in distributed system domain. By developing techniques to address those challenges, we prove the soundness and completeness of DPOR-DS. The performance of DPOR-DS is then compared to exhaustive search and state-of-the-art heuristics. The experimental results show that even though dynamic partial order reduction can alleviate the exponential explosion problem of state space exploration algorithms, the exponential growth still shows up after some certain steps.

  • Files
  • Details
  • Metrics
Loading...
Thumbnail Image
Name

paper_2.pdf

Access type

openaccess

Size

190.47 KB

Format

Adobe PDF

Checksum (MD5)

a126098c8bd9f95862c3c6060564fa02

Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés