We address the problem of designing distributed algorithms for large scale networks that are robust to Byzantine faults. We consider a message passing, full information model: the adversary is malicious, controls a co...
详细信息
ISBN:
(纸本)9783642176784
We address the problem of designing distributed algorithms for large scale networks that are robust to Byzantine faults. We consider a message passing, full information model: the adversary is malicious, controls a constant fraction of processors, and can view all messages in a round before sending out its own messages for that round. Furthermore, each had processor may send an unlimited number of messages. the only constraint on the adversary is that it must choose its corrupt processors at the start, without knowledge of the processors' private random bits. A good quorum is a set of 0(log n) processors, which contains a majority of good processors. In this paper, we give a synchronous algorithm which uses polylogarithmic time and (O) over tilde(root n,) bits of communication per processor to bring all processors to agreement on a collection of n good quorums, solving Byzantine agreement as well. the collection is balanced in that no processor is in more than 0(log n) quorums. this yields the first solution to Byzantine agreement which is both scalable and load-balanced in the full information model. the technique which involves going from situation where slightly more than 1/2 fraction of processors are good and and agree on a short string with a constant fraction of random bits to a situation where all good processors agree on n good quorums can be done in a fully asynchronous model as well, providing an approach for extending the Byzantine agreement result to this model.
the proceedings contain 192 papers. the topics discussed include: techniques of minimizing parasitics for the enhancement of modulation bandwidth of an oxide-confined VCSEL;analysis of resistances and transconductance...
ISBN:
(纸本)9781424462797
the proceedings contain 192 papers. the topics discussed include: techniques of minimizing parasitics for the enhancement of modulation bandwidth of an oxide-confined VCSEL;analysis of resistances and transconductance of SiC MESFET considering fabrication parameters and mobility as a function of temperature;analysis of base transit time for a bipolar junction transistor considering base current;a single polarization fiber with ultra flattened dispersion and high birefringence;impact of chipshape on the performance of DSOCDMA in dispersive fiber medium;incoherent crosstalk analysis in fiber Bragg grating based optical add/drop multiplexer in optical networks;outage probability of OFDMA based regenerative multihop transmission;design of a duobinary encoder and decoder circuits for communication systems;performance analysis of network coded bidirectional relaying in OFDM networks;and fuzzy logic based sliding mode controlled DC-DC boost converter.
Internet supercomputing provides means for harnessing the power of a vast number of interconnected computers. Withthis come the challenges of marshaling distributed resources and dealing with failures. Traditional ce...
详细信息
ISBN:
(纸本)9783642258725
Internet supercomputing provides means for harnessing the power of a vast number of interconnected computers. Withthis come the challenges of marshaling distributed resources and dealing with failures. Traditional centralized approaches employ a master processor and many worker processors that execute a collection of tasks on behalf of the master. Despite the simplicity and advantages of centralized schemes, the master processor is a performance bottleneck and a single point of failure. Additionally, a phenomenon of increasing concern is that workers may return incorrect results, e.g., due to unintended failures, over-clocked processors, or due to workers claiming to have performed work to obtain a high rank in the system. this paper develops an original approach that eliminates the master and instead uses a decentralized algorithm, where workers cooperate in performing tasks. the failure model assumes that the average probability of a worker returning a wrong result is inferior to 1/2. We present a randomized synchronous algorithm for n processors and t tasks (t >= n) achieving time complexity circle minus(t/n log n) and work circle minus(t log n). It is shown that upon termination the workers know the results of all tasks with high probability, and that these results are correct with high probability. the message complexity of the algorithm is circle minus(n log n), and the bit complexity is O(tn log(3) n). Simulations illustrate the behavior of the algorithm under realistic assumptions.
Motivated by a security problem in geographic information systems, we study the following graph theoretical problem: given a graph G, two special nodes s and t in G, and a number k, find k paths from s to t in G so as...
详细信息
the proceedings contain 11 papers. the topics discussed include: intrinsic definition in software architecture evolution;a component-based approach to adaptive user-centric pervasive applications;validating model-driv...
ISBN:
(纸本)3642138209
the proceedings contain 11 papers. the topics discussed include: intrinsic definition in software architecture evolution;a component-based approach to adaptive user-centric pervasive applications;validating model-driven performance predictions on random software systems;statistical inference of software performance models for parametric performance completions;parameterized reliability prediction for component-based software architectures;architecture-driven reliability and energy optimization for complex embedded systems;a hybrid approach for multi-attribute QoS optimization in component based software systems;using QoS-contracts to drive architecture-centric self-adaptation;is BPMN really first choice in joint architecture development? an empirical study on the usability of BPMN and UML activity diagrams for business users;and barriers to modularity - an empirical study to assess the potential for modularization of Java programs.
the proceedings contain 6 papers. the topics discussed include: design and implementation of user-managed access framework for web 2.0 applications;carbon: towards an server building framework for SOA platform;EVEREST...
ISBN:
(纸本)9781450304528
the proceedings contain 6 papers. the topics discussed include: design and implementation of user-managed access framework for web 2.0 applications;carbon: towards an server building framework for SOA platform;EVEREST+: run-time SLA violations prediction;a middleware for adaptive service orientation in pervasive computing environments;a programming model for self-adaptive open enterprise systems;and middleware enabled data sharing on cloud storage services.
the proceedings contain 37 papers. the topics discussed include: low correlation zone sequences;an algorithm for constructing a fastest Galois NLFSR generating a given sequence;acquisition times of contiguous and dist...
ISBN:
(纸本)3642158730
the proceedings contain 37 papers. the topics discussed include: low correlation zone sequences;an algorithm for constructing a fastest Galois NLFSR generating a given sequence;acquisition times of contiguous and distributed marker sequences: a cross-bifix analysis;lower bounds on the average partial hamming correlations of frequency hopping sequences with low hit zone;new families of frequency-hopping sequences of length MN derived from the k-fold cyclotomy;user-irrepressible sequences;new optimal variable-weight optical orthogonal codes;recent results on recursive nonlinear pseudorandom number generators;a general approach to construction and determination of the linear complexity of sequences based on cosets;on the autocorrelation and the linear complexity of q-ary prime n-square sequences;and an improved approximation algorithm for computingthe k-error linear complexity of sequences using the discrete Fourier transform.
the proceedings contain 17 papers. the topics discussed include: analyzing explicit information flow;toward securely programming the Internet;strengthening XSRF defenses for legacy web applications using whitebox anal...
ISBN:
(纸本)3642177131
the proceedings contain 17 papers. the topics discussed include: analyzing explicit information flow;toward securely programming the Internet;strengthening XSRF defenses for legacy web applications using whitebox analysis and transformation;coverage criteria for automatic security testing of web applications;a practical generic privacy language;efficient detection of the return-oriented programming malicious code;mining RBAC roles under cardinality constraint;specification of history based constraints for access control in conceptual level;abstracting audit data for lightweight intrusion detection;a persistent public watermarking of relational databases;security rules versus security properties;and protecting and restraining the third party in RFID-enabled 3PL supply chains.
the proceedings contain 67 papers. the topics discussed include: solving the scalability dilemma with clouds, crowds, and algorithms;the trend of cloud computing - from industry's perspective;collaboration of reco...
ISBN:
(纸本)3642130666
the proceedings contain 67 papers. the topics discussed include: solving the scalability dilemma with clouds, crowds, and algorithms;the trend of cloud computing - from industry's perspective;collaboration of reconfigurable processors in grid computing for multimedia kernels;a new heuristic for broadcasting in cluster of clusters;SLA-driven automatic bottleneck detection and resolution for read intensive multi-tier applications hosted on a cloud;a matrix scheduling strategy with multi-QoS constraints in computational grid;the mini-grid framework: application programming support for ad-hoc, peer-to-peer volunteer grids;a genetic context interpreter for context-aware systems in pervasive computing environments;supporting filename partial matches in structured peer-to-peer overlay;multi-dimensional resilient statistical en-route filtering in wireless sensor networks;and a 2D barcode validation system for mobile commerce.
the proceedings contain 50 papers. the topics discussed include: diagrams in the mind: visual or spatial?;understanding diagrams, and more: the computer's view;the efficacy of Euler and Venn diagrams in deductive ...
ISBN:
(纸本)364214599X
the proceedings contain 50 papers. the topics discussed include: diagrams in the mind: visual or spatial?;understanding diagrams, and more: the computer's view;the efficacy of Euler and Venn diagrams in deductive reasoning: empirical findings;drawing Euler diagrams with circles;colored Euler diagrams: a tool for visualizing dynamic systems and structured information;drawing area-proportional Venn-3 diagrams with convex polygons;fragments of spider diagrams of order and their relative expressiveness;two types of diagrammatic inference systems: natural deduction style and resolution style;alternative strategies for spatial reasoning with diagrams;relating two image-based diagrammatic reasoning architectures;a spatial search framework for executing perceptions and actions in diagrammatic reasoning;diagram editing on interactive displays using multi-touch and pen gestures;and getting a clue: gist extraction from scenes and causal systems.
暂无评论