Search

In Byzantine Agreement (BA), there is a set of $n$ parties, from which up to $t$ can act byzantine. All honest parties must eventually decide on a common value (agreement), which must belong to a set determined by the inputs (validity). Depending on the use case, this set can grow or shrink, leading to various possible desiderata collectively known as validity conditions. Varying the validity property requirement can affect the regime under which BA is solvable. We study how the selected validity property impacts BA solvability in the network-agnostic model, where the network can either be synchronous with up to $t_s$ byzantine parties or asynchronous with up to $t_a \leq t_s$ byzantine parties. We show that for any non-trivial validity property the condition $2t_s + t_a < n$ is necessary for BA to be solvable, even with cryptographic setup. Noteworthy, specializing this claim to $t_a = 0$ gives that $t < n / 2$ is required when one expects a purely synchronous protocol to also work in asynchrony when there are no corruptions. This is especially surprising given that for some validity properties $t < n$ are known to be achievable without the last stipulation. Thereafter, we give necessary and sufficient conditions for a validity property to render BA solvable, both for the case with cryptographic setup and for the one without. This traces the precise boundary of solvability in the network-agnostic model for every validity property. Our proof of sufficiency provides a universal protocol, that achieves BA for a given validity property whenever the provided conditions are satisfied., Comment: Working paper

The distributed computing literature considers multiple options for modeling communication. Most simply, communication is categorized as either synchronous or asynchronous. Synchronous communication assumes that messages get delivered within a publicly known timeframe and that parties' clocks are synchronized. Asynchronous communication, on the other hand, only assumes that messages get delivered eventually. A more nuanced approach, or a middle ground between the two extremes, is given by the partially synchronous model, which is arguably the most realistic option. This model comes in two commonly considered flavors: (i) The Global Stabilization Time (GST) model: after an (unknown) amount of time, the network becomes synchronous. This captures scenarios where network issues are transient. (ii) The Unknown Latency (UL) model: the network is, in fact, synchronous, but the message delay bound is unknown. This work formally establishes that any time-agnostic property that can be achieved by a protocol in the UL model can also be achieved by a (possibly different) protocol in the GST model. By time-agnostic, we mean properties that can depend on the order in which events happen but not on time as measured by the parties. Most properties considered in distributed computing are time-agnostic. The converse was already known, even without the time-agnostic requirement, so our result shows that the two network conditions are, under one sensible assumption, equally demanding.

We consider binary group decision-making under a rich model of liquid democracy recently proposed by Colley, Grandi, and Novaro (2022): agents submit ranked delegation options, where each option may be a function of multiple agents' votes; e.g., "I vote yes if a majority of my friends vote yes." Such ballots are unravelled into a profile of direct votes by selecting one entry from each ballot so as not to introduce cyclic dependencies. We study delegation via monotonic Boolean functions, and two unravelling procedures: MinSum, which minimises the sum of the ranks of the chosen entries, and its egalitarian counterpart, MinMax. We provide complete computational dichotomies: MinSum is hard to compute (and approximate) as soon as any non-trivial functions are permitted, and polynomial otherwise; for MinMax the easiness results extend to arbitrary-arity logical ORs and ANDs taken in isolation, but not beyond. For the classic model of delegating to individual agents, we give asymptotically near-tight algorithms for carrying out the two procedures and efficient algorithms for finding optimal unravellings with the highest vote count for a given alternative. These algorithms inspire novel tie-breaking rules for the setup of voting to change a status quo. We then introduce a new axiom, which can be viewed as a variant of the participation axiom, and use algorithmic techniques developed earlier in the paper to show that it is satisfied by MinSum and a lexicographic refinement of MinMax (but not MinMax itself)., Comment: To appear in AAAI'24

A decade ago, Gerhard Woeginger posed an open problem that became well-known as "Woeginger's Hiking Problem": Consider a group of $n$ people that want to go hiking; everyone expresses preferences over the size of their hiking group in the form of an interval between $1$ and $n$. Is it possible to efficiently assign the $n$ people to a set of hiking subgroups so that every person approves the size of their assigned subgroup? The problem is also known as efficiently deciding if an instance of an anonymous Hedonic Game with interval approval preferences admits a wonderful partition. We resolve the open problem in the affirmative by presenting an $O(n^5)$ time algorithm for Woeginger's Hiking Problem. Our solution is based on employing a dynamic programming approach for a specific rectangle stabbing problem from computational geometry. Moreover, we propose natural, more demanding extensions of the problem, e.g., maximizing the number of satisfied participants and variants with single-peaked preferences, and show that they are also efficiently solvable. Last but not least, we employ our solution to efficiently compute a partition that maximizes the egalitarian welfare for anonymous single-peaked Hedonic Games., Comment: To appear in ICALP 2024; contains omitted material and small writing improvements

