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

54th Annual IEEE Global Telecommunications Conference (GLOBECOM)

作者： Picu, Andreea Spyropoulos, Thrasyvoulos Swiss Fed Inst Technol Commun Syst Grp Zurich Switzerland EURECOM Mobil Commun Biot France

ISBN: (纸本)9781424492688

Opportunistic or Delay Tolerant Networks (DTNs) are envisioned to complement existing wireless technologies (cellular, WiFi). Wireless peers communicate when in contact, forming a network "on the fly", whose connectivity graph is highly dynamic and only partly connected. Because of this stringent environment, solutions to common networking problems (routing, congestion control, etc.) in this context are greedy, choosing the best solution among the locally available ones. This shared trait motivates the common treatment of such greedy algorithms for DTNs and raises some interesting questions: Do they converge? How fast are they? Yet, existing models study individual solutions. Moreover, they often assume homogeneous node mobility. The study of real world traces reveals considerable heterogeneity and non-trivial structure in human mobility. While algorithms have been proposed, accounting for this heterogeneity, their analytical tractability is still a challenge. In this paper, we propose a new model for greedy DTN algorithms, supporting the full heterogeneity of node mobility. We provide closed form solutions for crucial performance metrics (delivery probability and delay) and prove necessary and sufficient conditions for algorithm convergence. For illustration, we apply our model to the content placement problem, a variant of distributed caching. We use real and synthetic mobility traces to validate our findings and examine the impact of mobility properties in depth.

关键词： Absorption Algorithm design and analysis Convergence Delay Markov processes Optimization Peer to peer computing analytical framework connectivity graph content placement problem delay tolerant networks delay tolerant networks distributed algorithm distributed algorithms distributed caching greedy DTN algorithm greedy algorithm heterogeneous mobility homogeneous node mobility human mobility mobility management (mobile radio) opportunistic networks synthetic mobility traces tractability wireless peers wireless technology

来源：评论

学校读者我要写书评

暂无评论

Linear-Time and Efficient distributed algorithms for List Coloring Graphs on Surfaces 60

Linear-Time and Efficient Distributed Algorithms for List Co...

引用

60th IEEE Annual Symposium on Foundations of Computer Science (FOCS)

作者： Postle, Luke Univ Waterloo Dept Combinator & Optimizat Waterloo ON Canada

ISBN: (纸本)9781728149523

In 1994, Thomassen proved that every planar graph is 5-list-colorable. In 1995, Thomassen proved that every planar graph of girth at least five is 3-list-colorable. His proofs naturally lead to quadratic-time algorithms to find such colorings. Here, we provide the first linear-time algorithms to find such colorings. For a fixed surface S, Thomassen showed in 1997 that there exists a linear-time algorithm to decide if a graph embedded in S is 5-colorable and similarly in 2003 if a graph of girth at least five embedded in S is 3-colorable. Using the theory of hyperbolic families, the author and Thomas showed such algorithms exist for list-colorings. Around the same time, Dvorak and Kawarabayashi also provided such algorithms. Moreover, they gave an algorithm to find such colorings (if they exist). Here we provide the first such algorithm which is fixed parameter tractable with genus as the parameter;indeed, we provide a linear-time algorithm to find such colorings. In 1988, Goldberg, Plotkin and Shannon provided a deterministic distributed algorithm for 7-coloring n-vertex planar graphs in O(log n) rounds. In 2018, Aboulker, Bonamy, Bousquet, and Esperet provided a deterministic distributed algorithm for 6-coloring n-vertex planar graphs in polylogarithmic rounds. Their algorithm in fact works for 6-list-coloring. They also provided a polylogarithmic algorithm for 4-list-coloring triangle-free planar graphs. Chechik and Mukhtar independently obtained such algorithms for ordinary coloring in O(log n) rounds, which is best possible in terms of running time. Here we provide the first polylogarithmic deterministic distributed algorithms for 5-coloring n-vertex planar graphs and similarly for 3-coloring planar graphs of girth at least five. Indeed, these algorithms run in O(log n) rounds, work also for list-colorings, and even work on a fixed surface (assuming such a coloring exists).

关键词： Graph Coloring distributed algorithms Planar Graphs List Coloring

来源：评论

学校读者我要写书评

暂无评论

Characterizing Topological Assumptions of distributed algorithms in Dynamic Networks

Characterizing Topological Assumptions of Distributed Algori...

引用

16th International Colloquium on Structural Information and Communication Complexity

作者： Casteigts, Arnaud Chaumette, Serge Ferreira, Afonso Univ Ottawa SITE Ottawa ON K1N 6N5 Canada Univ Bordeaux 1 LaBRI Talence France CNRS MASCOTTE Project INRIA Valbonne France

ISBN: (纸本)9783642114755

Besides the complexity in time or in number of messages, a common approach for analyzing distributed algorithms is to look at their assumptions on the underlying network. This paper focuses on the study of such assumptions in dynamic networks, where the connectivity is expected to change, predictably or not, during the execution. Our main contribution is a theoretical framework dedicated to such analysis. By combining several existing components (local computations, graph relabellings, and evolving graphs), this framework allows to express detailed properties on the network dynamics and to prove that a given property is necessary, or sufficient, for the success of an algorithm. Consequences of this work include (i) the possibility to compare distributed algorithms on the basis of their topological requirements, (ii) the elaboration of a formal classification of dynamic networks with respect to these properties, and (iii) the possibility to check automatically whether a network trace belongs to one of the classes, and consequently to know which algorithm should run on it.

关键词： Dynamic networks distributed algorithms evolving graphs local interactions topological assumptions

来源：评论

学校读者我要写书评

暂无评论

A Preliminary Study for Implementation of distributed algorithms Over Vehicle Network 24

A Preliminary Study for Implementation of Distributed Algori...

引用

24th International Conference on Control, Automation and Systems

作者： Kim, Yeong-Ung Park, Hwan-Yong Park, Jun-Oh Ahn, Hyo-Sung Bae, Yoo-Bin Gwangju Inst Sci & Technol GIST Dept Mech Engn Gwangju 61005 South Korea Korea Aerosp Res Inst KARI Unmanned Aircraft Syst Res Div Daejeon 34133 South Korea

ISBN: (纸本)9798331517939;9788993215380

This paper discusses an architecture for implementing distributed algorithms in vehicular networks. In the context of vehicular networks, vehicles frequently change their positions, which leads to a constantly evolving network topology. We propose an architecture for distributed algorithms in vehicular networks using ROS2, focusing on the dynamic topology characteristic of peer-to-peer networks, which are significantly influenced by the movement and positioning of vehicles. Our approach leverages an all-to-all communication method where each message includes a timestamp, allowing only messages within a certain time frame to be utilized. This approach ensures that the communication network closely mirrors the physical network, making it adaptable to changes in network topology due to the movement of vehicles. The all-to-all communication model in the architecture ensures that any vehicle (or agent) can join or leave the network, provided it has the topic information. This capability is essential to maintaining a flexible and scalable network that allows vehicles to dynamically enter or leave the network without disrupting overall functionality.

关键词： Multi-agent systems Networked systems Vehicle Networks distributed algorithms

来源：评论

学校读者我要写书评

暂无评论

Continuous-Time distributed algorithms for Solving Linear Algebraic Equation 36

Continuous-Time Distributed Algorithms for Solving Linear Al...

引用

第36届中国控制会议

作者： Kai Cao Xianlin Zeng Yiguang Hong Key Laboratory of Systems and Control Institute of Systems ScienceChinese Academy of Sciences

ISBN: (纸本)9781538629185

In this paper,a multi-agent distributed continuous-time algorithm is proposed to solve a large-scale linear algebraic equation Ax = *** many existing results assuming each agent knows a few rows of A,the algorithm proposed in this paper assumes each agent knows a few columns of *** solve the linear algebraic equation,the problem is first converted to an optimization problem with a linear ***,a distributed continuous-time algorithm is designed based on the Lagrangian function of the optimization *** algorithm is proved to solve the linear algebraic equation with any initial condition via a Lyapunov *** example is presented to show the efficacy of the proposed algorithm.

关键词： distributed algorithms Multi-agent systems Linear algebraic equation Lagrangian function

来源：评论

学校读者我要写书评

暂无评论

On Derandomizing Local distributed algorithms 59

On Derandomizing Local Distributed Algorithms

引用

59th IEEE Annual Symposium on Foundations of Computer Science (FOCS)

作者： Ghaffari, Mohsen Harris, David G. Kuhn, Fabian Swiss Fed Inst Technol Zurich Switzerland Univ Maryland College Pk MD 20742 USA Univ Freiburg Freiburg Germany

ISBN: (纸本)9781538642306

The gap between the known randomized and deterministic local distributed algorithms underlies arguably the most fundamental and central open question in distributed graph algorithms. In this paper, we combine the method of conditional expectation with network decompositions to obtain a generic and clean recipe for derandomizing LOCAL algorithms. This leads to significant improvements on a number of problems, in cases resolving known open problems. Two main results are: An improved deterministic distributed algorithm for hypergraph maximal matching, improving on Fischer, Ghaffari, and Kuhn [FOCS'17]. This yields improved algorithms for edge-coloring, maximum matching approximation, and low out-degree edge orientation. The last result gives the first positive resolution in the Open Problem 11.10 in the book of Barenboim and Elkin. Improved randomized and deterministic distributed algorithms for the Lovasz Local Lemma, which get closer to a conjecture of Chang and Pettie [FOCS'17].

关键词： LOCAL distributed algorithms hypergraph matching Lovasz Local Lemma derandomization

来源：评论

学校读者我要写书评

暂无评论

Efficient distributed algorithms suited for uncertain context

Efficient distributed algorithms suited for uncertain contex...

引用

作者： Anais Durand Communaute Universite Grenoble Alpes

学位级别：博士

