A Typical Verification Challenge for the GRID

    Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademic

    13 Downloads (Pure)

    Abstract

    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.
    Original languageUndefined
    Title of host publicationDagstuhl Seminar Proceedings 08332 'Distributed Verification and Grid Computing '
    EditorsH. E. Bal, L. Brim, M. Leucker
    Place of PublicationDagstuhl, Germany
    PublisherDagstuhl
    Pages-
    Number of pages2
    ISBN (Print)1862-4405
    Publication statusPublished - 2008

    Publication series

    NameDagstuhl Seminar Proceedings
    PublisherSchloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany
    Number08332
    ISSN (Print)1862-4405

    Keywords

    • METIS-252106
    • EWI-14070
    • Distributed algorithms
    • IR-65101
    • Strongly connected components
    • breadth first search
    • FMT-MC: MODEL CHECKING

    Cite this

    van de Pol, J. C. (2008). A Typical Verification Challenge for the GRID. In H. E. Bal, L. Brim, & M. Leucker (Eds.), Dagstuhl Seminar Proceedings 08332 'Distributed Verification and Grid Computing ' (pp. -). (Dagstuhl Seminar Proceedings; No. 08332). Dagstuhl, Germany: Dagstuhl.
    van de Pol, Jan Cornelis. / A Typical Verification Challenge for the GRID. Dagstuhl Seminar Proceedings 08332 'Distributed Verification and Grid Computing '. editor / H. E. Bal ; L. Brim ; M. Leucker. Dagstuhl, Germany : Dagstuhl, 2008. pp. - (Dagstuhl Seminar Proceedings; 08332).
    @inproceedings{88a59839567c4458a9b1f9fa510d58dc,
    title = "A Typical Verification Challenge for the GRID",
    abstract = "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.",
    keywords = "METIS-252106, EWI-14070, Distributed algorithms, IR-65101, Strongly connected components, breadth first search, FMT-MC: MODEL CHECKING",
    author = "{van de Pol}, {Jan Cornelis}",
    year = "2008",
    language = "Undefined",
    isbn = "1862-4405",
    series = "Dagstuhl Seminar Proceedings",
    publisher = "Dagstuhl",
    number = "08332",
    pages = "--",
    editor = "Bal, {H. E.} and L. Brim and M. Leucker",
    booktitle = "Dagstuhl Seminar Proceedings 08332 'Distributed Verification and Grid Computing '",
    address = "Germany",

    }

    van de Pol, JC 2008, A Typical Verification Challenge for the GRID. in HE Bal, L Brim & M Leucker (eds), Dagstuhl Seminar Proceedings 08332 'Distributed Verification and Grid Computing '. Dagstuhl Seminar Proceedings, no. 08332, Dagstuhl, Dagstuhl, Germany, pp. -.

    A Typical Verification Challenge for the GRID. / van de Pol, Jan Cornelis.

    Dagstuhl Seminar Proceedings 08332 'Distributed Verification and Grid Computing '. ed. / H. E. Bal; L. Brim; M. Leucker. Dagstuhl, Germany : Dagstuhl, 2008. p. - (Dagstuhl Seminar Proceedings; No. 08332).

    Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademic

    TY - GEN

    T1 - A Typical Verification Challenge for the GRID

    AU - van de Pol, Jan Cornelis

    PY - 2008

    Y1 - 2008

    N2 - 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.

    AB - 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.

    KW - METIS-252106

    KW - EWI-14070

    KW - Distributed algorithms

    KW - IR-65101

    KW - Strongly connected components

    KW - breadth first search

    KW - FMT-MC: MODEL CHECKING

    M3 - Conference contribution

    SN - 1862-4405

    T3 - Dagstuhl Seminar Proceedings

    SP - -

    BT - Dagstuhl Seminar Proceedings 08332 'Distributed Verification and Grid Computing '

    A2 - Bal, H. E.

    A2 - Brim, L.

    A2 - Leucker, M.

    PB - Dagstuhl

    CY - Dagstuhl, Germany

    ER -

    van de Pol JC. A Typical Verification Challenge for the GRID. In Bal HE, Brim L, Leucker M, editors, Dagstuhl Seminar Proceedings 08332 'Distributed Verification and Grid Computing '. Dagstuhl, Germany: Dagstuhl. 2008. p. -. (Dagstuhl Seminar Proceedings; 08332).