View in EDS HTML Full Text PDF Full Text

Extending the wait-free hierarchy to multi-threaded systems.

Saved in:
Bibliographic Details
Title: Extending the wait-free hierarchy to multi-threaded systems.
Authors: Perrin, Matthieu1 (AUTHOR) matthieu.perrin@univ-nantes.fr, Mostéfaoui, Achour1 (AUTHOR), Bonin, Grégoire1 (AUTHOR), Courtillat-Piazza, Ludmila2 (AUTHOR)
Source: Distributed Computing. Aug2022, Vol. 35 Issue 4, p375-398. 24p.
Subjects: Infinite processes, Computer architecture, Programming languages, Shared workspaces
Abstract: In modern operating systems and programming languages adapted to multicore computer architectures, parallelism is abstracted by the notion of execution threads. Multi-threaded systems have two major specificities: on the one part, new threads can be created dynamically at runtime, so there is no bound on the number of threads participating in long-running executions. On the other part, threads have access to a memory allocation mechanism that cannot allocate infinite arrays. These specificities make it challenging to adapt some algorithms to multi-threaded systems, in particular those that need to assign one shared register per process. This paper explores the synchronization power of shared objects in multi-threaded systems by extending the famous Herlihy's wait-free hierarchy to take these constraints into consideration. It proposes to subdivide the set of objects with an infinite consensus number into nine new degrees, depending on their ability to synchronize a bounded, finite or infinite number of processes, with or without the need to allocate an infinite array. To show the relevance of the proposed extension, for each new degree it is either proved that it is empty, or an object illustrating it is proposed. [ABSTRACT FROM AUTHOR]
Copyright of Distributed Computing is the property of Springer Nature and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database: Engineering Source
Full text is not displayed to guests.
FullText Links:
  – Type: pdflink
Text:
  Availability: 1
Header DbId: egs
DbLabel: Engineering Source
An: 158138072
AccessLevel: 6
PubType: Academic Journal
PubTypeId: academicJournal
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: Extending the wait-free hierarchy to multi-threaded systems.
– Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22Perrin%2C+Matthieu%22">Perrin, Matthieu</searchLink><relatesTo>1</relatesTo> (AUTHOR)<i> matthieu.perrin@univ-nantes.fr</i><br /><searchLink fieldCode="AR" term="%22Mostéfaoui%2C+Achour%22">Mostéfaoui, Achour</searchLink><relatesTo>1</relatesTo> (AUTHOR)<br /><searchLink fieldCode="AR" term="%22Bonin%2C+Grégoire%22">Bonin, Grégoire</searchLink><relatesTo>1</relatesTo> (AUTHOR)<br /><searchLink fieldCode="AR" term="%22Courtillat-Piazza%2C+Ludmila%22">Courtillat-Piazza, Ludmila</searchLink><relatesTo>2</relatesTo> (AUTHOR)
– Name: TitleSource
  Label: Source
  Group: Src
  Data: <searchLink fieldCode="JN" term="%22Distributed+Computing%22">Distributed Computing</searchLink>. Aug2022, Vol. 35 Issue 4, p375-398. 24p.
– Name: Subject
  Label: Subjects
  Group: Su
  Data: <searchLink fieldCode="DE" term="%22Infinite+processes%22">Infinite processes</searchLink><br /><searchLink fieldCode="DE" term="%22Computer+architecture%22">Computer architecture</searchLink><br /><searchLink fieldCode="DE" term="%22Programming+languages%22">Programming languages</searchLink><br /><searchLink fieldCode="DE" term="%22Shared+workspaces%22">Shared workspaces</searchLink>
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: In modern operating systems and programming languages adapted to multicore computer architectures, parallelism is abstracted by the notion of execution threads. Multi-threaded systems have two major specificities: on the one part, new threads can be created dynamically at runtime, so there is no bound on the number of threads participating in long-running executions. On the other part, threads have access to a memory allocation mechanism that cannot allocate infinite arrays. These specificities make it challenging to adapt some algorithms to multi-threaded systems, in particular those that need to assign one shared register per process. This paper explores the synchronization power of shared objects in multi-threaded systems by extending the famous Herlihy's wait-free hierarchy to take these constraints into consideration. It proposes to subdivide the set of objects with an infinite consensus number into nine new degrees, depending on their ability to synchronize a bounded, finite or infinite number of processes, with or without the need to allocate an infinite array. To show the relevance of the proposed extension, for each new degree it is either proved that it is empty, or an object illustrating it is proposed. [ABSTRACT FROM AUTHOR]
– Name: AbstractSuppliedCopyright
  Label:
  Group: Ab
  Data: <i>Copyright of Distributed Computing is the property of Springer Nature and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.)
PLink https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=158138072
RecordInfo BibRecord:
  BibEntity:
    Identifiers:
      – Type: doi
        Value: 10.1007/s00446-022-00425-x
    Languages:
      – Code: eng
        Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 24
        StartPage: 375
    Subjects:
      – SubjectFull: Infinite processes
        Type: general
      – SubjectFull: Computer architecture
        Type: general
      – SubjectFull: Programming languages
        Type: general
      – SubjectFull: Shared workspaces
        Type: general
    Titles:
      – TitleFull: Extending the wait-free hierarchy to multi-threaded systems.
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: Perrin, Matthieu
      – PersonEntity:
          Name:
            NameFull: Mostéfaoui, Achour
      – PersonEntity:
          Name:
            NameFull: Bonin, Grégoire
      – PersonEntity:
          Name:
            NameFull: Courtillat-Piazza, Ludmila
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 01
              M: 08
              Text: Aug2022
              Type: published
              Y: 2022
          Identifiers:
            – Type: issn-print
              Value: 01782770
          Numbering:
            – Type: volume
              Value: 35
            – Type: issue
              Value: 4
          Titles:
            – TitleFull: Distributed Computing
              Type: main
ResultId 1