{"controller"=>"catalog", "action"=>"show", "id"=>"8478254"}
  • EN
  • DA

Danish NationalResearch Database

  • Search Publications & Researchers
  • Open Access Indicator
  • Publications
  • Researchers
Example Finds records
water{} containing the word "water".
water supplies"{}" containing the phrase "water supplies".
author:"Doe, John"author:"{}" containing the prase "Doe, John" in the author field.
title:IEEEtitle:{} containing the word "IEEE" in the title field.
Need more help? Advanced search tutorial
  • Selected (0)
  • History

Algebraic topology and concurrency

    • Save to Mendeley
    • Export to BibTeX
    • Export to RIS
    • Email citation
Authors:
  • Fajstrup, Lisbeth ;
    Close
    Department of Mathematical Sciences, The Faculty of Engineering and Science, Aalborg University
  • Raussen, Martin ;
    Close
    The Faculty of Engineering and Science, Aalborg University
  • Goubault, Eric
    Close
    CEA, Gif-sur-Yvette Cedex, France
DOI:
10.1016/j.tcs.2006.03.022
Abstract:
We show in this article that some concepts from homotopy theory, in algebraic topology,are relevant for studying concurrent programs. We exhibit a natural semantics of semaphore programs, based on partially ordered topological spaces, which are studied up to “elastic deformation” or homotopy, giving information about important properties of the program, such as deadlocks, unreachables, serializability, essential schedules, etc. In fact, it is not quite ordinary homotopy that has to be used, but rather a “directed homotopy” that does not reverse the flow of time. We show some of the essential differences between ordinary and directed homotopy through examples. We also relate the topological view to a combinatorial view of concurrent programs closer to transition systems, through the notion of a cubical set. Finally we apply some of these concepts to the proof of the safeness of a two-phase protocol, well-known and used in concurrent database theory. We end up with a list of problems from both a mathematical and a computer-scientific point of view.
Type:
Journal article
Language:
English
Published in:
Theoretical Computer Science, 2006, Vol 357, Issue 1-3, p. 241-278
Main Research Area:
Science/technology
Publication Status:
Published
Review type:
Peer Review
Submission year:
2006
Scientific Level:
Scientific
ID:
8478254

Full text access

  • Doi Get publisher edition via DOI resolver
Checking for on-site access...

On-site access

At institution

  • Aalborg university.en
Feedback

Sitemap

  • Search
    • Statistics
    • Tutorial
    • Data
    • FAQ
    • Contact
  • Open Access
    • Overview
    • Development
    • FAQ
    • Contact
  • About
    • Institutions
    • Release History
    • Cookies and privacy policy

Copyright © 1998–2018.

Fivu en