Theoretical Foundations for Reliable Computing in Unreliable Mobile ad hoc Networks
不可靠移动自组织网络中可靠计算的理论基础
基本信息
- 批准号:0726514
- 负责人:
- 金额:$ 27.5万
- 依托单位:
- 依托单位国家:美国
- 项目类别:Standard Grant
- 财政年份:2007
- 资助国家:美国
- 起止时间:2007-09-15 至 2012-08-31
- 项目状态:已结题
- 来源:
- 关键词:
项目摘要
"Theoretical Foundations for Reliable Computing in Unreliable Mobile ad hoc Networks"Nancy Lynch, MIT CSAILThis project is developing theoretical foundations---formal models, complexity measures, abstract problem definitions, algorithms, and impossibility results---to explain what can and what cannot be computed reliably in realistic, unreliable mobile ad hoc networks (MANETs). The long-range goal of this work is to provide guidance for building high quality, reliable, high performance applications for such networks. Motivating applications include data management, communication, and coordination (e.g., of people, robots, or vehicles).The assumed MANET model consists of a collection of mobile nodes, moving according to specified constraints. A special ``real world'' component provides the mobile nodes with approximate information about the current time and their own locations. Nodes communicate using local wireless radio broadcast, subject to realistic message delivery constraints. A ``contention manager'' component encapsulates strategies such as exponential backoff, advising nodes about when they are likely to be able to transmit successfully. A ``collision detector'' component provides (possibly unreliable) information to each node about messages that it might not have received.Some problems being studied arise directly from MANET applications. Others describe abstractions that are intended to simplify the task of writing applications, such as leader and cluster management services, group membership services, location services, and virtual networks. The need for reliability arises from reliability requirements of the applications and from the need for abstractions with clear guarantees.Results being sought are:(1) Definitions of realistic MANET models.(2) Definitions of application and abstraction problems with strong reliability requirements.(3) Efficient algorithms and corresponding impossibility results for these problems.(4) Integration of individual algorithmic results to yield end-to-end guarantees for high-level problems in terms of the basic MANET model.
“不可靠的移动的ad hoc网络中可靠计算的理论基础”Nancy Lynch,麻省理工学院CSAIL该项目正在开发理论基础--形式模型、复杂性度量、抽象问题定义、算法和不可能性结果--以解释在现实、不可靠的移动的ad hoc网络(MANET)中可以可靠地计算什么和不能可靠地计算什么。这项工作的长期目标是为此类网络构建高质量,可靠,高性能的应用程序提供指导。 激励应用程序包括数据管理、通信和协调(例如,假设的MANET模型由根据指定约束移动的移动的节点的集合组成。 特殊的"真实的世界“组件为移动的节点提供关于当前时间和它们自己的位置的近似信息。 节点使用本地无线电广播进行通信,受到现实的消息传递约束。 一个“竞争管理器”组件封装了指数退避等策略,告知节点何时能够成功传输。 一个“冲突检测器”组件提供(可能不可靠)的信息,每个节点的消息,它可能没有收到。 其他人则描述了旨在简化编写应用程序任务的抽象,例如领导者和集群管理服务、组成员服务、位置服务和虚拟网络。 对可靠性的需求来自于应用的可靠性要求和对具有明确保证的抽象的需求。(2)具有强可靠性要求的应用和抽象问题的定义。(3)这些问题的有效算法和相应的不可能性结果。(4)集成各个算法的结果,以产生端到端的保证高层次的问题,在基本的MANET模型。
项目成果
期刊论文数量(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 }}
Nancy Lynch其他文献
Trade-offs between selection complexity and performance when searching the plane without communication
在没有通信的情况下搜索平面时选择复杂性和性能之间的权衡
- DOI:
10.1145/2611462.2611463 - 发表时间:
2014 - 期刊:
- 影响因子:0
- 作者:
Christoph Lenzen;Nancy Lynch;Calvin Newport;Tsvetomira Radeva - 通讯作者:
Tsvetomira Radeva
Modeling radio networks
- DOI:
10.1007/s00446-011-0135-7 - 发表时间:
2011-07-06 - 期刊:
- 影响因子:2.100
- 作者:
Calvin Newport;Nancy Lynch - 通讯作者:
Nancy Lynch
On the weakest failure detector ever
- DOI:
10.1007/s00446-009-0079-3 - 发表时间:
2009-01-30 - 期刊:
- 影响因子:2.100
- 作者:
Rachid Guerraoui;Maurice Herlihy;Petr Kuznetsov;Nancy Lynch;Calvin Newport - 通讯作者:
Calvin Newport
Analyzing Security Protocols Using Time-Bounded Task-PIOAs
- DOI:
10.1007/s10626-007-0032-1 - 发表时间:
2008-01-05 - 期刊:
- 影响因子:1.600
- 作者:
Ran Canetti;Ling Cheung;Dilsun Kaynar;Moses Liskov;Nancy Lynch;Olivier Pereira;Roberto Segala - 通讯作者:
Roberto Segala
Some perspectives on PODC
- DOI:
10.1007/s00446-002-0072-6 - 发表时间:
2003-09-01 - 期刊:
- 影响因子:2.100
- 作者:
Nancy Lynch - 通讯作者:
Nancy Lynch
Nancy Lynch的其他文献
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
{{ truncateString('Nancy Lynch', 18)}}的其他基金
AF: Small: An Algorithmic Theory of Brain Behavior: Concept Representation and Learning in Spiking Neural Networks
AF:小:大脑行为的算法理论:尖峰神经网络中的概念表示和学习
- 批准号:
2139936 - 财政年份:2022
- 资助金额:
$ 27.5万 - 项目类别:
Standard Grant
AF: Small: Distributed Algorithms for Dynamic, Noisy Platforms: Wireless Networks, Robot Swarms, and Insect Colonies
AF:小型:适用于动态、嘈杂平台的分布式算法:无线网络、机器人群和昆虫群
- 批准号:
2003830 - 财政年份:2020
- 资助金额:
$ 27.5万 - 项目类别:
Standard Grant
NSF-BSF: AF: Small: An Algorithmic Theory of Brain Networks
NSF-BSF:AF:小:脑网络的算法理论
- 批准号:
1810758 - 财政年份:2018
- 资助金额:
$ 27.5万 - 项目类别:
Standard Grant
AF: Medium: Distributed Algorithms for Resource-Constrained and Dynamic Settings
AF:中:资源受限和动态设置的分布式算法
- 批准号:
1461559 - 财政年份:2015
- 资助金额:
$ 27.5万 - 项目类别:
Continuing Grant
AF: Small: Bounded-Contention Coding for Wireless Networks
AF:小型:无线网络的有界竞争编码
- 批准号:
1217506 - 财政年份:2012
- 资助金额:
$ 27.5万 - 项目类别:
Standard Grant
CCF-AF: Abstract Medium Access Control Layers
CCF-AF:抽象媒体访问控制层
- 批准号:
0937274 - 财政年份:2010
- 资助金额:
$ 27.5万 - 项目类别:
Standard Grant
CPS: Medium: Collaborative Research: Geometric Distributed Algorithms for Multi-Robot Coordination and Control
CPS:中:协作研究:多机器人协调与控制的几何分布式算法
- 批准号:
1035199 - 财政年份:2010
- 资助金额:
$ 27.5万 - 项目类别:
Standard Grant
CSR-EHS: Virtual Node Abstraction Layers for Designing Embedded Systems
CSR-EHS:用于设计嵌入式系统的虚拟节点抽象层
- 批准号:
0715397 - 财政年份:2007
- 资助金额:
$ 27.5万 - 项目类别:
Standard Grant
Extending the Power and Applicability of the Timed Input/Output Automata Framework
扩展定时输入/输出自动机框架的功能和适用性
- 批准号:
0702670 - 财政年份:2007
- 资助金额:
$ 27.5万 - 项目类别:
Standard Grant
CSR--EHS: Collaborative Research: Verification of Probabilistic Hybrid Systems: Stability and Beyond
CSR--EHS:协作研究:概率混合系统的验证:稳定性及其他
- 批准号:
0614414 - 财政年份:2006
- 资助金额:
$ 27.5万 - 项目类别:
Continuing Grant
相似海外基金
Collaborative Research: AF: Medium: Foundations of Oblivious Reconfigurable Networks
合作研究:AF:媒介:遗忘可重构网络的基础
- 批准号:
2402851 - 财政年份:2024
- 资助金额:
$ 27.5万 - 项目类别:
Continuing Grant
Conference: Theory and Foundations of Statistics in the Era of Big Data
会议:大数据时代的统计学理论与基础
- 批准号:
2403813 - 财政年份:2024
- 资助金额:
$ 27.5万 - 项目类别:
Standard Grant
Social Foundations of Cryptography
密码学的社会基础
- 批准号:
EP/X017524/1 - 财政年份:2024
- 资助金额:
$ 27.5万 - 项目类别:
Research Grant
Mathematical Foundations of Intelligence: An "Erlangen Programme" for AI
智能的数学基础:人工智能的“埃尔兰根计划”
- 批准号:
EP/Y028872/1 - 财政年份:2024
- 资助金额:
$ 27.5万 - 项目类别:
Research Grant
SAFER - Secure Foundations: Verified Systems Software Above Full-Scale Integrated Semantics
SAFER - 安全基础:高于全面集成语义的经过验证的系统软件
- 批准号:
EP/Y035976/1 - 财政年份:2024
- 资助金额:
$ 27.5万 - 项目类别:
Research Grant
Statistical Foundations for Detecting Anomalous Structure in Stream Settings (DASS)
检测流设置中的异常结构的统计基础 (DASS)
- 批准号:
EP/Z531327/1 - 财政年份:2024
- 资助金额:
$ 27.5万 - 项目类别:
Research Grant
Social foundations of cryptography
密码学的社会基础
- 批准号:
EP/X016226/1 - 财政年份:2024
- 资助金额:
$ 27.5万 - 项目类别:
Research Grant
Foundations of Classical and Quantum Verifiable Computing
经典和量子可验证计算的基础
- 批准号:
MR/X023583/1 - 财政年份:2024
- 资助金额:
$ 27.5万 - 项目类别:
Fellowship
CAREER: Statistical foundations of particle tracking and trajectory inference
职业:粒子跟踪和轨迹推断的统计基础
- 批准号:
2339829 - 财政年份:2024
- 资助金额:
$ 27.5万 - 项目类别:
Continuing Grant
CAREER: Architectural Foundations for Practical Privacy-Preserving Computation
职业:实用隐私保护计算的架构基础
- 批准号:
2340137 - 财政年份:2024
- 资助金额:
$ 27.5万 - 项目类别:
Continuing Grant