Population protocol, Diffuse computation, Sensor networks, Passive mobility, Computational complexity, Space hierarchy, Symmetriccomputation, Complexity class
Abstract: Many of the network security protocols employed today utilize symmetric block ciphers (DES, AES and CAST etc). The majority of the symmetric block ciphers implement the crucial substitution operation using look up tables, called substitution boxes. These structures should be highly nonlinear and have bit dispersal, i.e. avalanche, properties in order to render the cipher with resistant to cryptanalysis attempts, such as linear and differential cryptanalysis. Highly secure substitution boxes can be constructed using particular Boolean functions as components that have certain mathematical properties which enhance the robustness of the whole cryptoalgorithm. However, enforcing these properties on SBoxes is a highly computationally intensive task. In this paper, we present a distributed algorithm and its implementation on a computing cluster that accelerates the construction of secure substitution boxes with good security properties. It is fully parametric since it can employ any class of Boolean functions with algorithmically definable properties and can construct SBoxes of arbitrary sizes. We demonstrate the efficiency of the distributed algorithm implementation compared to its sequential counterpart, in a number of experiments.
Abstract: This work focuses on the computational power of the Mediated Population Protocol model on complete communication graphs and initially identical edges (SMPP). In particular, we investigate the class MPS of all predicates that are stably computable by the SMPP model. It is already known that MPS is in the symmetric subclass of NSPACE(n^2). Here we prove that this inclusion holds with equality, thus, providing the following exact characterization for MPS: A predicate is in MPS iff it is symmetric and is in NSPACE(n^2).
Abstract: We study the partially eponymous model of distributed computation, which simultaneously
generalizes the anonymous and the eponymous models. In this model, processors have
identities, which are neither necessarily all identical (as in the anonymous model) nor
necessarily unique (as in the eponymous model). In a decision problem formalized as a
relation, processors receive inputs and seek to reach outputs respecting the relation. We
focus on the partially eponymous ring, and we shall consider the computation of circularly
symmetric relations on it. We consider sets of rings where all rings in the set have the same
multiset of identity multiplicities.
We distinguish between solvability and computability: in solvability, processors are
required to always reach outputs respecting the relation; in computability, they must
do so whenever this is possible, and must otherwise report impossibility.
We present a topological characterization of solvability for a relation on a set of rings,
which can be expressed as an efficiently checkable, number-theoretic predicate.
We present a universal distributed algorithm for computing a relation on a set of
rings; it runs any distributed algorithm for constructing views, followed by local steps.
We derive, as our main result, a universal upper bound on the message complexity to
compute a relation on a set of rings; this bound demonstrates a graceful degradation
with the Least Minimum Base, a parameter indicating the degree of least possible
eponymity for a set of rings. Thereafter, we identify two cases where a relation can be
computed on a set of rings, with rings of size n, with an efficient number of O .n lg n/
messages.
Abstract: We extend here the Population Protocol model of Angluin et al. [2004,2006] in order to model more powerful networks of resource-limited agents that are possibly mobile. The main feature of our extended model, called the Mediated Population Protocol (MPP) model, is to allow edges of the communication graph to have states that belong to a constant size set. We then allow the protocol rules for pairwise interactions to modify the corresponding edge state. Protocol specifications preserve both uniformity and anonymity. We first focus on the computational power of the MPP model on complete communication graphs and initially identical edges. We provide the following exact characterization for the class MPS of stably computable predicates: A predicate is in MPS iff it is symmetric and is in NSPACE(n^2)$. We finally ignore the input to the agents and study MPP's ability to compute graph properties.
Abstract: Wireless Sensor Networks (WSNs) constitute a recent and promising new
technology that is widely applicable. Due to the applicability of this
technology and its obvious importance for the modern distributed
computational world, the formal scientific foundation of its inherent laws
becomes essential. As a result, many new computational models for WSNs
have been proposed. Population Protocols (PPs) are a special category of
such systems. These are mainly identified by three distinctive
characteristics: the sensor nodes (agents) move passively, that is, they
cannot control the underlying mobility pattern, the available memory to
each agent is restricted, and the agents interact in pairs. It has been
proven that a predicate is computable by the PP model iff it is
semilinear. The class of semilinear predicates is a fairly small class. In
this work, our basic goal is to enhance the PP model in order to improve
the computational power. We first make the assumption that not only the
nodes but also the edges of the communication graph can store restricted
states. In a complete graph of n nodes it is like having added O(n2)
additional memory cells which are only read and written by the endpoints
of the corresponding edge. We prove that the new model, called Mediated
Population Protocol model, can operate as a distributed nondeterministic
Turing machine (TM) that uses all the available memory. The only
difference from a usual TM is that this one computes only symmetric
languages. More formally, we establish that a predicate is computable by
the new model iff it is symmetric and belongs to NSPACE(n2). Moreover, we
study the ability of the new model to decide graph languages (for general
graphs). The next step is to ignore the states of the edges and provide
another enhancement straight away from the PP model. The assumption now is
that the agents are multitape TMs equipped with infinite memory, that can
perform internal computation and interact with other agents, and we define
space-bounded computations. We call this the Passively mobile Machines
model. We prove that if each agent uses at most f(n) memory for f(n)={\`U}(log
n) then a predicate is computable iff it is symmetric and belongs to
NSPACE(nf(n)). We also show that this is not the case for f(n)=o(log n).
Based on these, we show that for f(n)={\`U}(log n) there exists a space
hierarchy like the one for classical symmetric TMs. We also show that the
latter is not the case for f(n)=o(loglog n), since here the corresponding
class collapses in the class of semilinear predicates and finally that for
f(n)={\`U}(loglog n) the class becomes a proper superset of semilinear
predicates. We leave open the problem of characterizing the classes for
f(n)={\`U}(loglog n) and f(n)=o(log n).
Abstract: We propose a new theoretical model for passively mobile Wireless Sensor Networks, called PM, standing for Passively mobile Machines. The main modification w.r.t. the Population Protocol model [Angluin et al. 2006] is that agents now, instead of being automata, are Turing Machines. We provide general definitions for unbounded memories, but we are mainly interested in computations upper-bounded by plausible space limitations. However, we prove that our results hold for more general cases. We focus on \emph{complete interaction graphs} and define the complexity classes PMSPACE(f(n)) parametrically, consisting of all predicates that are stably computable by some PM protocol that uses O(f(n)) memory in each agent. We provide a protocol that generates unique identifiers from scratch only by using O(log n) memory, and use it to provide an exact characterization of the classes PMSPACE(f(n)) when f(n) = Ω(log n): they are precisely the classes of all symmetric predicates in NSPACE(nf(n)). As a consequence, we obtain a space hierarchy of the PM model when the memory bounds are Ω(log n). We next explore the computability of the PM model when the protocols use o(loglog n) space per machine and prove that SEM = PMSPACE(f(n)) when f(n) = o(loglog n), where SEM denotes the class of the semilinear predicates. Finally, we establish that the minimal space requirement for the computation of non-semilinear predicates is O(log log n).
Abstract: We propose a new theoretical model for passively mobile Wireless Sensor Networks, called PM, standing for Passively mobile Machines. The main modification w.r.t. the Population Protocol model [Angluin et al. 2006] is that the agents now, instead of being automata, are Turing Machines. We provide general definitions for unbounded memories, but we are mainly interested in computations upper-bounded by plausible space limitations. However, we prove that our results hold for more general cases. We focus on complete interaction graphs and define the complexity classes PMSPACE(f(n)) parametrically, consisting of all predicates that are stably computable by some PM protocol that uses O(f(n)) memory in each agent. We provide a protocol that generates unique identifiers from scratch only by using O(log n) memory, and use it to provide an exact characterization of the classes PMSPACE(f(n)) when f(n)=Omega(log n): they are precisely the classes of all symmetric predicates in NSPACE(nf(n)). As a consequence, we obtain a space hierarchy of the PM model when the memory bounds are Omega(log n). Finally, we establish that the minimal space requirement for the computation of non-semilinear predicates is O(log log n).
Abstract: We study computational and coordination efficiency issues of
Nash equilibria in symmetric network congestion games. We first propose
a simple and natural greedy method that computes a pure Nash equilibrium
with respect to traffic congestion in a network. In this algorithm
each user plays only once and allocates her traffic to a path selected via
a shortest path computation. We then show that this algorithm works
for series-parallel networks when users are identical or when users are of
varying demands but have the same best response strategy for any initial
network traffic. We also give constructions where the algorithm fails if
either the above condition is violated (even for series-parallel networks)
or the network is not series-parallel (even for identical users). Thus, we
essentially indicate the limits of the applicability of this greedy approach.
We also study the price of anarchy for the objective of maximum
latency. We prove that for any network of m uniformly related links and
for identical users, the price of anarchy is {\`E}( logm
log logm).
Abstract: We consider a strategic game with two classes of confronting
randomized players on a graph G(V,E): {\'i} attackers, each choosing vertices
and wishing to minimize the probability of being caught, and a
defender, who chooses edges and gains the expected number of attackers
it catches. The Price of Defense is the worst-case ratio, over all Nash
equilibria, of the optimal gain of the defender over its gain at a Nash equilibrium.
We provide a comprehensive collection of trade-offs between the
Price of Defense and the computational efficiency of Nash equilibria.
– Through reduction to a Two-Players, Constant-Sum Game, we prove
that a Nash equilibrium can be computed in polynomial time. The
reduction does not provide any apparent guarantees on the Price of
Defense.
– To obtain such, we analyze several structured Nash equilibria:
• In a Matching Nash equilibrium, the support of the defender is
an Edge Cover. We prove that they can be computed in polynomial
time, and they incur a Price of Defense of {\'a}(G), the
Independence Number of G.
• In a Perfect Matching Nash equilibrium, the support of the defender
is a Perfect Matching. We prove that they can be computed
in polynomial time, and they incur a Price of Defense of
|V |
2 .
• In a Defender Uniform Nash equilibrium, the defender chooses
uniformly each edge in its support. We prove that they incur a
Price of Defense falling between those for Matching and Perfect
Matching Nash Equilibria; however, it is NP-complete to decide
their existence.
• In an Attacker Symmetric and Uniform Nash equilibrium, all
attackers have a common support on which each uses a uniform
distribution. We prove that they can be computed in polynomial
time and incur a Price of Defense of either
|V |
2 or {\'a}(G).