論文の概要: Weakly synchronous systems with three machines are Turing powerful
- arxiv url: http://arxiv.org/abs/2308.10578v1
- Date: Mon, 21 Aug 2023 09:24:12 GMT
- ステータス: 処理完了
- システム内更新日: 2023-08-22 14:19:54.451465
- Title: Weakly synchronous systems with three machines are Turing powerful
- Title（参考訳）: 3台のマシンを持つ弱い同期システムはチューリング力がある
- Authors: Cinzia Di Giusto (C&A), Davide Ferr\'e, Etienne Lozes (I3S, LSV),
Nicolas Nisse
- Abstract要約: 3つのプロセスの弱い同期システムの到達性問題は決定不可能であることを示す。
この研究の主な貢献は、3つのプロセスが任意に大きなツリー幅のMSCを生成する弱い同期システムである。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Communicating finite-state machines (CFMs) are a Turing powerful model of
asynchronous message-passing distributed systems. In weakly synchronous
systems, processes communicate through phases in which messages are first sent
and then received, for each process. Such systems enjoy a limited form of
synchronization, and for some communication models, this restriction is enough
to make the reachability problem decidable. In particular, we explore the
intriguing case of p2p (FIFO) communication, for which the reachability problem
is known to be undecidable for four processes, but decidable for two. We show
that the configuration reachability problem for weakly synchronous systems of
three processes is undecidable. This result is heavily inspired by our study on
the treewidth of the Message Sequence Charts (MSCs) that might be generated by
such systems. In this sense, the main contribution of this work is a weakly
synchronous system with three processes that generates MSCs of arbitrarily
large treewidth.
- Abstract（参考訳）: 通信有限状態マシン(CFM)は、非同期メッセージパッシング分散システムのチューリング強力なモデルである。
弱い同期システムでは、プロセスは各プロセスに対してメッセージが最初に送信され、受信されるフェーズを通して通信する。
このようなシステムには限られた同期形式があり、いくつかの通信モデルでは、この制限は到達可能性の問題を決定するのに十分である。
特に, p2p (FIFO) 通信の興味深い事例について検討し, 到達性問題は4つのプロセスでは決定不能であるが2つのプロセスでは決定不能であることが知られている。
3つのプロセスの弱い同期系の構成到達性問題は決定不可能であることを示す。
この結果は、このようなシステムによって生成される可能性のあるメッセージシーケンスチャート(MSC)のツリー幅に関する我々の研究に大きく影響されている。
この意味で、この研究の主な貢献は、3つのプロセスが任意に大きなツリー幅のMSCを生成する弱い同期システムである。
関連論文リスト
- Asynchronous Tool Usage for Real-Time Agents [61.3041983544042]
並列処理とリアルタイムツール利用が可能な非同期AIエージェントを導入する。
私たちの重要な貢献は、エージェントの実行とプロンプトのためのイベント駆動有限状態マシンアーキテクチャです。
この研究は、流体とマルチタスクの相互作用が可能なAIエージェントを作成するための概念的なフレームワークと実践的なツールの両方を提示している。
論文 参考訳（メタデータ） (2024-10-28T23:57:19Z) - Federated Contextual Cascading Bandits with Asynchronous Communication
and Heterogeneous Users [95.77678166036561]
繊細な通信プロトコルを用いたUPB型アルゴリズムを提案する。
同期フレームワークで達成されたものと同等のサブ線形後悔境界を与えます。
合成および実世界のデータセットに関する実証評価は、後悔と通信コストの観点から、我々のアルゴリズムの優れた性能を検証する。
論文 参考訳（メタデータ） (2024-02-26T05:31:14Z) - A Structural Complexity Analysis of Synchronous Dynamical Systems [33.788917274180484]
同期力学系における3つの問題について検討する。
これら3つの問題は、古典的な意味では難解であることが知られている。
定常木幅の例においても, いずれも難解であることを示す。
論文 参考訳（メタデータ） (2023-12-12T10:49:33Z) - Asynchronous SGD on Graphs: a Unified Framework for Asynchronous
Decentralized and Federated Optimization [13.119144971868632]
本稿では,グラフ上での非同期SGD(AGRAF SGD)について紹介する。
従来の分散非同期計算処理よりも遥かに穏やかな仮定の下で収束率を提供する。
論文 参考訳（メタデータ） (2023-11-01T11:58:16Z) - Qubit-based distributed frame synchronization for quantum key distribution [9.43392013925968]
本稿では,連続的に動作するシステムにおいて,時間回復が可能なキュービットベースの分散フレーム同期手法を提案する。
実験の結果,提案手法はQubit4Syncよりも優れていることがわかった。
我々は,ドローンによるQKDや量子ネットワーク構築など,幅広いQKDシナリオに適用できると考えている。
論文 参考訳（メタデータ） (2023-08-25T03:17:43Z) - Formal Controller Synthesis for Markov Jump Linear Systems with
Uncertain Dynamics [64.72260320446158]
マルコフジャンプ線形系に対する制御器の合成法を提案する。
本手法は,MJLSの離散(モードジャンピング)と連続(確率線形)の両方の挙動を捉える有限状態抽象化に基づいている。
本手法を複数の現実的なベンチマーク問題,特に温度制御と航空機の配送問題に適用する。
論文 参考訳（メタデータ） (2022-12-01T17:36:30Z) - A non-sequential hierarchy of message-passing models [0.0]
本稿では,大規模モデルと局所モデルの両方を含む通信モデルの統一階層について述べる。
私たちが考慮しているすべての通信モデルは、モナディック二階述語論理において公理化することができる。
論文 参考訳（メタデータ） (2022-10-24T09:31:25Z) - Asynchronous Parallel Incremental Block-Coordinate Descent for
Decentralized Machine Learning [55.198301429316125]
機械学習(ML)は、巨大なIoT(Internet of Things)ベースのインテリジェントでユビキタスなコンピューティングのビッグデータ駆動モデリングと分析のための重要なテクニックである。
急成長するアプリケーションやデータ量にとって、分散学習は有望な新興パラダイムである。
本稿では,多くのユーザデバイスに分散した分散システム上でMLモデルをトレーニングする問題について検討する。
論文 参考訳（メタデータ） (2022-02-07T15:04:15Z) - Quantum indirect synchronization [0.0]
2つ以上のレベルを持つシステムが制限サイクルが存在し、システムとドライブが直接結合されたときに外部ドライブと同期できることはよく知られている。
本稿では,2つの結合型2レベル量子システムからなる複合システムについて検討する。
We found the phase locking phenomenon in the phase diagram characterized by Husimi $Q$ function, and the sync can be generated。
論文 参考訳（メタデータ） (2021-12-13T15:05:25Z) - Disentangling Online Chats with DAG-Structured LSTMs [55.33014148383343]
DAG-LSTMはTree-LSTMの一般化であり、間接的な非循環的依存関係を処理できる。
提案する新モデルでは,リプライ・トゥ・リレーション(Repend-to-Relation)を回復する作業において,アート・ステータスの状態を達成できることが示される。
論文 参考訳（メタデータ） (2021-06-16T18:00:00Z) - Event-based Asynchronous Sparse Convolutional Networks [54.094244806123235]
イベントカメラはバイオインスパイアされたセンサーで、非同期でスパースな「イベント」の形で画素ごとの明るさ変化に反応する。
同期画像のようなイベント表現で訓練されたモデルを、同じ出力を持つ非同期モデルに変換するための一般的なフレームワークを提案する。
理論的および実験的に、これは高容量同期ニューラルネットワークの計算複雑性と遅延を大幅に減少させることを示す。
論文 参考訳（メタデータ） (2020-03-20T08:39:49Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。