Distributed network algorithms

分布式网络算法

基本信息

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

项目摘要

The subject of the proposed research is the design and analysis of distributed algorithms working in a network environment. Such algorithms are executed by individual entities, such as processors or mobile agents, without any central monitor controlling the execution. We investigate the impact of unreliable or incomplete information processed by distributed algorithms on their performance, and design algorithms working efficiently in the presence of faults, or in spite of incomplete knowledge of the network. We focus on the following topics: communication in (partially) unknown networks, computational tasks performed by mobile agents in networks, and network algorithms with advice. The main objectives of the research program are:***1. Construct efficient communication algorithms for such tasks as broadcasting and all-to-all communication, working in networks whose topology is (partially) unknown, in anonymous networks, and in networks some of whose components (nodes and/or links) may be faulty. ***2. Construct efficient algorithms for such tasks as exploration and mapping of a (partially) unknown network by mobile agents, gathering all agents in one node of the network, finding a target by a team of mobile agents, detecting faults by mobile agents, and others, under various restrictions on perceptive and moving capabilities of the agents, on their communication capabilities and on their memory size. ***3. Establish trade-offs between the amount of information about the network (called advice) supplied to nodes or mobile agents, and the efficiency of performing a given task in the network, such as communication, leader election, network exploration, or gathering of agents. The advice paradigm permits to measure the minimum amount of information sufficient for a given task, regardless of the type of this information, which can concern numerical parameters of the network, such as the diameter or the size, or provide knowledge about network topology.***In our research, networks are modeled as graphs whose nodes represent processors, and edges represent communication links. The methodology we propose is two-fold: conjectures concerning algorithm performance will be formulated using computer simulations, and subsequently proved using techniques from combinatorial mathematics, graph theory and probabilistic analysis. The novelty of our approach is in focusing on trade-offs between the amount of information available to network entities executing a distributed algorithm and the efficiency of accomplishing a computational task. We want to design the best methods of performing distributed computations in a network, under a given amount and type of available knowledge. The significance of this research is in showing efficient ways of coping with incomplete information and of handling faults of components, while performing computations in various network computing environments.
所提出的研究的主题是分布式算法的设计和分析工作在网络环境中。这样的算法由诸如处理器或移动的代理的各个实体执行,而没有任何控制执行的中央监视器。我们调查的影响,不可靠或不完整的信息处理分布式算法对它们的性能,并设计算法有效地工作在故障的存在下,或尽管不完整的网络知识。我们专注于以下主题:(部分)未知网络中的通信,网络中的移动的代理执行的计算任务,和网络算法的意见。本研究的主要目的是:**1。为广播和所有对所有通信等任务构建有效的通信算法,工作在拓扑结构(部分)未知的网络中,匿名网络中,以及某些组件(节点和/或链路)可能有故障的网络中。*2。构建有效的算法,如勘探和映射的(部分)未知网络的移动的代理,收集所有代理在网络的一个节点,找到一个目标的一组移动的代理,检测故障的移动的代理,和其他人,在各种限制下感知和移动能力的代理,他们的通信能力和他们的内存大小。*3。在提供给节点或移动的代理的关于网络的信息(称为建议)的量与在网络中执行给定任务(例如通信、领导者选举、网络探索或代理收集)的效率之间建立权衡。建议范式允许测量足够用于给定任务的最小信息量,而不管这些信息的类型,这些信息可以涉及网络的数值参数,例如直径或大小,或提供有关网络拓扑的知识。在我们的研究中,网络被建模为图,其节点代表处理器,边代表通信链路。我们提出的方法是双重的:有关算法的性能将制定使用计算机模拟,并随后证明使用组合数学,图论和概率分析技术。我们的方法的新奇之处在于专注于执行分布式算法的网络实体可用的信息量和完成计算任务的效率之间的权衡。我们希望在给定数量和类型的可用知识下,设计在网络中执行分布式计算的最佳方法。这项研究的意义是在各种网络计算环境中进行计算时,显示有效的方法来处理不完整的信息和处理组件的故障。

项目成果

期刊论文数量(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 }}

Pelc, Andrzej其他文献

