AF: Small: A Framework For Algorithmic Design of Self-Stabilizing Network Protocols
AF: Small: A Framework For Algorithmic Design of Self-Stabilizing Network Protocols
批准号:
1116546
负责人:
Ali Ebnenasir
金额:
$25.4万
依托单位国家:
美国
项目类别:
Standard Grant
财政年份:
2011
资助国家:
美国
项目状态:
已结题
起止时间:
2011-08-01 至 2015-12-31
中文摘要
本研究的重点是促进自稳定(SS)网络协议的设计,其中SS协议最终从任何问题配置恢复到合法配置(即收敛),并且只要没有扰动(即关闭)就保持在合法配置中。这是一个重要的问题,因为当今复杂的分布式系统(例如,互联网)经常由于临时故障的发生而达到非法配置,这些故障会干扰协议而不会造成永久损坏(例如,内存中的位翻转,错误的初始化)。大多数现有的方法都是基于手工创建初始设计和事后对手工设计的验证。本研究提出了一种基于“小规模综合和概括”哲学的范式转变。具体来说,研究人员研究了(i)自动生成SS协议的小实例,以及(ii)将合成实例推广到更大的协议。本研究不是设计和验证特定问题的SS协议,而是提供了一个可重用的综合方法存储库,用于向非稳定协议添加收敛性。此外,本文还提出了综合协议小实例泛化的三种技术,即综合收敛阶梯、截止定理和结构归纳法。为了评估,研究人员在不同的拓扑结构和不同的公平假设下,研究了现实世界协议和经典分布式计算问题(如互斥和领导者选举)的自动收敛设计。调查人员还确定了复杂性标准,并将其汇编为公共基准。
英文摘要
This research focuses on facilitating the design of Self-Stabilizing (SS) network protocols, where a SS protocol eventually recovers from any troubled configuration to a legitimate configuration (i.e., convergence) and stays in legitimate configurations as long as there are no perturbations (i.e., closure). This is an important problem as today's complex distributed systems (e.g., the Internet) frequently reach illegitimate configurations due to the occurrence of the transient faults that perturb the protocols without causing permanent damage (e.g., bit flips in memory, bad initialization). Most existing methods are based on the manual creation of an initial design and after-the-fact verification of the manual design. This research presents a paradigm shift based on a philosophy of 'synthesize in small scale and generalize'. Specifically, the investigators study (i) the automatic generation of small instances of SS protocol, and (ii) the generalization of the synthesized instances to larger protocols.Instead of designing and verifying problem-specific SS protocols, this research provides a reusable repository of synthesis methods for the addition of convergence to nonstabilizing protocols. Moreover, this research presents three techniques for the generalization of the small instances of the synthesized protocols, namely synthesized convergence stairs, cutoff theorems and structural induction. For evaluation, the investigators study the automated design of convergence for real world protocols and classic distributed computing problems (e.g., mutual exclusion and leader election) under different topologies and distinct fairness assumptions. The investigators also identify complexity criteria and compile them in a public benchmark.
期刊论文(0)
专著(0)
科研奖励(0)
会议论文
EAGER: Towards the Model Checking of the Partitioned Global Address Space (PGAS) Applications
-
批准号:0950678
-
项目类别:Standard Grant
-
资助金额:$10.67万
-
财政年份:2009
-
负责人:Ali Ebnenasir
-
依托单位:
国内基金
海外基金
登录
查看更多内容
昼夜节律性small RNA在血斑形成时间推断中的法医学应用研究
-
批准号:
-
项目类别:省市级项目
-
资助金额:--
-
批准年份:2024
-
负责人:
-
依托单位:
tRNA-derived small RNA上调YBX1/CCL5通路参与硼替佐米诱导慢性疼痛的机制研究
-
批准号:
-
项目类别:省市级项目
-
资助金额:10.0万元
-
批准年份:2022
-
负责人:张祥忠
-
依托单位:
Small RNA调控I-F型CRISPR-Cas适应性免疫性的应答及分子机制
-
批准号:32000033
-
项目类别:青年科学基金项目
-
资助金额:24.0万元
-
批准年份:2020
-
负责人:林平
-
依托单位:
Small RNAs调控解淀粉芽胞杆菌FZB42生防功能的机制研究
-
批准号:31972324
-
项目类别:面上项目
-
资助金额:58.0万元
-
批准年份:2019
-
负责人:高学文
-
依托单位:
变异链球菌small RNAs连接LuxS密度感应与生物膜形成的机制研究
-
批准号:81900988
-
项目类别:青年科学基金项目
-
资助金额:21.0万元
-
批准年份:2019
-
负责人:毛梦莹
-
依托单位:
肠道细菌关键small RNAs在克罗恩病发生发展中的功能和作用机制
-
批准号:31870821
-
项目类别:面上项目
-
资助金额:56.0万元
-
批准年份:2018
-
负责人:陈江宁
-
依托单位:
基于small RNA 测序技术解析鸽分泌鸽乳的分子机制
-
批准号:31802058
-
项目类别:青年科学基金项目
-
资助金额:26.0万元
-
批准年份:2018
-
负责人:麻慧
-
依托单位:
Small RNA介导的DNA甲基化调控的水稻草矮病毒致病机制
-
批准号:31772128
-
项目类别:面上项目
-
资助金额:60.0万元
-
批准年份:2017
-
负责人:吴建国
-
依托单位:
基于small RNA-seq的针灸治疗桥本甲状腺炎的免疫调控机制研究
-
批准号:81704176
-
项目类别:青年科学基金项目
-
资助金额:20.0万元
-
批准年份:2017
-
负责人:赵继梦
-
依托单位:
水稻OsSGS3与OsHEN1调控small RNAs合成及其对抗病性的调节
-
批准号:91640114
-
项目类别:重大研究计划
-
资助金额:85.0万元
-
批准年份:2016
-
负责人:何祖华
-
依托单位: