A typical verification challenge for the GRID community is
presented. The concrete challenge is to implement a simple recursive algorithm for finding the strongly connected components in a graph. The graph is typically stored in the collective memory of a number of computers, so a distributed algorithm is necessary.
The implementation should be efficient and scalable, and separate synchronization and implementation details from the purely algorithmic aspects. In the end, a framework is envisaged for distributed algorithms on very large graphs. This would be useful to explore various alternative algorithmic choices.
|Title of host publication||Dagstuhl Seminar Proceedings 08332 'Distributed Verification and Grid Computing '|
|Editors||H. E. Bal, L. Brim, M. Leucker|
|Place of Publication||Dagstuhl, Germany|
|Number of pages||2|
|Publication status||Published - 2008|
|Name||Dagstuhl Seminar Proceedings|
|Publisher||Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany|
- Distributed algorithms
- Strongly connected components
- breadth first search
- FMT-MC: MODEL CHECKING