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

On the round complexity of Byzantine agreement without initial set-up

INFORMATION AND COMPUTATION 2009年第12期207卷 1351-1368页

作者： Okun, Michael Hebrew Univ Jerusalem Dept Comp Sci IL-91904 Jerusalem Israel

It is well known that in order to (deterministically) achieve Byzantine agreement (consensus) among n processors in a fully connected network in which f processors may be faulty, where f satisfies f < n/3, exactly f + 1 communication rounds are required. This result was proved under the assumption that the network topology is known a priori to each processor, i.e., the identifiers of the processors and of the links between processors are known. This paper deals with the Byzantine agreement problem when such initial setup is not available. It is shown that f + 1 rounds are Sufficient to reach agreement if the faulty processors are not able to identify themselves with names of the correct processors, and that this upper bound no longer holds when Such identity theft is possible. (C) 2009 Elsevier Inc. All rights reserved.

关键词： Byzantine agreement Consensus fault-tolerant distributed computing

来源：评论

学校读者我要写书评

暂无评论

PARTITIONED ENCRYPTION AND ACHIEVING SIMULTANEITY BY PARTITIONING

引用

INFORMATION PROCESSING LETTERS 1987年第2期26卷 81-88页

作者： GALIL, Z YUNG, M TEL AVIV UNIV DEPT COMP SCIIL-69978 TEL AVIVISRAEL

The authors present a method called Partitioned Encryption whose main property is its simplicity. It is an extension of Probabilistic Public-Key Encryption, which can be used in designing cryptographic protocols and can be applied to distributed problem solving. They give a modification of Secret Sharing called Partitioned Secret Sharing. They demonstrate the power of Partitioned Encryption: combining it with the partitioning of the user set gives a solution scheme for "Verifiable Secret Sharing" and "Simultaneous Broadcast in the Presence of faults, which are important primitives of fault-tolerant distributed computing introduced by Chor, Goldwasser, Micali and Awerbuch (1985). The scheme is fully polynomial, simple, and efficient in terms of communication rounds.

关键词： Cryptography fault-tolerant distributed computing probabilistic encryption partitioned encryption cryptographic protocol zero-knowledge interactive proof-system verifiable secret-sharing simultaneous broadcast

来源：评论

学校读者我要写书评

暂无评论

Geometric and combinatorial views on asynchronous computability

引用

distributed computing 2018年第4期31卷 289-316页

作者： Goubault, Eric Mimram, Samuel Tasson, Christine Univ Paris Saclay CNRS Ecole Polytech LIX F-91128 Palaiseau France Univ Paris Diderot Univ Sorbonne Paris Cite CNRS IRIF Paris France

We show that the protocol complex formalization of fault-tolerant protocols can be directly derived from a suitable semantics of the underlying synchronization and communication primitives, based on a geometrization of the state space. By constructing a one-to-one relationship between simplices of the protocol complex and (di)homotopy classes of (di)paths in the latter semantics, we describe a connection between these two geometric approaches to distributed computing: protocol complexes and directed algebraic topology. This is exemplified on atomic snapshot, iterated snapshot and layered immediate snapshot protocols, where a well-known combinatorial structure, interval orders, plays a key role. We believe that this correspondence between models will extend to proving impossibility results for much more intricate fault-tolerant distributed architectures.

关键词： fault-tolerant distributed computing Atomic snapshot protocol Protocol complex Directed algebraic topology Dihomotopy Interval order

来源：评论

学校读者我要写书评

暂无评论

Communication-efficient leader election in crash-recovery systems

引用

JOURNAL OF SYSTEMS AND SOFTWARE 2011年第12期84卷 2186-2195页

作者： Larrea, Mikel Martin, Cristian Soraluze, Iratxe Univ Basque Country UPV EHU San Sebastian 20018 Spain

This work addresses the leader election problem in partially synchronous distributed systems where processes can crash and recover. More precisely, it focuses on implementing the Omega failure detector class, which provides a leader election functionality, in the crash-recovery failure model. The concepts of communication efficiency and near-efficiency for an algorithm implementing Omega are defined. Depending on the use or not of stable storage, the property satisfied by unstable processes, i.e., those that crash and recover infinitely often, varies. Two algorithms implementing Omega are presented. In the first algorithm, which is communication-efficient and uses stable storage, eventually and permanently unstable processes agree on the leader with correct processes. In the second algorithm, which is near-communication-efficient and does not use stable storage, processes start their execution with no leader in order to avoid the disagreement among unstable processes, that will agree on the leader with correct processes after receiving a first message from the leader. (C) 2011 Elsevier Inc. All rights reserved.