Negative Ion Formation by Thermal Surface Ionization of Sulfur Dioxide
  • DOI:
    10.1002/cphc.202000388
  • 发表时间:
    2020-07-14
  • 期刊:
  • 影响因子:
    2.9
  • 作者:
    Marciszuk, Karolina;Pienkos, Tomasz;Pelc, Andrzej
  • 通讯作者:
    Pelc, Andrzej
Decidability classes for mobile agents computing
Negative ion formation and fragmentation upon dissociative electron attachment to the nicotinamide molecule.
  • DOI:
    10.1039/d1ra06083j
  • 发表时间:
    2021-09-27
  • 期刊:
  • 影响因子:
    3.9
  • 作者:
    Ziegler, Patrick;Pelc, Andrzej;Arthur-Baidoo, Eugene;Ameixa, Joao;Oncak, Milan;Denifl, Stephan
  • 通讯作者:
    Denifl, Stephan
Leader election for anonymous asynchronous agents in arbitrary networks
  • DOI:
    10.1007/s00446-013-0196-x
  • 发表时间:
    2014-02-01
  • 期刊:
  • 影响因子:
    1.3
  • 作者:
    Dereniowski, Dariusz;Pelc, Andrzej
  • 通讯作者:
    Pelc, Andrzej

Pelc, Andrzej的其他文献

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

{{ truncateString('Pelc, Andrzej', 18)}}的其他基金

Distributed network algorithms
分布式网络算法
  • 批准号:
    RGPIN-2018-03899
  • 财政年份:
    2022
  • 资助金额:
    $ 3.5万
  • 项目类别:
    Discovery Grants Program - Individual
Distributed network algorithms
分布式网络算法
  • 批准号:
    RGPIN-2018-03899
  • 财政年份:
    2021
  • 资助金额:
    $ 3.5万
  • 项目类别:
    Discovery Grants Program - Individual
Distributed network algorithms
分布式网络算法
  • 批准号:
    RGPIN-2018-03899
  • 财政年份:
    2020
  • 资助金额:
    $ 3.5万
  • 项目类别:
    Discovery Grants Program - Individual
Distributed network algorithms
分布式网络算法
  • 批准号:
    RGPIN-2018-03899
  • 财政年份:
    2019
  • 资助金额:
    $ 3.5万
  • 项目类别:
    Discovery Grants Program - Individual
Distributed network algorithms
分布式网络算法
  • 批准号:
    8136-2013
  • 财政年份:
    2017
  • 资助金额:
    $ 3.5万
  • 项目类别:
    Discovery Grants Program - Individual
Distributed network algorithms
分布式网络算法
  • 批准号:
    8136-2013
  • 财政年份:
    2015
  • 资助金额:
    $ 3.5万
  • 项目类别:
    Discovery Grants Program - Individual
Distributed network algorithms
分布式网络算法
  • 批准号:
    8136-2013
  • 财政年份:
    2014
  • 资助金额:
    $ 3.5万
  • 项目类别:
    Discovery Grants Program - Individual
Distributed network algorithms
分布式网络算法
  • 批准号:
    8136-2013
  • 财政年份:
    2013
  • 资助金额:
    $ 3.5万
  • 项目类别:
    Discovery Grants Program - Individual
Network algorithms processing unreliable or incomplete information
网络算法处理不可靠或不完整的信息
  • 批准号:
    8136-2008
  • 财政年份:
    2012
  • 资助金额:
    $ 3.5万
  • 项目类别:
    Discovery Grants Program - Individual
Network algorithms processing unreliable or incomplete information
网络算法处理不可靠或不完整的信息
  • 批准号:
    8136-2008
  • 财政年份:
    2011
  • 资助金额:
    $ 3.5万
  • 项目类别:
    Discovery Grants Program - Individual

相似国自然基金

铜募集微纳米网片上调LOX活性稳定胶原网络促进盆底修复的研究
  • 批准号:
    82371638
  • 批准年份:
    2023
  • 资助金额:
    49.00 万元
  • 项目类别:
    面上项目
GPSM1介导Ca2+循环-II型肌球蛋白网络调控脂肪产热及代谢稳态的机制研究
  • 批准号:
    82370879
  • 批准年份:
    2023
  • 资助金额:
    49.00 万元
  • 项目类别:
    面上项目
