Search

Over the past few decades, the harmful effects of industrial activity and consumer society have resulted in global warming. Governments and international organizations are looking for ways to monitor activities of individuals and companies to assess their ecological impact. Unfortunately, such an approach would easily be seen as a mass surveillance tool. This is why we are proposing in this paper a novel privacy-aware global infrastructure for ecological footprint calculator based on the Internet of things and blockchain. Indeed, we take advantage of the data collection capacity of the Internet of things, the anonymization provided by public key identification and encryption, and the immutability of blockchain to implement this global system. A three-stage approach was used to validate our architecture: modeling in Petri nets to verify that the infrastructure fulfills all the required missions, implementing the three central authorities with python to record parameters such as durations, and finally modeling in queuing networks to demonstrate stability. The blockchain and Internet of things parts are used in a purely abstract manner relying on standard concepts; therefore, we have not implemented them. The experiments have produced very promising results. We have shown that for the simplest form of queue modeling, the involved servers have a utilization rate that is close to 50 % and that the overall waiting time remains below one minute. [ABSTRACT FROM AUTHOR]

Leader election is one of the fundamental problems in distributed computing: a single node, called the leader, must be specified. This task can be formulated either in a weak way, where one node outputs leader and all other nodes output non-leader, or in a strong way, where all nodes must also learn which node is the leader. If the nodes of the network have distinct identifiers, then such an agreement means that all nodes have to output the identifier of the elected leader. For anonymous networks, the strong version of leader election requires that all nodes must be able to find a path to the leader, as this is the only way to identify it. In this paper, we study variants of deterministic leader election in arbitrary anonymous networks. Leader election is impossible in some anonymous networks, regardless of the allocated amount of time, even if nodes know the entire map of the network. This is due to possible symmetries in the network. However, even in networks in which it is possible to elect a leader knowing the map, the task may be still impossible without any initial knowledge, regardless of the allocated time. On the other hand, for any network in which leader election (weak or strong) is possible knowing the map, there is a minimum time, called the election index, in which this can be done. We consider four formulations of leader election discussed in the literature in the context of anonymous networks: one is the weak formulation, and the three others specify three different ways of finding the path to the leader in the strong formulation. Our aim is to compare the amount of initial information needed to accomplish each of these "four shades" of leader election in minimum time. Following the framework of algorithms with advice, this information (a single binary string) is provided to all nodes at the start by an oracle knowing the entire network. The length of this string is called the size of advice. We show that the size of advice required to accomplish leader election in the weak formulation in minimum time is exponentially smaller than that needed for any of the strong formulations. Thus, if the required amount of advice is used as a measure of the difficulty of the task, the weakest version of leader election in minimum time is drastically easier than any version of the strong formulation in minimum time. [ABSTRACT FROM AUTHOR]

Blockchain is an innovative application of distributed storage, consensus mechanism, cryptographic algorithm, and other computer technologies. As the underlying architecture of blockchain, consensus is the key to realizing service-oriented applications of blockchain in terms of its security, efficiency, and scalability optimization. In some high-complexity consensus, such as Practical Byzantine Fault Tolerance (PBFT), throughput is severely reduced as the number of nodes increases. Even in low-complexity algorithms such as Raft, the load on the leader is severely affected as the network size increases, negatively affecting consensus efficiency. To solve these problems, we propose a node reliable shard model based on guarantee tree that achieves high scalability while maintaining a certain degree of decentralization and security based on consortium blockchain. Firstly, we create a guarantee mechanism to represent the trust relationship between nodes, and then, we design a reliable node selection strategy based on the guarantee mechanism to evaluate the node guarantee results and consensus behavior, determine the node trust status, and identify malicious nodes and choose a list of trusted leaders. Secondly, we propose a Dual-Leaders supervision mechanism, in which the deputy senses the heartbeat of leader while the deputy activity is detected by consensus nodes. Finally, we use a guarantee mechanism and reliable node selection strategy to design a network partitioning method to achieve high concurrent consensus for multiple partitions and significantly improve consensus efficiency. Subsequent experiments show that the throughput of the proposed algorithm improves by 48% over Raft and is significantly greater than PBFT, which has better throughput but lower consensus latency. [ABSTRACT FROM AUTHOR]

