检索结果-内蒙古大学图书馆

distributed computing in the asynchronous LOCAL model

THEORETICAL COMPUTER SCIENCE 2025年 1025卷

作者： Delporte-Gallet, Carole Fauconnier, Hugues Fraigniaud, Pierre Rabie, Mikael Univ Paris Cite Inst Rech Informat Fondamentale Paris France CNRS Paris France

The LOCAL model is among the main models for studying locality in the framework of distributed network computing. This model is however subject to pertinent criticisms, including the facts that all nodes wake up simultaneously, perform in lock steps, and are failure-free. We show that relaxing these hypotheses to some extent does not hurt local computing. In particular, we show that, for any task T associated to a locally checkable labeling (lcl), if T is solvable in t rounds by a deterministic algorithm in the LOCAL model, then T remains solvable by a deterministic algorithm in O(t) rounds in an asynchronous variant of the LOCAL model whenever t = O(polylog n). This improves the result by Casta & ntilde;eda et al. [TCS, 2019], which was restricted to 3-coloring the rings. More generally, the main contribution of this paper is to show that, perhaps surprisingly, asynchrony and failures in the computations do not restrict the power of the LOCAL model, as long as the communications remain synchronous and failure-free. To this end, this paper introduces a new distributed renaming technique to provide nodes with consistent identifiers.

关键词： distributed network computing Locality Asynchrony Fault-tolerance

来源：评论

学校读者我要写书评

暂无评论

Certification of Compact Low-Stretch Routing Schemes

引用

COMPUTER JOURNAL 2019年第5期62卷 730-746页

作者： Balliu, Alkida Fraigniaud, Pierre Aalto Univ Dept Comp Sci Konemiehentie 2 Espoo 02150 Finland Univ Paris Diderot CNRS IRIF Batiment Sophie Germain8 Pl Aurelie Nemours F-75013 Paris France

On the one hand, the correctness of routing protocols in networks is an issue of utmost importance for guaranteeing the delivery of messages from any source to any target. On the other hand, a large collection of routing schemes have been proposed during the last two decades, with the objective of transmitting messages along short routes, while keeping the routing tables small. Regrettably, all these schemes share the property that an adversary may modify the content of the routing tables with the objective of, e.g. blocking the delivery of messages between some pairs of nodes, without being detected by any node. In this paper, we present a simple certification mechanism which enables the nodes to locally detect any alteration of their routing tables. In particular, we show how to locally verify the stretch-3 routing scheme by Thorup and Zwick, presented in SPAA in 2001, by adding certificates of the same order of magnitude as the original routing tables. We also propose a new name-independent routing scheme using routing tables of size (O) over tilde (root n) bits at each node in n-node networks. This new routing scheme can be locally verified using certificates of (O) over tilde (root n) bits. Its stretch is 3 if using handshaking, and 5 otherwise.

关键词： distributed network computing distributed decision distributed verification distributed data structures

来源：评论

学校读者我要写书评

暂无评论

Local certification in distributed computing: error-sensitivity, uniformity, redundancy, and interactivity

Local certification in distributed computing: error-sensitiv...

引用

作者： Laurent Feuilloley Universite Sorbonne Paris Cite

学位级别：博士

This dissertation is about local certification, a central topic in distributed decision, a subfield of distributed computing. The distributed decision mechanism consists, for the nodes of a network, in deciding in a distributed manner whether the network is in a proper configuration or not, with respect to some fixed predicate. This decision is said to be local because the nodes of the network can communicate only with their neighbours. After communication, every node outputs a decision, stating whether the network is locally correct, that is, correct given the partial information gathered so far by this node. The network is declared to be globally correct, if and only if, it is declared to be locally correct by every node. Most predicates cannot be verified by this type of computation, due to the loc- ality constraint. Local certification is a mechanism that enables to circumvent this difficulty, and to check any property. It consists in providing the nodes of the network with labels, called certificates, that can be verified locally by a distributed algorithm. A local certification scheme is correct if only the networks that satisfy the predicate can be certified. In addition to its theoretical appeal, as a form of distributed non- determinism, the concept of local certification is especially relevant in the study of fault-tolerant distributed algorithms, where a key step consists in checking the status of the network, based on information stored at the nodes. This dissertation deals with four aspects of local certification: error-sensitivity, uniformity, redundancy, and interactivity. The study of these four topics is motivated by the same essential question: How to reduce the resources needed for certification, and/or ensure a better fault-tolerance? In order to tackle this question we have to understand fundamental properties of certification. In particular, in this dissertation we answer questions such as: How redundant the certificates need to be for a proper

关键词： distributed network computing distributed decision local certification proof-labelling scheme fault-tolerance

来源：评论

学校读者我要写书评

暂无评论

What Can Be Verified Locally? 34

What Can Be Verified Locally?

引用

34th Symposium on Theoretical Aspects of Computer Science (STACS)

作者： Balliu, Alkida D'Angelo, Gianlorenzo Fraigniaud, Pierre Olivetti, Dennis CNRS IRIF Paris France Univ Paris Diderot Paris France GSSI Laquila Italy

ISBN: (纸本)9783959770286

