Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userSpace and Time Bounded Multiversion Garbage Collection
83
0
0.0
(
0
)
Added by
Yuanhao Wei
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We present a general technique for garbage collecting o
rate research
Read More
In this paper we are interested in bounding the number of instructions taken to process transactions. The main result is a multiversion transactional system that supports constant delay (extra instructions beyond running in isolation) for all read-only transactions, delay equal to the number of processes for writing transactions that are not concurrent with other writers, and lock-freedom for concurrent writers. The system supports precise garbage collection in th
Modern high-end machines feature multiple processor packages, each of which contains multiple independent cores and integrated memory controllers connected directly to dedicated physical RAM. These packages are connected via a shared bus, creating a system with a heterogeneous memory hierarchy. Since this shared bus has less bandwidth than the sum of the links to memory, aggregate memory bandwidth is higher when parallel threads all access memory local to their processor package than when they access memory attached to a remote package. This bandwidth limitation has traditionally limited the scalability of modern functional language implementations, which seldom scale well past 8 cores, even on small benchmarks. This work presents a garbage collector integrated with our strict, parallel functional language implementation, Manticore, and shows that it scales effectively on both a 48-core AMD Opteron machine and a 32-core Intel Xeon machine.
We show that asynchronous $t$ faults Byzantine system is equivalent to asynchronous $t$-resilient system, where unbeknownst to all, the private inputs of at most $t$ processors were altered and installed by a malicious oracle. The immediate ramification is that dealing with asynchronous Byzantine systems does not call for new topological methods, as was recently employed by various researchers: Asynchronous Byzantine is a standard asynchronous system with an input caveat. It also shows that two recent independent investigations of vector $epsilon$-agreement in the Byzantine model, and then in the fail-stop model, one was superfluous - in these problems the change of $t$ inputs allowed in the Byzantine has no effect compared to the fail-stop case. This result was motivated by the aim of casting any asynchronous system as a synchronous system where all processors are correct and it is the communication substrate in the form of message-adversary that misbehaves. Thus, in addition, we get such a characterization for the asynchronous Byzantine system.
A graph separator is a subset of vertices of a graph whose removal divides the graph into small components. Computing small graph separators for various classes of graphs is an important computational task. In this paper, we present a polynomial time algorithm that uses $O(g^{1/2}n^{1/2}log n)$-space to find an $O(g^{1/2}n^{1/2})$-sized separator of a graph having $n$ vertices and embedded on a surface of genus $g$.
The Reliable Broadcast concept allows an honest party to send a message to all other parties and to make sure that all honest parties receive this message. In addition, it allows an honest party that received a message to know that all other honest parties would also receive the same message. This technique is important to ensure distributed consistency when facing failures. In the current paper, we study the ability to use RR to consistently transmit a sequence of input values in an asynchronous environment with a designated sender. The task can be easily achieved using counters, but cannot be achieved with a bounded memory facing failures. We weaken the problem and ask whether the receivers can at least share a common suffix. We prove that in a standard (lossless) asynchronous system no bounded memory protocol can guarantee a common suffix at all receivers for every input sequence if a single party might crash. We further study the problem facing transient faults and prove that when limiting the problem to transmitting a stream of a single value being sent repeatedly we show a bounded memory self-stabilizing protocol that can ensure a common suffix even in the presence of transient faults and an arbitrary number of crash faults. We further prove that this last problem is not solvable in the presence of a single Byzantine fault. Thus, this problem {bf separates} Byzantine behavior from crash faults in an asynchronous environment.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