Summary: Raft is a consensus algorithm that implements highly available replicas. As raft requires a leader to drive the protocol execution, it usually employs a round‐robin leader election mechanism to select a random leader among all nodes. However, when the elected leader suffers from performance issues, the protocol will temporarily lose aliveness. To address this issue, we propose a multi‐strategy leader election mechanism that allows nodes to proactively trigger a new round of election when they believe the leader suffers from performance issues, and replace this leader with a new one in a designated priority queue. The formal analysis and experimental results show that the mechanism can improve the system's throughput/latency without additional election time overhead. [ABSTRACT FROM AUTHOR]

Distributed wireless network devices are mostly battery-powered. Transmitting a message on distributed wireless networks uses more energy than receiving one, which in turn uses more energy than internal computations. Therefore, in this paper, we study the problem of randomized leader election in synchronous distributed single-hop networks with a special focus on the energy complexity. We provide algorithmic solutions to the implicit version of leader election problem where non-leader nodes need not be aware of the identity of the leader. Because the size of a message impacts the energy consumption, we highlight that the solutions we propose consume very little energy: each device is allowed to send a single one-bit message only once and listen to the network during two time slots at most. We first consider four well-studied variants of the radio network (RN) model depending on the transmission and reception abilities of the participating devices: RNstrongCD: both transmitters and listeners can detect collision, RNsenderCD: only transmitters can detect collision, RNCD: only listeners can detect collision, RNnoCD: no device can detect collision. Next, we study the beeping network model. The time and energy complexities of all our algorithms are deterministic and they succeed in electing a unique leader with high probability even under the restriction that each node can only send once a single one-bit signal. When the nodes are aware of the total number n of the participants, our algorithm elects a leader in O (log n) rounds. When n is not known beforehand but an upper bound u on n with log u = Θ (log n) is known by all participating nodes, we design a randomized algorithm with O (log 2 n) time complexity for the RN models. For beeping networks, our algorithm has O (n ε) time complexity ( 0 < ε < 1 ). The parameter ε can be tuned to increase the probability of success of the algorithms. [ABSTRACT FROM AUTHOR]

Previous years have seen increased interest in a new network paradigm, Software defined networking (SDN). The basic idea behind this new concept consists of removing the smart parts of the connectivity components and moving them to a seul control point known as a controller. This centralized network view makes the network maintenance and management easier and facilitates the creation of new services. Despite many advantages of SDN, the concentration of network intelligence in a single controller raises serious challenges that impact SDN scalability, performance, and fault tolerance. One of the main problems in SDN is controller failure. In this article, we develop a fault tolerant model called fault-tolerant load balancing (FTLBC) for SDN controllers. To reduce the cascading failure problem, the proposed model requires the load of the failing controller to be shared among other controllers. In the case of a controller failure, The FTLBC model concentrates on distributing the load among the remaining controllers based on the load of the orphans' switches and the load of the remaining controllers. [ABSTRACT FROM AUTHOR]

With the exponential growth of data and the company's cross-domain disaster recovery requirements, companies increasingly need to manage data across spatial domains. Cross-domain data management requires a distributed consensus algorithm to make the data consistent. However, the existing distributed consensus algorithms only consider the situation of a single data center, and do not consider the uncertainty of network communication between data centers, so they face long log synchronization delays and low system throughput in cross-space region scenarios and other issues. The current status and new challenges of distributed consensus algorithms in the cross-space domain were sorted out systematically, and the technical route to solve these challenges was looked forward. [ABSTRACT FROM AUTHOR]

We study two fundamental communication primitives: broadcasting and leader election in the classical model of multi-hop radio networks with unknown topology andwithout collision detection mechanisms. It has been known for almost 20 years that in undirected networks with n nodes and diameter D, randomized broadcasting requiresΩ(D log n/D + log²n) rounds, assuming that uninformed nodes are not allowed to communicate (until they are informed). Only very recently, Haeupler and Wajc (PODC'2016) showed that this bound can be improved for the model with spontaneous transmissions, providing an O(D log n log log n/log D + logO(1) n)-time broadcasting algorithm. In this article, we give a new and faster algorithm that completes broadcasting in O(D log n/log D + logO(1) n) time, succeeding with high probability. This yields the first optimal O(D)-time broadcasting algorithm whenever n is polynomial in D. Furthermore, our approach can be applied to design a new leader election algorithm that matches the performance of our broadcasting algorithm. Previously, all fast randomized leader election algorithms have used broadcasting as a subroutine and their complexity has been asymptotically strictly larger than the complexity of broadcasting. In particular, the fastest previously known randomized leader election algorithm of Ghaffari and Haeupler (SODA'2013) requires O(D log n/D min{log logn, log n/D} + logO(1) n)-time, succeeding with high probability. Our new algorithm again requires O(D log n/log D + logO(1) n) time, also succeeding with high probability. [ABSTRACT FROM AUTHOR]