We are considering distributed network computing, in which computing entities are connected by a network modeled as a connected graph. These entities are located at the nodes of the graph, and they exchange information by message-passing along its edges. In this context, we are adopting the classical framework for local distributed decision, in which nodes must collectively decide whether their network configuration satisfies some given boolean predicate, by having each node interacting with the nodes in its vicinity only. A network configuration is accepted if and only if every node individually accepts. It is folklore that not every Turing-decidable network property (e.g., whether the network is planar) can be decided locally whenever the computing entities are Turing machines (TM). On the other hand, it is known that every Turing-decidable network property can be decided locally if nodes are running non-deterministic Turing machines (NTM). However, this holds only if the nodes have the ability to guess the identities of the nodes currently in the network. That is, for different sets of identities assigned to the nodes, the correct guesses of the nodes might be different. If one asks the nodes to use the same guess in the same network configuration even with different identity assignments, i.e., to perform identity-oblivious guesses, then it is known that not every Turing-decidable network property can be decided locally. In this paper, we show that every Turing-decidable network property can be decided. locally if nodes are running alternating Turing machines (ATM), and this holds even if nodes are bounded to perform identity-oblivious guesses. More specifically, we show that, for every network property, there is a local algorithm for ATMs, with at most 2 alternations, that decides that property. To this aim, we define a hierarchy of classes of decision tasks where the lowest level contains tasks solvable with This, the first level those solvable with NTMs, and l

关键词： distributed network computing distributed Algorithm distributed Decision Locality

来源：评论

学校读者我要写书评

暂无评论

Local Conflict Coloring 57

Local Conflict Coloring

引用

57th IEEE Annual Symposium on Foundations of Computer Science (FOCS)

作者： Fraigniaud, Pierre Heinrich, Marc Kosowski, Adrian CNRS F-75700 Paris France Paris Diderot Univ Paris France Inria Paris GANG Project Paris France

ISBN: (纸本)9781509039333

Locally finding a solution to symmetry-breaking tasks such as vertex-coloring, edge-coloring, maximal matching, maximal independent set, etc., is a long-standing challenge in distributed network computing. More recently, it has also become a challenge in the framework of centralized local computation. We introduce conflict coloring as a general symmetry-breaking task that includes all the aforementioned tasks as specific instantiations - conflict coloring includes all locally checkable labeling tasks from [Naor & Stockmeyer, STOC 1993]. Conflict coloring is characterized by two parameters l and d, where the former measures the amount of freedom given to the nodes for selecting their colors, and the latter measures the number of constraints which colors of adjacent nodes are subject to. We show that, in the standard LOCAL model for distributed network computing, if l/d > Delta, then conflict coloring can be solved in (O) over tilde(root Delta) + log* n rounds in n-node graphs with maximum degree Delta, where (O) over tilde ignores the polylog factors in Delta. The dependency in n is optimal, as a consequence of the Omega(log* n) lower bound by [Linial, SIAM J. Comp. 1992] for (Delta + 1)-coloring. An important special case of our result is a significant improvement over the best known algorithm for distributed (Delta + 1)-coloring due to [Barenboim, PODC 2015], which required (O) over tilde (Delta(3/4)) + log* n rounds. Improvements for other variants of coloring, including (Delta + 1)-list-coloring, (2 Delta - 1)-edge-coloring, coloring with forbidden color distances, etc., also follow from our general result on conflict coloring. Likewise, in the framework of centralized local computation algorithms (LCAs), our general result yields an LCA which requires a smaller number of probes than the previously best known algorithm for vertex-coloring, and works for a wide range of coloring problems.

关键词： distributed network computing Symmetry Breaking List-coloring (Delta+1)-coloring Local Computation Algorithm

来源：评论

学校读者我要写书评

暂无评论

P2P Grid Technology for Virtual Classrooms and Laboratories

P2P Grid Technology for Virtual Classrooms and Laboratories

引用

16th Communications and networking Symposium (CNS 2013) / Spring Simulation Multi-Conference (SpringSim '13)

作者： Rajaei, Hassan Hakami, Nada Bowling Green State Univ Dept Comp Sci Bowling Green OH 43403 USA

ISBN: (纸本)9781627480314

computing technologies can play important role in Virtual Classrooms and Laboratories (VCL) and e-learning settings. In these systems, the underlying computing platforms enable large number of students across the globe to collaborate and interact with each other as well as with the learning components. A typical VCL can be setup based on a traditional or Peer-to-Pear (P2P) Grid computing. While several VCLs are currently using the traditional Grid, few have been reported utilizing P2P Grid. The latter provides with an alternative computing system, which mainly targets the scalability of the system and often with improved flexibility and interactions. We studied whether P2P Grid could provide an improved platform over its counterpart. We inspected large number of systems, examples of which are presented in this paper. We scrutinized their features, capabilities, and performance. Our investigation indicates that P2P Grid exhibits a superior behavior over its traditional counterpart for VCL setting. This is especially true for courses such as Parallel computing, Simulation, and networking since P2P Grid offers accessing to larger scale computational and data resources as well as much improved collaborative environment in heterogeneous and distributed communities.

关键词： Grid computing Cloud computing P2P Grid distributed network computing Virtual Classrooms

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：