Algorithms and Complexity of Distributed Computation

分布式计算的算法和复杂性

基本信息

  • 批准号:
    RGPIN-2014-04739
  • 负责人:
  • 金额:
    $ 3.93万
  • 依托单位:
  • 依托单位国家:
    加拿大
  • 项目类别:
    Discovery Grants Program - Individual
  • 财政年份:
    2018
  • 资助国家:
    加拿大
  • 起止时间:
    2018-01-01 至 2019-12-31
  • 项目状态:
    已结题

项目摘要

Distributed computing systems ranging from simple desktop PCs or even cell phones with multi-core CPUs to high-performance computer clusters and systems "in-the-cloud" have to deal with problems that arise from concurrency, asynchrony, and failures. In these settings, the design of time and space efficient algorithms, proof of their correctness, and analysis of their complexity are challenging tasks. Algorithms and data structures for fundamental tasks in distributed systems are critical for the future development of efficient and fault-tolerant software. Lower bounds and impossibility results can guide researchers and software developers in their efforts to build efficient software systems, and can help hardware designers to decide what hardware primitives are needed.**In my research program I will devise new efficient algorithms and data structures for shared memory systems. I will try to find solutions for fundamental problems such as mutual exclusion, consensus, or the efficient and randomized implementation of strong primitives (e.g., compare-and-swap) from weaker ones. I will complement new algorithms with proofs of lower bounds in order to determine the time and space complexity of these problems.**I will also investigate new methods for measuring the quality of randomized and deterministic shared memory algorithms and the complexity of problems. The classical worst-case analysis is often too pessimistic to predict the actual performance of programs in practice, and sometimes leads to complicated algorithms. Therefore, novel ways of theoretically predicting the performance of algorithms need to be developed and evaluated.**Results of this research program will yield a better understanding of the system requirements of synchronization problems. Algorithms resulting from the research can be used as building blocks in software development, and lower bounds can help software and hardware developers making design decisions. Research on novel analytical performance measures for shared memory algorithms will directly and indirectly yield new solutions to synchronization problems, and improve the performance of systems relying on synchronization algorithms.
从简单的台式PC甚至是具有多核CPU的手机到高性能计算机集群和“云中”系统的分布式计算系统必须处理并发、并发和故障引起的问题。在这些环境中,设计时间和空间有效的算法,证明其正确性,并分析其复杂性是具有挑战性的任务。分布式系统中基本任务的算法和数据结构对于未来高效和容错软件的开发至关重要。下界和不可能性结果可以指导研究人员和软件开发人员努力构建有效的软件系统,并可以帮助硬件设计人员决定需要什么硬件原语。在我的研究计划中,我将为共享内存系统设计新的有效算法和数据结构。我将试图找到基本问题的解决方案,如互斥,共识,或强原语的有效和随机实现(例如,比较和交换)。为了确定这些问题的时间和空间复杂度,我将用下界的证明来补充新的算法。我还将研究新的方法来衡量随机和确定性共享内存算法的质量和问题的复杂性。经典的最坏情况分析在实际应用中往往过于悲观,不能准确预测程序的实际性能,而且有时会导致算法复杂。因此,需要开发和评估理论上预测算法性能的新方法。这项研究计划的结果将产生一个更好的了解系统的同步问题的要求。从研究中产生的算法可以用作软件开发中的构建块,下限可以帮助软件和硬件开发人员做出设计决策。研究新的共享内存算法的性能分析方法,将直接或间接地为同步问题提供新的解决方案,提高依赖于同步算法的系统的性能。

项目成果

期刊论文数量(0)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)

数据更新时间:{{ journalArticles.updateTime }}

{{ item.title }}
{{ item.translation_title }}
  • DOI:
    {{ item.doi }}
  • 发表时间:
    {{ item.publish_year }}
  • 期刊:
  • 影响因子:
    {{ item.factor }}
  • 作者:
    {{ item.authors }}
  • 通讯作者:
    {{ item.author }}

数据更新时间:{{ journalArticles.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ monograph.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ sciAawards.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ conferencePapers.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ patent.updateTime }}

Woelfel, Philipp其他文献

Woelfel, Philipp的其他文献

{{ item.title }}
{{ item.translation_title }}
  • DOI:
    {{ item.doi }}
  • 发表时间:
    {{ item.publish_year }}
  • 期刊:
  • 影响因子:
    {{ item.factor }}
  • 作者:
    {{ item.authors }}
  • 通讯作者:
    {{ item.author }}

{{ truncateString('Woelfel, Philipp', 18)}}的其他基金

Randomized and Distributed Algorithms
随机和分布式算法
  • 批准号:
    CRC-2016-00289
  • 财政年份:
    2022
  • 资助金额:
    $ 3.93万
  • 项目类别:
    Canada Research Chairs
Design and Complexity of Distributed Algorithms
分布式算法的设计和复杂性
  • 批准号:
    RGPIN-2019-04852
  • 财政年份:
    2022
  • 资助金额:
    $ 3.93万
  • 项目类别:
    Discovery Grants Program - Individual
