Questions about the challenges of solving problems with multiple cooperating but separate agents.

learn more… | top users | synonyms (1)

0
votes
1answer
26 views

Distributed parallel computing algorithms for content dependent data

I have implemented group of pictures parallelism for hevc encoding on distributed platform. In this we have to send different video chunks to different machines, these machines encode data in parallel ...
3
votes
1answer
34 views

Best data structure for storing an ordered list, where each item is located on a separate server?

I need a structure that resembles an RSS feed of items, but each item is on a different network machine. Users cannot insert in the middle of the feed but only at its head. Deletions are possible. ...
0
votes
0answers
22 views

Who said: you need to send few messages over the network and they need to be as small as possible so that a distributed application scales up?

I wonder if there is a well known law or scientific article to cite for this. I am writing a manuscript and I am looking for the right reference. Is there something like the Amdahl's law saying that? ...
3
votes
6answers
236 views

Parallel vs Distributed Algorithms

Let me clear first that I am not asking about parallel (data/task) or distributed computing architecture. A lot had been discussed here. I am just asking a plain theoretical question. What is core ...
1
vote
1answer
31 views

Synchronisation and ordering in distributed systems

I have been wondering, what are some ways to handle synchronisation and/or sequencing issues in distributed systems. For example, assume multiple homogeneous nodes listening on a stream of messages ...
2
votes
0answers
32 views

What are the theoretical and practical contributions of Multiagent Systems to science?

Speaking about multiagent systems (MAS) is about as fuzzy as talking about artificial intelligence systems (AI). They are in essence the distributed counterpart of AI. While there are no so-called ...
2
votes
1answer
25 views

Call-by-reference semantics for RPC

Does call-by-reference semantics for remote procedure call (RPC) have a real use case? Why does call-by-reference RPC exist? Is it useful for anything? Is there a scenario where call-by-value can't ...
2
votes
1answer
36 views

Term for shifting work to idle machines

I am looking for a term here. A while ago, i was told about a network in which all the computers are connected in parallel, and when a computer is idle, the central server sends heavy cpu usage tasks ...
0
votes
0answers
28 views

What differs in the message passing model?

Doing a very basic course in distributed computing. I just went through Dijkstra's self-stabilizing mutual exclusion in the shared memory model. We where encouraged to think about what would change in ...
3
votes
1answer
73 views

Is there a difference between total-ordering consistency and linearizability?

By total-ordering I mean the following definition[0]: Total Event Ordering: Controller replicas should process events in the same order and subsequently all controller application instances ...
1
vote
0answers
34 views

Processes running in Distributed Systems (Advanced Operating System)

I had a test today, there was a question that was a bit confusing. Anyway I am asking the question, from memory, and explaining what I answered. It would be great if someone could explain if I did ...
3
votes
1answer
52 views

Algorithm for executing a command against a million hosts

Consider the following problem: you are given a set of one million machines (hosts), and you would like to have the ability to execute at will an arbitrary command against the whole set; for the ...
2
votes
0answers
39 views

Floating output/making a non-self stabilizing algorithm self stabilizing

So we're using this book by Shlomi Dolev on self-stabilization in class. Not being from a theretical CS background, I think the book is rather terse. Most of it is fine but there's this section on ...
1
vote
1answer
39 views

Complexity of calculating average across distributed network?

What is the communication complexity of the best known algorithm for computing the average of a set of N*D numbers distributed across N nodes with D values per node? Assume you have full control over ...
4
votes
0answers
71 views

Optimal schedule for broadcasting a file in a complete graph with overheads

I am trying to solve the following problem and despite having performed quite extensive literature review, I do not seem to find any similar problem or technique that would be useful here. PROBLEM ...
1
vote
0answers
43 views

Working of the GHS algorithm

Can someone explain the working of the GHS algorithm using the graph given below. GHS is a distributed algorithm for finding the Minimum Spanning tree of a graph. The description of which can be found ...
6
votes
0answers
61 views

What is 2g-precedence?

