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

40th acm SIGACT-SIGOPS symposium on principles of distributed computing (PODC)

作者： Fraigniaud, Pierre Gelles, Ran Lotker, Zvi Univ Paris Paris France CNRS Paris France Bar Ilan Univ Ramat Gan Israel

ISBN: (纸本)9781450385480

Studying distributed computing through the lens of algebraic topology has been the source of many significant breakthroughs during the last two decades, especially in the design of lower bounds or impossibility results for deterministic algorithms. In a nutshell, this approach consists of capturing all the possible states of a distributed system at a certain time as a simplicial complex called protocol complex, and viewing computation as a simplicial map from that complex to the so-called output complex, that captures all possible legal output states of the system. This paper aims at studying randomized synchronous distributed computing through the lens of algebraic topology. We do so by studying the wide class of (input-free) symmetry-breaking tasks, e.g., leader election, in synchronous fault-free anonymous systems. We show that it is possible to redefine solvability of a task "locally", i.e., for each simplex of the protocol complex individually, without requiring any global consistency. However, this approach has a drawback: it eliminates the topological aspect of the computation, since a single facet has a trivial topological structure. To overcome this issue, we introduce a "projection" pi of both protocol and output complexes, where every simplex.. is mapped to a complex pi (sigma);the later has a rich structure that replaces the structure we lost by considering one single facet at a time. To show the significance and applicability of our topological approach, we derive necessary and sufficient conditions for solving leader election in synchronous fault-free anonymous sharedmemory and message-passing models. In both models, we consider scenarios in which there might be correlations between the random values provided to the nodes. In particular, different parties might have access to the same randomness source so their randomness is not independent but equal. Interestingly, we find that solvability of leader election relates to the number of parties that posse

关键词： distributed computing lower bounds algebraic topology correlated randomness leader election

来源：评论

学校读者我要写书评

暂无评论

Brief Announcement: Temporal Locality in Online Algorithms 36

Brief Announcement: Temporal Locality in Online Algorithms

引用

36th International symposium on distributed computing, DISC 2022

作者： Pacut, Maciej Parham, Mahmoud Rybicki, Joel Schmid, Stefan Suomela, Jukka Tereshchenko, Aleksandr Technische Universität Berlin Germany Faculty of Computer Science Universität Wien Austria Institute of Science and Technology Austria Klosterneuburg Austria TU Berlin Germany Fraunhofer SIT Berlin Germany Aalto University Espoo Finland

ISBN: (纸本)9783959772556

Online algorithms make decisions based on past inputs, with the goal of being competitive against an algorithm that sees also future inputs. In this work, we introduce time-local online algorithms;these are online algorithms in which the output at any given time is a function of only T latest inputs. Our main observation is that time-local online algorithms are closely connected to local distributed graph algorithms: distributed algorithms make decisions based on the local information in the spatial dimension, while time-local online algorithms make decisions based on the local information in the temporal dimension. We formalize this connection, and show how we can directly use the tools developed to study distributed approximability of graph optimization problems to prove upper and lower bounds on the competitive ratio achieved with time-local online algorithms. Moreover, we show how to use computational techniques to synthesize optimal time-local algorithms. © Maciej Pacut, Mahmoud Parham, Joel Rybicki, Stefan Schmid, Jukka Suomela, and Aleksandr Tereshchenko.

关键词： distributed computer systems

来源：评论

学校读者我要写书评

暂无评论

Locally Checkable Problems in Rooted Trees 21

Locally Checkable Problems in Rooted Trees

引用

40th acm SIGACT-SIGOPS symposium on principles of distributed computing (PODC)

作者： Balliu, Alkida Brandt, Sebastian Olivetti, Dennis Studeny, Jan Suomela, Jukka Tereshchenko, Aleksandr Univ Freiburg Freiburg Germany Swiss Fed Inst Technol Zurich Switzerland Aalto Univ Espoo Finland

ISBN: (纸本)9781450385480