The model of population protocols refers to the growing in popularity theoretical framework suitable for studying pairwise interactions within a large collection of simple indistinguishable entities, frequently called agents. In this article, the emphasis is on the space complexity of fast leader election in population protocols governed by the random scheduler, which uniformly at random selects pairwise interactions between n agents. One of the main results of this article is the first fast space optimal leader election protocol, whichworks with high probability. The new protocol operates in parallel time O(log2 n) equivalent to O(n log2 n) sequential pairwise interactions with each agent's memory space limited to O(log logn) states. This double logarithmic space utilisation matches asymptotically the lower bound 12 log logn on the number of states utilised by agents in any leader election algorithm with the running time o(n polylog n); see Reference [7]. Our new solution expands also on the classical concept of phase clocks used to synchronise and to coordinate computations in distributed algorithms. In particular, we formalise the concept and provide a rigorous analysis of phase clocks operating in nested modes. Our arguments are also valid for phase clocks propelled by multiple leaders. The combination of the two results in the first time-space efficient leader election algorithm. We also provide a complete formal argumentation, indicating that our solution is always correct, fast, and it works with high probability. [ABSTRACT FROM AUTHOR]

Abstract This paper is concerned with distributed detection of central nodes in complex networks using closeness centrality. Closeness centrality plays an essential role in network analysis. Distributed tasks such as leader election can make effective use of centrality information for highly central nodes, but complete network information is not locally available. Evaluating closeness centrality exactly requires complete knowledge of the network; for large networks, this may be inefficient, so closeness centrality should be approximated. Here, situations for decentralised network view construction where a node has zero knowledge about other nodes on the network at initial and there is no central node to coordinate evaluations of node closeness centrality are considered. Unlike centralized methods for detection of central nodes, in decentralized methods an approximated view of the network must be available at each node, then each node can evaluate its own closeness centrality before it can share it with others when applicable. Based on our knowledge, there is no much work done under this setting where the leading approach consists of running the breadth-first search Skiena (1998) on each node with a limited number of iterations (which is less than the diameter of the graph into consideration), as done by You et al. (2017), Wehmuth and Ziviani (2012), before each node evaluates its centrality. Running the breadth-first search on each node in a decentralized fashion requires high cost in terms of communication. Our contribution is to consider a better way of constructing network view in a decentralised manner with less communication cost. This paper refines a distributed centrality computation algorithm by You et al. (2017) by pruning nodes which are almost certainly not most central. For example, in a large network, leave nodes can not play a central role. This leads to a reduction in the number of messages exchanged to determine the centrality of the remaining nodes. Our results show that our approach reduces the number of messages for networks which contain many prunable nodes. Our results also show that reducing the number of messages may have a positive impact on running time and memory size.

In wireless sensor and IoT networks dedicated to smart-cities, a leader node performs critical tasks such as generating encryption/decryption keys. In this paper, the leader is the node situated at the extreme left of the network. It is the node which starts the algorithm of searching the boundary nodes. These nodes will be used to monitor any sensitive, dangerous or inaccessible site. For this type of application, the used algorithm must be robust and fault-tolerant because it is difficult or even impossible to intervene in the presence of node failures. If this node is the leader, such a situation can be catastrophic. In this article, we present a new algorithm called DoTRo, which is based on a tree routing protocol. It starts with local leaders which will launch the flooding process to determine a spanning tree. During this process, their values will be forwarded. If two spanning trees meet, the tree that routes the best value continues its process while the other tree stops. The remaining tree root will be the leader. This algorithm is low energy consuming with reduction rates that can exceed 85% with respect to the classical minium finding algorithm. It is efficient and fault-tolerant since it works even in the presence of node failures and communication disconnectivity. Additionally, the energy consumption is well balanced between nodes. Finally, the complexity and the proof of convergence of the proposed algorithm is presented. [ABSTRACT FROM AUTHOR]

