• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>IEEE Transactions on Parallel and Distributed Systems >Analysis of Minimum Interaction Time for Continuous Distributed Interactive Computing
【24h】

Analysis of Minimum Interaction Time for Continuous Distributed Interactive Computing

机译：连续分布式交互式计算的最小交互时间分析

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Distributed interactive computing allows participants at different locations to interact with each other in real time. In this paper, we study the interaction times of continuous Distributed Interactive Applications (DIAs) in which the application states change due to not only user-initiated operations but also time passing. Given the clients and servers of a continuous DIA, its interaction time is directly affected by how the clients are assigned to the servers as well as the simulation time settings of the servers. We formulate the Minimum Interaction Time (MIT) problem as a combinatorial problem of these two tuning knobs and prove that it is NP-hard. We then approximate the problem by fixing the client assignment or the simulation time offsets among the servers. When the client assignment is fixed, we show that finding the minimum achievable interaction time can be reduced to a weighted bipartite matching problem. We further show that this approach establishes a tight approximation factor of 3 to the MIT problem if each client is assigned to its nearest server. When the simulation time offsets among the servers are fixed, we show that finding the minimum achievable interaction time is still NP-hard. This approach can approximate the MIT problem by a factor within 2 if the simulation times of all servers are synchronized. A mix of the above two approaches better approximates the MIT problem within a factor of 5/3. We further conduct experimental evaluation of these approaches with three real Internet latency datasets.
机译：分布式交互式计算使位于不同位置的参与者可以实时进行交互。在本文中，我们研究了连续分布式交互式应用程序（DIA）的交互时间，其中应用程序状态不仅由于用户启动的操作而且随着时间的流逝而发生变化。对于连续DIA的客户端和服务器，其交互时间直接受客户端分配给服务器的方式以及服务器的模拟时间设置的影响。我们将最小交互作用时间（MIT）问题公式化为这两个调整旋钮的组合问题，并证明它是NP难的。然后，我们通过固定客户端分配或服务器之间的模拟时间偏移来近似问题。当客户分配固定时，我们表明寻找最小可实现的交互时间可以减少为加权二分匹配问题。我们进一步证明，如果将每个客户端分配给其最近的服务器，则该方法将为MIT问题建立3的近似值。当服务器之间的仿真时间偏移固定时，我们表明找到最小的可实现交互时间仍然是NP-hard。如果所有服务器的仿真时间都已同步，则此方法可以将MIT问题近似2倍。上面两种方法的混合可以更好地将MIT问题近似在5/3的范围内。我们使用三个真实的Internet延迟数据集进一步对这些方法进行了实验评估。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号