On the Complexity of Universal Leader Election

Electing a leader is a fundamental task in distributed computing. In its implicit version, only the leader must know who is the elected leader. This article focuses on studying the message and time complexity of randomized implicit leader election in synchronous distributed networks. Surprisingly, the most "obvious" complexity bounds have not been proven for randomized algorithms. In particular, the seemingly obvious lower bounds of Ω(m) messages, where m is the number of edges in the network, and Ω(D) time, where D is the network diameter, are nontrivial to show for randomized (Monte Carlo) algorithms. (Recent results, showing that even Ω(n), where n is the number of nodes in the network, is not a lower bound on the messages in complete networks, make the above bounds somewhat less obvious). To the best of our knowledge, these basic lower bounds have not been established even for deterministic algorithms, except for the restricted case of comparison algorithms, where it was also required that nodes may not wake up spontaneously and that D and n were not known. We establish these fundamental lower bounds in this article for the general case, even for randomized Monte Carlo algorithms. Our lower bounds are universal in the sense that they hold for all universal algorithms (namely, algorithms that work for all graphs), apply to every D, m, and n, and hold even if D, m, and n are known, all the nodes wake up simultaneously, and the algorithms can make any use of node's identities. To show that these bounds are tight, we present an O(m) messages algorithm. An O(D) time leader election algorithm is known. A slight adaptation of our lower bound technique gives rise to an Ω(m) message lower bound for randomized broadcast algorithms. 

An interesting fundamental problem is whether both upper bounds (messages and time) can be reached simultaneously in the randomized setting for all graphs. The answer is known to be negative in the deterministic setting. We answer this problem partially by presenting a randomized algorithm that matches both complexities in some cases. This already separates (for some cases) randomized algorithms from deterministic ones. As first steps towards the general case, we present several universal leader election algorithms with bounds that tradeoff messages versus time. We view our results as a step towards understanding the complexity of universal leader election in distributed networks.

Microneedle characterisation: the need for universal acceptance criteria and GMP specifications when moving towards commercialisation

With interest in microneedles as a novel drug transdermal delivery system increasing rapidly since the late 1990s (Margetts and Sawyer Contin Educ Anaesthesia Crit Care Pain. 7(5):171-76, 2007), a diverse range of microneedle systems have been fabricated with varying designs and dimensions. However, there are still very few commercially available microneedle products. One major issue regarding microneedle manufacture on an industrial scale is the lack of specific quality standards for this novel dosage form in the context of Good Manufacturing Practice (GMP). A range of mechanical characterisation tests and microneedle insertion analysis techniques are used by researchers working on microneedle systems to assess the safety and performance profiles of their various designs. The lack of standardised tests and equipment used to demonstrate microneedle mechanical properties and insertion capability makes it difficult to directly compare the in use performance of candidate systems. This review highlights the mechanical tests and insertion analytical techniques used by various groups to characterise microneedles. This in turn exposes the urgent need for consistency across the range of microneedle systems in order to promote innovation and the successful commercialisation of microneedle products.

The United Kingdom, the United Nations Human Rights Council and the first cycle of the Universal Periodic Review

The introduction of the Universal Periodic Review (UPR) mechanism as an innovative component of the new Human Rights Council in 2006 has suffered little academic scrutiny. This is partly because it holds as its objective an improvement in human rights situations on the ground, a goal that is difficult to test amongst so many possible causal factors attributable to law reform and policy change, and partly due to the fact that the mechanism has only completed one full cycle of review. This article seeks to remedy this absence of analysis by examining the experience of the United Kingdom during its first review. In doing so, the article first considers the conception of the UPR, before progressing to examine the procedure and recommendations made to the UK by its peers. Finally, the article considers the five year review of the UPR which occurred as a subset of the Human Rights Council Review in 2011 and the resulting changes to the process modalities.

Reclaiming the Radical in Universal Human Rights: Universality as Universalisation

The universality of human rights has been a fiercely contested issue throughout their history. This article contributes to scholarly engagements with the universality of human rights by proposing a re-engagement with this concept in a way that is compatible with the aims of radical politics. Instead of a static attribute or characteristic of rights this article proposes that universality can be thought of as, drawing from Judith Butler, an ongoing process of universalisation. Universality accordingly emerges as a site of powerful contest between competing ideas of what human rights should mean, do or say, and universal concepts are continually reworked through political activity. This leads to a differing conception of rights politics than traditional liberal approaches but, moreover, challenges such approaches. This understanding of universality allows human rights to come into view as potentially of use in interrupting liberal regimes and, crucially, opens possibilities to reclaim the radical in rights.

The Casimir effect in the presence of compactified universal extra dimensions

The Casimir force in a system consisting of two parallel conducting plates in the presence of compactified universal extra dimensions (UXD) is analyzed. The Casimir force with UXDs differs from the force obtained without extra dimensions. A new power law for the Casimir force is derived. By comparison to experimental data the size R of the universal extra dimensions can be restricted to R⩽10 nm for one extra dimension.

Averaged Extended Tree Augmented Naive Classifier