In this paper, we look at the problem of randomized leader election in synchronous distributed networks with a special focus on the message complexity. We provide an algorithm that solves the implicit version of leader election (where non-leader nodes need not be aware of the identity of the leader) in any general network with O (n log 7 / 2 n · t mix) messages and in O (t mix log 2 n) time, where n is the number of nodes and t mix refers to the mixing time of a random walk in the network graph G. For several classes of well-connected networks (that have a large conductance or alternatively small mixing times e.g., expanders, hypercubes, etc), the above result implies extremely efficient (sublinear running time and messages) leader election algorithms. Correspondingly, we show that any substantial improvement is not possible over our algorithm, by presenting an almost matching lower bound for randomized leader election. We show that Ω (n / ϕ 3 / 4) messages are needed for any leader election algorithm that succeeds with probability at least 1 - o (1) , where ϕ refers to the conductance of a graph. To the best of our knowledge, this is the first work that shows a dependence between the time and message complexity to solve leader election and the connectivity of the graph G, which is often characterized by the graph's conductance ϕ . Apart from the Ω (m) bound in Kutten et al. (J ACM 62(1):7:1–7:27, 2015) (where m denotes the number of edges of the graph), this work also provides one of the first non-trivial lower bounds for leader election in general networks. [ABSTRACT FROM AUTHOR]

A team of mobile agents with different labels, starting from different nodes of an unknown anonymous network, must meet at the same node and declare that they all met. This task of gathering was traditionally considered assuming that agents at the same node can exchange information. We ask if this ability of talking is needed. The answer turns out to be no. We design two deterministic algorithms that accomplish gathering in a much weaker model. We only assume that each agent knows how many agents are at the node that it currently occupies. Our first algorithm assumes that agents know some upper bound N on the size of the network, and works in time polynomial in N and in the length l of the smallest label. Our second algorithm does not assume any knowledge about the network, but its complexity is at least exponential in the size of the network and in the labels of agents. Its purpose is to show feasibility of gathering under this harsher scenario. As a by-product we solve, in the same weak model, the fundamental problem of leader election among agents. As an application we solve the gossiping problem in this model: if each agent has a message, all agents can learn all messages. This is perhaps our most surprising finding: agents without any transmitting devices can solve the most general information exchange problem if they can count the number of agents present at visited nodes. [ABSTRACT FROM AUTHOR]

Given a boolean predicate Π on labeled networks (e.g., proper coloring, leader election, etc.), a self-stabilizing algorithm for Π is a distributed algorithm that can start from any initial configuration of the network (i.e., every node has an arbitrary value assigned to each of its variables), and eventually converge to a configuration satisfying Π. It is known that leader election does not have a deterministic self-stabilizing algorithm using a constant-size register at each node, i.e., for some networks, some of their nodes must have registers whose sizes grow with the size n of the networks. On the other hand, it is also known that leader election can be solved by a deterministic self-stabilizing algorithm using registers of O(log log n) bits per node in any n-node bounded-degree network. We show that this latter space complexity is optimal. Specifically, we prove that every deterministic self-stabilizing algorithm solving leader election must use (log log n)-bit per node registers in some n-node networks. In addition, we show that our lower bounds go beyond leader election, and apply to all problems that cannot be solved by anonymous algorithms. [ABSTRACT FROM AUTHOR]

Recent developments in unmanned aerial vehicles (UAVs) have led to the introduction of a wide variety of innovative applications, especially in the Mobile Edge Computing (MEC) field. UAV swarms are suggested as a promising solution to cope with the issues that may arise when connecting Internet of Things (IoT) applications to a fog platform. We are interested in a crucial aspect of designing a swarm of UAVs in this work, which is the coordination of swarm agents in complicated and unknown environments. Centralized leader–follower formations are one of the most prevalent architectural designs in the literature. In the event of a failed leader, however, the entire mission is canceled. This paper proposes a framework to enable the use of UAVs under different MEC architectures, overcomes the drawbacks of centralized architectures, and improves their overall performance. The most significant contribution of this research is the combination of distributed formation control, online leader election, and collaborative obstacle avoidance. For the initial phase, the optimal path between departure and arrival points is generated, avoiding obstacles and agent collisions. Next, a quaternion-based sliding mode controller is designed for formation control and trajectory tracking. Moreover, in the event of a failed leader, the leader election phase allows agents to select the most qualified leader for the formation. Multiple possible scenarios simulating real-time applications are used to evaluate the framework. The obtained results demonstrate the capability of UAVs to adapt to different MEC architectures under different constraints. Lastly, a comparison is made with existing structures to demonstrate the effectiveness, safety, and durability of the designed framework. [ABSTRACT FROM AUTHOR]

