In this paper we define a spatial language used to verify global properties of self-organizing systems at run-time. The language can be used to assess spatial properties of system components to check desired global pr...
详细信息
In this paper we define a spatial language used to verify global properties of self-organizing systems at run-time. The language can be used to assess spatial properties of system components to check desired global properties of the system against emergent global behaviors arising from local interactions among components. The spatial language extends a logic-chemical-based coordination model that we have recently proposed and the verification of spatial properties is performed in a distributed manner among the nodes of the system.
This paper introduces a group communication protocol ensuring message causality condition based on gossippull systems. The message causality condition can be satisfied by making all multicast messages transferred to g...
详细信息
This paper introduces a group communication protocol ensuring message causality condition based on gossippull systems. The message causality condition can be satisfied by making all multicast messages transferred to group recipients through redundant message sending by sensor brokers, especially based on gossip-pull systems, which are only used when recipients request their messages to sensor brokers. These advantageous aspects enable the proposed protocol to enormously lower the redundancy of gossip messages compared with the gossip-push systems.
This paper presents a modified leader election algorithm for complete networks without sense of direction. The original algorithm, introduced by Villadangos et al. in (2005), had the aim of reducing the number of exch...
详细信息
This paper presents a modified leader election algorithm for complete networks without sense of direction. The original algorithm, introduced by Villadangos et al. in (2005), had the aim of reducing the number of exchanged messages in order to select a leader. However, the original O(n) algorithm fails to choose a leader on several occasions. A modified algorithm, which eliminates the problems that cause the wrong behaviour, is proposed. It is formally proved that the new algorithm verifies the correctness criteria that consist of selecting a unique leader in every case. Additionally, the algorithm maintains the O(n) complexity in both messages and time, where n is the number of nodes in the system
Traditional spectrum management mode results in spectrum scarcity and deployment difficulty and new spectrum management is desiderated. To overcome this problem, autonomous spectrum management system based on viable s...
详细信息
ISBN:
(纸本)9781424472352
Traditional spectrum management mode results in spectrum scarcity and deployment difficulty and new spectrum management is desiderated. To overcome this problem, autonomous spectrum management system based on viable system model is proposed. It decouples policy from behavior and protocol in order to reduce the deployment complexity, and exploits viable system model to partitions the system into six function modules. The interconnections between these modules bring autonomy to networks and radios which enable the self-management of spectrum. Finally, the spectrum utilization and deployment efficiency is analyzed and simulated in a scenario of dynamic spectrum allocation among heterogeneous networks.
We present a new abstraction to replace the t of n assumption used in designing fault-tolerant algorithms. This abstraction models dependent process failures yet it is as simple to use as the t of n assumption. To ill...
详细信息
We present a new abstraction to replace the t of n assumption used in designing fault-tolerant algorithms. This abstraction models dependent process failures yet it is as simple to use as the t of n assumption. To illustrate this abstraction, we consider Consensus for synchronous systems with both crash and arbitrary process failures. By considering failure correlations, we are able to reduce latency and enable the solution of Consensus for system configurations in which it is not possible when forced to use algorithms designed under the t of n assumption. We show that, in general, the number of rounds required in the worst case when assuming crash failures is different from the number of rounds required when assuming arbitrary failures. This is in contrast with the traditional result under the t of n assumption.
In past years, a large number of published distributed algorithms have been shown to be incorrect. Unfortunately, designers of distributed algorithms typically use informal correctness proofs, which tend to be unrelia...
详细信息
In past years, a large number of published distributed algorithms have been shown to be incorrect. Unfortunately, designers of distributed algorithms typically use informal correctness proofs, which tend to be unreliable. Formal correctness proofs offer a much higher degree of reliability, but they are not popular among algorithm designers because they are too mathematical and they typically assume synchronous message communication or some other abstract notation, and are therefore not easily applicable to the asynchronous message passing environment, the environment commonly assumed by many algorithm designers. To address this problem, we have developed a semiformal correctness proof method for the asynchronous message passing environment, using ideas from well known formal correctness proof methods. We illustrate part of the proof method by proving the safety property of a simple network broadcast algorithm.
Citizens envision the transition from the representative democracy to the online direct democracy. Inspired by the ancient Athenians' direct democracy, we propose an initial version of the framework Digital Eccles...
详细信息
Citizens envision the transition from the representative democracy to the online direct democracy. Inspired by the ancient Athenians' direct democracy, we propose an initial version of the framework Digital Ecclesia. We model the Digital Ecclesia as a social network that offers dynamic and large-scale reachability of citizens. Citizens are dynamically notified to participate and vote on discussion topics of new working groups. To address scalability and privacy challenges, the architecture of the Digital Ecclesia is distributed, i.e. each node runs a local program with its own storage that executes the voting procedure in parallel with other nodes. Nodes communicate to each other via exchanging encrypted messages in a scalable manner. We model the voting procedure as a non-cooperative game and we specify an algorithm for employing the voting game in a distributed fashion. Finally, we conduct the preliminary evaluation of the algorithm on a corpus of real-world votes.
distributed adaptive algorithms are proposed to address the problem of estimation in distributed networks. We extend recent work by relying on static and adaptive diffusion strategies. The resulting adaptive networks ...
详细信息
distributed adaptive algorithms are proposed to address the problem of estimation in distributed networks. We extend recent work by relying on static and adaptive diffusion strategies. The resulting adaptive networks are robust to node and link failures and present a substantial improvement over the non-cooperative case asserting that cooperation improves estimation performance. The distributed algorithms are peer-to-peer implementations suitable for networks with general topologies.
We consider a distributed multi-agent network system where the goal is to minimize an objective function that can be written as the sum of component functions, each of which is known (with stochastic errors) to a spec...
详细信息
We consider a distributed multi-agent network system where the goal is to minimize an objective function that can be written as the sum of component functions, each of which is known (with stochastic errors) to a specific network agent. We propose an asynchronous algorithm that is motivated by a random gossip scheme where each agent has a local Poisson clock. At each tick of its local clock, the agent averages its estimate with a randomly chosen neighbor and adjusts the average using the gradient of its local function that is computed with stochastic *** investigate the convergence properties of the algorithm for two different classes of functions: differentiable but not necessarily convex and convex but not necessarily differentiable.
The Border Gateway Protocol (BGP) populates Internet backbone routers with routes or prefixes. We present an algorithm to locally compute (without any modification to BGP) equivalent forwarding tables that provably co...
详细信息
The Border Gateway Protocol (BGP) populates Internet backbone routers with routes or prefixes. We present an algorithm to locally compute (without any modification to BGP) equivalent forwarding tables that provably contain the minimal number of prefixes. For large backbone routers, the Optimal Routing Table Constructor (ORTC) algorithm that we present produces routing tables with roughly 60% of the original number of prefixes. The publicly available MaeEast database with 41315 prefixes reduces to 23007 prefixes when ORTC is applied. We present performance measurements on four publicly available databases and a formal proof that ORTC does produce the optimal set of routes.
暂无评论