Author: Dilsun Kaynar
Publisher: Springer Nature
ISBN: 3031020030
Category : Computers
Languages : en
Pages : 130
Get Book Here
Book Description
This monograph presents the Timed Input/Output Automaton (TIOA) modeling framework, a basic mathematical framework to support description and analysis of timed (computing) systems. Timed systems are systems in which desirable correctness or performance properties of the system depend on the timing of events, not just on the order of their occurrence. Timed systems are employed in a wide range of domains including communications, embedded systems, real-time operating systems, and automated control. Many applications involving timed systems have strong safety, reliability, and predictability requirements, which make it important to have methods for systematic design of systems and rigorous analysis of timing-dependent behavior. The TIOA framework also supports description and analysis of timed distributed algorithms -- distributed algorithms whose correctness and performance depend on the relative speeds of processors, accuracy of local clocks, or communication delay bounds. Such algorithms arise, for example, in traditional and wireless communications, networks of mobile devices, and shared-memory multiprocessors. The need to prove rigorous theoretical results about timed distributed algorithms makes it important to have a suitable mathematical foundation. An important feature of the TIOA framework is its support for decomposing timed system descriptions. In particular, the framework includes a notion of external behavior for a timed I/O automaton, which captures its discrete interactions with its environment. The framework also defines what it means for one TIOA to implement another, based on an inclusion relationship between their external behavior sets, and defines notions of simulations, which provide sufficient conditions for demonstrating implementation relationships. The framework includes a composition operation for TIOAs, which respects external behavior, and a notion of receptiveness, which implies that a TIOA does not block the passage of time. The TIOA framework also defines the notion of a property and what it means for a property to be a safety or a liveness property. It includes results that capture common proof methods for showing that automata satisfy properties. Table of Contents: Introduction / Mathematical Preliminaries / Describing Timed System Behavior / Timed Automata / Operations on Timed Automata / Properties for Timed Automata / Timed I/O Automata / Operations on Timed I/O Automata / Conclusions and Future Work
Author: Othon Michail
Publisher: Springer Nature
ISBN: 3031020049
Category : Computers
Languages : en
Pages : 140
Get Book Here
Book Description
Wireless sensor networks are about to be part of everyday life. Homes and workplaces capable of self-controlling and adapting air-conditioning for different temperature and humidity levels, sleepless forests ready to detect and react in case of a fire, vehicles able to avoid sudden obstacles or possibly able to self-organize routes to avoid congestion, and so on, will probably be commonplace in the very near future. Mobility plays a central role in such systems and so does passive mobility, that is, mobility of the network stemming from the environment itself. The population protocol model was an intellectual invention aiming to describe such systems in a minimalistic and analysis-friendly way. Having as a starting-point the inherent limitations but also the fundamental establishments of the population protocol model, we try in this monograph to present some realistic and practical enhancements that give birth to some new and surprisingly powerful (for these kind of systems) computational models. Table of Contents: Population Protocols / The Computational Power of Population Protocols / Enhancing the model / Mediated Population Protocols and Symmetry / Passively Mobile Machines that Use Restricted Space / Conclusions and Open Research Directions / Acronyms / Authors' Biographies
Author: Jennifer Welch
Publisher: Springer Nature
ISBN: 3031020065
Category : Computers
Languages : en
Pages : 93
Get Book Here
Book Description
Link reversal is a versatile algorithm design technique that has been used in numerous distributed algorithms for a variety of problems. The common thread in these algorithms is that the distributed system is viewed as a graph, with vertices representing the computing nodes and edges representing some other feature of the system (for instance, point-to-point communication channels or a conflict relationship). Each algorithm assigns a virtual direction to the edges of the graph, producing a directed version of the original graph. As the algorithm proceeds, the virtual directions of some of the links in the graph change in order to accomplish some algorithm-specific goal. The criterion for changing link directions is based on information that is local to a node (such as the node having no outgoing links) and thus this approach scales well, a feature that is desirable for distributed algorithms. This monograph presents, in a tutorial way, a representative sampling of the work on link-reversal-based distributed algorithms. The algorithms considered solve routing, leader election, mutual exclusion, distributed queueing, scheduling, and resource allocation. The algorithms can be roughly divided into two types, those that assume a more abstract graph model of the networks, and those that take into account more realistic details of the system. In particular, these more realistic details include the communication between nodes, which may be through asynchronous message passing, and possible changes in the graph, for instance, due to movement of the nodes. We have not attempted to provide a comprehensive survey of all the literature on these topics. Instead, we have focused in depth on a smaller number of fundamental papers, whose common thread is that link reversal provides a way for nodes in the system to observe their local neighborhoods, take only local actions, and yet cause global problems to be solved. We conjecture that future interesting uses of link reversal are yet to be discovered. Table of Contents: Introduction / Routing in a Graph: Correctness / Routing in a Graph: Complexity / Routing and Leader Election in a Distributed System / Mutual Exclusion in a Distributed System / Distributed Queueing / Scheduling in a Graph / Resource Allocation in a Distributed System / Conclusion
Author: Marko Vukolic
Publisher: Springer Nature
ISBN: 3031020073
Category : Computers
Languages : en
Pages : 141
Get Book Here
Book Description
A quorum system is a collection of subsets of nodes, called quorums, with the property that each pair of quorums have a non-empty intersection. Quorum systems are the key mathematical abstraction for ensuring consistency in fault-tolerant and highly available distributed computing. Critical for many applications since the early days of distributed computing, quorum systems have evolved from simple majorities of a set of processes to complex hierarchical collections of sets, tailored for general adversarial structures. The initial non-empty intersection property has been refined many times to account for, e.g., stronger (Byzantine) adversarial model, latency considerations or better availability. This monograph is an overview of the evolution and refinement of quorum systems, with emphasis on their role in two fundamental applications: distributed read/write storage and consensus. Table of Contents: Introduction / Preliminaries / Classical Quorum Systems / Classical Quorum-Based Emulations / Byzantine Quorum Systems / Latency-efficient Quorum Systems / Probabilistic Quorum Systems
Author: Paola Flocchini
Publisher: Springer Nature
ISBN: 3031020081
Category : Computers
Languages : en
Pages : 179
Get Book Here
Book Description
The study of what can be computed by a team of autonomous mobile robots, originally started in robotics and AI, has become increasingly popular in theoretical computer science (especially in distributed computing), where it is now an integral part of the investigations on computability by mobile entities. The robots are identical computational entities located and able to move in a spatial universe; they operate without explicit communication and are usually unable to remember the past; they are extremely simple, with limited resources, and individually quite weak. However, collectively the robots are capable of performing complex tasks, and form a system with desirable fault-tolerant and self-stabilizing properties. The research has been concerned with the computational aspects of such systems. In particular, the focus has been on the minimal capabilities that the robots should have in order to solve a problem. This book focuses on the recent algorithmic results in the field of distributed computing by oblivious mobile robots (unable to remember the past). After introducing the computational model with its nuances, we focus on basic coordination problems: pattern formation, gathering, scattering, leader election, as well as on dynamic tasks such as flocking. For each of these problems, we provide a snapshot of the state of the art, reviewing the existing algorithmic results. In doing so, we outline solution techniques, and we analyze the impact of the different assumptions on the robots' computability power. Table of Contents: Introduction / Computational Models / Gathering and Convergence / Pattern Formation / Scatterings and Coverings / Flocking / Other Directions
Author: Chryssis Georgiou
Publisher: Springer Nature
ISBN: 3031020057
Category : Computers
Languages : en
Pages : 155
Get Book Here
Book Description
Cooperative network supercomputing is becoming increasingly popular for harnessing the power of the global Internet computing platform. A typical Internet supercomputer consists of a master computer or server and a large number of computers called workers, performing computation on behalf of the master. Despite the simplicity and benefits of a single master approach, as the scale of such computing environments grows, it becomes unrealistic to assume the existence of the infallible master that is able to coordinate the activities of multitudes of workers. Large-scale distributed systems are inherently dynamic and are subject to perturbations, such as failures of computers and network links, thus it is also necessary to consider fully distributed peer-to-peer solutions. We present a study of cooperative computing with the focus on modeling distributed computing settings, algorithmic techniques enabling one to combine efficiency and fault-tolerance in distributed systems, and the exposition of trade-offs between efficiency and fault-tolerance for robust cooperative computing. The focus of the exposition is on the abstract problem, called Do-All, and formulated in terms of a system of cooperating processors that together need to perform a collection of tasks in the presence of adversity. Our presentation deals with models, algorithmic techniques, and analysis. Our goal is to present the most interesting approaches to algorithm design and analysis leading to many fundamental results in cooperative distributed computing. The algorithms selected for inclusion are among the most efficient that additionally serve as good pedagogical examples. Each chapter concludes with exercises and bibliographic notes that include a wealth of references to related work and relevant advanced results. Table of Contents: Introduction / Distributed Cooperation and Adversity / Paradigms and Techniques / Shared-Memory Algorithms / Message-Passing Algorithms / The Do-All Problem in Other Settings / Bibliography / Authors' Biographies
Author: Dimitris Sakavalas
Publisher: Springer Nature
ISBN: 3031020146
Category : Computers
Languages : en
Pages : 129
Get Book Here
Book Description
As the structure of contemporary communication networks grows more complex, practical networked distributed systems become prone to component failures. Fault-tolerant consensus in message-passing systems allows participants in the system to agree on a common value despite the malfunction or misbehavior of some components. It is a task of fundamental importance for distributed computing, due to its numerous applications. We summarize studies on the topological conditions that determine the feasibility of consensus, mainly focusing on directed networks and the case of restricted topology knowledge at each participant. Recently, significant efforts have been devoted to fully characterize the underlying communication networks in which variations of fault-tolerant consensus can be achieved. Although the deduction of analogous topological conditions for undirected networks of known topology had shortly followed the introduction of the problem, their extension to the directed network case has been proven a highly non-trivial task. Moreover, global knowledge restrictions, inherent in modern large-scale networks, require more elaborate arguments concerning the locality of distributed computations. In this work, we present the techniques and ideas used to resolve these issues. Recent studies indicate a number of parameters that affect the topological conditions under which consensus can be achieved, namely, the fault model, the degree of system synchrony (synchronous vs. asynchronous), the type of agreement (exact vs. approximate), the level of topology knowledge, and the algorithm class used (general vs. iterative). We outline the feasibility and impossibility results for various combinations of the above parameters, extensively illustrating the relation between network topology and consensus.
Author: Vincent Gramoli
Publisher: Springer Nature
ISBN: 3031020154
Category : Computers
Languages : en
Pages : 176
Get Book Here
Book Description
Providing a shared memory abstraction in distributed systems is a powerful tool that can simplify the design and implementation of software systems for networked platforms. This enables the system designers to work with abstract readable and writable objects without the need to deal with the complexity and dynamism of the underlying platform. The key property of shared memory implementations is the consistency guarantee that it provides under concurrent access to the shared objects. The most intuitive memory consistency model is atomicity because of its equivalence with a memory system where accesses occur serially, one at a time. Emulations of shared atomic memory in distributed systems is an active area of research and development. The problem proves to be challenging, and especially so in distributed message passing settings with unreliable components, as is often the case in networked systems. We present several approaches to implementing shared memory services with the help of replication on top of message-passing distributed platforms subject to a variety of perturbations in the computing medium.
Author: Gadi Taubenfeld
Publisher: Springer Nature
ISBN: 303102012X
Category : Computers
Languages : en
Pages : 107
Get Book Here
Book Description
Computers and computer networks are one of the most incredible inventions of the 20th century, having an ever-expanding role in our daily lives by enabling complex human activities in areas such as entertainment, education, and commerce. One of the most challenging problems in computer science for the 21st century is to improve the design of distributed systems where computing devices have to work together as a team to achieve common goals. In this book, I have tried to gently introduce the general reader to some of the most fundamental issues and classical results of computer science underlying the design of algorithms for distributed systems, so that the reader can get a feel of the nature of this exciting and fascinating field called distributed computing. The book will appeal to the educated layperson and requires no computer-related background. I strongly suspect that also most computer-knowledgeable readers will be able to learn something new.
Author: Karine Altisen
Publisher: Springer Nature
ISBN: 3031020138
Category : Computers
Languages : en
Pages : 147
Get Book Here
Book Description
This book aims at being a comprehensive and pedagogical introduction to the concept of self-stabilization, introduced by Edsger Wybe Dijkstra in 1973. Self-stabilization characterizes the ability of a distributed algorithm to converge within finite time to a configuration from which its behavior is correct (i.e., satisfies a given specification), regardless the arbitrary initial configuration of the system. This arbitrary initial configuration may be the result of the occurrence of a finite number of transient faults. Hence, self-stabilization is actually considered as a versatile non-masking fault tolerance approach, since it recovers from the effect of any finite number of such faults in an unified manner. Another major interest of such an automatic recovery method comes from the difficulty of resetting malfunctioning devices in a large-scale (and so, geographically spread) distributed system (the Internet, Pair-to-Pair networks, and Delay Tolerant Networks are examples of such distributed systems). Furthermore, self-stabilization is usually recognized as a lightweight property to achieve fault tolerance as compared to other classical fault tolerance approaches. Indeed, the overhead, both in terms of time and space, of state-of-the-art self-stabilizing algorithms is commonly small. This makes self-stabilization very attractive for distributed systems equipped of processes with low computational and memory capabilities, such as wireless sensor networks. After more than 40 years of existence, self-stabilization is now sufficiently established as an important field of research in theoretical distributed computing to justify its teaching in advanced research-oriented graduate courses. This book is an initiation course, which consists of the formal definition of self-stabilization and its related concepts, followed by a deep review and study of classical (simple) algorithms, commonly used proof schemes and design patterns, as well as premium results issued from the self-stabilizing community. As often happens in the self-stabilizing area, in this book we focus on the proof of correctness and the analytical complexity of the studied distributed self-stabilizing algorithms. Finally, we underline that most of the algorithms studied in this book are actually dedicated to the high-level atomic-state model, which is the most commonly used computational model in the self-stabilizing area. However, in the last chapter, we present general techniques to achieve self-stabilization in the low-level message passing model, as well as example algorithms.
