Arrow Research search

Author name cluster

Shay Kutten

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

20 papers
2 author rows

Possible papers

20

AAAI Conference 2013 Conference Paper

Composition Games for Distributed Systems: The EU Grant Games

  • Shay Kutten
  • Ron Lavi
  • Amitabh Trehan

We analyze ways by which people decompose into groups in distributed systems. We are interested in systems in which an agent can increase its utility by connecting to other agents, but must also pay a cost that increases with the size of the system. The right balance is achieved by the right size group of agents. We formulate and analyze three intuitive and realistic games and show how simple changes in the protocol can drastically improve the price of anarchy of these games. In particular, we identify two important properties for a low price of anarchy: agreement in joining the system, and the possibility of appealing a rejection from a system. We show that the latter property is especially important if there are some preexisting constraints regarding who may collaborate (or communicate) with whom.

PDF Details

FOCS Conference 1995 Conference Paper

Tight Fault Locality (Extended Abstract)

  • Shay Kutten
  • David Peleg

The notion of fault local mending was suggested as a paradigm for designing fault tolerant algorithms that scale to large networks. For such algorithms the complexity of recovering is proportional to the number of faults. We refine this notion by introducing the concept of tight fault locality to deal with problems whose complexity (in the absence of faults) is sublinear in the size of the network. For a function whose complexity on an n-node network is f(n), a tightly fault local algorithm recovers a legal global state in O(f(x)) time when the (unknown) number of faults is x. We illustrate this concept by presenting a general transformation for MIS algorithms to make them fault local. In particular, our transformation yields an O(logx) randomized mending algorithm and a 2/sup /spl radic//spl beta/logx/ deterministic mending algorithm for MIS. Similar results are obtained for other local functions such as a /spl Delta/+1 coloring. We also present the first tight fault local mending algorithm for global functions, using our results for MIS. This improves (by a logarithmic factor) the complexity of a previous fault-local mending algorithm for global functions.

Details

FOCS Conference 1993 Conference Paper

A Sub-Linear Time Distributed Algorithm for Minimum-Weight Spanning Trees (Extended Abstract)

  • Juan A. Garay 0001
  • Shay Kutten
  • David Peleg

This paper considers the question of identifying the parameters governing the behavior of fundamental global network problems. Many papers on distributed network algorithms consider the task of optimizing the running time successful when an O(n) bound is achieved on an n-vertex network. We propose that a more sensitive parameter is the network's diameter Diam. This is demonstrated in the paper by providing a distributed minimum-weight spanning tree algorithm whose time complexity is sub-linear in n, but linear in Diam (specifically, O(Diam+n/sup 0. 614/)). Our result is achieved through the application of graph decomposition and edge elimination techniques that may be of independent interest. >

Details

FOCS Conference 1990 Conference Paper

Communication-Optimal Maintenance of Replicated Information

  • Baruch Awerbuch
  • Israel Cidon
  • Shay Kutten

It is shown that keeping track of history allows significant improvements in the realistic model of communication complexity of dynamic network protocols. The communication complexity for solving an arbitrary graph problem is improved from Theta (E) to Theta (V), thus achieving the lower bound. Moreover, O(V) is also the amortized complexity of solving an arbitrary function (not only graph functions) defined on the local inputs of the nodes. As a corollary, it is found that amortized communication complexity, i. e. incremental cost of adapting to a single topology change, can be smaller than the communication complexity of solving the problem from scratch. The first stage in the solution is a communication-optimal maintenance of a spanning tree in a dynamic network. The second stage is the optimal maintenance of replicas of databases. An important example of this task is the problem of updating the description of the network's topology at every node. For this problem the message complexity is improved from O(EV) to Theta (V). The improvement for a general database is even larger if the size of the database is larger than E. >

Details