Consider any locally checkable labeling problem Pi in rooted regular trees: there is a finite set of labels Sigma, and for each label x is an element of Sigma we specify what are permitted label combinations of the children for an internal node of label x (the leaf nodes are unconstrained). This formalism is expressive enough to capture many classic problems studied in distributed computing, including vertex coloring, edge coloring, and maximal independent set. We show that the distributed computational complexity of any such problem Pi falls in one of the following classes: it is O(1), Theta(log* n), Theta(log n), or n(Theta)(1) rounds in trees with n nodes (and all of these classes are nonempty). We show that the complexity of any given problem is the same in all four standard models of distributed graph algorithms: deterministic LOCAL, randomized LOCAL, deterministic CONGEST, and randomized CONGEST model. In particular, we show that randomness does not help in this setting, and the complexity class Theta(log log n) does not exist (while it does exist in the broader setting of general trees). We also show how to systematically determine the complexity class of any such problem Pi, i.e., whether II takes Theta(1), Theta(log* n), Theta(log n), or n(Theta(1)) rounds. While the algorithm may take exponential time in the size of the description of II, it is nevertheless practical: we provide a freely available implementation of the classifier algorithm, and it is fast enough to classify many problems of interest.

关键词： distributed algorithms LOCAL model CONGEST model Rooted trees LCL problems

来源：评论

学校读者我要写书评

暂无评论

Emotional Design and User Study on Guidance System For MR distributed Collaboration 10

Emotional Design and User Study on Guidance System For MR Di...

引用

Joint Meeting of the 10th International symposium of Chinese CHI (Chinese CHI) / International Workshop on Human-Engaged computing (IWHEC)

作者： Liang, Xiaozhan Hu, Yong Li, Chuchen Beihang Univ Sch New Media Art & Design Beijing Peoples R China Beihang Univ Yunnan Innovat Inst Beijing Peoples R China Beihang Univ State Key Lab Virtual Real Technol & Syst Beijing Peoples R China

ISBN: (纸本)9781450398695

In recent years, especially after the outbreak of COVID-19, the applications of distributed collaboration in mixed reality (MR) environment has developed rapidly. Due to the cutting-edge technology and the specialized nature of the equipment, many studies have focused on the design of tutorials in MR, but few studies have taken the factors of emotional design into consideration. Since the perception of the state among users is based on their avatar firstly, which is helpful for users' perceptions about collaborative content in novice guidance. Based on Norman's principles of reflective design and James' theory about the experience self, we built a MR virtual sandtable collaboration system, which contains three guiding parts that are the full practice of theoretical research. Furthermore, We generated three progressive levels of emotional solutions in guidance design and conducted user experience research to explore the impact of three different degrees of emotional design, summarizing the applicable paradigm of novice guidance of emotional design in MR distributed collaborative scenarios. Through the evaluation and analysis of SUS model and task load, we found that novice guidance with a higher emotional design level, which combines static graphics, dynamic hand models and conversational voice would result in a better user experience.

关键词： Human-centered computing Interaction design Interaction design theory Concepts and paradigms

来源：评论

学校读者我要写书评

暂无评论

Reaching Consensus for Asynchronous distributed Key Generation 21

Reaching Consensus for Asynchronous Distributed Key Generati...

引用

40th acm SIGACT-SIGOPS symposium on principles of distributed computing (PODC)

作者： Abraham, Ittai Jovanovic, Philipp Maller, Mary Meiklejohn, Sarah Stern, Gilad Tomescu, Alin VMware Res Herzliyya Israel UCL London England Ethereum Fdn London England Google London England Hebrew Univ Jerusalem Jerusalem Israel VMware Res Palo Alto CA USA

