A Typical Verification Challenge for the GRID

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

11 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
PublisherSchloss Dagstuhl - Leibniz-Zentrum fuer Informatik
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: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik.
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 : Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 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 = "Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik",
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, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 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 : Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 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 - Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik

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: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik. 2008. p. -. (Dagstuhl Seminar Proceedings; 08332).