Leader election is a fundamental task in distributed computing. It is a symmetry breaking problem, calling for one node of the network to become the leader, and for all other nodes to become non-leaders. We consider leader election in anonymous radio networks modeled as simple undirected connected graphs. Nodes communicate in synchronous rounds. In each round, a node can either transmit a message to all its neighbours, or stay silent and listen. A node v hears a message from a neighbour w in a given round if v listens in this round and if w is its only neighbour transmitting in this round. If v listens in a round in which more than one neighbour transmits, then v hears noise that is different from any message and different from silence. We assume that nodes are identical (anonymous) and execute the same deterministic algorithm. Under this scenario, symmetry can be broken only in one way: by different wake-up times of the nodes. In which situations is it possible to break symmetry and elect a leader using time as symmetry breaker? In order to answer this question, we consider configurations. A configuration is the underlying graph with nodes tagged by non-negative integers with the following meaning. A node can either wake up spontaneously in the round shown on its tag, according to some global clock, or can be woken up hearing a message sent by one of its already awoken neighbours. The local clock of a node starts at its wakeup and nodes do not have access to the global clock determining their tags. A configuration is feasible if there exists a distributed algorithm that elects a leader for this configuration. Our main result is a complete algorithmic characterization of feasible configurations. More precisely, we design a centralized decision algorithm, working in polynomial time, whose input is a configuration and which decides if the configuration is feasible. Using this algorithm we also provide a dedicated deterministic distributed leader election algorithm for each feasible configuration that elects a leader for this configuration in time O(n²σ), where n is the number of nodes and σ is the difference between the largest and smallest tag of the configuration. We then ask the question whether there exists a universal deterministic distributed algorithm electing a leader for all feasible configurations. The answer turns out to be no, and we show that such a universal algorithm cannot exist even for the class of 4-node feasible configurations. We also prove that a distributed version of our decision algorithm cannot exist. [ABSTRACT FROM AUTHOR]

In this work, we propose a multi-tier architectural model to separate functionality and security concerns for distributed cyber-physical systems. On the line of distributed computing, such systems require the identification of leaders for distribution of work, aggregation of results, etc. Further, we propose a fault-tolerant leader election algorithm that can independently elect the functionality and security leaders. The proposed election algorithm identifies a list of potential leader capable nodes to reduce the leader election overhead. It keeps identifying the highest potential node as the leader, whenever needed, including the situation when one has failed. We also explain the proposed architecture and its management method through a case study. Further, we perform several experiments to evaluate the system performance. The experimental results show that the proposed architectural model improves the system performance in terms of latency, average response time, and the number of real-time tasks completed within the deadline. [ABSTRACT FROM AUTHOR]

The recent advances in unmanned aerial vehicles (UAVs) enormously improve their utility and expand their application scope. The UAV and swarm implementation further prevail in Smart City practices with the aid of edge computing and urban Internet of Things. The lead–follow formation in UAV swarm is an important organization means and has been adopted in diverse exercises, for its efficiency and ease of control. However, the reliability of centralization makes the entire swarm system in risk of collapse and instability, if a fatal fault incident happens in the leader. The motivation is to build a mechanism helping the distributed swarm recover from possible failures. Existing ways include assigning definite backups, temporary clustering and traversing to select a new leader are traditional ways that lack flexibility and adaptability. In this article, we propose a voting-based leader election scheme inspired by the Raft method in distributed computation consensus to solve the problem. We further discuss the impact of communication conditions imposed on the decentralized voting process by implementing a network resource pool. To dynamically evaluate UAV individuals, we outline measurement design principles and provide a realizable calculation example. Lastly but not least, empirical simulation results manifest better performance than the Raft-based method. Our voting-based approach exhibits advantages and is a promising way for quick regrouping and fault recovery in lead–follow swarms. [ABSTRACT FROM AUTHOR]

In this paper, we investigate the abilities of systems of self-assembling tiles which can each pass a constant number of signals to their immediate neighbors to create replicas of input shapes. Namely, we work within the Signal-passing Tile Assembly Model (STAM), and we provide a universal STAM tile set which is capable of creating unbounded numbers of assemblies of shapes identical to those of input assemblies. The shapes of the input assemblies can be arbitrary 2-dimensional hole-free shapes. This improves previous shape replication results in self-assembly that required models in which multiple assembly stages and/or bins were required, and the shapes which could be replicated were more constrained, as well as a previous version of this result that required input shapes to be represented at scale factor 2. [ABSTRACT FROM AUTHOR]