We give a protocol for Asynchronous distributed Key Generation (A-DKG) that is optimally resilient (can withstand f (n(3)) expected communication complexity, and assumes only the existence of a PKI. Prior to our work,... 详细信息

ISBN: (纸本)9781450385480

We give a protocol for Asynchronous distributed Key Generation (A-DKG) that is optimally resilient (can withstand f < n/3 sfaulty parties), has a constant expected number of rounds, has <(O)over tilde>(n(3)) expected communication complexity, and assumes only the existence of a PKI. Prior to our work, the best A-DKG protocols required Omega (n) expected number of rounds, and Q (n(4)) expected communication. Our A-DKG protocol relies on several building blocks that are of independent interest. We define and design a Proposal Election (PE) protocol that allows parties to retrospectively agree on a valid proposal after enough proposals have been sent from different parties. With constant probability the elected proposal was proposed by a nonfaulty party. In building our PE protocol, we design a Verifiable Gather protocol which allows parties to communicate which proposals they have and have not seen in a verifiable manner. The final building block to our A-DKG is a Validated Asynchronous Byzantine Agreement (VABA) protocol. We use our PE protocol to construct a VABA protocol that does not require leaders or an asynchronous DKG setup. Our VABA protocol can be used more generally when it is not possible to use threshold signatures.

关键词： distributed algorithms cryptographic protocols Byzantine fault tolerance distributed key generation consensus leader election

来源：评论

学校读者我要写书评

暂无评论

distributed Randomness from Approximate Agreement 36

Distributed Randomness from Approximate Agreement

引用

36th International symposium on distributed computing, DISC 2022

作者： Freitas, Luciano Kuznetsov, Petr Tonkikh, Andrei LTCI Télécom Paris Institut Polytechnique de Paris France

ISBN: (纸本)9783959772556

Randomisation is a critical tool in designing distributed systems. The common coin primitive, enabling the system members to agree on an unpredictable random number, has proven to be particularly useful. We observe, however, that it is impossible to implement a truly random common coin protocol in a fault-prone asynchronous system. To circumvent this impossibility, we introduce two relaxations of the perfect common coin: (1) approximate common coin generating random numbers that are close to each other;and (2) Monte Carlo common coin generating a common random number with an arbitrarily small, but non-zero, probability of failure. Building atop the approximate agreement primitive, we obtain efficient asynchronous implementations of the two abstractions, tolerating up to one third of Byzantine processes. Our protocols do not assume trusted setup or public key infrastructure and converge to the perfect coin exponentially fast in the protocol running time. By plugging one of our protocols for Monte Carlo common coin in a well-known consensus algorithm, we manage to get a binary Byzantine agreement protocol with O(n3 log n) communication complexity, resilient against an adaptive adversary, and tolerating the optimal number f 4). We also show how the approximate common coin, combined with a variant of Gray code, can be used to solve an interesting problem of Intersecting Random Subsets, which we introduce in this paper. © Luciano Freitas, Petr Kuznetsov, and Andrei Tonkikh.

关键词： Monte Carlo methods

来源：评论

学校读者我要写书评

暂无评论

Improved distributed Lower Bounds for MIS and Bounded (Out-)Degree Dominating Sets in Trees 21

Improved Distributed Lower Bounds for MIS and Bounded (Out-)...

引用

40th acm SIGACT-SIGOPS symposium on principles of distributed computing (PODC)

作者： Balliu, Alkida Brandt, Sebastian Kuhn, Fabian Olivetti, Dennis Univ Freiburg Freiburg Germany Swiss Fed Inst Technol Zurich Switzerland

ISBN: (纸本)9781450385480