This work presents a new general purpose classifier named Averaged Extended Tree Augmented Naive Bayes (AETAN), which is based on combining the advantageous characteristics of Extended Tree Augmented Naive Bayes (ETAN) and Averaged One-Dependence Estimator (AODE) classifiers. We describe the main properties of the approach and algorithms for learning it, along with an analysis of its computational time complexity. Empirical results with numerous data sets indicate that the new approach is superior to ETAN and AODE in terms of both zero-one classification accuracy and log loss. It also compares favourably against weighted AODE and hidden Naive Bayes. The learning phase of the new approach is slower than that of its competitors, while the time complexity for the testing phase is similar. Such characteristics suggest that the new classifier is ideal in scenarios where online learning is not required.

Learning Extended Tree Augmented Naive Structures

This work proposes an extended version of the well-known tree-augmented naive Bayes (TAN) classifier where the structure learning step is performed without requiring features to be connected to the class. Based on a modification of Edmonds' algorithm, our structure learning procedure explores a superset of the structures that are considered by TAN, yet achieves global optimality of the learning score function in a very efficient way (quadratic in the number of features, the same complexity as learning TANs). We enhance our procedure with a new score function that only takes into account arcs that are relevant to predict the class, as well as an optimization over the equivalent sample size during learning. These ideas may be useful for structure learning of Bayesian networks in general. A range of experiments shows that we obtain models with better prediction accuracy than naive Bayes and TAN, and comparable to the accuracy of the state-of-the-art classifier averaged one-dependence estimator (AODE). We release our implementation of ETAN so that it can be easily installed and run within Weka.

Learning Bounded Tree-Width Bayesian Networks via Sampling

Learning Bayesian networks with bounded tree-width has attracted much attention recently, because low tree-width allows exact inference to be performed efficiently. Some existing methods [12, 14] tackle the problem by using k-trees to learn the optimal Bayesian network with tree-width up to k. In this paper, we propose a sampling method to efficiently find representative k-trees by introducing an Informative score function to characterize the quality of a k-tree. The proposed algorithm can efficiently learn a Bayesian network with tree-width at most k. Experiment results indicate that our approach is comparable with exact methods, but is much more computationally efficient.

Learning Bayesian Networks with Bounded Tree-Width via Guided Search

Bounding the tree-width of a Bayesian network can reduce the chance of overfitting, and allows exact inference to be performed efficiently. Several existing algorithms tackle the problem of learning bounded tree-width Bayesian networks by learning from k-trees as super-structures, but they do not scale to large domains and/or large tree-width. We propose a guided search algorithm to find k-trees with maximum Informative scores, which is a measure of quality for the k-tree in yielding good Bayesian networks. The algorithm achieves close to optimal performance compared to exact solutions in small domains, and can discover better networks than existing approximate methods can in large domains. It also provides an optimal elimination order of variables that guarantees small complexity for later runs of exact inference. Comparisons with well-known approaches in terms of learning and inference accuracy illustrate its capabilities.

Estrategias pedagógicas basadas en el diseño universal para el aprendizaje: una aproximación desde la comunicación educativa

Libro que presenta estrategias pedagógicas para la educación inclusiva en las diferentes etapas educativas como preescolar, básica, media y universitaria.

Observatorio de la accesibilidad universal en la vivienda en España 2013

Estudio elaborado por Fundación ONCE y Vía Libre y cuenta con la colaboración del Comité Español de Representantes de Personas con Discapacidad (CERMI). El objetivo del Observatorio es analizar la accesibilidad del parque de viviendas familiares de uso principal en España, determinar posibles variables que están influyendo en la accesibilidad, proponer recomendaciones orientadas a la mejora y realizar mediciones posteriores para conocer la evolución en este ámbito. Para ello, la investigación se ha abordado desde una metodología cuantitativa, desarrollada a través de encuesta telefónica, que se ha completado con una fase cualitativa previa y una evaluación técnica de la accesibilidad “in situ” de una muestra de vivienda.

La accesibilidad y el diseño universal entendido por todos. De cómo Stephen Hawking viajó por el espacio

La publicación ‘La accesibilidad y el diseño universal entendido por todos. De cómo Stephen Hawking viajó por el espacio’ es un libro al alcance de todos los públicos para acercarse a la accesibilidad universal, al diseño para todos y a la importancia de la igualdad de oportunidades para todas las personas. Sin duda, el autor se esfuerza con este libro en recopilar y sintetizar gran parte del conocimiento que había disperso en la materia, para condensarlo en una obra amena y apta para cualquier persona, independientemente si es profesional de la accesibilidad o está relacionada con el mundo de la discapacidad.

Reflections of universal algebras into semilattices, their Galois theories, and related factorization systems

Estabelecemos uma condição suficiente para a preservação dos produtos finitos, pelo reflector de uma variedade de álgebras universais numa subvariedade, que é, também, condição necessária se a subvariedade for idempotente. Esta condição é estabelecida, seguidamente, num contexto mais geral e caracteriza reflexões para as quais a propriedade de ser semi-exacta à esquerda e a propriedade, mais forte, de ter unidades estáveis, coincidem. Prova-se que reflexões simples e semi-exactas à esquerda coincidem, no contexto das variedades de álgebras universais e caracterizam-se as classes do sistema de factorização derivado da reflexão. Estabelecem-se resultados que ajudam a caracterizar morfismos de cobertura e verticais-estáveis em álgebras universais e no contexto mais geral já referido. Caracterizam-se as classes de morfismos separáveis, puramente inseparáveis e normais. O estudo dos morfismos de descida de Galois conduz a condições suficientes para que o seu par kernel seja preservado pelo reflector.