Wireless Sensor Network applications profit from or necessitate the use of leaders, elected on the basis of some quantifiable and comparable criteria. Hence, a panoply of leader election algorithms have been proposed in the literature. Even though most of the algorithms focus on lowering the control message (messages needed to elect a leader) count, there has been almost no focus on ensuring high availability of a leader despite various types of failures like battery exhaustion and sensor crash, especially, in the scenarios of rescue and warfare, where the absence of the leader, even for a short duration, may lead to havoc. To overcome the problem of electing a unique leader, in this paper, we propose an efficient protocol for electing k-leaders in a wireless sensor network. The proposed protocol, called SEALEA for A Scalable Leader Election protocol, is distributed and, by means of the exchange of messages among neighbors, terminates after informing the elected nodes. The correctness of the protocol is proven through simulation. SEALEA is implemented on the OMNET++ simulator. Our experimental evaluations demonstrate the effectiveness of SEALEA in determining network leaders swiftly and efficiently. The performance of SEALEA is compared to that of other previously proposed k-leaders election protocols WiLE [1] and K-Top Leader [2]. Results show that SEALEA determines the leader faster and consuming less energy than previous solutions. On average, SEALEA is shown to send 0.845% of the messages sent by WiLE, transmitting 0.87% of the bytes transmitted by that protocol. Against K-TOP, SEALEA sends 19.25% of the messages and transmits only 19.28% of the bytes transmitted by K-TOP. [ABSTRACT FROM AUTHOR]

Raft is a fast, scalable, understandable consensus algorithm widely used in distributed systems. The Leader handles client requests and interacts with other servers to reach a consensus, so a stable, reliable, and powerful Leader is crucial for the cluster. We designed a policy-based voting mechanism to make the elected Leader as reliable as possible. In order to improve the asymmetric relationship between the Followers and Leader, we designed a mechanism to trigger a new round of the election actively so that the Leader node can actively transform into a Follower under certain conditions and enhance the symmetry between servers. Our proposed Raft-PLUS algorithm makes the elected Leader as reliable as possible through four election policies and designed three opposition policies to trigger a new round of the election. To verify the effectiveness of the Raft-PLUS algorithm, we configure different election and opposition policies on 12 servers to simulate the election and opposition process of the Leader and explain the process. To demonstrate the advantages of the Raft-PLUS algorithm, we built key-value stores based on Raft and Raft-PLUS, and we tested the performance of Raft-PLUS and the Raft algorithm in normal and abnormal states. Experimental results show that the Raft-PLUS algorithm has similar write throughput to the Raft algorithm under normal conditions. Regarding the quality of the Leader network changes, the average write throughput of the Raft-PLUS algorithm is 40% higher than that of the Raft algorithm. The Leader's CPU usage fluctuated; the average write throughput of Raft-PLUS was 38% higher than Raft. [ABSTRACT FROM AUTHOR]

We consider an extension to the geometric amoebot model that allows amoebots to form so-called circuits. Given a connected amoebot structure, a circuit is a subgraph formed by the amoebots that permits the instant transmission of signals. We show that such an extension allows for significantly faster solutions to a variety of problems related to programmable matter. More specifically, we provide algorithms for leader election, consensus, compass alignment, chirality agreement, and shape recognition. Leader election can be solved in Θ (log n) rounds, with high probability (w.h.p.), consensus in O (1) rounds, and both, compass alignment and chirality agreement, can be solved in O (log n) rounds, w.h.p. For shape recognition, the amoebots have to decide whether the amoebot structure forms a particular shape. We show that the amoebots can detect a shape composed of triangles within O (1) rounds. Finally, we show how the amoebots can detect a parallelogram with linear and polynomial side ratio within Θ (log n) rounds, w.h.p. [ABSTRACT FROM AUTHOR]

This paper presents a deterministic and indulgent algorithm for leader election. Our algorithm is adapted to large-scale systems with the primary objective of faster execution time to elect a leader. We modify the single-decree Paxos consensus (Synod) algorithm such that proposers proposing the same value do not conflict with each other. Although any process in the system can initiate election, we restrict the decision making on electing the leader to a select set of processes A, called acceptors. For a given k ( = A ) acceptors in the system, our algorithm can tolerate up to f = ⌈ k 2 − 1 ⌉ failures in A, and any number of process failures outside A. The restriction on decision making allows our algorithm to scale without compromising on performance. Experimental results show that our algorithm is faster to elect a leader than existing algorithms which are optimised for large-scale systems. We also adapt our algorithm for leader election in Wireless Sensor Networks (WSNs) and Internet of Things (IoTs) and show that it performs better than the existing graph-based techniques employed in these systems. [ABSTRACT FROM AUTHOR]

