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

19th International Conference on Security and Privacy in communication Networks

作者： Lyu, Hanzheng Xie, Shaokang Niu, Jianyu Feng, Chen Univ British Columbia Okanagan Campus Kelowna BC Canada Southern Univ Sci & Technol Shenzhen Peoples R China SUSTech Res Inst Trustworthy Autonomous Syst Shenzhen Peoples R China

ISBN: (纸本)9783031649479;9783031649486

Byzantine agreement protocols are essential components in distributed systems and hold significant relevance for blockchain networks. However, the communication complexity of these protocols remains a major obstacle when considering their application in large-scale blockchain systems. Recently, several elegant Byzantine protocols in the synchronous authenticated setting have been proposed to enjoy expected constant round complexity or optimal good-case latency. However, their overall communication complexity is still Omega(n(2)l) bits for an l-bit message to be agreed by a set of n replicas. This quadratic communication complexity makes them unsuitable for large-scale applications. In this paper, we systematically aim to reduce the communication complexity of these protocols. In particular, we show how these protocols can be extended to have a complexity of O(nl + n(2)kappa) bits, where. is determined by the security parameter lambda. This communication complexity is optimal when l reaches Omega(kappa n).

关键词： Blockchain Byzantine agreement State machine replication communication complexity Round complexity

来源：评论

学校读者我要写书评

暂无评论

Randomized Lifting to Semi-Structured communication complexity via Linear Diversity 16

Randomized Lifting to Semi-Structured Communication Complexi...

引用

16th Innovations in Theoretical Computer Science Conference, ITCS 2025

作者： Podolskii, Vladimir Shekhovtsov, Alexander Tufts University MedfordMA United States Moscow Institute of Physics and Technology Russia

ISBN: (纸本)9783959773614

We study query-to-communication lifting. The major open problem in this area is to prove a lifting theorem for gadgets of constant size. The recent paper [2] introduces semi-structured communication complexity, in which one of the players can only send parities of their input bits. They have shown that for any m ≥ 4 deterministic decision tree complexity of a function f can be lifted to the so called semi-structured communication complexity of f ◦ Indm, where Indm is the Indexing gadget. As our main contribution we extend these results to randomized setting. Our results also apply to a substantially larger set of gadgets. More specifically, we introduce a new complexity measure of gadgets, linear diversity. For all gadgets g with non-trivial linear diversity we show that randomized decision tree complexity of f lifts to randomized semi-structured communication complexity of f ◦ g. In particular, this gives tight lifting results for Indexing gadget Indm, Inner Product gadget IPm for all m ≥ 2, and for Majority gadget MAJm for all m ≥ 4. We prove the same results for deterministic case. From our result it immediately follows that deterministic/randomized decision tree complexity lifts to deterministic/randomized parity decision tree complexity. For randomized case this is the first result of this type. For deterministic case, our result improves the bound in [6] for Inner Product gadget. To obtain our results we introduce a new secret sets approach to simulation of semi-structured communication protocols by decision trees. It allows us to simulate (restricted classes of) communication protocols on truly uniform distribution of inputs. © Vladimir Podolskii and Alexander Shekhovtsov.

关键词： communication complexity decision trees lifting

来源：评论

学校读者我要写书评

暂无评论

communication complexity method for measuring nondeterminism in finite automata

引用

INFORMATION AND COMPUTATION 2002年第2期172卷 202-217页

作者： Hromkovic, J Seibert, S Karhumäki, J Klauck, H Schnitger, G Rhein Westfal TH Aachen Lehrstuhl Informat 1 D-52074 Aachen Germany Univ Turku Dept Math SF-20500 Turku Finland Univ Frankfurt FB Informat D-60054 Frankfurt Germany