An electorate with fully-ranked innate preferences casts approval votes over a finite set of alternatives. As a result, only partial information about the true preferences is revealed to the voting authorities. In an effort to understand the nature of the true preferences given only partial information, one might ask whether the unknown innate preferences could possibly be single-crossing. The existence of a polynomial time algorithm to determine this has been asked as an outstanding problem in the works of Elkind and Lackner. We hereby give a polynomial time algorithm determining a single-crossing collection of fully-ranked preferences that could have induced the elicited approval ballots, or reporting the nonexistence thereof. Moreover, we consider the problem of identifying negative instances with a set of forbidden sub-ballots, showing that any such characterization requires infinitely many forbidden configurations., Comment: To appear in WINE'23; add acknowledgements, change formatting, minor corrections

A group of $n$ agents with numerical preferences for each other are to be assigned to the $n$ seats of a dining table. We study two natural topologies:~circular (cycle) tables and panel (path) tables. For a given seating arrangement, an agent's utility is the sum of their preference values towards their (at most two) direct neighbors. An arrangement is envy-free if no agent strictly prefers someone else's seat, and it is stable if no two agents strictly prefer each other's seats. Recently, it was shown that for both paths and cycles it is NP-hard to decide whether an envy-free arrangement exists, even for symmetric binary preferences. In contrast, we show that, if agents come from a bounded number of classes, the problem is solvable in polynomial time for arbitrarily-valued possibly asymmetric preferences, including outputting an arrangement if possible. We also give simpler proofs of the previous hardness results if preferences are allowed to be asymmetric. For stability, it is known that deciding the existence of stable arrangements is NP-hard for both topologies, but only if sufficiently-many numerical values are allowed. As it turns out, even constructing unstable instances can be challenging in certain cases, e.g., binary values. We completely characterize the existence of stable arrangements based on the number of distinct values in the preference matrix and the number of agent classes. We also ask the same question for non-negative values and give an almost-complete characterization, the most interesting outstanding case being that of paths with two-valued non-negative preferences, for which we experimentally find that stable arrangements always exist and prove it under the additional constraint that agents can only swap seats when sitting at most two positions away. We moreover give a polynomial algorithm for determining a stable arrangement assuming a bounded number of classes., Comment: To appear in WINE'23; preliminary version presented at COMSOC'23

Traditional blockchain design gives miners or validators full control over transaction ordering, i.e., they can freely choose which transactions to include or exclude, as well as in which order. While not an issue initially, the emergence of decentralized finance has introduced new transaction order dependencies allowing parties in control of the ordering to make a profit by front-running others' transactions. In this work, we present the Decentralized Clock Network, a new approach for achieving fair transaction ordering. Users submit their transactions to the network's clocks, which run an agreement protocol that provides each transaction with a timestamp of receipt which is then used to define the transactions' order. By separating agreement from ordering, our protocol is efficient and has a simpler design compared to other available solutions. Moreover, our protocol brings to the blockchain world the paradigm of asynchronous fallback, where the algorithm operates with stronger fairness guarantees during periods of synchronous use, switching to an asynchronous mode only during times of increased network delay., Comment: In Proceedings of 27th International Conference on Principles of Distributed Systems (OPODIS)

An assembly of $n$ voters needs to decide on $t$ independent binary issues. Each voter has opinions about the issues, given by a $t$-bit vector. Anscombe's paradox shows that a policy following the majority opinion in each issue may not survive a vote by the very same set of $n$ voters, i.e., more voters may feel unrepresented by such a majority-driven policy than represented. A natural resolution is to come up with a policy that deviates a bit from the majority policy but no longer gets more opposition than support from the electorate. We show that a Hamming distance to the majority policy of at most $\lfloor (t - 1) / 2 \rfloor$ can always be guaranteed, by giving a new probabilistic argument relying on structure-preserving symmetries of the space of potential policies. Unless the electorate is evenly divided between the two options on all issues, we in fact show that a policy strictly winning the vote exists within this distance bound. Our approach also leads to a deterministic polynomial-time algorithm for finding policies with the stated guarantees, answering an open problem of previous work. For odd $t$, unless we are in the pathological case described above, we also give a simpler and more efficient algorithm running in expected polynomial time with the same guarantees. We further show that checking whether distance strictly less than $\lfloor (t - 1) /2 \rfloor$ can be achieved is NP-hard, and that checking for distance at most some input $k$ is FPT with respect to several natural parameters., Comment: Accepted by AAMAS'23; fixed typos and improved clarity

