An anonymous distributed routing protocol in mobile ad-hoc networks

This paper proposes an efficient anonymous routing protocol for mobile ad hoc networks (MANETs). This protocol considers symmetric and asymmetric links during the wireless communication of MANETs. A MANET is one type of self-organized wireless network that can be formed by several wireless devices such as laptops, tablet PCs, and smartphones. Different wireless transmission ranges of different mobile devices lead to a special communication condition called an asymmetric link. Most research on this topic focuses on providing security and anonymity for the symmetric link without considering the asymmetric link. This paper proposes a novel distributed routing protocol beyond the symmetric and asymmetric links. This protocol guarantees the security, anonymity, and high reliability of an established route by avoiding unreliable intermediate nodes. The routes generated by the proposed protocol are shorter than previous research. The proposed protocol enhances MANET performance in assuring security and anonymity.     

Efficient distributed location verification in wireless sensor networks

In wireless sensor networks, reliable location information is not only necessary to event reports but also crucial to network functionalities such as geographic routing, distributed information storage/retrieval. However, sensors could be compromised by adversaries to claim arbitrary locations to disrupt the normal network operation. Thus, location verification should be carried out for security considerations. Due to the importance of the problem, we propose a highly efficient algorithm that effectively detects false location claims from compromised sensors. Extensive analysis and simulation results demonstrate that our algorithm is energy-efficient and resilient against adversaries.     

Computing functions on asynchronous anonymous networks

In an “anonymous” network the processors have no identity numbers. We investigate the problem of computing a given functionf on an asynchronous anonymous network in the sense that each processor computesf(I) for any inputI = (I(v ₁),...,I(v _n )), whereI(v _i) is the input to processorv _i ,i = 1, 2,...,n. We address the following three questions: (1) What functions are computable on a given network? (2) Is there a “universal” algorithm which, given any networkG and any functionf computable onG as inputs, computesf onG? (3) How can one find lower bounds on the message complexity of computing various functions on anonymous networks? We give a necessary and sufficient condition for a function to be computable on an asynchronous anonymous network, and present a universal algorithm for computingf(I) on any networkG, which acceptsG andf computable onG, as well as {I(v _i )}, as inputs. The universal algorithm requiresO(mn) messages in the worst case, wheren andm are the numbers of processors and links in the network, respectively. We also propose a method for deriving a lower bound on the number of messages necessary to solve the above problem on asynchronous anonymous networks.     

Circuit-switched broadcasting in torus networks

In this paper we present three broadcast algorithms and lower bounds on the three main components of the broadcast time for 2-dimensional torus networks (wrap-around meshes) that use synchronous circuit-switched routing. The first algorithm is based on a recursive tiling of a torus and is optimal in terms of both phases and intermediate switch settings when the start-up time to initiate message transmissions is the dominant cost. It is the first broadcast algorithm to match the lower bound of log₅ N on number of phases (where N is the number of nodes). The second and third algorithms are hybrids which combine circuit-switching with the pipelining and arc-disjoint spanning trees techniques that are commonly used to speed up store-and-forward routing. When the propagation time of messages through the network is significant, our hybrid algorithms achieve close to optimal performance in terms of phases, intermediate switch settings, and total transmission time. They are the first algorithms to achieve this performance in terms of all three parameters simultaneously     

Open source verification in an anonymous volunteer network

An ‘open’ certification process is characterised here that is not based on any central agency, but rather on the option for any party to confirm any part of the certification process at will. The model for this paradigm has been a distributed, piece-wise, semantic audit carried out on the Linux kernel source code using a lightweight formal method.Our goal is a technology that allows open source developers to receive formally backed certifications for their project, in quid pro quo exchanges of resources and expertise with other developers within an amorphous and anonymous cloud of volunteers. To help ensure the integrity of the results, identifying details such as subroutine and variable names are not included in the data sent for analysis, each part of the computation is repeated many times at different sites, and checkpoint information is generated that enables independent checks to be carried out without starting from scratch each time.     

Circuit-switched broadcasting in torus and mesh networks

We consider the problem of broadcasting on torus and mesh networks using circuit-switched, half-duplex, and link-bound communication. In this paper, we obtain an optimal broadcasting algorithm that uses pd time steps for a d-dimensional torus with (2d+1)^p nodes in each side of the torus. Using this algorithm, we show that a broadcasting on a d-dimensional mesh with the same size can be done in pd+p+d-1 time steps     

Finding routes in anonymous sensor networks

We consider networks of anonymous sensors and address the problem of constructing routes for the delivery of information from a group of sensors in response to a query by a sink. In order to circumvent the restrictions imposed by anonymity, we rely on using the power level perceived by the sensors in the query from the sink. We introduce a simple distributed algorithm to achieve the building of routes to the sink and evaluate its performance by means of simulations.     

Computing on anonymous networks. II. Decision and membershipproblems

For pt I see ibid. In anonymous networks, the processors do not have identity numbers. In Part I of this paper, we characterized the classes of networks on which some representative distributed computation problems are solvable under different conditions. A new graph property called symmetricity played a central role in our analysis of anonymous networks. In Part II, we turn our attention to the computational complexity issues. We first discuss the complexity of determining the symmetricity of a given graph, and then that of testing membership in each of the 16 classes of anonymous networks defined in Part I. It turns out that, depending on the class, the complexity varies from P-time to NP-complete or co-NP-complete     

