From clarity to efficiency for distributed algorithms
From clarity to efficiency for distributed algorithms
复制标题
分布式算法从清晰到高效
DOI：
10.1145/2384616.2384645
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
Michael Gorbovitski
中科院分区：
文献类型：
--
作者：
Yanhong A. Liu;S. Stoller;Bo Lin;Michael Gorbovitski
本文描述了一种非常高级的语言，用于清晰地描述分布式算法和生成高效实现所需的优化。该语言支持高级控制流，其中复杂的同步条件可以使用消息历史序列上的高级查询（特别是逻辑量化）来表示。不幸的是，如果直接执行，这些程序将非常低效，包括消耗无限内存。
This paper describes a very high-level language for clear description of distributed algorithms and optimizations necessary for generating efficient implementations. The language supports high-level control flows where complex synchronization conditions can be expressed using high-level queries, especially logic quantifications, over message history sequences. Unfortunately, the programs would be extremely inefficient, including consuming unbounded memory, if executed straightforwardly.
We present new optimizations that automatically transform complex synchronization conditions into incremental updates of necessary auxiliary values as messages are sent and received. The core of the optimizations is the first general method for efficient implementation of logic quantifications. We have developed an operational semantics of the language, implemented a prototype of the compiler and the optimizations, and successfully used the language and implementation on a variety of important distributed algorithms.