We introduce two-crossing elections as a generalization of single-crossing elections, showing a number of new results. First, we show that two-crossing elections can be recognized in polynomial time, by reduction to the well-studied consecutive ones problem. We also conjecture that recognizing $k$-crossing elections is NP-complete in general, providing evidence by relating to a problem similar to consecutive ones proven to be hard in the literature. Single-crossing elections exhibit a transitive majority relation, from which many important results follow. On the other hand, we show that the classical Debord-McGarvey theorem can still be proven two-crossing, implying that any weighted majority tournament is inducible by a two-crossing election. This shows that many voting rules are NP-hard under two-crossing elections, including Kemeny and Slater. This is in contrast to the single-crossing case and outlines an important complexity boundary between single- and two-crossing. Subsequently, we show that for two-crossing elections the Young scores of all candidates can be computed in polynomial time, by formulating a totally unimodular linear program. Finally, we consider the Chamberlin-Courant rule with arbitrary disutilities and show that a winning committee can be computed in polynomial time, using an approach based on dynamic programming., Comment: Accepted by the Thirty-First International Joint Conference on Artificial Intelligence (IJCAI 2022); fixed formatting of Figure 2 and swapped \ceil and \floor in Theorems 16 and 17

Manufactured materials usually contain random imperfections due to the fabrication process, e.g., the 3D-printing, casting, etc. These imperfections affect significantly the effective material properties and result in uncertainties in the mechanical response. Numerical analysis of the effects of the imperfections and the uncertainty quantification (UQ) can be often done by use of digital stochastic surrogate material models. In this work, we present a new flexible class of surrogate models depending on a small number of parameters with special focus on two-phase materials. The surrogate models are constructed as the level-set of a linear combination of an intensity field representing the topological shape and a Gaussian perturbation representing the imperfections. The mathematical design parameters of the model are related to physical ones and thus easy to interpret. The calibration of the model parameters is performed using progressive batching sub-sampled quasi-Newton minimization, using a designed distance measure between the synthetic samples and the data. Then, employing a fast sampling algorithm, an arbitrary number of synthetic samples can be generated to use in Monte Carlo type methods. In particular, we illustrate the method in application to UQ of the elasto-plastic response of an imperfect octet-truss lattice which plays an important role in additive manufacturing. To this end, we study the effective material properties of the lattice unit cell under elasto-plastic deformations and investigate the sensitivity of the effective Young's modulus to the imperfections., Comment: 21 pages, 15 figures

We study the complexity of determining a winning committee under the Chamberlin--Courant voting rule when voters' preferences are single-crossing on a line, or, more generally, on a median graph (this class of graphs includes, e.g., trees and grids). For the line, Skowron et al. (2015) describe an $O(n^2mk)$ algorithm (where $n$, $m$, $k$ are the number of voters, the number of candidates and the committee size, respectively); we show that a simple tweak improves the time complexity to $O(nmk)$. We then improve this bound for $k=\Omega(\log n)$ by reducing our problem to the $k$-link path problem for DAGs with concave Monge weights, obtaining a $nm2^{O\left(\sqrt{\log k\log\log n}\right)}$ algorithm for the general case and a nearly linear algorithm for the Borda misrepresentation function. For trees, we point out an issue with the algorithm proposed by Clearwater, Puppe and Slinko (2015), and develop a $O(nmk)$ algorithm for this case as well. For grids, we formulate a conjecture about the structure of optimal solutions, and describe a polynomial-time algorithm that finds a winning committee if this conjecture is true; we also explain how to convert this algorithm into a bicriterial approximation algorithm whose correctness does not depend on the conjecture.

Materials that change their shape in response to external stimuli opens up new prospects for efficient and versatile design and shaping of three-dimensional objects. Here, we present a novel class of micro-structures exhibiting an extension-bending coupling (EBC) effect, that can be harnessed as an elementary building block for shape-shifting panels. They are built with a single material as a network of undulated ribbons. The deformations mechanisms of both single and connected undulated ribbons are analysed using the finite element method to explain the main features of the EBC mechanism. For a particular micro-structure of the proposed class, the complete elastic stiffness tensor is computed combining two-scale homogenization with Kirchhoff-Love plate theory. The range of achievable EBC ratio is then assessed with respect to the geometric parameters of the unit cell. Patterned specimens are manufactured using a commercial FFF Ultimaker 3-d printer and are mechanically tested at finite strain up to 20%. The displacement measured by point tracking match the predictions from the finite element simulations and indicate that the structure maintain its properties at finite strain. Moreover, a tensile test load with point-like boundary is proposed to highlight exceptional out of plane displacement. We envision these structures to be leveraged in combination with responsive materials for the actuation of soft robots, compliant systems and reconfigurable structures, as alternatives to external mechanical motors, control systems and power devices., Comment: 17 pages, 8 figures, 2 appendices

