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: We here present the Forward Planning Situated Protocol (FPSP), for scalable, energy efficient and fault tolerant data propagation in situated wireless sensor networks. To deal with the increased complexity of such deeply networked sensor systems, instead of emphasizing on a particular aspect of the services provided, i.e. either for low-energy periodic, or low-latency event-driven, or high-success query-based sensing, FPSP uses two novel mechanisms that allow the network operator to adjust the performance of the protocol in terms of energy, latency and success rate on a per-task basis. We emphasize on distributedness, direct or indirect interactions among relatively simple agents, flexibility and robustness.
The protocol operates by employing a series of plan & forward phases through which devices self-organize into forwarding groups that propagate data over discovered paths. FPSP performs a limited number of long range, high power data transmissions to collect information regarding the neighboring devices. The acquired information, allows to plan a (parameterizable long by {\"e}) sequence of short range, low power transmissions between nearby particles, based on certain optimization criteria. All particles that decide to respond (based on local criteria) to these long range transmissions enter the forwarding phase during which information is propagated via the acquired plan. Clearly, the duration of the forwarding phases is characterized by the parameter {\"e}, the transmission medium and the processing speed of the devices. In fact the parameter {\"e} provides a mechanism to adjust the protocol performance in terms of the latency--energy trade-off. By reducing {\"e} the latency is reduced at the cost of spending extra energy, while by increasing {\"e}, the energy dissipation is reduced but the latency is increased.
To control the success rate--energy trade-off, particles react locally on environment and context changes by using a set of rules that are based on response thresholds that relate individual-level plasticity with network-level resiliency, motivated by the nature-inspired method for dividing labor, a metaphor of social insect behavior for solving problems [1]. Each particle has an individual response threshold {\`E} that is related to the "local" density (as observed by the particle, [2]); particles engage in propagation of events when the level of the task-associated stimuli exceeds their thresholds. Let s be the intensity of a stimulus associated with a particular sensing task, set by the human authorities. We adopt the response function T{\`e}(s) = snover sn + {\`e}n, the probability of performing the task as a function of s, where n > 1 determines the steepness of the threshold. Thus, when {\`e} is small (i.e. the network is sparse) then the response probability increases; when s increases (i.e. for critical sensing tasks) the response probability increases as well.
This role-based approach where a selective number of devices do the high cost planning and the rest of the network operates in a low cost state leads to systems that have increased energy efficiency and high fault-tolerance since these long range planning phases allow to bypass obstacles (where no sensors are available) or faulty sensors (that have been disabled due to power failure or other natural events).
Abstract: Grid Infrastructures have been used to solve large scale scientific problems that do not have special requirements on QoS. However, the introduction and success of the Grids in commercial applications as well, entails the provision of QoS mechanisms which will allow for meeting the special requirements of the users-customers. In this paper we present an advanced Grid Architecture which incorporates appropriate mechanisms so as to allow guarantees of the diverse and contradictory usersrsquo QoS requirements. We present a runtime estimation model, which is the heart of any scheduling and resource allocation algorithm, and we propose a scheme able to predict the runtime of submitted jobs for any given application on any computer by introducing a general prediction model. Experimental results are presented which indicate the robustness and reliability of the proposed architecture. The scheme has been implemented in the framework of GRIA IST project (Grid Resources for Industrial Applications).
Abstract: We conduct an experimental study for the timetabling proble
m in a public railway network
under disruptions. We investigate three bicriteria optimi
zation problems introduced recently
that model the robustness of a timetable towards delays. We e
xperimentally evaluated these
models against various waiting time rules at stations. Our r
esults constitute the first proofs-
of-concept for these new robust timetabling approaches.
Abstract: We conduct an experimental study for a fundamental case of the timetabling problem in a public railway network under disruptions. Three bicriteria optimazation problems, modeling the robustness of the timetable towards delays, are experimentally evaluated against various waiting time rules at stations. Our results constitute the first proofs-of-concept for these models.
Abstract: We conduct an experimental study for the timetabling problem in a public railway network under disruptions. We investigate three bicriteria optimization problems introduced recently that model the robustness of a timetable towards delays. We experimentally evaluated these models against various waiting time rules at stations. Our results constitute the rst proofs-of-concept for these new robust timetabling approaches.
Abstract: We study here the problem of determining the majority type in an arbitrary connected network, each vertex of which has initially two possible types. The vertices may have a few additional possible states and can interact in pairs only if they share an edge. Any (population) protocol is required to stabilize in the initial majority. We first present and analyze a protocol with 4 states per vertex that always computes the initial majority value, under any fair scheduler. As we prove, this protocol is optimal, in the sense that there is no population protocol that always computes majority with fewer than 4 states per vertex. However this does not rule out the existence of a protocol with 3 states per vertex that is correct with high probability. To this end, we examine a very natural majority protocol with 3 states per vertex, introduced in [Angluin et al. 2008] where its performance has been analyzed for the clique graph. We study the performance of this protocol in arbitrary networks. We prove that, when the two initial states are put uniformly at random on the vertices, this protocol converges to the initial majority with probability higher than the probability of converging to the initial minority. In contrast, we present an infinite family of graphs, on which the protocol can fail whp, even when the difference between the initial majority and the initial minority is n−Θ(lnn). We also present another infinite family of graphs in which the protocol of Angluin et al. takes an expected exponential time to converge. These two negative results build upon a very positive result concerning the robustness of the protocol on the clique. Surprisingly, the resistance of the clique to failure causes the failure in general graphs. Our techniques use new domination and coupling arguments for suitably defined processes whose dynamics capture the antagonism between the states involved.
Abstract: Evolutionary Game Theory is the study of strategic interactions
among large populations of agents who base their decisions on simple,
myopic rules. A major goal of the theory is to determine broad classes
of decision procedures which both provide plausible descriptions of selfish
behaviour and include appealing forms of aggregate behaviour. For example,
properties such as the correlation between strategies¢ growth rates
and payoffs, the connection between stationary states and the well-known
game theoretic notion of Nash equilibria, as well as global guarantees of
convergence to equilibrium, are widely studied in the literature.
Our paper can be seen as a quick introduction to Evolutionary Game
Theory, together with a new research result and a discussion of many
algorithmic and complexity open problems in the area. In particular, we
discuss some algorithmic and complexity aspects of the theory, which
we prefer to view more as Game Theoretic Aspects of Evolution rather
than as Evolutionary Game Theory, since the term “evolution” actually
refers to strategic adaptation of individuals¢ behaviour through a
dynamic process and not the traditional evolution of populations. We
consider this dynamic process as a self-organization procedure which,
under certain conditions, leads to some kind of stability and assures robustness
against invasion. In particular, we concentrate on the notion of
the Evolutionary Stable Strategies (ESS). We demonstrate their qualitative
difference from Nash Equilibria by showing that symmetric 2-person
games with random payoffs have on average exponentially less ESS than
Nash Equilibria. We conclude this article with some interesting areas of
future research concerning the synergy of Evolutionary Game Theory
and Algorithms.
Abstract: Evolutionary Game Theory is the study of strategic interactions among large populations of agents who base their decisions on simple, myopic rules. A major goal of the theory is to determine broad classes of decision procedures which both provide plausible descriptions of selfish behaviour and include appealing forms of aggregate behaviour. For example, properties such as the correlation between strategies' growth rates and payoffs, the connection between stationary states and Nash equilibria and global guarantees of convergence to equilibrium, are widely studied in the literature. In this paper we discuss some computational aspects of the theory, which we prefer to view more as Game Theoretic Aspects of Evolution than Evolutionary Game Theory, since the term "evolution" actually refers to strategic adaptation of individuals ' behaviour through a dynamic process and not the traditional evolution of populations. We consider this dynamic process as a self-organization procedure, which under certain conditions leads to some kind of stability and assures robustness against invasion.
Abstract: The problem of robust line planning requests for a set of
origin-destination paths (lines) along with their frequencies in an underlying
railway network infrastructure, which are robust to
uctuations of
real-time parameters of the solution.
In this work, we investigate a variant of robust line planning stemming
from recent regulations in the railway sector that introduce competition
and free railway markets, and set up a new application scenario: there is
a (potentially large) number of line operators that have their lines xed
and operate as competing entities struggling to exploit the underlying
network infrastructure via frequency requests, while the management of
the infrastructure itself remains the responsibility of a single (typically
governmental) entity, the network operator.
The line operators are typically unwilling to reveal their true incentives.
Nevertheless, the network operator would like to ensure a fair (or, socially
optimal) usage of the infrastructure, e.g., by maximizing the (unknown to
him) aggregate incentives of the line operators. We show that this can be
accomplished in certain situations via a (possibly anonymous) incentivecompatible
pricing scheme for the usage of the shared resources, that is
robust against the unknown incentives and the changes in the demands
of the entities. This brings up a new notion of robustness, which we
call incentive-compatible robustness, that considers as robustness of the
system its tolerance to the entities' unknown incentives and elasticity
of demands, aiming at an eventual stabilization to an equilibrium point
that is as close as possible to the social optimum.
Abstract: We consider a fundamental problem, called QoS-aware Multicommodity Flow, for assessing robustness in transportation planning.
It constitutes a natural generalization of the weighted multicommodity
flow problem, where the demands and commodity values are elastic to
the Quality-of-Service (QoS) characteristics of the underlying network.
The problem is also fundamental in other domains beyond transportation
planning. In this work, we provide an extensive experimental study of
two FPTAS for the QoS-aware Multicommodity Flow Problem enhanced
with several heuristics, and show the superiority of a new heuristic we
introduce here.
Abstract: We consider the line planning problem in public transporta-
tion, under a robustness perspective. We present a mechanism for robust
line planning in the case of multiple line pools, when the line operators
have a different utility function per pool. We conduct an experimen-
tal study of our mechanism on both synthetic and real-world data that
shows fast convergence to the optimum. We also explore a wide range of
scenarios, varying from an arbitrary initial state (to be solved) to small
disruptions in a previously optimal solution (to be recovered). Our ex-
periments with the latter scenario show that our mechanism can be used
as an online recovery scheme causing the system to re-converge to its
optimum extremely fast.
Abstract: The problem of robust line planning requests for a set of
origin-destination paths (lines) along with their tra±c rates (frequencies)
in an underlying railway network infrastructure, which are robust to
°uctuations of real-time parameters of the solution.
In this work, we investigate a variant of robust line planning stemming
from recent regulations in the railway sector that introduce competition
and free railway markets, and set up a new application scenario: there is
a (potentially large) number of line operators that have their lines ¯xed
and operate as competing entities struggling to exploit the underlying
network infrastructure via frequency requests, while the management of
the infrastructure itself remains the responsibility of a single (typically
governmental) entity, the network operator.
The line operators are typically unwilling to reveal their true incentives.
Nevertheless, the network operator would like to ensure a fair (or, socially
optimal) usage of the infrastructure, e.g., by maximizing the (unknown to
him) aggregate incentives of the line operators. We show that this can be
accomplished in certain situations via a (possibly anonymous) incentive-
compatible pricing scheme for the usage of the shared resources, that is
robust against the unknown incentives and the changes in the demands
of the entities. This brings up a new notion of robustness, which we
call incentive-compatible robustness, that considers as robustness of the
system its tolerance to the entities' unknown incentives and elasticity
of demands, aiming at an eventual stabilization to an equilibrium point
that is as close as possible to the social optimum.