While deterministic finite automata seem to be well understood, surprisingly many important problems concerning nondeterministic finite automata (nfa's) remain open, One such problem area is the study of different measures of nondeterminism in finite automata and the estimation of the sizes of minimal nondeterministic finite automata. In this paper the concept of communication complexity is applied in order to achieve progress in this problem area. The main results are as follows: 1. Deterministic communication complexity provides lower bounds on the size of nfa's with bounded unambiguity. Applying this fact, the proofs of several results about nfa's with limited ambiguity can be simplified and presented in a uniform way. 2. There is a family of languages KONk2 with an exponential size gap between nfa's with polynomial leaf number/ambiguity and nfa's with ambiguity k. This partially provides an answer to the open problem posed by B. Ravikumar and O. Ibarra (1989, SIAM J. Comput. 18, 1263-1282) and H. Leung (1998, SIAM J. Comput. 27, 1073-1082). (C) 2002 Elsevier Science (USA).

关键词： finite automata nondeterminism limited ambiguity descriptional complexity communication complexity

来源：评论

学校读者我要写书评

暂无评论

communication complexity OF COMPUTING THE HAMMING DISTANCE: 收藏
分享
引用; SIAM JOURNAL ON COMPUTING 1986年第4期15卷 932-947页; 作者： PANG, KF ELGAMAL, A Stanford Univ Stanford CA USA Stanford Univ Stanford CA USA; Let x,y∈{0,<span class="mn" id="MathJax-Spa; Let $x, y \in {0, 1}^{n}$; 来源：评论; 学校读者我要写书评

暂无评论

communication complexity of simultaneous messages

引用

SIAM JOURNAL ON COMPUTING 2003年第1期33卷 137-166页

作者： Babai, L Gál, A Kimmel, PG Lokam, SV Univ Chicago Dept Comp Sci Chicago IL 60637 USA Univ Texas Dept Comp Sci Austin TX 78712 USA NE Illinois Univ Dept Comp Sci Chicago IL 60625 USA Univ Michigan Dept Elect Engn & Comp Sci Ann Arbor MI 48109 USA Inst Adv Study Sch Math Princeton NJ 08540 USA

In the multiparty communication game (CFL game) of Chandra, Furst, and Lipton [Proceedings of the 15th Annual ACM Symposium on Theory of Computing, Boston, MA, 1983, pp. 94-99] k players collaboratively evaluate a function f(x(0),...,x(k-1)) in which player i knows all inputs except x(i). The players have unlimited computational power. The objective is to minimize communication. In this paper, we study the Simultaneous Messages (SM) model of multiparty communication complexity. The SM model is a restricted version of the CFL game in which the players are not allowed to communicate with each other. Instead, each of the k players simultaneously sends a message to a referee, who sees none of the inputs. The referee then announces the function value. We prove lower and upper bounds on the SM complexity of several classes of explicit functions. Our lower bounds extend to randomized SM complexity via an entropy argument. A lemma establishing a tradeoff between average Hamming distance and range size for transformations of the Boolean cube might be of independent interest. Our lower bounds on SM complexity imply an exponential gap between the SM model and the CFL model for up to (log n)(1-epsilon) players for any epsilon > 0. This separation is obtained by comparing the respective complexities of the Generalized Addressing Function, GAF(G,k), where G is a group of order n. We also combine our lower bounds on SM complexity with the ideas of Hastad and Goldmann [Comput. complexity, 1 (1991), pp. 113-129] to derive superpolynomial lower bounds for certain depth-2 circuits computing a function related to the GAF function. We prove some counterintuitive upper bounds on SM complexity. We show that GAF(Zt 2,3) has SM complexity O(n(0.92)). When the number of players is at least c log n, for some constant c > 0, our SM protocol for GAF(Zt2,k) has polylog(n) complexity. We also examine a class of functions defined by certain depth-2 circuits. This class includes the Generalized Inn

关键词： communication complexity circuit complexity lower bounds group theory

来源：评论

学校读者我要写书评

暂无评论

communication complexity meets cellular automata: Necessary conditions for intrinsic universality

引用

NATURAL COMPUTING 2021年第2期20卷 307-320页

作者： Briceno, Raimundo Rapaport, Ivan Pontificia Univ Catolica Chile Fac Matemat Santiago Chile Univ Chile Dept Ingn Matemat Santiago Chile Univ Chile Ctr Modelamiento Matemat UMI 2807 CNRS Santiago Chile

A natural way to interpret a cellular automaton (CA) is as a mechanism that computes, in a distributed way, some function f. In other words, from a computer science point of view, CAs can be seen as distributed systems where the cells of the CAs are nodes of a network linked by communication channels. A classic measure of efficiency in such distributed systems is the number of bits exchanged during the computation process. A typical approach is to look for bottlenecks: channels through which the nature of the function f forces the exchange of a significant number of bits. In practice, a widely used way to understand such congestion phenomena is to partition the system into two subsystems and try to find bounds for the number of bits that must pass through the channels that join them. Finding these bounds is the focus of communication complexity theory. Measuring the communication complexity of some problems induced by a CA phi turned out to be tremendously useful to give clues regarding the intrinsic universality of phi (a CA is said to be intrinsically universal if it is capable of emulating any other). In fact, there exist particular problems P's for which the following key property holds: if phi is intrinsically universal, then the communication complexity of P(phi) must be maximal. In this tutorial, we intend to explain the connections that were found, through a series of papers, between intrinsic universality and communication complexity in CAs.

关键词： Cellular automata communication complexity Intrinsic universality

来源：评论

学校读者我要写书评

暂无评论

communication complexity in number-conserving and monotone cellular automata

引用

THEORETICAL COMPUTER SCIENCE 2011年第29期412卷 3616-3628页

作者： Goles, E. Moreira, A. Rapaport, I. Univ Tecn Federico Santa Maria Dept Informat Valparaiso Chile Univ Tecn Federico Santa Maria Ctr Tecnol Valparaiso CCTVal Valparaiso Chile Univ Adolfo Ibanez Santiago Chile Inst Complex Syst ISCV Valparaiso Chile Univ Chile CNRS CMM DIMUMI 2807 Santiago Chile

One third of the elementary cellular automata (CAs) are either number-conserving (NCCAs) or monotone (increasing or decreasing). In this paper we prove that, for all of them, we can find linear or constant communication protocols for the prediction problem. In other words, we are able to give a succinct description for their dynamics. This is not necessarily true for general NCCAs. In fact, we also show how to explicitly construct, from any CA, a new NCCA which preserves the original communication complexity. (C) 2011 Elsevier B.V. All rights reserved.

关键词： Cellular automata communication complexity Elementary cellular automata Number-conserving

来源：评论

学校读者我要写书评

暂无评论

communication complexity OF MULTI-PROCESSOR SYSTEMS

引用

INFORMATION PROCESSING LETTERS 1989年第2期30卷 57-65页

作者： FLEISCHER, R FB-10 - Inf. Univ. Saarbruecken D-6600 Saarbruecken FRG

A simple model of a multiprocessor system with the k processors connected via a common bus is used to generalize the bounds known for 2-processor systems. Each processor has unlimited computational power and initially knows only one of the inputs in a function with k variables. Three rank-functions are used to directly derive a lower bound for Las Vegas protocols: 1. tensor-rank, 2. d and d subscript y, with d defined as the smallest number of monochromatic submatrixes necessary to cover M entirely and d subscript y denoting the smallest number of pairwise disjoint y-monochromatic submatrixes necessary to cover all y-entries of M, and 3. the magnitude of the greatest foolingset. This final rank-function is used to prove maximal complexity for a specific function. The nondeterministic complexity is shown to be, at most, quadratically better than the deterministic complexity. A rather tight lower bound is found for the nondeterministic complexity.

关键词： communication complexity multi-processor systems

来源：评论

学校读者我要写书评

暂无评论

communication complexity of byzantine agreement, revisited

引用

DISTRIBUTED COMPUTING 2023年第1期36卷 3-28页

作者： Abraham, Ittai Chan, T. -H. Hubert Dolev, Danny Nayak, Kartik Pass, Rafael Ren, Ling Shi, Elaine VMware Res Haifa Israel Univ Hong Kong Hong Kong Peoples R China Hebrew Univ Jerusalem Jerusalem Israel Duke Univ Durham NC 27710 USA Cornell Tech New York NY USA Univ Illinois Urbana IL 61801 USA Carnegie Mellon Univ Pittsburgh PA 15213 USA

As Byzantine Agreement (BA) protocols find application in large-scale decentralized cryptocurrencies, an increasingly important problem is to design BA protocols with improved communication complexity. A few existing works have shown how to achieve subquadratic BA under an adaptive adversary. Intriguingly, they all make a common relaxation about the adaptivity of the attacker, that is, if an honest node sends a message and then gets corrupted in some round, the adversary cannot erase the message that was already sent-henceforth we say that such an adversary cannot perform "after-the-fact removal". By contrast, many (super-)quadratic BA protocols in the literature can tolerate after-the-fact removal. In this paper, we first prove that disallowing after-the-fact removal is necessary for achieving subquadratic-communication BA. Next, we show new subquadratic binary BA constructions (of course, assuming no after-the-fact removal) that achieve near-optimal resilience and expected constant rounds under standard cryptographic assumptions and a public-key infrastructure (PKI) in both synchronous and partially synchronous settings. In comparison, all known subquadratic protocols make additional strong assumptions such as random oracles or the ability of honest nodes to erase secrets from memory, and even with these strong assumptions, no prior work can achieve the above properties. Lastly, we show that some setup assumption is necessary for achieving subquadratic multicast-based BA.

关键词： Byzantine agreement communication complexity Subquadratic Lower bounds

来源：评论

学校读者我要写书评

暂无评论

Byzantine Reliable Broadcast with Low communication and Time complexity 28

Byzantine Reliable Broadcast with Low Communication and Time...

引用

28th International Conference on Principles of Distributed Systems, OPODIS 2024

作者： Locher, Thomas DFINITY Zurich Switzerland

ISBN: (纸本)9783959773607

Byzantine reliable broadcast is a fundamental problem in distributed computing, which has been studied extensively over the past decades. State-of-the-art algorithms are predominantly based on the approach to share encoded fragments of the broadcast message, yielding an asymptotically optimal communication complexity when the message size exceeds the network size, a condition frequently encountered in practice. However, algorithms following the standard coding approach incur an overhead factor of at least 3, which can already be a burden for bandwidth-constrained applications. Minimizing this overhead is an important objective with immediate benefits to protocols that use a reliable broadcast routine as a building block. This paper introduces a novel mechanism to lower the communication and computational complexity. Two algorithms are presented that employ this mechanism to reliably broadcast messages in an asynchronous network where less than a third of all nodes are Byzantine. The first algorithm reduces the overhead factor to 2 and has a time complexity of 3 if the sender is honest, whereas the second algorithm attains an optimal time complexity of 2 with the same overhead factor in the absence of equivocation. Moreover, an optimization is proposed that reduces the overhead factor to 3/2 under normal operation in practice. Lastly, a lower bound is proved that an overhead factor lower than 3/2 cannot be achieved for a relevant class of reliable broadcast algorithms. © Thomas Locher.

关键词： Asynchronous Networks communication complexity Reliable Broadcast

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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