Recently, Balliu, Brandt, and Olivetti [FOCS '20] showed the first omega(log* n) lower bound for the maximal independent set (MIS) problem in trees. In this work we prove lower bounds for a much more relaxed family of distributed symmetry breaking problems. As a by-product, we obtain improved lower bounds for the distributed MIS problem in trees. For a parameter k and an orientation of the edges of a graph G, we say that a subset S of the nodes of G is a k-outdegree dominating set if S is a dominating set of G and if in the induced sub- graph G [S], every node in S has outdegree at most k. Note that for k = 0, this definition coincides with the definition of an MIS. For a given k, we consider the problem of computing a k-outdegree dominating set. We show that, even in regular trees of degree at most A, in the standard LOCAL model, there exists a constant omega > 0 such that for k <= Delta(epsilon), for the problem of computing a k-outdegree dominating set, any randomized algorithm requires at least Omega ( min {log Delta, root log log n}) rounds and any deterministic algorithm requires at least Omega ( min {log Delta, root log log n} ) rounds. The proof of our lower bounds is based on the recently highly successful round elimination technique. We provide a novel way to do simplifications for round elimination, which we expect to be of independent interest. Our new proof is considerably simpler than the lower bound proof in [FOCS '20]. In particular, our round elimination proof uses a family of problems that can be described by only a constant number of labels. The existence of such a proof for the MIS problem was believed impossible by the authors of [FOCS '20].

关键词： maximal independent set dominating set LOCAL model lower bounds

来源：评论

学校读者我要写书评

暂无评论

Ultra-Sparse Near-Additive Emulators 21

Ultra-Sparse Near-Additive Emulators

引用

40th acm SIGACT-SIGOPS symposium on principles of distributed computing (PODC)

作者： Elkin, Michael Matar, Shaked Ben Gurion Univ Negev Dept Comp Sci Beer Sheva Israel

ISBN: (纸本)9781450385480

Near-additive (aka (1 + epsilon, beta)-) emulators and spanners are a fundamental graph-algorithmic construct, with numerous applications for computing approximate shortest paths and related problems in distributed, streaming and dynamic settings. Known constructions of near-additive emulators enable one to trade between their sparsity (i.e., number of edges) and the additive stretch beta. Specifically, for any pair of parameters epsilon > 0, kappa = 1, 2, ..., one can have a (1 + epsilon, beta)-emulator with O(n(1+1/kappa)) edges, with beta = (log kappa/epsilon)(log kappa). At their sparsest, these emulators employ c . n edges, for some constant c >= 2. We tighten this bound, and show that in fact precisely n(1+1/kappa )edges suffice. In particular, our emulators can be ultra-sparse, i.e., we can have an emulator with n + o(n) edges and beta (log log n/epsilon)(log log n (1+o(1))).( ) We also devise a distributed deterministic algorithm in the CONG EST model that builds these emulators in low polynomial time (i.e., in O(n(rho)) time, for an arbitrarily small constant parameter time, for an arbitrarily small constant parameter rho > 0). Finally, we also improve the state-of-the-art distributed deterministic CONGEST-model construction of (1 + epsilon, beta)-spanners devised in the PODC'19 paper [13]. Specifically, the spanners of [13] have O(beta . n(1+1/kappa)) edges, i.e., at their sparsest they employ O(log log n/epsilon) (log log n). n edges. In this paper, we devise an efficient distributed deterministic CONGEST-model algorithm that builds such spanners with O(n(1+1/kappa)) edges for kappa = O (log n/log((3) )n). K = 0 At their sparsest, these spanners employ only O(n. log log n) edges.

关键词： Emulators Deterministic distributed Algorithms

来源：评论

学校读者我要写书评

暂无评论

Time-space trade-offs in population protocols for the majority problem

引用

distributed computing 2021年第2期34卷 91-111页

作者： Berenbrink, Petra Elsaesser, Robert Friedetzky, Tom Kaaser, Dominik Kling, Peter Radzik, Tomasz Univ Hamburg Vogt Kolln Str 3 D-22527 Hamburg Germany Univ Salzburg Jakob Haringer Str 2 A-5020 Salzburg Austria Univ Durham Lower Mountjoy South Rd Durham DH1 3LE England Kings Coll London Strand CampusBush House London WC2B 4BG England

Population protocols are a model for distributed computing that is focused on simplicity and robustness. A system ofnidentical agents (finite state machines) performs a global task like electing a unique leader or determining the majority opinion when each agent has one of two opinions. Agents communicate in pairwise interactions with randomly assigned communication partners. Quality is measured in two ways: the number of interactions to complete the task and the number of states per agent. We present protocols for the majority problem that allow for a trade-off between these two measures. Compared to the only other trade-off result (Alistarh et al. in proceedings of the 2015 acm symposium on principles of distributed computing, Donostia-San Sebastian, 2015), we improve the number of interactions by almost a linear factor. Furthermore, our protocols can be made uniform (working correctly without any information on the population sizen), yielding the first uniform majority protocols that stabilize in a subquadratic number of interactions.

关键词： distributed computing Majority Population protocols Stochastic processes

来源：评论

学校读者我要写书评

暂无评论

2022 Edsger W. Dijkstra Prize in distributed computing 22

2022 Edsger W. Dijkstra Prize in Distributed Computing

引用

proceedings of the 2022 acm symposium on principles of distributed computing

作者： Marcos Aguiliera Andrea Richa Alexander Schwarzmann Alessandro Panconesi Christian Scheideler Philipp Woelfel VMware Research Germany Arizona State University AZ USA Augusta University APO AA Sapienza Università Di Roma Rome Italy Universität Paderborn Paderborn Germany University of Calgary Calgary AB Canada

ISBN: (纸本)9781450392624

The Edsger W. Dijkstra Prize in distributed computing is awarded for outstanding papers on the principles of distributed computing, whose significance and impact on the theory or practice of distributed computing have been evident for at least a decade. It is sponsored jointly by the acm symposium on principles of distributed computing (PODC) and the EATCS symposium on distributed computing (DISC). The prize is presented annually, with the presentation taking place alternately at PODC and DISC.

关键词：

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：