Design and Complexity of Distributed Algorithms
分布式算法的设计和复杂性
  • 批准号:
    RGPIN-2019-04852
  • 财政年份:
    2021
  • 资助金额:
    $ 3.93万
  • 项目类别:
    Discovery Grants Program - Individual
Randomized And Distributed Algorithms
随机和分布式算法
  • 批准号:
    CRC-2016-00289
  • 财政年份:
    2021
  • 资助金额:
    $ 3.93万
  • 项目类别:
    Canada Research Chairs
Randomized and Distributed Algorithms
随机和分布式算法
  • 批准号:
    CRC-2016-00289
  • 财政年份:
    2020
  • 资助金额:
    $ 3.93万
  • 项目类别:
    Canada Research Chairs
Design and Complexity of Distributed Algorithms
分布式算法的设计和复杂性
  • 批准号:
    RGPIN-2019-04852
  • 财政年份:
    2020
  • 资助金额:
    $ 3.93万
  • 项目类别:
    Discovery Grants Program - Individual
Randomized and Distributed Algorithms
随机和分布式算法
  • 批准号:
    CRC-2016-00289
  • 财政年份:
    2019
  • 资助金额:
    $ 3.93万
  • 项目类别:
    Canada Research Chairs
Design and Complexity of Distributed Algorithms
分布式算法的设计和复杂性
  • 批准号:
    RGPIN-2019-04852
  • 财政年份:
    2019
  • 资助金额:
    $ 3.93万
  • 项目类别:
    Discovery Grants Program - Individual
Randomized and Distributed Algorithms
随机和分布式算法
  • 批准号:
    CRC-2016-00289
  • 财政年份:
    2018
  • 资助金额:
    $ 3.93万
  • 项目类别:
    Canada Research Chairs
Randomized and Distributed Algorithms
随机和分布式算法
  • 批准号:
    CRC-2016-00289
  • 财政年份:
    2017
  • 资助金额:
    $ 3.93万
  • 项目类别:
    Canada Research Chairs

相似海外基金

Design and Complexity of Distributed Algorithms
分布式算法的设计和复杂性
  • 批准号:
    RGPIN-2019-04852
  • 财政年份:
    2022
  • 资助金额:
    $ 3.93万
  • 项目类别:
    Discovery Grants Program - Individual
Design and Complexity of Distributed Algorithms
分布式算法的设计和复杂性
  • 批准号:
    RGPIN-2019-04852
  • 财政年份:
    2021
  • 资助金额:
    $ 3.93万
  • 项目类别:
    Discovery Grants Program - Individual
Design and Complexity of Distributed Algorithms
分布式算法的设计和复杂性
  • 批准号:
    RGPIN-2019-04852
  • 财政年份:
    2020
  • 资助金额:
    $ 3.93万
  • 项目类别:
    Discovery Grants Program - Individual
Design and Complexity of Distributed Algorithms
分布式算法的设计和复杂性
  • 批准号:
    RGPIN-2019-04852
  • 财政年份:
    2019
  • 资助金额:
    $ 3.93万
  • 项目类别:
    Discovery Grants Program - Individual
Algorithms and Complexity of Distributed Computation
分布式计算的算法和复杂性
  • 批准号:
    RGPIN-2014-04739
  • 财政年份:
    2017
  • 资助金额:
    $ 3.93万
  • 项目类别:
    Discovery Grants Program - Individual
Algorithms and Complexity of Distributed Computation
分布式计算的算法和复杂性
  • 批准号:
    RGPIN-2014-04739
  • 财政年份:
    2016
  • 资助金额:
    $ 3.93万
  • 项目类别:
    Discovery Grants Program - Individual
Centralized and Distributed Reduced-Complexity User Scheduling and Radio Resource Allocation Algorithms for MIMO Wireless Networks
用于 MIMO 无线网络的集中式和分布式复杂度降低用户调度和无线资源分配算法
  • 批准号:
    436903-2012
  • 财政年份:
    2015
  • 资助金额:
    $ 3.93万
  • 项目类别:
    Industrial Postgraduate Scholarships
Algorithms and Complexity of Distributed Computation
分布式计算的算法和复杂性
  • 批准号:
    RGPIN-2014-04739
  • 财政年份:
    2015
  • 资助金额:
    $ 3.93万
  • 项目类别:
    Discovery Grants Program - Individual
Algorithms and Complexity of Distributed Computation
分布式计算的算法和复杂性
  • 批准号:
    462331-2014
  • 财政年份:
    2015
  • 资助金额:
    $ 3.93万
  • 项目类别:
    Discovery Grants Program - Accelerator Supplements
Algorithms and Complexity of Distributed Computation
分布式计算的算法和复杂性
  • 批准号:
    RGPIN-2014-04739
  • 财政年份:
    2014
  • 资助金额:
    $ 3.93万
  • 项目类别:
    Discovery Grants Program - Individual
{{ showInfoDetail.title }}

作者:{{ showInfoDetail.author }}

知道了