Summary: In this article, we present two deterministic leader election algorithms for programmable matter on the face‐centered cubic grid. The face‐centered cubic grid is a three‐dimensional 12‐regular infinite grid that represents an optimal way to pack spheres (i.e., spherical particles or modules in the context of the programmable matter) in the three‐dimensional space. While the first leader election algorithm requires a strong hypothesis about the initial configuration of the particles and no hypothesis on the system configurations that the particles are forming, the second one requires fewer hypothesis about the initial configuration of the particles but does not work for all possible particles' arrangement. We also describe a way to compute and assign ℓ‐local identifiers to the particles in this grid with a memory space not dependent on the number of particles. A ℓ‐local identifier is a variable assigned to each particle in such a way that particles at distance at most ℓ each have a different identifier. [ABSTRACT FROM AUTHOR]

Internet of Things (IoT) is the interconnection of thousands of heterogeneous addressable smart objects (i.e., devices embedded with sensors and actuators) with Internet connectivity. Internet of Mobile Things (IoMT) is characterized by considering the mobility of smart objects. For managing smart objects, it is necessary to provide a middleware. Mobile Hub (M-Hub) is an IoT middleware that collects, processes and distributes data from a large number of smart objects on the edge of the network. M-Hub runs on mobile devices, enabling them to be gateways. It represents an autonomous entity, able to detect a set of objects available in the neighborhood and to monitor them independently of other M-Hubs. Hence, in some situations it may happen that a same object is eligible to be monitored by several M-Hubs. In this context, this paper proposes Neighborhood-aware M-Hub (NAM-Hub), a leader election mechanism integrated to the M-Hub to determine a suitable gateway for each smart object discovered opportunistically. It considers context data gathered from the mobile device to dynamically elect leaders (i.e., a leader and a sub-leader). The proposed solution contributes to take advantage from the resources provided for the mobile gateway and avoids their wastage. The proposed leader election mechanism was tested and evaluated considering its performance and the results were promising, with short detection time and recovery time in the system. [ABSTRACT FROM AUTHOR]

We propose a general scheme to compute tree-based data structures on arbitrary networks. This scheme is self-stabilizing, silent, and despite its generality, also efficient. It is written in the locally shared memory model with composite atomicity assuming the distributed unfair daemon, the weakest scheduling assumption of the model. Its stabilization time is in at most 4 n maxCC rounds, where n maxCC is the maximum number of processes in any connected component of the network. We illustrate the versatility and efficiency of our approach by proposing several instantiations solving classical spanning tree problems such as DFS, BFS, shortest-path, or unconstrained spanning tree/forest constructions, as well as other fundamental problems like leader election or finding maximum-bottleneck-bandwidth paths. We also exhibit polynomial upper bounds on its stabilization time in steps and process moves, holding for a large class of instantiations. In several cases, the polynomial step and move complexities we obtain for those instantiations match the best known complexities of existing algorithms, despite the latter being dedicated to particular problems. Furthermore, a significant set of instantiations of our scheme requires only bounded memory space per process. This set includes, but is not limited to, DFS, BFS, and shortest-path spanning tree constructions. [ABSTRACT FROM AUTHOR]

This paper discusses the game theory based consensus learning in unidirectional rings. Distributed systemfindstheambiguousprocessorsorrationalagentsinthesamewayasgametheoryfindsambiguous players. The rational agents are those processors which deviate from the protocol and instead they follow their own path in order to fulfil their utility. In a bidirectional rings, the rational agents can be detected easily by each neighbourhood agents. But, in unidirectional case, the rational agents cannot be easily detected. This limits the honest agent to detect incorrect IDs sent by adversarial agents. So, our main focus is on the asynchronous unidirectional ring. We study the shortcomings of the protocol presented in (Abrahametal.2013) and (Afeketal.2014). In this paper, we present an improved version of the protocol based on Game Theory which is more resilient to the previous one, by applying invasion of adversarial processors and by proving it to be resilient in presence of adversaries. [ABSTRACT FROM AUTHOR]