Activating anonymous ad hoc radio networks

We consider the task of activating an anonymous ad hoc radio network from a single source, by a deterministic algorithm. In the beginning only the source is active and has to activate other nodes by disseminating messages throughout the network. Nodes of the network do not know its topology and they do not have distinct labels. In such networks some nodes are impossible to reach. A node in a network is accessible if it can be activated by some (possibly network-dependent) deterministic algorithm. We show that the problem of recognizing whether a given node of an anonymous radio network is accessible, can be solved in polynomial time for the synchronous scenario. A deterministic wake-up algorithm for ad hoc networks is universal if it activates all accessible nodes in all networks. We study the question of the existence of such a universal activating algorithm. For synchronous communication we design a universal activating algorithm, and for asynchronous communication we show that no such algorithm exists. Research partially supported by NSERC discovery grant and by the Research Chair in Distributed Computing at the Université du Québec en Outaouais. A preliminary version of this paper (with title “Waking up anonymous ad hoc radio networks”) appeared in the Proceedings of the 19th International Symposium on Distributed Computing (DISC 2005), September 2005, Cracow, Poland.     

Optimal multicast communication in wormhole-routed torus networks

This paper presents efficient algorithms that implement one-to-many, or multicast, communication in wormhole-routed torus networks. By exploiting the properties of the switching technology and the use of virtual channels, a minimum-time multicast algorithm is presented for n-dimensional torus networks that use deterministic, dimension-ordered routing of unicast messages. The algorithm can deliver a multicast message to m-1 destinations in [log₂ m] message-passing steps, while avoiding contention among the constituent unicast messages. Performance results of a simulation study on torus networks with up to 4096 nodes are also given     

The hamiltonicity of generalized honeycomb torus networks

Yang et al. (2004) [8] proved that the generalized honeycomb torus GHT(m,n,d)$\mathit{GHT}(m,n,d)$ is hamiltonian, but their proofs are not sufficient when the width m   is odd. In this paper, we propose a series of procedures for constructing hamiltonian cycles in generalized honeycomb tori, which apply to every instance of GHT(m,n,d)$\mathit{GHT}(m,n,d)$ with odd width m.     

Efficient distributed snapshots in an anonymous asynchronous message-passing system

We present a global snapshot algorithm with concurrent initiators, with termination detection in an anonymous asynchronous distributed message-passing system having FIFO channels. In anonymous systems, process identifiers are not available and an algorithm cannot use process identifiers in its operation. Such systems arise in several domains due to a variety of reasons. In the proposed snapshot algorithm for anonymous systems, each instance of algorithm initiation is identified by a random number (nonce); however, this is not used as an address in any form of communication. In the algorithm, each process can determine an instant when the local snapshot recordings at all the processes have terminated. This is a challenging problem when an algorithm cannot use process identifiers and a process does not know the number of processes in the system or the diameter of the network and cannot use a predefined topology overlay on the network, because there is no easy way to identify the global termination condition. The message complexity of our algorithm is (cn²)$\left(c{n}^2\right)$, where c$c$ is the number of concurrent initiators and n$n$ is the number of processes in the system, which is much better than that of the algorithm by Chalopin et al. (2012) [6]. Further, the algorithm by Chalopin et al. also requires knowledge of the network diameter.     

Computing on anonymous networks. I. Characterizing the solvablecases

In anonymous networks, the processors do not have identity numbers. We investigate the following representative problems on anonymous networks: (a) the leader election problem, (b) the edge election problem, (c) the spanning tree construction problem, and (d) the topology recognition problem. On a given network, the above problems may or may not be solvable, depending on the amount of information about the attributes of the network made available to the processors. Some possibilities are: (1) no network attribute information at all is available, (2) an upper bound on the number of processors in the network is available, (3) the exact number of processors in the network is available, and (4) the topology of the network is available. In terms of a new graph property called “symmetricity”, in each of the four cases (1)-(4) above, we characterize the class of networks on which each of the four problems (a)(d) is solvable. We then relate the symmetricity of a network to its 1- and 2-factors     

Electrostatic force computation for bio-molecules on supercomputers with torus networks

We present an application of the Ewald algorithm for electrostatic force computation on a supercomputer with a torus network, like those on QCDOC and BlueGene/L. Typical bio-molecular systems have thousands, possibly millions of atoms interacting, with simulation time ranging from microseconds to milliseconds. The most dominant time consuming calculation for bio-molecules is the electrostatic interactions. The importance of an efficient all-gather method is discussed, in particular for QCDOC since it does not have a network specific for global communication like the tree network on BlueGene/L. In addition, we demonstrate the ability for QCDOC to run non QCD (Quantum Chromodynamics) applications, in particular, electrostatic force computation on bio-molecules.     

Computer networks and distributed systems

Three major justifications for distributed computing-sharing physically distributed resources, combining computers for fast solutions, and providing reliability through replication-are discussed. Distributed computing milestones from 1969 to 1991 are examined, focusing on the ARPAnet national research network, Ethernet and token-ring local area networks, and workstation networks united by distributed systems software. Three themes that dominate current trends in distributed systems and computer networks are examined. They comprise tapping the immense data-carrying potential of optical fibers, efficiently using tightly coupled networks of thousands of computers, and making network access inexpensive so many people will buy services. Developments for the next decade are predicted by extrapolating from these trends