The multi-scale nature of architectured materials raises the need for advanced experimental methods suitable for the identification of their effective properties, especially when their size is finite and they undergo extreme deformations. The present work demonstrates that state-of-the art image processing methods combined with numerical and analytical models provide a comprehensive quantitative description of these solids and their global behaviour, including the influence of the boundary conditions, of the manufacturing process, and of geometric and constitutive non-linearities. To this end, an adapted multi-scale digital image correlation analysis is used to track both elongations and rotations of particular features of the unit cell at the local and global (homogenized) scale of the material. This permits to observe with unprecedented clarity the strains for various unit cells in the structure and to detect global deformation patterns and heterogeneities of the homogenized strain distribution. This method is here demonstrated on elastic sheets undergoing extreme longitudinal and shear deformations. These experimental results are compared to non-linear finite element simulations, which are also used to evaluate the effects of manufacturing imperfections on the response. A skeletal representation of the architectured solid is then extracted from the experiments and used to create a purely-kinematic truss-hinge model that can accurately capture its behaviour. The analysis proposed in this work can be extended to guide the design of two-dimensional architectured solids featuring other regular, quasi-regular or graded patterns, and subjected to other types of loads., Comment: 12 pages, 8 figures

Random microstructures of heterogeneous materials play a crucial role in the material macroscopic behavior and in predictions of its effective properties. A common approach to modeling random multiphase materials is to develop so-called surrogate models approximating statistical features of the material. However, the surrogate models used in fatigue analysis usually employ simple microstructure, consisting of ideal geometries such as ellipsoidal inclusions, which generally does not capture complex geometries. In this paper, we introduce a simple but flexible surrogate microstructure model for two-phase materials through a level-cut of a Gaussian random field with covariance of Mat\'ern class. Such parametrization of the covariance function allows for the representation of a few key design parameters while representing the geometry of inclusions in a more general setting for a large class of random heterogeneous two-phase media. In addition to the traditional morphology descriptors such as porosity, size and aspect ratio, it provides control of the regularity of the inclusions interface and sphericity. These parameters are estimated from a small number of real material images using Bayesian inversion. An efficient process of evaluating the samples, based on the Fast Fourier Transform, makes possible the use of Monte-Carlo methods to estimate statistical properties for the quantities of interest in a given material class. We demonstrate the overall framework of the use of the surrogate material model in application to the uncertainty quantification in fatigue analysis, its feasibility and efficiency, and its role in the microstructure design.

Predictive analytics systems are currently one of the most important areas of research and development within the Artificial Intelligence domain and particularly in Machine Learning. One of the "holy grails" of predictive analytics is the research and development of the "perfect" recommendation system. In our paper, we propose an advanced pipeline model for the multi-task objective of determining product complementarity, similarity and sales prediction using deep neural models applied to big-data sequential transaction systems. Our highly parallelized hybrid model pipeline consists of both unsupervised and supervised models, used for the objectives of generating semantic product embeddings and predicting sales, respectively. Our experimentation and benchmarking processes have been done using pharma industry retail real-life transactional Big-Data streams., Comment: 2018 17th RoEduNet Conference: Networking in Education and Research (RoEduNet)

This work proposes the complete design cycle for several auxetic materials where the cycle consists of three steps (i) the design of the micro-architecture, (ii) the manufacturing of the material and (iii) the testing of the material. We use topology optimization via a level-set method and asymptotic homogenization to obtain periodic micro-architectured materials with a prescribed effective elasticity tensor and Poisson's ratio. The space of admissible micro-architectural shapes that carries orthotropic material symmetry allows to attain shapes with an effective Poisson's ratio below -1. Moreover, the specimens were manufactured using a commercial stereolithography Ember printer and are mechanically tested. The observed displacement and strain fields during tensile testing obtained by digital image correlation match the predictions from the finite element simulations and demonstrate the efficiency of the design cycle., Comment: 17 pages, 12 figures

This work is concerned with the micro-architecture of multi-layer material that globally exhibits desired mechanical properties, for instance a negative apparent Poisson ratio. We use inverse homogenization, the level set method, and the shape derivative in the sense of Hadamard to identify material regions and track boundary changes within the context of the smoothed interface. The level set method and the shape derivative obtained in the smoothed interface context allows to capture, within the unit cell, the optimal micro-geometry. We test the algorithm by computing several multi-layer auxetic micro-structures. The multi-layer approach has the added benefit that contact during movement of adjacent "branches" of the micro-structure can be avoided in order to increase its capacity to withstand larger stresses., Comment: 21 pages