关键词： fault-tolerant distributed computing Consensus Omega failure detector Leader election Crash-recovery Communication-efficient algorithm

来源：评论

学校读者我要写书评

暂无评论

fault Injection Framework for Organic computing Architecture

Fault Injection Framework for Organic Computing Architecture

引用

Intelligent Systems Conference (IntelliSys)

作者： Nahar, Sabikun Meckel, Simon Obermaisser, Roman Univ Siegen Siegen Germany

ISBN: (纸本)9783031477232;9783031477249

In the future, autonomous systems such as self-driving cars must robustly and flexibly handle various fault situations. Static models of faults and countermeasures are standard in classical approaches;however, such static models are no longer efficient as the complexity of fault scenarios tremendously increased. The bio-inspired concept of organic computing applies biological concepts to technical systems. Organic computing utilizes an artificial hormone system as a decentralized mechanism, i.e., a middleware that continuously monitors and organizes task allocations to computing nodes in distributed real-time embedded systems. By introducing different types of artificial hormones for the tasks, task allocations are realized by constantly establishing hormone balances via distributed closed control loops. This process handles the increasing complexity of e.g., distributed control systems by enabling self-configuration, -adaptation, improvement and -healing. Such an organic computing environment inherently overcomes system-level faults, such as computation node failures, since missing (i.e., non-executed) tasks directly lead to hormone imbalances that are compensated for, thereby restoring these tasks. However, faults in the artificial hormone system, e.g., due to incorrect hormone values, are currently not covered by the organic computing environment and can result in adverse and critical system behavior and even complete system failure. To address these types of faults and thus improve the capabilities and safety of current organic computing systems, this paper presents a fault injection framework to analyze the effects of an extended range of fault cases, including faults in the artificial hormone system. Such analyses are important as they mark the foundation for future fault-handling strategies and safety features in next-generation organic computing systems for autonomous systems. The statistical analyses and results based on the fault injection framework reveal

关键词： fault-tolerant distributed computing Organic computing Artificial hormone system Hormone fault model fault injection framework

来源：评论

学校读者我要写书评

暂无评论

Adaptively Secure Broadcast, Revisited 11

Adaptively Secure Broadcast, Revisited

引用

30th Annual ACM SIGACT-SIGOPS Symposium on Principles of distributed computing (PODC)

作者： Garay, Juan A. Katz, Jonathan Kumaresan, Ranjit Zhou, Hong-Sheng AT&T Labs - Research New Jersey USA University of Maryland College Park USA

ISBN: (纸本)9781450307192

We consider the classical problem of synchronous broadcast with dishonest majority, when a public-key infrastructure and digital signatures are available. In a surprising result, Hirt and Zikas (Eurocrypt 2010) recently observed that all existing protocols for this task are insecure against an adaptive adversary who can choose which parties to corrupt as the protocol progresses. Moreover, they prove an impossibility result for adaptively secure broadcast in their setting. We argue that the communication model adopted by Hirt and Zikas is unrealistically pessimistic. We revisit the problem of adaptively secure broadcast in a more natural synchronous model (with rushing), and show that broadcast is possible in this setting for an arbitrary number of corruptions. Our positive result holds under a strong, simulation-based definition in the universal-composability framework. We also study the impact of adaptive attacks on protocols for secure multi-party computation where broadcast is used as a sub-routine.

关键词： Broadcast fault-tolerant distributed computing adaptive security cryptographic protocols

来源：评论

学校读者我要写书评

暂无评论

Robust TCP connections for fault tolerant computing 9

Robust TCP connections for fault tolerant computing

引用

International Conference on Parallel and distributed Systems (ICPADS 2002)

作者： Ekwall, R Urbán, P Schiper, A Ecole Polytech Fed Lausanne Sch Comp & Commun Sci Distributed Syst Lab CH-1015 Lausanne Switzerland

ISBN: (纸本)0769517609

When processes on two different machines communicate, they most often do so using the TCP protocol. While TCP is appropriate for a wide range of applications, it has shortcomings in other application areas. One of these areas is fault tolerant distributed computing. For some of those applications, TCP does not address link failures adequately: TCP breaks the connection if connectivity is lost for some duration (typically minutes). This is sometimes undesirable. The paper proposes robust TCP connections, a solution to the problem of broken TCP connections. The paper presents a session layer protocol on top of TCP that ensures reconnection, and provides exactly-once delivery for all transmitted data. A prototype has been implemented as a Java library. The prototype has less than 10% overhead on TCP sockets with respect to the most important performance figures.