I am currently reading a couple of papers about event processing. In the context of ordering events, "2g-precedence" is frequently mentioned. I don't know what it is, and I cannot find much ...
1
vote
0answers
27 views

parallel computation and GPGPU question [closed]

is there a mean of creating a cluster of machines, that can be seen as an entire system, using perhaps mac OS X or mac os x server, and use parallelism and GPGPU optimisation to compute all the tasks ...
1
vote
0answers
49 views

What advantage does Tangaroa offer over PBFT?

Tangaroa is a relatively new project adding Byzantine fault-tolerance to the Raft consensus protocol using techniques that were already used in the PBFT algorithm. What are the advantages, when should ...
1
vote
1answer
60 views

What does atomicity mean in distributed systems?

In a distributed system, how atomic operations are done when network connections inherently have the Two Generals problem? Does atomicity have a different meaning in this context?
3
votes
1answer
40 views

Understanding the fundamentals of building an in-Memory Distributed Graph

I am working on a project where I have to build an in-memory distributed graph capturing the relation between similar files(based on some similarity metric) stored in shared file system over multiple ...
5
votes
1answer
124 views

Paxos consistency

I'm looking at the paxos family of protocols for solving consensus in a network of unreliable processors. I'm working through scenarios where processors fail, and I know I'm wrong, but I don't know ...
0
votes
1answer
26 views

How can I take advantage of the capabilities of a cluster [closed]

I'm developing a model in C, and I need to run a couple of simulations (lengthy, and heavy ones). I seem to have a cluster at my disposal, but I'm not very familiar with the concept. I understand that ...
2
votes
0answers
23 views

What are the prerequisites for working on multi agent systems? [closed]

I am starting to study about Multi Agent Systems and I wanted to know which sciences are most used in these systems, I am aware of game theory and Markov statistical relations (Markov Decision Process ...
2
votes
0answers
50 views

Client-Server Architecture /State Model and Process Mode [closed]

how i can define what are Client-Server Architecture for a website that suggestion courses for students after students insert the history of courses. The language will be PHP,mysql and HTML. In this ...
4
votes
1answer
62 views

solving large nonlinear systems in parallel

I am solving a large (~1e5 equations & unknowns) set of nonlinear equations using Newton-Raphson iterations. Currently I am using the GPU accelerated Krylov methods implemented in ViennaCL to ...
1
vote
1answer
31 views

In a distributed system is it possible for both parties to simultaneously agree a message exchange was made?

Given that the two generals problema is unsolvable, which means that both parties involved cannot agree that both know something, i ask something simpler. Is it possible for both parties to agree ...
4
votes
1answer
45 views

Symmetric protocols for consensus

All the consensus algorithms that I've seen always depend on having a leader elected with all queries directed at the leader (assuming that we're not OK with getting back stale data). Are there any ...
5
votes
1answer
280 views

Consensus problem of distributed systems

I just started reading about distributed systems for the first time ever. There is a fairly slick proof of the impossibility of consensus in an asynchronous model using some combinatorial topology. On ...
3
votes
1answer
79 views

What happens when two processes hold an election using bully algorithm simultaneously

A coordinator is used to sychronise the usage of resources in a distributed system. The Bully Algorithm is a method to elect a new coordinator in a distributed system when the current coordinator ...
3
votes
1answer
89 views

Counting the nodes in a network in a distributed way

There is a network with $n$ nodes. Each node can contact only the neighbouring nodes (the degree of each node is bounded, if that matters). One of the nodes, say $s$, wants to know $n$. How can it do ...
2
votes
1answer
52 views

Paxos: Instances, Rounds, Phases

In the paper, Paxos Made Simple, Lamport describes a round of Paxos as two phases: a $prepare$ phase, and an $accept$ phase. An instance of Paxos can have multiple rounds. Can a round have multiple ...
3
votes
1answer
35 views

Paxos: Responding to Reordered Prepare Requests

In the paper, Paxos Made Simple, a proposer asks an acceptor to respond to a prepare request with: A promise never to again accept a proposal numbered less than n, and the proposal with the ...
3
votes
1answer
75 views

