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

43rd acm symposium on Theory of computing

作者： Golab, Wojciech Higham, Lisa Woelfel, Philipp Hewlett Packard Labs Palo Alto CA USA

ISBN: (纸本)9781450306911

Linearizability is the gold standard among algorithm designers for deducing the correctness of a distributed algorithm using implemented shared objects from the correctness of the corresponding algorithm using atomic versions of the same objects. We show that linearizability does not suffice for this purpose when processes can exploit randomization, and we discuss the existence of alternative correctness conditions. This paper makes the following contributions: 1. Various examples demonstrate that using well-known linearizable implementations of objects (e.g., snapshots) in place of atomic objects can change the probability distribution of the outcomes that the adversary is able to generate. In some cases, an oblivious adversary can create a probability distribution of outcomes for an algorithm with implemented, linearizable objects, that not even a strong adversary can generate for the same algorithm with atomic objects. 2. A new correctness condition for shared object implementations, called strong linearizability, is defined. We prove that a strong adversary (i.e., one that sees the outcome of each coin flip immediately) gains no additional power when atomic objects are replaced by strongly linearizable implementations. In general, no strictly weaker correctness condition suffices to ensure this. We also show that strong linearizability is a local and composable property. 3. In contrast to the situation for the strong adversary, for a natural weaker adversary (one that cannot see a process' coin flip until its next operation on a shared object) we prove that there is no correspondingly general correctness condition. Specifically, any linearizable implementation of counters from atomic registers and load-linked/store-conditional objects, that satisfies a natural locality property, necessarily gives the weak adversary more power than it has with atomic counters.

关键词： Randomized algorithms adversary models atomicity linearizability

来源：评论

学校读者我要写书评

暂无评论

Brief Announcement: Understanding Read-Write Wait-Free Coverings in the Fully-Anonymous Shared-Memory Model 24

Brief Announcement: Understanding Read-Write Wait-Free Cover...

引用

43rd acm SIGACT-SIGOPS symposium on principles of distributed computing, PODC 2024

作者： Losa, Giuliano Gafni, Eli Stellar Development Foundation San FranciscoCA United States University of California Los Angeles Los AngelesCA United States

ISBN: (纸本)9798400706684

In the fully-anonymous (shared-memory) model, inspired by a biological setting, processors have no identifiers and memory locations are anonymous, meaning there is no pre-existing agreement among processors on any naming of the memory locations. In this work, we ask fundamental questions about the fully-anonymous model in the hope to obtain a better understanding of the role of naming and anonymity in distributed ***, we ask what it means to solve a task under processor anonymity. With tasks such as renaming, the traditional notion obviously does not apply. Instead of restricting ourselves to colorless tasks, we propose using the notion of group solvability, which allows transferring any task to processor-anonymous ***, the difficulty with anonymity is that processors can hardly avoid covering and then overwriting each other's writes, erasing information written by their predecessors. To get to the bottom of this phenomenon, we ask what system configurations are stable when processors keep reading and writing ad infinitum. Resolving this question leads us to a wait-free solution to the snapshot task, which then allows us to solve renaming and obstruction-free consensus. © 2024 Association for computing Machinery. All rights reserved.

关键词： distributed computer systems

来源：评论

学校读者我要写书评

暂无评论

computing Minimum Weight Cycle in the CONGEST Model 24

Computing Minimum Weight Cycle in the CONGEST Model

引用

43rd acm SIGACT-SIGOPS symposium on principles of distributed computing, PODC 2024

作者： Manoharan, Vignesh Ramachandran, Vijaya The University of Texas at Austin AustinTX United States

ISBN: (纸本)9798400706684

Minimum Weight Cycle (MWC) is the problem of finding a simple cycle of minimum weight in a graph G = (V, E). This is a fundamental graph problem with classical sequential algorithms that run in Õ(n3) and Õ(mn) time† where n = |V| and m = |E|. In recent years this problem has received significant attention in the context of fine-grained sequential complexity [3, 50] as well as in the design of faster sequential approximation algorithms [13, 26, 32, 33], though not much is known in the distributed CONGEST *** present near-optimal ω(n) CONGEST lower bounds on the round complexity of computing exact and (2 - ϵ)-approximate MWC in undirected weighted graphs and in directed graphs even if unweighted. We complement these lower bounds with sublinear-round algorithms for computing 2-approximation of MWC. Our algorithms use a variety of techniques in non-trivial ways, such as in our approximate directed unweighted MWC algorithm that efficiently computes BFS from all vertices restricted to certain implicitly computed neighborhoods in sublinear rounds, and in our weighted approximation algorithms that use unweighted MWC algorithms on scaled graphs combined with a fast and streamlined method for computing multiple source approximate SSSP. © 2024 Association for computing Machinery. All rights reserved.

关键词： Directed graphs

来源：评论

学校读者我要写书评

暂无评论

A Near-Optimal Low-Energy Deterministic distributed SSSP with Ramifications on Congestion and APSP 24

A Near-Optimal Low-Energy Deterministic Distributed SSSP wit...

引用

43rd acm SIGACT-SIGOPS symposium on principles of distributed computing, PODC 2024

作者： Ghaffari, Mohsen Trygub, Anton Mit CambridgeMA United States

ISBN: (纸本)9798400706684

We present a low-energy deterministic distributed algorithm that computes exact Single-Source Shortest Paths (SSSP) in near-optimal time: it runs in Õ(n) rounds and each node is awake during only poly(log n) rounds. When a node is not awake, it performs no computations or communications and spends no *** general approach we take along the way to this result can be viewed as a novel adaptation of Dijkstra's classic approach to SSSP, which makes it suitable for the distributed setting. Notice that Dijkstra's algorithm itself is not efficient in the distributed setting due to its need for repeatedly computing the minimum-distance unvisited node in the entire network. Our adapted approach has other implications, as we outline *** a step toward the above end-result, we obtain a simple deterministic algorithm for exact SSSP with near-optimal time and message complexities of Õ(n) and Õ(m), in which each edge communicates only poly(log n) messages. Therefore, one can simultaneously run n instances of it for n sources, using a simple random delay scheduling. That computes All Pairs Shortest Paths (APSP) in the near-optimal time complexity of Õ(n). This algorithm matches the complexity of the recent APSP algorithm of Bernstein and Nanongkai [STOC 2019] using a completely different method (and one that is more modular, in the sense that the SSSPs are solved independently). It also takes a step toward resolving the open problem on a deterministic Õ(n)-time APSP, as the only randomness used now is in the scheduling. © 2024 Association for computing Machinery. All rights reserved.

关键词： Graph theory

来源：评论

学校读者我要写书评

暂无评论

Brief Announcement: Massively Parallel Ruling Set Made Deterministic 24

Brief Announcement: Massively Parallel Ruling Set Made Deter...

引用

43rd acm SIGACT-SIGOPS symposium on principles of distributed computing, PODC 2024

作者： Giliberti, Jeff Parsaeian, Zahra University of Maryland United States University of Freiburg Germany

ISBN: (纸本)9798400706684

We study the deterministic complexity of the 2-Ruling Set problem in the model of Massively Parallel Computation (MPC) with linear and strongly sublinear local *** MPC: We present a constant-round deterministic algorithm for the 2-Ruling Set problem that matches the randomized round complexity recently settled by Cambus, Kuhn, Pai, and Uitto [DISC'23], and improves upon the deterministic O(log log n)-round algorithm by Pai and Pemmaraju [PODC'22]. Our main ingredient is a simpler analysis of CKPU's algorithm based solely on bounded independence, which makes its efficient derandomization *** MPC: We present a deterministic algorithm that computes a 2-Ruling Set in [EQUATION] rounds deterministically. Notably, this is the first deterministic ruling set algorithm with sublogarithmic round complexity, improving on the O(log δ+log log∗n)-round complexity that stems from the deterministic MIS algorithm of Czumaj, Davies, and Parter [TALG'21]. Our result is based on a simple and fast randomness-efficient construction that achieves the same sparsification as that of the randomized [EQUATION]-round LOCAL algorithm by Kothapalli and Pemmaraju [FSTTCS'12]. © 2024 Association for computing Machinery. All rights reserved.

关键词： distributed computer systems

来源：评论

学校读者我要写书评

暂无评论

Time of deterministic broadcasting in radio networks with local knowledge

引用

SIAM JOURNAL ON computing 2004年第4期33卷 870-891页

作者： Kowalski, DR Pelc, A Warsaw Univ Inst Informat PL-02097 Warsaw Poland Max Planck Inst Informat D-66123 Saarbrucken Germany Univ Quebec Outaouais Dept Informat Hull PQ J8X 3X7 Canada

We consider broadcasting in radio networks, modeled as undirected graphs, whose nodes know only their own label and labels of their neighbors. In every step every node acts either as a transmitter or as a receiver. A node acting as a transmitter sends a message which can potentially reach all of its neighbors. A node acting as a receiver in a given step gets a message if and only if exactly one of its neighbors transmits in this step. Bar-Yehuda, Goldreich, and Itai [J. Comput. System Sci., 45 ( 1992), pp. 104-126] considered broadcasting in this model. They claimed a linear lower bound on the time of deterministic broadcasting in such radio networks of diameter 3. This claim turns out to be incorrect in this model (although it is valid in a more pessimistic model [R. Bar-Yehuda, O. Goldreich, and A. Itai, Errata Regarding "On the time complexity of broadcast in radio networks: An exponential gap between determinism and randomization," http://***/mathusers/oded/p_***, 2002]). We construct an algorithm that broadcasts in logarithmic time on all graphs from the Bar-Yehuda, Goldreich, and Itai paper (BGI). Moreover, we show how to broadcast in sublinear time on all n-node graphs of diameter o(log log n). On the other hand, we construct a class of graphs of diameter 4, such that every broadcasting algorithm requires time Omega((4)rootn) on these graphs. In view of the randomized algorithm from BGI, running in expected time O(D log n + log(2) n) on all n-node graphs of diameter D (cf. also a recent O(D log(n/D) + log(2) n)-time algorithm from [D. Kowalski and A. Pelc, proceedings of the 22nd Annual acm symposium on principles of distributed computing, Boston, 2003, pp. 73-82;A. Czumaj and W. Rytter, proceedings of the 44th Annual IEEE symposium on Foundations of Computer Science, Cambridge, MA, 2003, pp. 492-501]), our lower bound gives the first correct proof of an exponential gap between determinism and randomization in the time of radio broa

关键词： broadcasting distributed deterministic radio network

来源：评论

学校读者我要写书评

暂无评论

Enhanced Malware Detection in distributed IoT Environment using Optimized Cascaded LSTM-GRU Framework 43

Enhanced Malware Detection in Distributed IoT Environment us...

引用

43rd International symposium on Reliable distributed Systems

作者： Gaurav, Akshat Gupta, Brij B. Sharma, Sachin Chui, Kwok Tai Ronin Inst Montclair NJ USA Asia Univ Dept Comp Sci & Informat Engn Taichung 413 Taiwan State Bank India Panchkula India Hong Kong Metropolitan Univ HKMU Hong Kong Peoples R China

ISBN: (纸本)9798331530044;9798331530037

In the changing terrain of Internet of Things (IoT) security, especially in distributed systems, effective and fast virus detection is a challenging task. Using a Cascaded LSTM-GRU architecture, this work presents a Malware Detection Framework tuned for the special needs of edge and cloud computing. This method leverages Gated Recurrent Units (GRUs) for sequence data management and Long Short-Term Memory (LSTM) networks' strengths for temporal pattern recognition to increase the efficacy of malware detection. The empirical assessment of our methodology revealed remarkable classification accuracy and F1 scores. These findings demonstrate the framework's ability to greatly improve cybersecurity measures across smart computing systems, especially in edge and cloud computing environments, therefore marking major progress in the area of intelligent malware detection.

关键词： distributed Systems IoT Security Malware Classification Cascaded LSTM-GRU Deep Learning Cybersecurity

来源：评论

学校读者我要写书评

暂无评论

Brief Announcement: Content-Oblivious Leader Election on Rings 24

Brief Announcement: Content-Oblivious Leader Election on Rin...

引用

43rd acm SIGACT-SIGOPS symposium on principles of distributed computing, PODC 2024

作者： Frei, Fabian Gelles, Ran Ghazy, Ahmed Nolin, Alexandre Cispa Helmholtz Center for Information Security Saarbrücken Germany Bar-Ilan University Ramat Gan Israel

ISBN: (纸本)9798400706684

In content-oblivious computation, n nodes wish to compute a given task over an asynchronous network that suffers from an extremely harsh type of noise, which corrupts the content of all messages across all channels. In a recent work, Censor-Hillel, Cohen, Gelles, and Sela (distributed computing, 2023) showed how to perform arbitrary computations in a content-oblivious way in 2-edge connected networks but only if the network has a distinguished node (called root) to initiate the *** goal is to remove this assumption, which was conjectured to be necessary. Achieving this goal essentially reduces to performing a content-oblivious leader election since an elected leader can then serve as the root required to perform arbitrary content-oblivious computations. We focus on ring networks, which are the simplest 2-edge connected graphs. On oriented rings, we obtain a leader election algorithm with message complexity O(n · IDmax), where IDmax is the maximal assigned ID. As it turns out, this dependency on IDmax is inherent: we show a lower bound of ω(n log(IDmax/n)) messages for content-oblivious leader election algorithms. We also extend our results to non-oriented rings, where nodes cannot tell which channel leads to which neighbor. In this case, however, the algorithm does not terminate but only reaches quiescence. © 2024 Copyright is held by the owner/author(s). Publication rights licensed to acm.

关键词： distributed computer systems

来源：评论

学校读者我要写书评

暂无评论

Brief Announcement: On the Limits of Information Spread by Memory-less Agents 24

Brief Announcement: On the Limits of Information Spread by M...

引用

43rd acm SIGACT-SIGOPS symposium on principles of distributed computing, PODC 2024

作者： D'Archivio, Niccolò Vacus, Robin Coati Inria d'Université Côte d'Azur Sophia Antipolis France Bocconi Institute for Data Science and Analytics Milan Italy

ISBN: (纸本)9798400706684

We address the self-stabilizing bit-dissemination problem, designed to capture the challenges of spreading information and reaching consensus among entities with minimal cognitive and communication capacities. Specifically, a group of n agents is required to adopt the correct opinion, initially held by a single informed individual, choosing from two possible opinions. In order to make decisions, agents are restricted to observing the opinions of a few randomly sampled agents, and lack the ability to communicate further and to identify the informed individual. Additionally, agents cannot retain any information from one round to the next. According to a recent publication in SODA (2024), a logarithmic convergence time without memory is achievable in the parallel setting (where agents are updated simultaneously), as long as the number of samples is at least(Formula presented.). However, determining the minimal sample size for an efficient protocol to exist remains a challenging open question. As a preliminary step towards an answer, we establish the first lower bound for this problem in the parallel setting. Specifically, we demonstrate that it is impossible for any memory-less protocol with constant sample size, to converge with high probability in less than an almost-linear number of rounds. © 2024 Copyright is held by the owner/author(s). Publication rights licensed to acm.

关键词： distributed computer systems

来源：评论

学校读者我要写书评

暂无评论

Brief Announcement: distributed Model Checking on Graphs of Bounded Treedepth 24

Brief Announcement: Distributed Model Checking on Graphs of ...

引用

43rd acm SIGACT-SIGOPS symposium on principles of distributed computing, PODC 2024

作者： Fomin, Fedor V. Fraigniaud, Pierre Montealegre, Pedro Rapaport, Ivan Todinca, Ioan University of Bergen Bergen Norway Université Paris Cité CNRS Paris France Universidad Adolfo Ibañez Santiago Chile Universidad de Chile Santiago Chile Université d'Orléans Insa Cvl Orléans France

ISBN: (纸本)9798400706684

We establish that every monadic second-order logic (MSO) formula on graphs with bounded treedepth is decidable in a constant number of rounds within the CONGEST model. To our knowledge, this marks the first meta-theorem regarding distributed model-checking. Various optimization problems on graphs are expressible in MSO. Examples include determining whether a graph G has a clique of size k, whether it admits a coloring with k colors, whether it contains a graph H as a subgraph or minor, or whether terminal vertices in G could be connected via vertex-disjoint paths. Our meta-theorem significantly enhances the work of Bousquet et al. [PODC 2022], which was focused on distributed certification of MSO on graphs with bounded treedepth. Moreover, our results can be extended to solving optimization and counting problems expressible in MSO, in graphs of bounded treedepth. © 2024 Copyright is held by the owner/author(s). Publication rights licensed to acm.

关键词： Model checking

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：