Notch1/β-catenin/Pax6通路调控角膜缘干细胞分化的机制研究
  • 批准号:
    32000537
  • 批准年份:
    2020
  • 资助金额:
    24.0 万元
  • 项目类别:
    青年科学基金项目
Jab1依赖结合蛋白和去泛素化功能在DNA损伤反应中的双重作用研究
  • 批准号:
    31900558
  • 批准年份:
    2019
  • 资助金额:
    24.0 万元
  • 项目类别:
    青年科学基金项目
多维在线跨语言Calling Network建模及其在可信国家电子税务软件中的实证应用
  • 批准号:
    91418205
  • 批准年份:
    2014
  • 资助金额:
    170.0 万元
  • 项目类别:
    重大研究计划
以PXR、CAR为核心的调控网络、作用机制及其指导环磷酰胺个体化用药的临床转化研究
  • 批准号:
    81173131
  • 批准年份:
    2011
  • 资助金额:
    60.0 万元
  • 项目类别:
    面上项目
转录因子DNA结合谱绘制新方法及其应用研究
  • 批准号:
    61171030
  • 批准年份:
    2011
  • 资助金额:
    60.0 万元
  • 项目类别:
    面上项目
内容分发网络中的P2P分群分发技术研究
  • 批准号:
    61100238
  • 批准年份:
    2011
  • 资助金额:
    20.0 万元
  • 项目类别:
    青年科学基金项目
基于贝叶斯网络可靠度演进模型的城市雨水管网整体优化设计理论研究
  • 批准号:
    51008191
  • 批准年份:
    2010
  • 资助金额:
    20.0 万元
  • 项目类别:
    青年科学基金项目

相似海外基金

Distributed network algorithms
分布式网络算法
  • 批准号:
    RGPIN-2018-03899
  • 财政年份:
    2022
  • 资助金额:
    $ 3.5万
  • 项目类别:
    Discovery Grants Program - Individual
Distributed network algorithms
分布式网络算法
  • 批准号:
    RGPIN-2018-03899
  • 财政年份:
    2021
  • 资助金额:
    $ 3.5万
  • 项目类别:
    Discovery Grants Program - Individual
CIF: Small: Timing Optimization Over Random Network Asynchrony - Theory And Distributed Algorithms
CIF:小:随机网络异步的时序优化 - 理论和分布式算法
  • 批准号:
    2008527
  • 财政年份:
    2020
  • 资助金额:
    $ 3.5万
  • 项目类别:
    Standard Grant
Distributed network algorithms
分布式网络算法
  • 批准号:
    RGPIN-2018-03899
  • 财政年份:
    2020
  • 资助金额:
    $ 3.5万
  • 项目类别:
    Discovery Grants Program - Individual
Distributed network algorithms
分布式网络算法
  • 批准号:
    RGPIN-2018-03899
  • 财政年份:
    2019
  • 资助金额:
    $ 3.5万
  • 项目类别:
    Discovery Grants Program - Individual
Distributed network algorithms
分布式网络算法
  • 批准号:
    8136-2013
  • 财政年份:
    2017
  • 资助金额:
    $ 3.5万
  • 项目类别:
    Discovery Grants Program - Individual
Distributed network algorithms
分布式网络算法
  • 批准号:
    8136-2013
  • 财政年份:
    2015
  • 资助金额:
    $ 3.5万
  • 项目类别:
    Discovery Grants Program - Individual
Distributed network algorithms
分布式网络算法
  • 批准号:
    8136-2013
  • 财政年份:
    2014
  • 资助金额:
    $ 3.5万
  • 项目类别:
    Discovery Grants Program - Individual
Distributed network algorithms
分布式网络算法
  • 批准号:
    8136-2013
  • 财政年份:
    2013
  • 资助金额:
    $ 3.5万
  • 项目类别:
    Discovery Grants Program - Individual
Designing distributed algorithms running on continuous network dynamics
设计在连续网络动态上运行的分布式算法
  • 批准号:
    22700010
  • 财政年份:
    2010
  • 资助金额:
    $ 3.5万
  • 项目类别:
    Grant-in-Aid for Young Scientists (B)
{{ showInfoDetail.title }}

作者:{{ showInfoDetail.author }}

知道了