What is the size of a queue associated with a resource when the resource becomes a bottleneck?

In Software Performance and Scalability: A Quantitative Approach - Henry H. Liu, the author is presenting a scenario where the hardware becomes a bottleneck. In one ot the tests, he is checking the ...
6
votes
1answer
111 views

Does location transparency imply access transparency?

In distributed systems theory, I have found the definition that a distributed system requires, among others, location and access transparency. I was wondering if location transparency does not ...
3
votes
2answers
148 views

Linearizability and Serializability in context of Software Transactional Memory

I've been trying to grasp serializability and linearizability in the context of software transactional memory. However, I think both notions can be applied to transactional memory in general. At this ...
3
votes
0answers
97 views

How to generate globally unique timestamps for transactions in distributed database systems?

According the paper [1] (Section 4), timestamp ordering (T/O) is a technique whereby a serialization order is selected a priori and transaction execution is forced to obey this order. In the ...
7
votes
2answers
82 views

Computer science fields that deal with peer-to-peer systems

I'm an undergraduate and am looking forward to becoming an academic; do the whole PhD stuff and start doing research. I'm interested in a variety of computer science related things but lately P2P ...
3
votes
1answer
155 views

Paxos: Accepting Proposals With Different Values and Consensus in Paxos

I have a number of questions about Paxos which I can't answer in full confidence from reading the paper (Paxos Made Simple). My questions are loosely based around the following quote: In Paxos, a ...
2
votes
1answer
44 views

How to make a “Secure by Design” client-server communication?

Is there a way to have a secure by design client-server communication in a sense that the server can check if the client is not a modified version? What I'd like to do is give the user access to both ...
3
votes
1answer
60 views

Residence time in multi server system

I'm reading Neil Gunther's Practical Performance Analyst, and he provides that when there's one queue and one server, the residence time (total time spent per request) is: ...
6
votes
3answers
242 views

Happened-before and Causal order

I'm reading Lamport's "Time, Clocks, and the Ordering of Events in a Distributed System" and there's a detail that's bugging me. Lamport defines the "happened before" partial order, which I ...
7
votes
1answer
100 views

Finding a maximal independent set in parallel

On a graph $G(V,E)$, we do the following process: Initially, all nodes in $V$ are uncolored. While there are uncolored nodes in $V$, each uncolored node does the following: Selects a random real ...
2
votes
1answer
317 views

Applications of Lamport's Distributed Mutual Exclusion algorithm

I'm trying to understand the relevance of the Lamport distributed mutual exclusion algorithm (or any of its variants), where a group of processes cooperate to gain exclusive access to a resource ...
3
votes
1answer
80 views

Confusion about example in Raft consensus paper

In part (c) of Figure 8 in this paper http://ramcloud.stanford.edu/raft.pdf, I am confused how S1 knows that the current term is 4 when it restarts and is elected leader. Here is the sequence as I ...
2
votes
1answer
92 views

How to interpret the execution of distributed computation from time-space diagram?

I'm following a course on Distributed Systems http://www.ict.kth.se/courses/ID2203/index.html and currently learning about asynchronous models. I can't seem to reconcile a given time-space diagram ...
1
vote
0answers
62 views

determining timeouts / retry attempts in distributed systems

Is there a methodical procedure for determining the optimal timeout / retry strategy for dealing with a remote server that handles processes responses for requests, given some probability distribution ...
2
votes
1answer
84 views

Difference between BSP model and synchronous round model in distributed computing

I've recently learned about distributed computing and the synchronous model where, assuming a complete network and no crashes, in each round the following happens: every node can send a message to ...
1
vote
1answer
425 views

Clock skew vs clock offset in the context of clock synchronization network protocols

In the context of clock synchronization among nodes of a network, what is clock offset and what is clock skew? Are these terms synonymous or is there a difference between them?
1
vote
0answers
104 views

Examples of real world graphs that are too big for a single commodity-type machine

I've been reading on distributed systems for processing on large graphs. The most prominent examples include Pregel (developed by Google) and Apache Giraph. Most of these systems argue their existence ...