关键词： session layer protocol TCP performance fault-tolerant distributed computing quasi-reliable channels java

来源：评论

学校读者我要写书评

暂无评论

Foreword to WASA Workshop 14

Foreword to WASA Workshop

引用

4th International Conference on Web Intelligence, Mining and Semantics(WIMS)

作者： Badica, Costin Ganzha, Maria Ivanovic, Mirjana Paprzycki, Marcin Univ Craiova Comp & Informat Technol Dept Craiova Romania Univ Gdansk Inst Informat Gdansk Poland Univ Novi Sad Fac Sci Dept Math & Informat Novi Sad 21000 Serbia Polish Acad Sci Syst Res Inst Warsaw Poland

This foreword paper introduces the 4th Workshop on Applications of Software Agents - WASA'2014 and outlines its contributions. The workshop was held as part of the 4th International Conference on Web Intelligence,... 详细信息

ISBN: (纸本)9781450325387

关键词： mobile computing vehicular network disaster management agent oriented programming fault-tolerant distributed computing sentic computing organisational network Web technologies

来源：评论

学校读者我要写书评

暂无评论

Noisy beeping networks

引用

INFORMATION AND COMPUTATION 2022年第PartA期289卷

作者： Ashkenazi, Yagel Gelles, Ran Leshem, Amir Bar Ilan Univ Fac Engn Ramat Gan Israel

Beeping networks consist of exceedingly simple computational devices whose communication is based on beeps and silence. In this work, we introduce noisy beeping networks, where the observed communication is noisy with some fixed probability of error. We show how to transform any algorithm over a noiseless beeping network into a noise-resilient version while incurring a multiplicative overhead of essentially O (log n) in its round complexity, with high probability. Our coding is optimal for some (short) tasks, such as the node-coloring of cliques. Interestingly, in the case of coloring, our technique achieves the same complexity as the standard beeping model while being noise resilient. We further show how to simulate a large family of algorithms designed for distributed networks in the CONGEST(B) model over a noisy beeping network, with a multiplicative overhead of O (B center dot A center dot min(n, A2)) in the round complexity, where A is the maximum degree of the network. (c) 2022 Elsevier Inc. All rights reserved.

关键词： fault-tolerant distributed computing Beeping networks Computation with noise

来源：评论

学校读者我要写书评

暂无评论

PROOFS THAT YIELD NOTHING BUT THEIR VALIDITY OR ALL LANGUAGES IN NP HAVE ZERO-KNOWLEDGE PROOF SYSTEMS

引用

JOURNAL OF THE ACM 1991年第3期38卷 691-729页

作者： GOLDREICH, O MICALI, S WIGDERSON, A MIT COMP SCI LAB CAMBRIDGE MA 02139 USA HEBREW UNIV JERUSALEM INST MATH & COMP SCI JERUSALEM ISRAEL

In this paper the generality and wide applicability of zero-knowledge proofs, a notion introduced by Goldwasser, Micali, and Rackoff is demonstrated. These are probabilistic and interactive proofs that, for the members of a language, efficiently demonstrate membership in the language without conveying any additional knowledge. All previously known zero-knowledge proofs were only for number-theoretic languages in NP and CoNP. Under the assumption that secure encryption functions exist or by using "physical means for hiding information," it is shown that all languages in NP have zero-knowledge proofs. Loosely speaking, it is possible to demonstrate that a CNF formula is satisfiable without revealing any other property of the formula, in particular, without yielding neither a satisfying assignment nor properties such as whether there is a satisfying assignment in which x1 = x3 etc. It is also demonstrated that zero-knowledge proofs exist "outside the domain of cryptography and number theory." Using no assumptions, it is shown that both graph isomorphism and graph nonisomorphism have zero-knowledge interactive proofs. The mere existence of an interactive proof for graph nonisomorphism is interesting, since graph nonisomorphism is not known to be in NP and hence no efficient proofs were known before for demonstrating that two graphs are not isomorphic.

关键词： CRYPTOGRAPHIC PROTOCOLS fault-tolerant distributed computing GRAPH ISOMORPHISM INTERACTIVE PROOFS METHODOLOGICAL DESIGN OF PROTOCOLS NP ONE-WAY FUNCTIONS PROOF SYSTEMS ZERO-KNOWLEDGE

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：