Theory of Computing Systems

Coordination mechanisms aim to mitigate the impact of selfishness when scheduling jobs to different machines. Such a mechanism defines a scheduling policy within each machine and naturally induces a game among the selfish job owners. The desirable properties of a coordination mechanism includes simplicity in its definition and efficiency of the outcomes of the induced game. We present a broad class of coordination mechanisms for unrelated machine scheduling that are simple to define and we identify one of its members (mechanism DCOORD) that is superior to all known mechanisms. In particular, DCOORD induces potential games with logarithmic price of anarchy and only constant price of stability. Both bounds are almost optimal.

Let η≥0 be an integer and G be a graph. A set X⊆V(G) is called a η-treewidth modulator in G if G∖X has treewidth at most η. Note that a 0-treewidth modulator is a vertex cover, while a 1-treewidth modulator is a feedback vertex set of G. In the η/ρ-Treewidth Modulator problem we are given an undirected graph G, a ρ-treewidth modulator X⊆V(G) in G, and an integer ℓ and the objective is to determine whether there exists an η-treewidth modulator Z⊆V(G) in G of size at most ℓ. In this paper we study the kernelization complexity of η/ρ-Treewidth Modulator parameterized by the size of X. We show that for every fixed η and ρ that either satisfy 1≤η<ρ, or η=0 and 2≤ρ, the η/ρ-Treewidth Modulator problem does not admit a polynomial kernel unless NP⊆coNP/poly. This resolves an open problem raised by Bodlaender and Jansen (STACS, pp. 177–188, 2011). Finally, we complement our kernelization lower bounds by showing that ρ/0-Treewidth Modulator admits a polynomial kernel for any fixed ρ.

In the Arc Disjoint Cycle Packing problem, we are given a simple directed graph (digraph) G, a positive integer k, and the task is to decide whether there exist k arc disjoint cycles. The problem is known to be W[1]-hard on general digraphs parameterized by the standard parameter k. In this paper we show that the problem admits a polynomial kernel on α-bounded digraphs. That is, we give a polynomial-time algorithm, that given an instance (D,k) of Arc Disjoint Cycle Packing, outputs an equivalent instance $(D^{\prime },k^{\prime })$ of Arc Disjoint Cycle Packing, such that $k^{\prime }\leq k$ and the size of $D^{\prime }$ is upper-bounded by a polynomial function of k. For any integer α ≥ 1, the class of α-bounded digraphs, denoted by ${\mathcal D}_{\alpha }$ , contains a digraph D such that the maximum size of an independent set in D is at most α. That is, in D, any set of α + 1 vertices has an arc with both end-points in the set. For α = 1, this corresponds to the well-studied class of tournaments. Our results generalize the recent result by Bessy et al. [MFCS, 2019] about Arc Disjoint Cycle Packing on tournaments.

This paper presents a schematic algorithm for distributed systems. This schematic algorithm uses a “black-box” procedure for communication, the output of which must meet two requirements: a global-order requirement and a deadlock-free requirement. This algorithm is valid in any distributed system model that can provide such a communication procedure that complies with these requirements. Two such models exist in an asynchronous fail-stop environment: one in the shared-memory model and one in the message-passing model. The implementation of the block-box procedure in these models enables us to translate existing algorithms between the two models whenever these algorithms are based on the schematic algorithm. We demonstrate this idea in two ways. First, we present a randomized algorithm for the consensus problem in the message-passing model based on the algorithm of Aspnes and Herlihy [AH] in the shared-memory model. This solution is the fastest known randomized algorithm that solves the consensus problem against a strong fail-stop adversary with one-half resiliency. Second, we solve the processor renaming problem in the shared-memory model based on the solution of Attiyaet al. [ABD+] in the message-passing model. The existence of the solution to the renaming problem should be contrasted with the impossibility result for the consensus problem in the shared-memory model [CIL], [DDS], [LA].

TheDistributed Consensus problem involvesn processors each of which holds an initial binary value. At mostt processors may be faulty and ignore any protocol (even behaving maliciously), yet it is required that the nonfaulty processors eventually agree on a value that was initially held by one of them. We measure the quality of a consensus protocol using the following parameters; total number of processorsn, number of rounds of message exchanger, and maximal message sizem. The known lower bounds are respectively 3t + 1,t + 1, and 1. While no known protocol is optimal in all these three aspects simultaneously,Cloture Votes—the protocol presented in this paper—takes further steps in this direction, by making consensus possible withn = 4t + 1,r = t + 1, and polynomial message size. Cloture is a parliamentary procedure (also known as “parliamentary guillotine”) which makes it possible to curtail unnecessary long debates. In our protocol the unanimous will of the correct processors (akin to parliamentarian supermajority) may curtail the debate. This is facilitated by having the processors open in each round a new process (debate), which either ends quickly, with the conclusion “continue” or “terminate with the default value,” or lasts through many rounds. Importantly, in the latter case the messages being sent are short.

Let S be a set of n taxa. Given a parameter k and a set of quartet topologies Q over S such that there is exactly one topology for every subset of four taxa, the parameterized Minimum Quartet Inconsistency (MQI) problem is to decide whether we can find an evolutionary tree inducing a set of quartet topologies that differs from the given set in at most k quartet topologies. The best fixed-parameter algorithm devised so far for the parameterized MQI problem runs in time O(4 k n+n 4). In this paper, first we present an O(3.0446 k n+n 4) fixed-parameter algorithm and an O(2.0162 k n 3+n 5) fixed-parameter algorithm for the parameterized MQI problem. Finally, we give an O *((1+ε) k ) fixed-parameter algorithm, where ε>0 is an arbitrarily small constant.

Counting functions can be defined syntactically or semantically depending on whether they count the number of witnesses in a non-deterministic or in a deterministic computation on the input. In the Turing-machine-based model these two ways of defining counting were proven to be equivalent for many important complexity classes. In the circuit-based model it was done for #P, but for low-level complexity classes such as #AC 0 and #NC 1 only the syntactical definitions were considered. We give appropriate semantical definitions for these two classes and prove them to be equivalent to the syntactical ones. We also consider semantically defined probabilistic complexity classes corresponding to AC 0 and NC ^{1} and prove that in the case of unbounded error, they are identical to their syntactical counterparts.