distributed systems become increasingly wide and complex, while their usage extends to various domains (e. g., communication, home automation, monitoring, cloud computing). Thus, distributed systems are executed in diverse contexts. In this thesis, we focus on uncertain contexts, i. e., the context is not completely known a priori or is unsettled. More precisely, we consider two main kinds of uncertainty: processes that are not completely identified and the presence of faults. The absence of identification is frequent in large networks composed of massively produced and deployed devices. In addition, anonymity is often required for security and privacy. Similarly, large networks are exposed to faults (e. g., process crashes, wireless connection drop), but the service must remain available. This thesis is composed of four main contributions. First, we study the leader election problem in unidirectional rings of homonym processes, i. e., processes are identified but their ID is not necessarily unique. Then, we propose a silent self-stabilizing leader election algorithm for arbitrary connected network. This is the first algorithm under such conditions that stabilizes in a polynomial number of steps. The third contribution is a new stabilizing property designed for dynamic networks that ensures fast and gradual convergences after topological changes. We illustrate this property with a clock synchronizing algorithm. Finally, we consider the issue of concurrency in resource allocation problems. In particular, we study the level of concurrency that can be achieved in a wide class of resource allocation problem, i. e., the local resource allocation.

关键词： distributed algorithms fault-tolerance self-stabilization anonymity dynamic networks

来源：评论

学校读者我要写书评

暂无评论

Neko:: A single environment to simulate and prototype distributed algorithms 15

Neko:: A single environment to simulate and prototype distri...

引用

15th International Conference on Information Networking (ICON-15)

作者： Urbán, P Défago, X Schiper, A Swiss Fed Inst Technol Commun Syst Dept CH-1015 Lausanne Switzerland

ISBN: (纸本)0769509517;0769509525

Designing, tuning, and analyzing the performance of distributed algorithms and protocols are complex tasks. A major factor that contributes to this complexity is the fact that there is no single environment to support all phases of the development of a distributed algorithm. This paper presents Neko, an easy to use Java platform that provides a uniform and extensible environment for the various phases of algorithm design and performance evaluation: prototyping, tuning, simulation, deployment, etc.

关键词： simulation prototyping distributed algorithms message passing middleware Java

来源：评论

学校读者我要写书评

暂无评论

Sampling and Output Estimation in distributed algorithms and LCAs 21

Sampling and Output Estimation in Distributed Algorithms and...

引用

22nd International Conference on distributed Computing and Networking (ICDCN)

作者： Barenboim, Leonid Maimon, Tzali Open Univ Israel Raanana Israel Ben Gurion Univ Negev Beer Sheva Israel

ISBN: (纸本)9781450389334

We consider the distributed message-passing model and the Local Computational algorithms (LCA) model. In both models a network is represented by an n-vertex graph G = (V, E). We focus on labeling problems, such as vertex-coloring, edge-coloring, maximal independent set (MIS) and maximal matching. In the distributed model the vertices of v perform computations in parallel, in order to compute their parts in the solution for G. In the LCA model, on the other hand, probes are performed on certain vertices in order to compute their labels in a solution to a given problem. We study the possibility of estimating a solution produced by an algorithm, much before the algorithm terminates. This estimation not only allows for size estimation of a solution, but also for an early detection of failure in randomized algorithms, so that a correcting procedure can be executed. To this end, we propose a sampling technique, in which the labels in the sampling are distributed proportionally to the distribution in the algorithm's output. However, the sampling running time is significantly smaller than that of the algorithm in hand. We achieve the following results, in terms of the maximum degree Delta and the arboricity a of the input graph. The running time of our procedures is O(log a + log log n), for sampling vertex-coloring, edge-coloring, maximal matching and MIS. This significantly improves upon previous sampling techniques, which incur additional dependency on the maximum degree Delta that can be much higher than the arboricity, as well as more significant dependency on n. Our techniques for sampling in the distributed model provide a powerful and general tool for estimation in the LCA model. In this setting the goal is estimating the size of a solution to a given problem, by making as few vertex probes as possible. For the above-mentioned problems, we achieve estimations with probe complexity d(O(log a+log log n)), where d = min(Delta, a . poly(log(n)).

关键词： distributed algorithms Randomized Scheme Graph Coloring Maximal Independent Set LCA

来源：评论

学校读者我要写书评

暂无评论

distributed algorithms solving the updating problems

Korean Journal of Computational and Applied Mathematics

引用

Korean Journal of Computational and Applied Mathematics 2002年第2期9卷 437-450页

作者： Park, Jung-Ho Park, Yoon-Young Choi, Sung-Hee Div. of Computer and Info. Sciences Sun Moon University Asan Chungnam 336-708 Korea Republic of

In this paper, we consider the updating problems to reconstruct the biconnected-components and to reconstruct the weighted shortest path in response to the topology change of the network. We propose two distributed algorithms. The first algorithm solves the updating problem that reconstructs the biconnected-components after the several processors and links are added and deleted. Its bit complexity is O((n prime + a + d)log n prime ), its message complexity is O(n prime + a + d), the ideal time complexity is O(n prime ), and the space complexity is O(e log n + e prime log n prime ). The second algorithm solves the updating problem that reconstructs the weighted shortest path. Its message complexity and ideal-time complexity are O(u2 + a + n prime ) respectively.

关键词： distributed algorithms Graph algorithms Network

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：